Теорема Вагнера
В теории графов теорема Вагнера — это математическая характеристика запрещенных графов плоских графов , названная в честь Клауса Вагнера , утверждающая, что конечный граф является планарным тогда и только тогда, когда его миноры не включают ни 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 ] согласно которому граф планарен тогда и только тогда, когда он не содержит в качестве подграфа подразделения одного из тех же двух запрещенных графов K 5 и K 3,3 . В некотором смысле теорема Куратовского сильнее теоремы Вагнера: подразделение можно преобразовать в второстепенное подразделение того же типа, сжимая все ребра, кроме одного, на каждом пути, образованном процессом подразделения, но преобразуя второстепенное подразделение в подразделение того же типа. не всегда возможно. Однако в случае двух графов K 5 и K 3,3 несложно доказать, что граф, в котором хотя бы один из этих двух графов является минорным, также имеет хотя бы один из них в качестве подразделения, поэтому две теоремы эквивалентны. [ 3 ]
Подразумеваемое
[ редактировать ]Одним из следствий более сильной версии теоремы Вагнера для четырехсвязных графов является характеризация графов, не имеющих K5 минора . Теорему можно перефразировать так: каждый такой граф либо планарен, либо его можно разложить на более простые части. Используя эту идею, графы без K 5 -миноров можно охарактеризовать как графы, которые могут быть сформированы как комбинации планарных графов и восьмивершинного графа Вагнера , склеенных операциями суммирования кликов . Например, K 3,3 можно образовать таким образом как клику-сумму трех планарных графов, каждый из которых является копией тетраэдрического графа K 4 .
Теорема Вагнера является важным предшественником теории миноров графов, кульминацией которой стали доказательства двух глубоких и далеко идущих результатов: теорема о структуре графа (обобщение разложения Вагнера по кликовой сумме K 5 ) графов без миноров [ 4 ] и теорема Робертсона-Сеймура (обобщение характеристики запрещенных миноров плоских графов, утверждающее, что каждое семейство графов, замкнутое относительно операции взятия миноров, имеет характеристику конечным числом запрещенных миноров). [ 5 ] Аналоги теоремы Вагнера можно распространить и на теорию матроидов : в частности, те же два графа К 5 и К 3,3 (вместе с тремя другими запрещенными конфигурациями) фигурируют в характеристике графических матроидов запрещенными минорами матроидов . [ 6 ]
Ссылки
[ редактировать ]- ^ Вагнер, К. (1937), «О свойстве плоских комплексов», Math. , 114 : 570–590, doi : 10.1007/BF01594196 , S2CID 123534907 .
- ^ Куратовский, Казимеж (1930), «К проблеме левых кривых в топологии» (PDF) , Fund. Математика. (на французском языке), 15 : 271–283, doi : 10.4064/fm-15-1-271-283 .
- ^ Бонди, JA ; Мурти, USR (2008), Теория графов , Тексты для выпускников по математике, том. 244, Спрингер, с. 269, ISBN 9781846289699 .
- ^ Ловас, Ласло (2006), «Теория граф-миноров», Бюллетень Американского математического общества , 43 (1): 75–86, doi : 10.1090/S0273-0979-05-01088-8 , MR 2188176 .
- ^ Шартран, Гэри ; Лесняк, Линда; Чжан, Пин (2010), Графики и орграфы (5-е изд.), CRC Press, стр. 307, ISBN 9781439826270 .
- ^ Сеймур, П.Д. (1980), «О характеристике графических матроидов Тутте», Annals of Discrete Mathematics , 8 : 83–90, doi : 10.1016/S0167-5060(08)70855-0 , ISBN 9780444861108 , МР 0597159 .