Основные определения

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

Если граф укладывается на плоскости, то он называется планарным.

Граф, уложенный на плоскости называется плоским графом.

Плоский граф на плоскости определяет ее области. При этом неограниченная область называется внешней гранью графа, а остальные области – внутренние грани. Внешнюю грань обозначим S₀, а внутренние S₁, S₂, …, S_k . На рисунке представлен планарный граф и соответствующий ему плоский граф с гранями:

Для плоских графов справедлива формула Эйлера: n + k = m + 2, где n – число вершин графа, k – число граней, m – число ребер.

Для представленного графа: число вершин равно 5, число ребер – 8, число граней – 5. проверим формулу Эйлера:

5 + 5 = 8 – 2 – равенство верно.

Вопрос о распознавании планарности графа являлся в свое время серьезной математической проблемой, которую на сегодняшний день удалось решить.

Для формулировки этого важного результата введем два понятия.

Элементарное стягивание ребра. Элементарным стягиванием ребра {v, w} называется отождествление вершин v и w:

Два графа G' и G'' называютя гомеоморфными, если они могут быть получены из некоторого графа с помощью последовательности элементарных стягиваний его ребер.

Выше приведенные графы гомеоморфны. Никакие другие вершины стягивать нельзя, так как это повлечет за собой отождествление ребер, что недопустимо.

Сформулируем необходимое и достаточное условие планарности графа.

Для того чтобы граф G(V, X) был планарным, необходимо и достаточно, чтобы он не содержал подграфа , гомеоморфного либо полному графу К₅, либо графу К_3,3 .

Граф К₅