Теорема Вагнерса - Википедия - Wagners theorem

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

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

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

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

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

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

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

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

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

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

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

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

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