Планарный граф¶

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

¶Основные понятия

¶Определение и укладка

Формально, граф \( G = (V, E) \) называется планарным, если существует его вложение в плоскость, при котором вершины отображаются в различные точки плоскости, а рёбра — в непрерывные кривые, соединяющие соответствующие вершины, и эти кривые пересекаются только в общих вершинах. Такое вложение называется планарным представлением или плоским графом. Если граф уже изображён на плоскости без пересечений, его называют плоским графом.

¶Грани

При изображении плоского графа плоскость делится на несколько связных областей, называемых гранями. Одна из них — внешняя (неограниченная) грань, остальные — внутренние. Каждая грань ограничена циклом рёбер (возможно, повторяющихся). Для связного плоского графа количество граней \( f \), вершин \( v \) и рёбер \( e \) связаны формулой Эйлера: \[ v - e + f = 2. \] Эта формула является фундаментальной для планарных графов. Например, для треугольника (\( v=3, e=3 \)) получаем \( f = 2 \) (внутренняя и внешняя грани).

¶Степень грани

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

¶Критерии планарности

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

¶Теорема Куратовского (1930)

Наиболее известный критерий: граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного полному графу \( K_5 \) (пять вершин, все попарно соединены) или полному двудольному графу \( K_{3,3} \) (две доли по три вершины, все вершины одной доли соединены со всеми вершинами другой). Графы \( K_5 \) и \( K_{3,3} \) являются минимальными не планарными графами. Гомеоморфизм означает, что один граф может быть получен из другого добавлением или удалением вершин степени 2 (подразбиением рёбер).

¶Теорема Вагнера (1937)

Граф планарен тогда и только тогда, когда он не содержит минора, изоморфного \( K_5 \) или \( K_{3,3} \). Минор графа — это граф, получаемый из исходного удалением вершин, удалением рёбер и стягиванием рёбер (отождествлением смежных вершин). Этот критерий эквивалентен критерию Куратовского, но формулируется в терминах миноров.

¶Критерий Маклейна (1937)

Связный граф планарен тогда и только тогда, когда его пространство циклов имеет базис, в котором каждое ребро содержится не более чем в двух циклах. Этот критерий основан на алгебраической топологии.

¶Свойства планарных графов

¶Ограничение на число рёбер

Для любого связного планарного графа с \( v \ge 3 \) вершинами и \( e \) рёбрами выполняется неравенство: \[ e \le 3v - 6. \] Это следует из формулы Эйлера и того, что каждая грань имеет степень не менее 3 (если граф не содержит кратных рёбер и петель). Для полного графа \( K_5 \) (\( v=5 \)) неравенство даёт \( e \le 9 \), но в \( K_5 \) \( e=10 \), что подтверждает его не планарность. Если граф двудольный и не содержит треугольников, то \( e \le 2v - 4 \), что объясняет не планарность \( K_{3,3} \) (\( v=6, e=9 \), а \( 2v-4=8 \)).

¶Минимальная степень вершины

В любом планарном графе существует вершина степени не более 5. Это следует из неравенства \( e \le 3v - 6 \) и того, что сумма степеней вершин равна \( 2e \). Если бы все вершины имели степень не менее 6, то \( 2e \ge 6v \), откуда \( e \ge 3v \), что противоречит неравенству.

¶Раскраска

Знаменитая теорема о четырёх красках (доказана в 1976 году Аппелем и Хакеном) утверждает, что любой планарный граф может быть правильно раскрашен в 4 цвета (смежные вершины имеют разные цвета). Это эквивалентно утверждению, что любую карту на плоскости можно раскрасить в 4 цвета так, чтобы соседние страны (грани) имели разные цвета. Для непланарных графов хроматическое число может быть произвольно большим.

¶Разреженность

Планарные графы являются разреженными: средняя степень вершин меньше 6. Они также являются графами с ограниченной древесной шириной (древесная ширина планарного графа не превосходит \( O(\sqrt{v}) \)).

¶Примеры планарных и не планарных графов

¶Планарные графы

• Деревья (связные ациклические графы) — всегда планарны.
• Циклы — планарны.
• Полные графы \( K_1, K_2, K_3, K_4 \) — планарны. \( K_4 \) можно изобразить как треугольник с вершиной внутри.
• Двудольные графы \( K_{2,n} \) — планарны для любого \( n \).
• Графы многогранников (например, куб, октаэдр, додекаэдр) — планарны, так как их можно спроецировать на плоскость.

¶Не планарные графы

• Полный граф \( K_5 \) — минимальный не планарный граф.
• Полный двудольный граф \( K_{3,3} \) — также минимальный не планарный.
• Граф Петерсена — не планарен, содержит минор \( K_{3,3} \).

¶Классификация и родственные понятия

¶Внешнепланарные графы

Граф называется внешнепланарным, если его можно изобразить на плоскости так, что все вершины лежат на внешней грани. Все внешнепланарные графы являются планарными, но не наоборот. Например, \( K_4 \) — планарен, но не внешнепланарен.

¶Максимальные планарные графы

Планарный граф называется максимальным (или триангулированным), если добавление любого нового ребра (без кратных) делает его не планарным. В таком графе все грани (включая внешнюю) являются треугольниками. Для максимального планарного графа выполняется \( e = 3v - 6 \).

¶Двойственный граф

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

¶Применение

¶Картография

Планарные графы моделируют границы стран на карте. Задача раскраски карты в минимальное число цветов эквивалентна раскраске вершин двойственного графа.

¶Проектирование печатных плат

В электронике при проектировании печатных плат необходимо, чтобы проводники (рёбра) не пересекались (кроме точек соединения). Это соответствует планарности схемы. Если схема не планарна, используют многослойные платы.

¶Визуализация графов

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

¶Химия

Молекулярные графы (например, углеводородов) часто являются планарными, что связано с гибридизацией атомов углерода.

¶Интересные факты

• Задача о планарности графов тесно связана с задачей о трёх колодцах и трёх домах (провести дороги от трёх домов к трём колодцам без пересечений) — это в точности задача о планарности \( K_{3,3} \).
• Теорема о четырёх красках была первой крупной теоремой, доказанной с помощью компьютера (1976 год). Доказательство состояло из проверки 1936 конфигураций.
• Существуют алгоритмы, проверяющие планарность графа за линейное время (алгоритм Хопкрофта — Тарьяна, 1974 год).

¶Источники

• Харари Ф. Теория графов. — М.: Мир, 1973.
• Дистель Р. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002.
• Бонди Дж. А., Морти У. Р. Теория графов. — М.: Мир, 1977.
• Куратовский К. Sur le problème des courbes gauches en topologie // Fundamenta Mathematicae. — 1930. — Vol. 15. — P. 271–283.
• Appel K., Haken W. Every planar map is four colorable // Bulletin of the American Mathematical Society. — 1976. — Vol. 82. — P. 711–712.