Теорема Вагнера¶

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

¶История

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

Клаус Вагнер, работавший в области комбинаторной топологии, в 1937 году предложил альтернативную формулировку, используя понятие минора графа, а не гомеоморфизма. Минор графа получается удалением вершин, удалением рёбер и стягиванием рёбер (отождествлением смежных вершин). Вагнер показал, что условие запрета на миноры \( K_5 \) и \( K_{3,3} \) эквивалентно планарности. Это обобщение оказалось важным для развития теории миноров графов, кульминацией которой стала теорема Робертсона-Сеймура (1980-2004), утверждающая, что любой класс графов, замкнутый относительно взятия миноров, может быть охарактеризован конечным набором запрещённых миноров.

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

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

Теорема Вагнера. Граф \( G \) является планарным тогда и только тогда, когда ни \( K_5 \), ни \( K_{3,3} \) не являются минорами \( G \).

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

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

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

Вагнер также показал, что условие на миноры эквивалентно условию на гомеоморфные подграфы, хотя в общем случае эти понятия не совпадают. Например, граф может содержать минор \( K_5 \), но не содержать подграфа, гомеоморфного \( K_5 \). Однако для планарности эти два условия оказываются равносильными.

¶Связь с теоремой Куратовского

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

Известно, что любой граф, содержащий минор \( K_5 \) или \( K_{3,3} \), содержит и подграф, гомеоморфный одному из них, но обратное неверно. Тем не менее, для планарности оба условия эквивалентны, что и было доказано Вагнером.

¶Значение и обобщения

Теорема Вагнера стала важным шагом в развитии теории миноров графов. Она показала, что свойство планарности можно охарактеризовать через запрещённые миноры, что открыло путь к аналогичным характеризациям для других классов графов. В 1980-х годах Нил Робертсон и Пол Сеймур доказали, что любой класс графов, замкнутый относительно взятия миноров (то есть если граф принадлежит классу, то все его миноры тоже принадлежат), может быть описан конечным набором запрещённых миноров. Это грандиозное утверждение, известное как теорема Робертсона-Сеймура, обобщает теорему Вагнера на бесконечное множество классов.

Теорема Вагнера также используется в алгоритмической теории графов. Например, задача проверки планарности графа может быть решена за линейное время (алгоритм Хопкрофта-Тарьяна, 1974), и теорема Вагнера даёт теоретическую основу для таких алгоритмов, позволяя сводить проверку к поиску запрещённых миноров.

¶Примеры

1. Полный граф \( K_4 \) (четыре вершины, все попарно соединены) является планарным, так как его можно изобразить в виде треугольника с вершиной внутри. Он не содержит миноров \( K_5 \) или \( K_{3,3} \).
2. Граф Петерсена (10 вершин, 15 рёбер) является непланарным. Он содержит минор \( K_{3,3} \), что можно показать стягиванием некоторых рёбер.
3. Полный граф \( K_5 \) сам является непланарным, и его минор — он сам — запрещён.
4. Граф \( K_{3,3} \) также непланарен, и его минор — он сам — запрещён.

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

Теорема Вагнера, как и теорема Куратовского, относится к конечным графам. Для бесконечных графов понятие планарности требует более тонкого определения, и теорема не обобщается напрямую. Кроме того, теорема даёт характеризацию планарности, но не предлагает конструктивного способа проверки. Практические алгоритмы планарности используют другие методы, такие как поиск подграфов, гомеоморфных \( K_5 \) или \( K_{3,3} \), или разбиение графа на компоненты.

¶Источники

• Klaus Wagner, "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen, 1937.
• Reinhard Diestel, Graph Theory, Springer, 2005 (4-е издание).
• Ф. Харари, Теория графов, Мир, 1973.
• Н. Робертсон, П. Сеймур, "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B, 2004.