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

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

¶История

Вопрос о том, какие графы можно нарисовать на плоскости без пересечения рёбер, возник в середине XIX века в связи с задачами картографии и электротехники. В 1930 году Казимеж Куратовский опубликовал работу «Sur le problème des courbes gauches en topologie», в которой впервые сформулировал и доказал критерий планарности. Независимо от него, в 1931 году аналогичный результат получил американский математик Оррин Фринк, однако приоритет остался за Куратовским. Позднее, в 1937 году, Карл Вагнер доказал более слабую версию теоремы, известную как теорема Вагнера, которая использует понятие минора графа, а не подграфа.

¶Формулировка

Пусть \(G\) — конечный неориентированный граф. Граф \(G\) является планарным тогда и только тогда, когда он не содержит в качестве подграфа ни один из графов \(K_5\) или \(K_{3,3}\). Под «содержанием в качестве подграфа» понимается, что в \(G\) можно найти подграф, гомеоморфный \(K_5\) или \(K_{3,3}\). Гомеоморфизм означает, что один граф может быть получен из другого путём добавления или удаления вершин степени 2 (то есть подразбиения рёбер). Иными словами, если из \(G\) удалить вершины степени 2 и слить инцидентные им рёбра, то полученный граф будет содержать \(K_5\) или \(K_{3,3}\).

¶Графы Куратовского

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

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

¶Доказательство

Доказательство теоремы Куратовского обычно проводится в два этапа. Сначала показывается, что любой непланарный граф содержит подграф, гомеоморфный \(K_5\) или \(K_{3,3}\). Затем доказывается, что если граф содержит такой подграф, то он не может быть планарным. Обратное утверждение (если граф не содержит подграфов, гомеоморфных \(K_5\) или \(K_{3,3}\), то он планарен) доказывается с помощью индукции по числу вершин и рёбер, с использованием теоремы Жордана о кривой.

Существует несколько вариантов доказательства. Одно из наиболее известных — доказательство Томассена (1990-е годы), которое является более конструктивным и использует понятие разделяющего цикла. Доказательство Куратовского было длинным и сложным; современные версии, как правило, короче и опираются на теорию миноров.

¶Значение и применение

Теорема Куратовского является фундаментальным результатом в топологической теории графов. Она позволяет алгоритмически проверять, является ли граф планарным, хотя прямой перебор всех подграфов, гомеоморфных \(K_5\) или \(K_{3,3}\), неэффективен. На практике для проверки планарности используются более быстрые алгоритмы, например, алгоритм Хопкрофта — Тарьяна (1974), который работает за линейное время \(O(|V|)\). Однако теорема Куратовского остаётся теоретической основой для этих алгоритмов.

¶Применение в теории графов

• Критерий планарности: Теорема даёт простое необходимое и достаточное условие, которое часто используется в доказательствах других теорем.
• Теория миноров: Теорема Куратовского является предшественником более общей теоремы Робертсона — Сеймура о запрещённых минорах, которая утверждает, что для любого свойства графов, замкнутого относительно взятия миноров, существует конечный набор запрещённых миноров.
• Алгоритмическая сложность: Задача проверки планарности графа является полиномиально разрешимой, и теорема Куратовского лежит в основе многих алгоритмов.

¶Применение в других областях

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

¶Примеры

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

• Деревья: Любое дерево (связный ациклический граф) является планарным, так как его можно нарисовать без пересечений.
• Циклы: Простой цикл \(C_n\) планарен.
• Полные графы \(K_n\) для \(n \le 4\): \(K_4\) (тетраэдр) планарен, так как его можно изобразить в виде треугольника с вершиной внутри.

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

• \(K_5\): Полный граф на 5 вершинах. Любое его изображение на плоскости содержит хотя бы одно пересечение рёбер.
• \(K_{3,3}\): Полный двудольный граф. Он также непланарен; например, его можно изобразить в виде трёх «домов» и трёх «колодцев», соединённых всеми возможными путями, что приводит к пересечениям.
• Граф Петерсена: Этот известный граф также непланарен, так как содержит подграф, гомеоморфный \(K_{3,3}\).

¶Обобщения

Теорема Куратовского была обобщена на случай графов, вложимых в другие поверхности, например, в тор или проективную плоскость. Для каждой поверхности существует конечный набор запрещённых подграфов (минимальных непланарных графов для данной поверхности). Однако для тора такой набор известен лишь частично (например, \(K_7\) и \(K_{3,4}\) являются непланарными на торе, но не все минимальные графы известны). В общем случае, согласно теореме Робертсона — Сеймура, для любой поверхности существует конечный набор запрещённых миноров, но его размер может быть очень большим.

¶Критика и ограничения

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

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

• Теорема Куратовского иногда называется теоремой Куратовского — Фринка, хотя в русскоязычной литературе чаще используется только имя Куратовского.
• В 1937 году Карл Вагнер доказал, что граф планарен тогда и только тогда, когда он не содержит \(K_5\) или \(K_{3,3}\) в качестве минора (а не подграфа). Это утверждение эквивалентно теореме Куратовского, но формулируется в терминах миноров.
• Теорема Куратовского является одним из первых примеров «запрещённой подструктуры» в комбинаторике, где свойство (планарность) характеризуется отсутствием конечного набора «запрещённых» графов.

¶Источники

• Куратовский К. «Sur le problème des courbes gauches en topologie» (1930).
• Харари Ф. «Теория графов» (1969).
• Дистель Р. «Теория графов» (2000).
• Томассен К. «The Kuratowski theorem» (1990).