Минор графа

Минор в теории графов — граф для заданного графа , который может быть образован из удалением рёбер и вершин и стягиванием рёбер.

Теория миноров графов началась с теоремы Вагнера, гласящей, что граф планарен в том и только в том случае, когда в его миноры не входят ни полный граф K5, ни полный двудольный граф K3,3[1][2]. Из теоремы Робертсона — Сеймура следует, что аналоги характеризации запрещёнными минорами существуют для любого свойства графов, которые сохраняются при удалениях и стягивании рёбер[3][4].

Для любого графа H можно проверить, является ли H минором входного графа G за полиномиальное время[5]. Вместе с характеризацией запрещёнными минорами из этого следует, что любое свойство графа, сохраняющееся при удалениях и стягиваниях, может быть распознано за полиномиальное время[6].

Среди других результатов и гипотез, использующих миноры графов, находятся теорема о структуре графа, согласно которой графы, не содержащие H в качестве минора, могут быть образованы склеиванием более простых частей, и гипотеза Хадвигера, связывающая невозможность раскраски графа с существованием большого полного графа в качестве его минора. Важными вариантами миноров графов являются топологические миноры и погружённые миноры.

Определения

Стягивание ребра — это операция, которая удаляет ребро из графа, а концы ребра сливаются в одну вершину. Неориентированный граф H является минором другого неориентированного графа G, если граф, изоморфный H, может быть получен из G стягиванием рёбер, удалением некоторых рёбер и удалением некоторых изолированных вершин. Порядок, в котором производится стягивания и удаления в G, не влияют на результирующий граф H.

Миноры графов часто изучаются в более общем контексте миноров матроидов[англ.]. В этом контексте обычно полагается, что графы связны, могут иметь петли и кратные ребра (то есть, рассматриваются мультиграфы, а не простые графы). Стягивание петли и удаление разрезающего ребра запрещены. При таком подходе удаление ребра оставляет ранг графа неизменным, а стягивание ребра всегда уменьшает ранг на единицу.

В других контекстах (как, например, при изучении псевдолесов) имеет смысл разрешить удаление разрезающих рёбер и позволить графам быть несвязными, но при этом имеет смысл запретить мультиграфы. В таком варианте теории миноров графов граф всегда упрощается после любого стягивания ребра для исключения петель и кратных рёбер[7]

Пример

В следующем примере граф H является минором графа G:

H. Граф H

G. Граф G

Следующий рисунок иллюстрирует это. Сначала строим подграф графа G путём удаления пунктирных рёбер (и возникающую изолированную вершину), а затем стягиваем серое ребро (объединяя две вершины, которые ребро соединяет):

Преобразование из G в H

Основные результаты и гипотезы

Можно легко проверить, что отношение миноров графов образует частичный порядок на классе изоморфизмов неориентированных графов — отношение транзитивно (минор минора графа G является сам минором G) и графы G и H могут быть минорами друг друга если они изоморфны, поскольку любая нетривиальная операция с минором удаляет рёбра или вершины. Глубокий результат Нейла Робертсона[англ.] и Пола Сеймура утверждает, что этот частичный порядок является, на самом деле, вполне квазиупорядоченным[англ.] — если задан бесконечный список G1, G2,… конечных графов, всегда существуют два индекса i < j, такие что Gi является минором графа Gj. Эквивалентная формулировка утверждения — любое множество графов может иметь лишь конечное число минимальных элементов по минорному отношению[8]. Этот результат доказывает гипотезу, до этого известную как гипотеза Вагнера. Вагнер высказал гипотезу много раньше, но опубликовал её лишь в 1970[9].

По ходу доказательства Сеймур и Робертсон также доказали теорему о структуре графа, в которой они определили для любого фиксированного графа H грубую структуру любого графа, который не содержит H в качестве минора. Утверждение теоремы длинно и запутано, но, вкратце, теорема устанавливает, что такой граф должен иметь структуру суммы по кликам меньших графов, которые получаются небольшой модификацией графов, вложенных в поверхности ограниченного рода. Таким образом, их теория устанавливает фундаментальную связь между минорами графа и топологическими вложениями графов[10][11].

Для любого графа H простые свободные от миноров H графы должны быть редкими, что означает, что число рёбер меньше некоторой константы, умноженной на число вершин[12]. Конкретнее, если H имеет h вершин, то простой n-вершинный свободный от H-миноров граф может иметь не более рёбер, а некоторые свободные от Kh миноров графы имеют по меньшей мере такое число рёбер[13]. Так, если H имеет h вершин, то свободные от H-миноров графы имеют среднюю степень и, кроме того, вырожденность . Вдобавок, свободные от H-миноров графы имеют теорему о разбиении, подобную теореме о разбиении в планарном графе — для любого фиксированного H, и любого n-вершинного свободного от H-миноров графа G можно найти подмножество вершин размером , удаление которого делит граф G на два (возможно несвязных) подграфа с максимум 2n/3 вершинами в каждом[14]. Даже более строго, для любого фиксированного H свободные от H-миноров графы имеют древесную ширину [15].

Гипотеза Хадвигера делает предположение, что если граф G не содержит минор, изоморфный полному графу с k вершинами, то граф G имеет правильную раскраску в k − 1 цветов[16]. Случай k = 5 является переформулировкой проблемы четырёх красок. Гипотеза Хадвигера доказана для k ≤ 6 [17], но не в общем виде. Болобас, Катлин и Эрдёш[18] назвали задачу «одной из глубочайших нерешённых задач теории графов». Другой результат, связывающий теорему четырёх красок с минорами графа — это теорема о снарках, о доказательстве которой объявили Робертсон, Сандерс, Сеймур и Томас[19]. Теорема является усилением теоремы четырёх красок и была высказана (как гипотеза) Таттом и она утверждает, что любой 3-регулярный граф без мостов, для рёберной раскраски которого требуется четыре цвета, должен содержать граф Петерсена в качестве минора[20][21].

Семейства графов, замкнутые по минорам

Подробнее по теме «семейства минорно замкнутых графов» см. Теорема Робертсона — Сеймура

Многие семейства графов обладают свойством, что любой минор графа из F также входит в F. В этом случае говорят, что класс графов минорно замкнут. Например, для любого планарного графа или вложения графа в фиксированную топологическую поверхность ни удаление рёбер, ни стягивание рёбер не может увеличить род вложения. Таким образом, планарные графы и графы, вложимые в любую фиксированную поверхность, образуют минорно замкнутые семейства.

Если F является минорно замкнутым семейством, то (ввиду свойства вполне квазиупорядоченности миноров) среди графов, не принадлежащих F, существует конечное множество X минорно минимальных графов. Эти графы являются запрещёнными минорами для F — граф принадлежит множеству F тогда и только тогда, когда он не содержит в качестве миноров любой граф из X. Таким образом, любое минорно замкнутое семейство F может быть охарактеризовано как семейство свободных от миноров из X графов для некоторого конечного множества X запрещённых миноров[3][4].

Хорошо известным примером характеризации такого типа является Теорема Вагнера, характеризующая планарные графы как графы, не имеющие ни K5, ни K3,3 в качестве миноров [1][2].

В некоторых случаях свойства графов в минорно замкнутом семействе могут быть тесно связаны со свойствами исключённых миноров. Например, минорно замкнутое семейство графов F имеет ограниченную путевую ширину тогда и только тогда, когда запрещённые семейства включают лес [22], F имеет ограниченную глубину дерева тогда и только тогда, когда запрещённые миноры включают разъединённое объединение путей, F имеет ограниченную древесную ширину тогда и только тогда, когда его запрещённые миноры включают планарный граф[23], и F имеет ограниченную локальную древесную ширину (функциональную связь между диаметром и древесной шириной) тогда и только тогда, когда его запрещённые миноры включают верхушечный граф (граф, который становится планарным при удалении одной вершины)[24][25]. Если H может быть нарисован на плоскости с единственным пересечением (то есть, число пересечений графа равно единице), то для свободных от H-миноров графов верна теорема об упрощённой структуре, по которой такие графы представляют собой кликовую сумму планарных графов и графов с ограниченной древесной шириной[26][27]. Например, как K5, так и K3,3 имеют число пересечений, равное единице, и как показал Вагнер, свободные от K5 графы — это в точности 3-кликовые суммы планарных графов и восьмивершинного графа Вагнера, в то время как свободные от K3,3 графы — это в точности 2-кликовые суммы планарных графов и K5[28].

Вариации

Топологические миноры

Граф H называется топологическим минором графа G, если граф подразбиений графа H изоморфен подграфу графа G [29]. Легко видеть, что любой топологический минор является минором (в обычном смысле). Обратное, однако, в общем случае неверно (например, полный граф K5 в графе Петерсена является минором, но не является топологическим минором), но выполняется для графа с максимальной степенью, не превосходящей трёх[30].

Отношения топологических миноров не является вполне квазиупорядоченным на множестве конечных графов[31] и потому результат Робертсона и Сеймура неприменим к топологическим минорам. Однако легко построить характеризации конечными запрещёнными топологическими минорами из характеризации конечными запрещёнными минорами.

Погружённый минор

Операция с графом, называемая подъёмом, является центральным понятием в концепции погружения. Подъём является операцией со смежными рёбрами. Если заданы три вершины v, u и w, где (v, u) и (u, w) — ребра графа, подъём vuw, или, эквивалентно, (v, u), (u, w) — это операция, которая удаляет два ребра (v, u) и (u, w) и добавляет ребро (v, w). В случае, когда ребро (v, w) уже присутствует, v и w будут соединены ещё одним ребром, а поэтому операция является существенно операцией с мультиграфами.

В случае, когда граф H может быть получен из графа G путём последовательности операций подъёма (над G) а затем нахождения изоморфного подграфа, мы говорим, что H является погружённым минором графа G.

Существует другой способ определения погружённых миноров, который эквивалентен операции подъёма. Мы говорим, что H является погружённым минором графа G, если существует инъективное отображение из вершин H в вершины G, при котором образы смежных элементов H соединены в G путями, не имеющими общих рёбер.

Отношение погружённых миноров является вполне квазиупорядоченным на множестве конечных графов, а потому результаты Робертсона и Сеймура применимы к погружённым минорам. Более того, это означает, что любое семейство, замкнутое по погружённым минорам, характеризуется конечным семейством запрещённых вложенных миноров.

В области визуализация графов погружённые миноры появляются как планаризации[англ.] непланарных графов — из рисунка графа на плоскости с пересечениями может быть образован погружённый минор путём замены каждой точки пересечения новой вершиной и разбиения каждого пересечённого ребра на путь. Это позволяет распространить методы рисования планарных графов на непланарные графы [32].

Неглубокие миноры

Неглубокий минор графа G — это минор, в котором рёбра графа G, стянутые для получения минора, образуют непересекающиеся подграфы малого диаметра. Неглубокие миноры образуют как бы мост между минорами графа и подграфами в том смысле, что неглубокие миноры с высокой глубиной совпадают с обычными типами миноров, в то время как неглубокие миноры с нулевой глубиной — это в точности подграфы[33]. Они также позволяют распространить теорию миноров графа на классы графов, такие как 1-планарные графы, которые не замкнуты по взятию миноров[34].

Алгоритмы

Задача разрешимости, содержится ли граф H в графе G в качестве минора является, в общем случае, NP-полной. Например, если H является циклом с тем же числом вершин, что и у G, то H является минором графа G тогда и только тогда, когда G содержит гамильтонов граф. Однако, если G является входным, а H фиксирован, задача может быть решена за полиномиальное время. Конкретнее, время работы проверки, является ли H минором графа G в этом случае равно O(n3), где n — число вершин в G, а O большое прячет константу, которая зависит суперэкспоненциально от H[5]. Вследствие результата о минорах графа этот алгоритм улучшается до O(n2)[35]. Таким образом, при применении алгоритма с полиномиальным временем работы для проверки, содержит ли заданный граф какой-либо из запрещённых миноров, можно распознать члены любого минорно замкнутого семейства за полиномиальное время. Однако, чтобы применять этот результат конструктивно, необходимо знать запрещённые миноры семейства графов[6].

Примечания

  1. ↑ 1 2 Lovász, 2006, p. 77.
  2. ↑ 1 2 Wagner, 1937a.
  3. ↑ 1 2 Lovász, 2006, Т. 4, p. 78.
  4. ↑ 1 2 Robertson, Seymour, 2004.
  5. ↑ 1 2 Robertson, Seymour, 1995.
  6. ↑ 1 2 Fellows, Langston, 1988.
  7. ↑ Ловаш (Lovász (2006)) противоречит сам себе. На странице 76 он пишет, что «параллельные рёбра и петли разрешаются», но на странице 77 от утверждает, что «граф является лесом тогда и только тогда, когда он не содержит треугольника K3 в качестве минора», что верно только для простых графов.
  8. ↑ Diestel (2005), Chapter 12: Minors, Trees, and WQO; Robertson, Seymour (2004).
  9. ↑ Lovász, 2006, p. 76.
  10. ↑ Lovász, 2006, p. 80—82.
  11. ↑ Robertson, Seymour, 2003.
  12. ↑ Mader, 1967.
  13. ↑ Kostochka, 1984; Thomason, 1984; Thomason, 2001.
  14. ↑ Alon, Seymour, Thomas, 1990; Plotkin, Rao, Smith, 1994; Reed, Wood, 2009.
  15. ↑ Grohe, 2003.
  16. ↑ Hadwiger, 1943.
  17. ↑ Robertson, Seymour, Thomas, 1993.
  18. ↑ Bollobás, Catlin, Erdős, 1980.
  19. ↑ Однако по состоянию на 2012 год доказательство опубликовано так и не было
  20. ↑ Thomas, 1999.
  21. ↑ Pegg, 2002.
  22. ↑ Robertson, Seymour, 1983.
  23. ↑ Lovász (2006), Theorem 9, p. 81; Robertson, Seymour (1986).
  24. ↑ Eppstein, 2000.
  25. ↑ Demaine, Hajiaghayi, 2004.
  26. ↑ Robertson, Seymour, 1993.
  27. ↑ Demaine, Hajiaghayi, Thilikos, 2002.
  28. ↑ Wagner, 1937a; Hall, 1943.
  29. ↑ Diestel, 2005, p. 20.
  30. ↑ Diestel, 2005, p. 22.
  31. ↑ Ding, 1996.
  32. ↑ Buchheim, Chimani, Gutwenger, Jünger, Mutzel, 2014.
  33. ↑ Nešetřil, de Mendez, 2012.
  34. ↑ Nešetřil, de Mendez, 2012, p. 319—321.
  35. ↑ Kawarabayashi, Kobayashi, Reed, 2012.

Литература

  • Noga Alon, Paul Seymour, Robin Thomas. A separator theorem for nonplanar graphs // Journal of the American Mathematical Society. — 1990. — Т. 3, вып. 4. — С. 801—808. — doi:10.2307/1990903. — JSTOR 1990903.
  • B. Bollobás, P. A. Catlin, Paul Erdős. Hadwiger's conjecture is true for almost every graph // European Journal of Combinatorics. — 1980. — Т. 1. — С. 195—199. — doi:10.1016/s0195-6698(80)80001-1. Архивировано 18 марта 2009 года.
  • Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, Petra Mutzel. Handbook of Graph Drawing and Visualization / Roberto Tamassia. — CRC Press, Boca Raton, FL, 2014. — (Discrete Mathematics and its Applications (Boca Raton)).
  • Erik D. Demaine, MohammadTaghi Hajiaghayi. Diameter and treewidth in minor-closed graph families, revisited // Algorithmica. — 2004. — Т. 40, вып. 3. — С. 211—215. — doi:10.1007/s00453-004-1106-1.
  • Erik D. Demaine, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos. Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002). — Springer-Verlag, 2002. — Т. 2462. — С. 67—80. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-45753-4_8.
  • Reinhard Diestel. Graph Theory. — 3rd. — Berlin, New York: Springer-Verlag, 2005. — ISBN 978-3-540-26183-4.
  • Guoli Ding. Excluding a long double path minor // Journal of Combinatorial Theory. — 1996. — Т. 66, вып. 1. — С. 11—23. — doi:10.1006/jctb.1996.0002.
  • David Eppstein. Diameter and treewidth in minor-closed graph families // Algorithmica. — 2000. — Т. 27. — С. 275—291. — doi:10.1007/s004530010020. — arXiv:math.CO/9907126.
  • Michael R. Fellows, Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability // Journal of the ACM. — 1988. — Т. 35, вып. 3. — С. 727—739. — doi:10.1145/44483.44491.
  • Martin Grohe. Local tree-width, excluded minors, and approximation algorithms // Combinatorica. — 2003. — Т. 23, вып. 4. — С. 613—632. — doi:10.1007/s00493-003-0037-9.
  • Hugo Hadwiger. Über eine Klassifikation der Streckenkomplexe // Vierteljschr. Naturforsch. Ges. Zürich. — 1943. — Т. 88. — С. 133—143.
  • Dick Wick Hall. A note on primitive skew curves // Bulletin of the American Mathematical Society. — 1943. — Т. 49, вып. 12. — С. 935—936. — doi:10.1090/S0002-9904-1943-08065-2.
  • Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed. The disjoint paths problem in quadratic time // Journal of Combinatorial Theory, Series B. — 2012. — Т. 102, вып. 2. — С. 424—435. — doi:10.1016/j.jctb.2011.07.004.
  • Косточка А. В. О минимуме числа Хадвигера для графов с данной средней степенью вершин. — Новосибирск: Институт математики СО АН СССР, 1982. — Вып. 38. — С. 37—58.
  • Alexandr V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree // Combinatorica. — 1984. — Т. 4. — С. 307—316. — doi:10.1007/BF02579141.
  • László Lovász. Graph minor theory // Bulletin of the American Mathematical Society. — 2006. — Т. 43, вып. 1. — С. 75—86. — doi:10.1090/S0273-0979-05-01088-8.
  • Wolfgang Mader. Homomorphieeigenschaften und mittlere Kantendichte von Graphen // Mathematische Annalen. — 1967. — Т. 174, вып. 4. — С. 265—268. — doi:10.1007/BF01364272.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — С. 62–65. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.
  • Ed Pegg Jr. Book Review: The Colossal Book of Mathematics // Notices of the American Mathematical Society. — 2002. — Т. 49, вып. 9. — С. 1084—1086. — doi:10.1109/TED.2002.1003756.
  • Serge Plotkin, Satish Rao, Warren D. Smith. Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994). — 1994. — С. 462—470.
  • Bruce Reed, David R. Wood. A linear-time algorithm to find a separator in a graph excluding a minor // ACM Transactions on Algorithms. — 2009. — Т. 5, вып. 4. — С. Article 39. — doi:10.1145/1597036.1597043.
  • Neil Robertson, Paul Seymour. Graph minors. I. Excluding a forest // Journal of Combinatorial Theory, Series B. — 1983. — Т. 35, вып. 1. — С. 39—61. — doi:10.1016/0095-8956(83)90079-5.
  • Neil Robertson, Paul D. Seymour. Graph minors. V. Excluding a planar graph // Journal of Combinatorial Theory, Series B. — 1986. — Т. 41, вып. 1. — С. 92—114. — doi:10.1016/0095-8956(86)90030-4.
  • Neil Robertson, Paul D. Seymour. Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors / Neil Robertson, Paul Seymour. — American Mathematical Society, 1993. — Т. 147. — С. 669–675. — (Contemporary Mathematics).
  • Neil Robertson, Paul D. Seymour. Graph Minors. XIII. The disjoint paths problem // Journal of Combinatorial Theory, Series B. — 1995. — Т. 63, вып. 1. — С. 65—110. — doi:10.1006/jctb.1995.1006.
  • Neil Robertson, Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph // Journal of Combinatorial Theory, Series B. — 2003. — Т. 89, вып. 1. — С. 43—76. — doi:10.1016/S0095-8956(03)00042-X.
  • Neil Robertson, Paul D. Seymour. Graph Minors. XX. Wagner's conjecture // Journal of Combinatorial Theory, Series B. — 2004. — Т. 92, вып. 2. — С. 325—357. — doi:10.1016/j.jctb.2004.08.001.
  • Neil Robertson, Paul Seymour, Robin Thomas. Hadwiger's conjecture for K6-free graphs // Combinatorica. — 1993. — Т. 13. — С. 279—361. — doi:10.1007/BF01202354.
  • Robin Thomas. Surveys in combinatorics, 1999 (Canterbury). — Cambridge: Cambridge Univ. Press, 1999. — Т. 267. — С. 201—222. — (London Math. Soc. Lecture Note Ser.).
  • Andrew Thomason. An extremal function for contractions of graphs // Mathematical Proceedings of the Cambridge Philosophical Society. — 1984. — Т. 95, вып. 2. — С. 261—265. — doi:10.1017/S0305004100061521.
  • Andrew Thomason. The extremal function for complete minors // Journal of Combinatorial Theory, Series B. — 2001. — Т. 81, вып. 2. — С. 318—338. — doi:10.1006/jctb.2000.2013.
  • Klaus Wagner. Über eine Eigenschaft der ebenen Komplexe // Math. Ann.. — 1937a. — Т. 114. — С. 570—590. — doi:10.1007/BF01594196.
  • Andrew Thomason. Über eine Erweiterung des Satzes von Kuratowski // Deutsche Mathematik. — 1937b. — Т. 2. — С. 280—285.

Ссылки