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

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

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

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

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

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

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

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

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

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

Следствия

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

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

Примечания
  1. Wagner, 1937, с. 570–590.
  2. Kuratowski, 1930, с. 271–283.
  3. Bondy, Murty, 2008, с. 269.
  4. Lovász, 2006, с. 75–86.
  5. Chartrand, Lesniak, Zhang, 2010, с. 307.
  6. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.