PROFILPELAJAR.COM

Кликовая сумма двух планарных графов и графа Вагнера, образующая граф без K₅

Теорема Вагнера — характеризация планарных графов тесно связанная с теоремой Понтрягина — Куратовского.

Названа в честь Клауса Вагнера. Теорема утверждает, что конечный граф является планарным тогда и только тогда, когда его миноры не включают ни K₅ (полный граф с пятью вершинами), ни K_3,3 (коммунальный граф, полный двудольный граф с тремя вершинами в каждой доле). Теорема была одной из наиболее ранних работ в теории миноров графа и её можно рассматривать как предшественницу теоремы Робертсона — Сеймура.

Определения и формулировка теоремы

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

Если данный граф планарен, то таковы и все его миноры — удаление вершины или ребра очевидно не нарушает планарности, а стягивание ребра также можно сделать с сохранением планарности, если одну из вершин стягиваемого ребра оставить на месте, а все рёбра, инцидентные второй вершине, пустить вдоль стягиваемого ребра. Минорно минимальный непланарный граф — это непланарный граф, но все его собственные миноры (миноры, полученные по меньшей мере удалением или стягиванием одного ребра) планарны. Другая формулировка теоремы Вагнера — есть только два минорно минимальных непланарных графа, это K₅ и K_3,3.

Другой результат, который иногда также называют теоремой Вагнера, утверждает, что вершинно 4-связный граф планарен тогда и только тогда, когда он не содержит K₅ в качестве минора. То есть при предположении более высокого уровня связности граф K_3,3 оказывается несущественным для описания, так что остаётся только один запрещённый минор, K₅. Соответственно, гипотеза Келманса – Сеймура^[англ.] утверждает, что вершинно 5-связный граф планарен тогда и только тогда, когда не содержит K₅ в качестве топологического минора.

История и связь с теоремой Понтрягина — Куратовского

Вагнер опубликовал обе теоремы в 1937^[1], уже после публикации Куратовского в 1930^[2] теоремы, согласно которой граф планарен тогда и только тогда, когда он не содержит в качестве подграфа подразделение одного из тех же самых запрещённых графов K₅ и K_3,3. Теорема Куратовского сильнее теоремы Вагнера — подразделение может быть преобразовано в минор того же типа путём стягивания всех, кроме одного, рёбер в каждом пути, полученном при разукрупнении, а вот преобразование из минора в подразделение того же типа не всегда возможно. Однако в случае двух графов K₅ и K_3,3 можно доказать напрямую, что граф, содержащий по меньшей мере один из этих графов в качестве минора, может быть получен из этих графов путём подразделения, так что две теоремы эквивалентны^[3].

Следствия

Одним из следствий версии теоремы Вагнера для четырёхсвязных графов является описание графов, не содержащих K₅ в качестве минора. Теорему можно перефразировать как утверждение, что любой такой граф либо планарен, или может быть разложен на более простые части. Если использовать эту идею, графы, не содержащие K₅ в качестве минора, можно описать как графы, образованные комбинациями планарного графа и графа Вагнера с шестью вершинами, склеенные вместе посредством сумм по клике. Например, K_3,3 можно образовать этим способом посредством сумм по клике из трёх планарных графов, каждый из которых является копией тетраэдрального графа K₄.

Теорема Вагнера является важной предшественницей теории миноров графа, которая достигла апогея доказательством двух глубоких результатов с широкими следствиями — cтруктурной теоремы графов (обобщение разложения Вагнера на кликовые суммы графов, не содержащих K₅ в качестве минора) ^[4] и теоремы Робертсона — Сеймура (обобщение описания графов с помощью запрещённых миноров, утверждающая, что любое семейство графов, замкнутое по операции взятия минора описывается конечным числом запрещённых миноров) ^[5]. Аналогия теоремы Вагнера может быть распространена на теорию матроидов. В частности, те же самые K₅ и K_3,3 (вместе с тремя другими) появляются в описании графовых матроидов^[англ.] запрещёнными матроидными минорами^[англ.]^[6].

Примечания

↑ Wagner, 1937, с. 570–590.
↑ Kuratowski, 1930, с. 271–283.
↑ Bondy, Murty, 2008, с. 269.
↑ Lovász, 2006, с. 75–86.
↑ Chartrand, Lesniak, Zhang, 2010, с. 307.
↑ Seymour, 1980, с. 83–90.

Литература

K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. — 1937. — Т. 114. — С. 570–590. — doi:10.1007/BF01594196.
Kazimierz Kuratowski. Sur le problème des courbes gauches en topologie (фр.) // Fund. Math.. — 1930. — Т. 15. — С. 271–283.
J. A. Bondy, U.S.R. Murty. Graph Theory. — Springer, 2008. — Т. 244. — С. 269. — (Graduate Texts in Mathematics). — ISBN 9781846289699.
László Lovász. Graph minor theory. — 2006. — Т. 43, вып. 1. — С. 75–86. — doi:10.1090/S0273-0979-05-01088-8.
Gary Chartrand, Linda Lesniak, Ping Zhang. Graphs & Digraphs. — 5th. — CRC Press, 2010. — С. 307. — ISBN 9781439826270.
P. D. Seymour. On Tutte's characterization of graphic matroids // Annals of Discrete Mathematics. — 1980. — Т. 8. — С. 83–90. — doi:10.1016/S0167-5060(08)70855-0.