В теории графов теорема Вагнера — это математическая характеристика запрещенного графа плоских графов , названная в честь Клауса Вагнера , утверждающая, что конечный граф является планарным тогда и только тогда, когда его миноры не включают ни 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]
Одним из следствий более сильной версии теоремы Вагнера для четырехсвязных графов является характеризация графов, не имеющих минора K5 . Теорему можно перефразировать так: каждый такой граф либо планарен, либо его можно разложить на более простые части. Используя эту идею, графы без K 5 -миноров можно охарактеризовать как графы, которые могут быть сформированы как комбинации планарных графов и восьмивершинного графа Вагнера , склеенных операциями суммы кликов . Например, K 3,3 может быть образован таким образом как клика-сумма трех планарных графов, каждый из которых является копией тетраэдрического графа K 4 .
Теорема Вагнера является важным предшественником теории миноров графов, кульминацией которой стали доказательства двух глубоких и далеко идущих результатов: теорема о структуре графа (обобщение разложения Вагнера по кликовой сумме графов без миноров K 5 ) [ 4] и теорема Робертсона-Сеймура (обобщение характеристики запрещенных миноров плоских графов, утверждающее, что каждое семейство графов, замкнутое относительно операции взятия миноров, имеет характеристику конечным числом запрещенных миноров). [5] Аналоги теоремы Вагнера могут быть распространены и на теорию матроидов : в частности, те же два графа K 5 и K 3,3 (вместе с тремя другими запрещенными конфигурациями) появляются в характеристике графических матроидов запрещенным матроидом. несовершеннолетние . [6]