Теорема Понтрягина-Куратовского: критерий планарности графа

Теорема Понтрягина-Куратовского - главный итоговый результат о планарности графов: она даёт не приближённую оценку, а точный критерий "да/нет". Граф можно нарисовать на плоскости без пересечения рёбер тогда и только тогда, когда в нём нет подграфа, гомеоморфного полному графу $K_5$ или полному двудольному графу $K_{3,3}$. Формулировку независимо друг от друга получили польский математик Казимеж Куратовский (публикация 1930 года) и советский тополог Лев Понтрягин (результат конца 1920-х, известный по независимым источникам) - поэтому в русскоязычной традиции теорему называют двойным именем. Ниже разберём точную формулировку, что такое "подразбиение" графа, почему более простое условие Эйлера само по себе не решает вопрос до конца, и как найти скрытый $K_5$ или $K_{3,3}$ в графе, который на первый взгляд выглядит безобидно. Прежде чем читать доказательство, поэкспериментируйте с калькулятором ниже: он показывает, как растёт разрыв между тем, что "разрешает" условие Эйлера, и тем, что на самом деле утверждает теорема.

Что утверждает теорема Понтрягина-Куратовского

Формально теорема звучит так:

$G \text{ планарен} \iff G \text{ не содержит подграфа, гомеоморфного } K_5 \text{ или } K_{3,3}.$

Здесь $K_5$ - полный граф на пяти вершинах (каждая соединена с каждой, всего $\binom{5}{2}=10$ рёбер), а $K_{3,3}$ - полный двудольный граф с долями по три вершины (девять рёбер, ни одного треугольника). Оба графа непланарны сами по себе - это отдельно доказывается через необходимое условие Эйлера. Но сила теоремы не в этом, а в обратном направлении: если граф не удаётся нарисовать без пересечений, то внутри него обязательно найдётся один из этих двух графов, пусть даже "растянутый" лишними вершинами. Других "источников" непланарности не существует - и это уже не наблюдение, а строгая теорема, доказательство которой существенно сложнее самого условия Эйлера.

Что такое подразбиение графа

Слово "гомеоморфный" здесь означает "с точностью до подразбиения". Подразбиение ребра $(u, v)$ - это замена его путём через одну или несколько новых вершин степени 2: было ребро $u - v$, стало $u - w - v$. С точки зрения топологии линия просто изогнулась, ничего принципиально не изменилось - если исходный граф нельзя было уложить на плоскости без пересечений, то и подразбитый нельзя, и наоборот. Поэтому теорема говорит не про точные копии $K_5$ и $K_{3,3}$, а про их подразбиения: граф может выглядеть как угодно сложно, с кучей дополнительных вершин на "рёбрах", но если стянуть все цепочки вершин степени 2 обратно в рёбра, где-то внутри проступит один из двух эталонных графов.

Рассчитать для своей задачи

Почему одного условия Эйлера недостаточно

Необходимое условие планарности из формулы Эйлера для связного плоского графа ($V - E + F = 2$) даёт неравенство $E \le \dfrac{g}{g-2}(V-2)$, где $g$ - обхват графа (длина кратчайшего цикла). Для $K_{3,3}$ ($V=6$, $E=9$, $g=4$) граница равна $2 \cdot 6 - 4 = 8$, а рёбер девять - неравенство нарушено, граф непланарен. Для $K_5$ ($V=5$, $E=10$, $g=3$) граница $3 \cdot 5 - 6 = 9$, рёбер десять - тоже нарушено. Пока всё согласуется.

Но что если пришить к вершине $K_{3,3}$ "хвост" - путь из $m$ новых вершин степени 2? Каждая новая вершина хвоста добавляет ровно одну вершину и одно ребро, не создавая новых циклов, поэтому обхват не меняется:

$V(m) = 6 + m, \qquad E(m) = 9 + m, \qquad \text{граница}(m) = 2V(m) - 4 = 8 + 2m.$

При $m=0$ имеем $9 > 8$ - условие Эйлера верно ловит непланарность. Но уже при $m \ge 1$ выполняется $E(m) \le \text{граница}(m)$: например, при $m=3$ рёбер $12$, граница $14$ - формальное условие "разрешает" укладку без пересечений. При этом граф по-прежнему непланарен - хвост из вершин степени 2 не меняет ничего в топологии, а внутри графа как был, так и остался неподразбитый $K_{3,3}$. Условие Эйлера необходимо, но не достаточно: оно смотрит только на подсчёт вершин и рёбер, а не на конкретную структуру графа. Именно этот разрыв и закрывает теорема Понтрягина-Куратовского - не приближённой оценкой, а точным структурным критерием.

Рассчитать для своей задачи

Как искать K5 или K3,3 внутри графа

На практике граф редко дан в виде "$K_{3,3}$ плюс хвост" - обычно нужно найти скрытую копию среди множества вершин и рёбер, которые не выглядят похожими ни на что конкретное. Практический приём: искать не точное совпадение, а шесть или пять вершин, между которыми существуют непересекающиеся по внутренним вершинам пути (не обязательно рёбра напрямую), реализующие нужную структуру связей. Если для шести вершин, разбитых на две тройки, между каждой парой "своя-чужая" найдётся отдельный путь - это подразбиение $K_{3,3}$. Если для пяти вершин найдутся десять попарно непересекающихся путей - это подразбиение $K_5$. Такой поиск - вычислительно нетривиальная задача (для больших графов её решают специализированные алгоритмы планарности вроде алгоритма Хопкрофта-Тарьяна), но для учебных графов на 6-10 вершин её вполне можно провести вручную, методично проверяя пары вершин высокой степени.

Пример: граф Петерсена и его непланарность

Классический учебный пример, где условие Эйлера "почти не спорит", но структура графа выдаёт непланарность - граф Петерсена: десять вершин, пятнадцать рёбер, обхват $g=5$ (в графе нет ни треугольников, ни четырёхугольников). Наивная граница $3V-6=24$ формально выполняется ($15 \le 24$), но она рассчитана для графов с обхватом 3 и здесь слишком грубая. Правильная граница с учётом реального обхвата:

$E \le \frac{g}{g-2}(V-2) = \frac{5}{3}(10-2) = \frac{40}{3} \approx 13{,}3.$

Пятнадцать рёбер больше $13{,}3$ - уточнённая граница Эйлера уже нарушена, и это само по себе доказывает непланарность. Но интереснее другое: граф Петерсена содержит явное подразбиение $K_{3,3}$ - если стянуть определённые пары смежных вершин (или, что то же самое, найти шесть вершин с девятью непересекающимися связывающими путями), внутри проступает ровно двудольная структура $K_{3,3}$. Это и есть демонстрация теоремы Понтрягина-Куратовского в действии: даже там, где формула Эйлера справляется, теорема даёт более глубокое структурное объяснение - непланарность не абстрактное свойство чисел $V$ и $E$, а конкретный "виновник"-подграф.

Рассчитать для своей задачи

Частые ошибки

• Считать выполнение условия Эйлера доказательством планарности. $E \le \frac{g}{g-2}(V-2)$ - необходимое условие, а не достаточное. Граф с "хвостом" из примера выше формально проходит проверку, оставаясь непланарным.
• Искать точную копию $K_5$ или $K_{3,3}$ вместо подразбиения. Забытая вершина степени 2 на пути между "узловыми" вершинами не убирает непланарность - подразбиение считается тем же самым графом с топологической точки зрения.
• Путать теорему Понтрягина-Куратовского с теоремой Вагнера. Теорема Вагнера - аналогичный критерий, но через миноры графа (стягивание рёбер, а не подразбиение); формулировка отличается, хотя оба критерия эквивалентны и дают тот же список запрещённых графов $K_5$, $K_{3,3}$.
• Забывать про обхват при оценке границы Эйлера. Для графов без треугольников (обхват $\ge 4$) граница $3V-6$ слишком грубая - нужно подставлять реальный обхват, как в примере с графом Петерсена.
• Считать, что непланарность зависит от расположения вершин на бумаге. Планарность - топологическое свойство самого графа (какие вершины с какими соединены), а не конкретного рисунка; перекрещивание линий на одном чертеже не доказывает непланарность, если существует другая укладка без пересечений.

FAQ

Чем подразбиение графа отличается от минора? Подразбиение получают только заменой рёбер путями через новые вершины степени 2 - без удаления вершин и рёбер. Минор получают более широким набором операций (удаление рёбер и вершин, стягивание рёбер). Теорема Понтрягина-Куратовского использует подразбиения, а эквивалентная теорема Вагнера - миноры; для планарности оба подхода приводят к одному и тому же списку запрещённых графов $K_5$ и $K_{3,3}$.

Почему в теореме именно два графа, а не один или три? Это доказанный факт, а не выбор: любой минимальный (по включению рёбер) непланарный граф обязательно оказывается подразбиением $K_5$ или $K_{3,3}$ - других "неделимых" источников непланарности не существует. Доказательство этого утверждения и составляет содержание теоремы.

Можно ли проверить планарность графа быстрее, чем перебором подразбиений K5 и K3,3? Да, для практических вычислений используют не прямой поиск подразбиений (это неэффективно для больших графов), а алгоритмы планарности с линейной сложностью - например, алгоритм Хопкрофта-Тарьяна. Теорема Понтрягина-Куратовского при этом остаётся теоретическим обоснованием того, почему такие алгоритмы вообще возможны.

Коротко

Теорема Понтрягина-Куратовского даёт точный критерий планарности: граф укладывается на плоскости без пересечений тогда и только тогда, когда он не содержит подграфа, гомеоморфного $K_5$ или $K_{3,3}$. Необходимое условие Эйлера $E \le \frac{g}{g-2}(V-2)$ полезно для быстрой отбраковки, но само по себе недостаточно - граф с "хвостом" из лишних вершин степени 2 может формально пройти проверку, оставаясь непланарным, как показывает и граф Петерсена. Только явное обнаружение подразбиения $K_5$ или $K_{3,3}$ даёт полное доказательство - в этом и есть разница между необходимым условием и настоящей теоремой.