Планарность: графы, которые помещаются на плоскости

Если ты умеешь выводить E ≤ 3V − 6 из формулы Эйлера, знаешь про K₅ и K₃,₃ и помнишь теорему о четырёх красках, листай до «Теперь сам».

Как думаешь, почему нельзя соединить три дома с тремя колодцами

Старая головоломка: три дома и три колодца, от каждого дома надо провести дорожку к каждому колодцу так, чтобы дорожки не пересекались. Прежде чем читать дальше, попробуй мысленно - и подумай, каким рассуждением можно ДОКАЗАТЬ, что нельзя, а не просто устать пробовать.

На что это похоже

Разводка печатной платы в один слой. Проводники не должны пересекаться, иначе будет короткое замыкание. Вопрос «уместится ли схема в один слой» - это в точности вопрос планарности графа соединений, а если не умещается, инженер добавляет второй слой и переходные отверстия. Число слоёв и есть мера непланарности.

Механизм: формула Эйлера и её следствия

Формула Эйлера. Для связного планарного графа, нарисованного без пересечений:

V − E + F = 2

где F - число ГРАНЕЙ, то есть областей, на которые рисунок делит плоскость, включая одну внешнюю (бесконечную).

Граница на число рёбер. Каждая грань ограничена минимум тремя рёбрами (при V >= 3 и отсутствии кратных рёбер), а каждое ребро граничит ровно с двумя гранями. Значит 3F <= 2E, откуда F <= 2E/3. Подставляем в формулу Эйлера:

2 = V − E + F <= V − E + 2E/3 = V − E/3
E/3 <= V − 2
E <= 3V − 6

Для ДВУДОЛЬНОГО планарного графа граница строже: в нём нет треугольников, поэтому каждая грань ограничена минимум ЧЕТЫРЬМЯ рёбрами, 4F <= 2E, и аналогично получается E <= 2V − 4.

Два запрещённых графа.

K₅   : V = 5, E = 10.  Граница: 3·5 − 6 = 9 < 10  → непланарен
K₃,₃ : V = 6, E = 9, двудолен. Граница: 2·6 − 4 = 8 < 9 → непланарен

Теорема Куратовского утверждает обратное: граф планарен тогда и только тогда, когда в нём нет подграфа, «похожего» на K₅ или K₃,₃ - то есть подграфа, полученного из них ПОДРАЗБИЕНИЕМ: добавлением вершин посреди рёбер. Пример: возьми K₅ и замени одно ребро путём из двух рёбер с новой вершиной посередине. Вершин стало шесть, рёбер одиннадцать, граница 3·6 − 6 = 12 теперь выполняется - а граф по-прежнему непланарен, потому что нарисовать его без пересечений мешает та же структура K₅, лишь растянутая. Поэтому критерий говорит не про сам K₅, а про его подразбиения. Проверить планарность можно за O(V) - алгоритм Хопкрофта и Тарьяна, но он сложен и в курсе не разбирается.

Следствие про степени. Если бы у всех вершин степень была >= 6, то 2E = Σ deg >= 6V, то есть E >= 3V, что противоречит E <= 3V − 6. Значит в любом планарном графе есть вершина степени не больше пяти - именно на этом факте строится доказательство теоремы о пяти красках.

Правило

Планарный граф - тот, который рисуется на плоскости без пересечения рёбер. Формула Эйлера: V − E + F = 2 для связного планарного графа. Следствия: E <= 3V − 6 при V >= 3, а для двудольного E <= 2V − 4; отсюда K₅ и K₃,₃ непланарны. По теореме Куратовского они - единственная причина непланарности. В любом планарном графе есть вершина степени <= 5. Любой планарный граф раскрашивается четырьмя цветами (теорема о четырёх красках).

Разбор: доказываем, что три дома и три колодца не соединить

Граф задачи - это K₃,₃: три дома, три колодца, девять дорожек (каждый дом к каждому колодцу), и рёбер между домами или между колодцами нет, то есть граф ДВУДОЛЬНЫЙ.

Считаем: V = 6, E = 9. Для двудольного планарного графа граница E <= 2V − 4 = 2·6 − 4 = 8. Но у нас девять рёбер, 9 > 8 - противоречие. Значит K₃,₃ не планарен, и головоломка не имеет решения. Не «у меня не получилось», а строго доказано двумя строками арифметики.

Тот же приём работает для K₅: V = 5, E = 10, граница 3·5 − 6 = 9, а рёбер десять. Заметь, что граница E <= 3V − 6 сама по себе не является критерием планарности: тот же K₃,₃ в неё укладывается (V = 6, E = 9, а 3·6 − 6 = 12 >= 9) и всё равно непланарен - поймала его только более строгая граница для двудольных. Формула Эйлера даёт только НЕОБХОДИМОЕ условие; достаточное - это Куратовский.

Разбор: почему граней ровно столько

Формула Эйлера легко проверяется на примерах, и такая проверка полезнее, чем кажется. Возьмём куб как граф: V = 8 вершин, E = 12 рёбер. Нарисуем его на плоскости (это возможно - куб планарен): получится шесть областей - пять «внутренних» и одна внешняя, то есть F = 6. Проверяем: 8 − 12 + 6 = 2 ✓.

Дерево из V вершин: рёбер V − 1, граней всего одна (внешняя), потому что замкнутых областей нет: V − (V−1) + 1 = 2 ✓.

Треугольник: V = 3, E = 3, граней две (внутри и снаружи): 3 − 3 + 2 = 2 ✓.

А теперь обещанная проверка границы: у куба E = 12 и 3V − 6 = 18 - укладывается с запасом. Запас понятен: границу E <= 3V − 6 даёт случай, когда ВСЕ грани треугольные, а у куба они квадратные. Отсюда же правило прикидки: планарные графы разреженные, E = O(V). Плотный граф (E ≈ V²) планарным быть не может в принципе - и это первый признак, по которому можно отбросить идею «нарисовать без пересечений».

Что ломается без этого

Первое: применять формулу Эйлера к несвязному графу - для графа с C компонентами она выглядит как V − E + F = 1 + C. Второе: считать E <= 3V − 6 критерием планарности: это лишь необходимое условие, обратное неверно. Третье: забывать про внешнюю грань при подсчёте F - её считают наравне с остальными. Четвёртое: применять границу к графам с кратными рёбрами и петлями - вывод предполагал, что каждая грань ограничена тремя РАЗНЫМИ рёбрами. Пятое: думать, что четыре краски - это про любые графы: теорема о четырёх красках верна только для ПЛАНАРНЫХ; у произвольного графа хроматическое число может быть сколь угодно большим (полный граф на k вершинах требует k цветов).

Зачем это в работе

Планарность - это про «уместится ли в один слой». Разводка печатных плат и микросхем: непланарный участок требует дополнительного слоя, и число слоёв напрямую влияет на цену изделия. Визуализация графов: планарный граф можно нарисовать красиво и без пересечений, и алгоритмы укладки этим пользуются - схемы метро, диаграммы зависимостей, карты процессов. Геоинформационные системы: карта регионов - планарный граф, и её раскраска четырьмя цветами гарантирована теоремой. Ещё одно применение - оценка сверху: увидев, что в задаче граф планарен, ты сразу знаешь E = O(V), а значит алгоритмы вида O(V + E) линейны по числу вершин. И отдельно стоит знать историю теоремы о четырёх красках: это первая крупная теорема, доказанная с помощью компьютера (1976), и её доказательство до сих пор нельзя проверить вручную - что само по себе занятный сюжет о границах математики.

Теперь сам

Планарный связный граф имеет 10 вершин, и каждая грань в его укладке ограничена ровно тремя рёбрами. Сколько в нём рёбер и граней? Может ли такой граф быть двудольным?