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

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

В теории графов, Вагнер теорема является математической запрещались графы характеризацией из плоских графов, названных в честь Клауса Вагнера, о том, что конечный граф является планарным тогда и только тогда, когда его несовершеннолетним включают ни K 5 (в полном граф на пять вершин ), ни K 3, 3 ( граф полезности, полный двудольный граф на шести вершинах). Это был один из самых ранних результатов в теории миноров графов, и его можно рассматривать как предшественник теоремы Робертсона – Сеймура.

СОДЕРЖАНИЕ

  • 1 Определения и утверждения
  • 2 История и связь с теоремой Куратовского
  • 3 Последствия
  • 4 ссылки

Определения и заявление

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

Если данный граф является плоским, то же самое и со всеми его минорами: удаление вершин и ребер, очевидно, сохраняет планарность, а сжатие ребер также может быть выполнено с сохранением планарности, оставив одну из двух конечных точек сжатого ребра на месте и разводя все ребра, инцидентные другой конечной точке на пути сжатого ребра. Минорный минимальны неплоский представляет собой граф, который не плоский, но в которых все собственных несовершеннолетних (несовершеннолетних образованно, по меньшей мере, одного удалении или сжатие) являются плоскими. Другой способ сформулировать теорему Вагнера состоит в том, что существует только два минорно-минимальных неплоских графа, K 5 и K 3,3.

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

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

Доказательство без слов, что тессеракт графа является неплоским использованием Куратовских или теорем Вагнера и нахождения либо К 5 (вверху) или К 3,3 (внизу) подграфам

Вагнер опубликовал обе теоремы в 1937 году после публикации в 1930 году теоремы Куратовского, согласно которой граф является плоским тогда и только тогда, когда он не содержит в качестве подграфа подразделения одного из тех же двух запрещенных графов K 5 и K 3, 3. В некотором смысле теорема Куратовского сильнее теоремы Вагнера: подразделение может быть преобразовано в минор того же типа, сжимая все ребра, кроме одного, на каждом пути, образованном процессом разделения, но преобразовывая второстепенное в подразделение того же типа. не всегда возможно. Однако в случае двух графов K 5 и K 3,3 несложно доказать, что граф, который имеет хотя бы один из этих двух графов как второстепенный, также имеет хотя бы один из них как подразделение, поэтому две теоремы эквивалентны.

Подразумеваемое

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

Теорема Вагнера является важным предшественником теории миноров графов, кульминацией которой стало доказательство двух глубоких и далеко идущих результатов: теоремы о структуре графа (обобщение разложения Вагнера по клике на сумму K 5 -мноров графов) и теорема Робертсон-Сеймура (обобщение запретной малой характеристики плоских графов, о том, что каждый графе семья замкнута относительно операции взятия несовершеннолетних имеет характеристику с помощью конечного числа запрещенных несовершеннолетних). Аналоги теоремы Вагнера также могут быть распространены на теорию матроидов : в частности, те же два графа K 5 и K 3,3 (вместе с тремя другими запрещенными конфигурациями) появляются в характеристике графических матроидов запрещенными минорами матроидов.

Рекомендации

Последняя правка сделана 2023-04-17 05:56:53
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте