В теории графов , Вагнер теорема является математической запрещались графы характеризацией из плоских графов , названных в честь Клауса Вагнера , о том , что конечный граф является планарным тогда и только тогда , когда его несовершеннолетним включают ни K 5 (в полном граф на пять вершин ) , ни K 3, 3 ( граф полезности , полный двудольный граф на шести вершинах). Это был один из самых ранних результатов в теории миноров графов, и его можно рассматривать как предшественник теоремы Робертсона – Сеймура .
Определения и заявление
Планарное вложение данного графа - это рисунок графа в евклидовой плоскости с точками для его вершин и кривыми для его ребер таким образом, что единственные пересечения между парами ребер находятся в общей конечной точке двух ребер. . Минор данного графа другой график , образованный удалением вершин, удаление ребер, а ребра заражения. Когда ребро сжимается, две его конечные точки объединяются, образуя единую вершину. В некоторых версиях теории второстепенных графов граф, полученный в результате сжатия, упрощается за счет удаления петель и множественных смежностей, в то время как в других версиях разрешены мультиграфы , но этот вариант не имеет значения для теоремы Вагнера. Теорема Вагнера утверждает, что каждый граф имеет либо планарное вложение, либо минор одного из двух типов: полный граф K 5 или полный двудольный граф K 3,3 . (Также возможно, чтобы один график имел оба типа второстепенных.)
Если данный граф является плоским, то же самое и со всеми его минорами: удаление вершин и ребер, очевидно, сохраняет планарность, и сжатие ребер также может быть выполнено с сохранением планарности, оставив одну из двух конечных точек стянутого ребра на месте и разводя все ребра, инцидентные другой конечной точке на пути сжатого ребра. Минорный минимальны неплоский представляет собой граф , который не плоский, но в которых все собственных несовершеннолетних (несовершеннолетних образованно , по меньшей мере , одного удалении или сжатие) являются плоскими. Другой способ сформулировать теорему Вагнера состоит в том, что существует только два минорно-минимальных неплоских графа, K 5 и K 3,3 .
Другой результат, также известный как теорема Вагнера, утверждает, что четырехсвязный граф является плоским тогда и только тогда, когда он не имеет K 5 минор. То есть, предполагая более высокий уровень связности, граф K 3,3 можно сделать ненужным в характеристике, оставив только один запрещенный второстепенный, K 5 . Соответственно, гипотеза Кельмана – Сеймура утверждает, что 5-связный граф является плоским тогда и только тогда, когда он не имеет K 5 в качестве топологического минора .
История и связь с теоремой Куратовского
Вагнер опубликовал обе теоремы в 1937 году, [1] после 1930 публикации теоремы Куратовской , [2] , согласно которому граф является плоским тогда и только тогда , когда она не содержит в качестве подграфа в подразделение одного из тех же самых двух запрещенных графов К 5 и К 3,3 . В некотором смысле теорема Куратовского сильнее теоремы Вагнера: подразделение может быть преобразовано в минор того же типа, сжимая все ребра, кроме одного, на каждом пути, образованном процессом разделения, но преобразовывая второстепенное в подразделение того же типа. не всегда возможно. Однако в случае двух графов K 5 и K 3,3 несложно доказать, что граф, который имеет хотя бы один из этих двух графов как второстепенный, также имеет хотя бы один из них как подразделение, поэтому две теоремы эквивалентны. [3]
Подразумеваемое
Одним из следствий более сильной версии теоремы Вагнера для четырехсвязных графов является характеризация графов, не имеющих минор K 5 . Теорема может быть перефразирована так, что каждый такой граф либо плоский, либо его можно разложить на более простые части. Используя эту идею, K 5 -безминорные графы можно охарактеризовать как графы, которые могут быть сформированы как комбинации плоских графов и восьмивершинного графа Вагнера , склеенных операциями клик-суммы . Например, K 3,3 может быть сформирован таким образом как клик-сумма трех плоских графов, каждый из которых является копией тетраэдрического графа K 4 .
Теорема Вагнера является важным предшественником теории миноров графов, кульминацией которой стало доказательство двух глубоких и далеко идущих результатов: теоремы о структуре графа (обобщение разложения Вагнера на клик-сумму K 5 -зависимых графов) [ 4] и теорему Робертсона – Сеймура (обобщение запрещенной минорной характеристики плоских графов, утверждающее, что каждое семейство графов, замкнутое относительно операции взятия миноров, имеет характеристику конечным числом запрещенных миноров). [5] Аналоги теоремы Вагнера также могут быть распространены на теорию матроидов : в частности, те же два графа K 5 и K 3,3 (вместе с тремя другими запрещенными конфигурациями) появляются в характеристике графических матроидов запрещенным матроидом. несовершеннолетние . [6]
Рекомендации
- ^ Вагнер, К. (1937), "Über eine Eigenschaft der ebenen Komplexe", Math. Аня. , 114 : 570-590, DOI : 10.1007 / BF01594196.
- ^ Куратовский, Казимеж (1930), "Sur le problème des Courbes gauches en topologie" (PDF) , Fund. Математика. (на французском языке), 15 : 271–283.
- ^ Bondy, JA ; Мурти, USR (2008), Теория графов , Тексты для выпускников по математике, 244 , Springer, стр. 269, ISBN 9781846289699.
- ^ Lovász, Ласло (2006), "Теория графов минор", Бюллетень Американского математического общества , 43 (1): 75-86, DOI : 10,1090 / S0273-0979-05-01088-8 , MR 2188176.
- ^ Чартран, Гэри ; Лесняк, Линда; Чжан, Пинг (2010), Графы и диграфы (5-е изд.), CRC Press, стр. 307, ISBN 9781439826270.
- ^ Seymour, PD (1980), "О характеризации TUTTE в графических матроидов", Annals дискретной математики , 8 : 83-90, DOI : 10.1016 / S0167-5060 (08) 70855-0 , MR 0597159.