Теория графов: планарность

Предмет: Теория графов
Раздел: Планарность

Определение планарности:

Граф называется планарным, если его можно изобразить на плоскости таким образом, что его рёбра пересекаются только в вершинах, которым они инцидентны. Другими словами, граф является планарным, если существует его плоское представление (или плоская укладка), где пересечения рёбер отсутствуют.

Для проверки планарности графа часто используют теоремы и критерии, например:

1. Теорема Куратовского: Граф является планарным тогда и только тогда, когда он не содержит подграфа, гомеоморфного графам [K5] (полный граф на 5 вершинах) или [K{3,3}] (полный двудольный граф с долями по 3 вершины).
   Здесь:

   • [K_5] — граф, где каждая вершина соединена с каждой другой вершиной.
   • [K_{3,3}] — двудольный граф, где каждая вершина одной доли соединена со всеми вершинами другой доли.

2. Формула Эйлера для планарных графов: Для связного планарного графа с [n] вершинами, [m] рёбрами и [f] гранями выполняется соотношение:
   n - m + f = 2.

Это соотношение помогает проверить планарность графа, если он уже изображён в плоской укладке.

Пример:
Граф с 4 вершинами ([n = 4]) и 6 рёбрами ([m = 6]) может быть планарным, если его можно нарисовать без пересечения рёбер. Например, полный граф [K_4] является планарным, так как его можно изобразить на плоскости без пересечений рёбер.