Мінор графа
В теорії графів неорієнтований граф Н називається мінором графу G, якщо H можна сформувати з G видаленням ребер і вершин або стягуванням ребер.
Теорія мінорів графів почалася з теореми Вагнера, в якій говориться, що граф є планарним, якщо і тільки якщо його мінори не включають в себе ні повний граф K5, ні повний двочастковий граф K3,3.[1]. Теорема Робертсон-Сеймура передбачає, що аналогічна характеризація забороненими мінорами існує для кожної властивості графів, що зберігається за рахунок видалення вершин і стягування ребер.[2] Для кожного фіксованого графу H можна перевірити, чи є Н мінором вхідного графу G за поліноміальний час. Разом з характеризацією забороненими мінорами це означає, що кожна властивість графу, збережена при діленні та скороченнях, може бути розпізнана за поліноміальний час.[3]
Інші результати і домисли за участю мінору графу включають теорему структури графу, відповідно до якої графи, в яких немає Н як мінору, можуть бути утворені шляхом склеювання більш простих частин. А гіпотеза Хадвігера описує неможливість пофарбувати графи згідно існуючого великого повного графу, як і його мінор. Важливі варіанти мінорів графу включають топологічні мінори і занурені мінори.
Визначення
Операція стягування ребра видаляє ребро з графу при одночасному об'єднанні двох вершин, які воно з'єднувало. Неорієнтований граф H є мінором іншого неорієнтованого графу G, якщо граф, схожий до H може бути отриманий з G стягуванням деяких ребер, видаленням деяких ребер і видаленням деяких ізольованих вершин. Порядок, в якому послідовність таких скорочень і вилучень виконується з G, не впливає на отриманий графік H.
Мінори графів часто вивчаються в більш загальному контексті матроїдних мінорів. У зв'язку з цим, прийнято вважати, що всі графи є більше мультиграфом, ніж простим графом. Ця точка зору має перевагу в тому, що крайові видалення залишають ранг графу без змін, а крайові сутички завжди зменшують ранг на одиницю.
Приклад
У наступному прикладі, граф Н — мінор графу G: H. 
G. 
Наступна діаграма ілюструє трансформацію із G в H: cпочатку побудуємо підграф G, видаливши пунктирні ребра (і ізольовану вершину), а потім позначимо сіру кромку (об'єднання двох вершин, які вона з'єднує):
Основні гіпотези
Нескладно перевірити, що відношення мінору графу утворює частковий порядок для ізоморфних класів неорієнтованих графів: відношення транзитивно (мінор мінору G є мінором самого G), а G і H можуть бути мінорами один одного тільки якщо вони ізоморфні, тому що будь-яка нетривіальна операція над мінором видаляє незначні ребра і вершини. Глибоке дослідження Ніла Робертсона і Пола Сеймура стверджує, що цей частковий порядок насправді є квазі-впорядкуванням: якщо дається нескінченний список G1, G2, … кінцевих графів, то завжди існують два індекси i < j такі, що Gi є мінором Gj. Інший еквівалентний спосіб завдання цього є те, що будь-який набір графів може мати лише кінцеве число мінімальних елементів під порядком мінорів[4]. Цей результат довів гіпотезу, раніше відому як гіпотеза Вагнера, за Клаусом Вагнером; Вагнер припускав її задовго раніше, але опублікував тільки в 1970 році.
Об'єднання мінорно-замкнутих графів
Багато об'єднань графів мають таку властивість, що кожен мінор графу з F також знаходиться в F; такий клас називається мінорно-замкнутим. Наприклад, в будь-якому планарному графі або будь-якому вкладеному графі на фіксованій топологічної поверхні ні видалення ребер, ні стягування ребер не можуть збільшити рід вкладеного графу; Таким чином, планарні графи і їх вкладені графи на будь-який закріпленій поверхні формують мінорно-замкнуті об'єднання.
Алгоритм
Якщо Н є циклічним графом з такою ж кількістю вершин, як і G, то Н — мінор G тоді і тільки тоді, коли G містить гамільтонів цикл. Проте, коли G є частиною вхідного, але Н фіксований, це може бути вирішено за поліноміальний час. Шляхом застосування алгоритму поліноміального часу для перевірки на те, чи містить даний граф будь-який з вказаних мінорів, можна розпізнати члени будь-якого мінорно-замкнутого об'єднання за поліноміальний час. Однак для того, щоб конструктивно застосувати цей результат, необхідно знати заборонені мінори сімейства графів.[3]
Примітки
- Lovász, (2006), p. 77; Wagner, (1937a).
- Lovász, (2006), theorem 4, p. 78; Robertson та Seymour, (2004).
- Fellows та Langston, (1988).
- Diestel, (2005), Chapter 12: Minors, Trees, and WQO; Robertson та Seymour, (2004).
Посилання
- Alon, Noga; Seymour, Paul; Thomas, Robin (1990). A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3 (4): 801–808. JSTOR 1990903. MR 1065053. doi:10.2307/1990903..
- Bollobás, B.; Catlin, P. A.; Erdős, Paul (1980). Hadwiger's conjecture is true for almost every graph. European Journal of Combinatorics 1: 195–199. doi:10.1016/s0195-6698(80)80001-1. Архів оригіналу за 18 березня 2009. Процитовано 27 березня 2016..
- Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2004). Diameter and treewidth in minor-closed graph families, revisited. Algorithmica 40 (3): 211–215. doi:10.1007/s00453-004-1106-1..
- Diestel, Reinhard (2005). Graph Theory (вид. 3rd). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4..
- Ding, Guoli (1996). Excluding a long double path minor. Journal of Combinatorial Theory. Series B 66 (1): 11–23. MR 1368512. doi:10.1006/jctb.1996.0002..
- Eppstein, David (2000). Diameter and treewidth in minor-closed graph families. Algorithmica 27: 275–291. MR 2001c:05132. arXiv:math.CO/9907126. doi:10.1007/s004530010020..
- Fellows, Michael R.; Langston, Michael A. (1988). Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM 35 (3): 727–739. doi:10.1145/44483.44491..
- Grohe, Martin (2003). Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23 (4): 613–632. doi:10.1007/s00493-003-0037-9..
- Hadwiger, Hugo (1943). Über eine Klassifikation der Streckenkomplexe. Vierteljschr. Naturforsch. Ges. Zürich 88: 133–143..
- Hall, Dick Wick (1943). A note on primitive skew curves. Bulletin of the American Mathematical Society 49 (12): 935–936. doi:10.1090/S0002-9904-1943-08065-2..
- Kostochka, Alexandr V. (1982). The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz. (Russian) 38: 37–58..
- Lovász, László (2006). Graph minor theory. Bulletin of the American Mathematical Society 43 (1): 75–86. doi:10.1090/S0273-0979-05-01088-8..
- Mader, Wolfgang (1967). Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen 174 (4): 265–268. doi:10.1007/BF01364272..
- Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012). Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics 28. Springer. с. 62–65. ISBN 978-3-642-27874-7. MR 2920058. doi:10.1007/978-3-642-27875-4..
- Pegg, Ed, Jr. (2002). Book Review: The Colossal Book of Mathematics. Notices of the American Mathematical Society 49 (9): 1084–1086. doi:10.1109/TED.2002.1003756..
- Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994). Shallow excluded minors and improved graph decompositions. Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994). с. 462–470..
- Reed, Bruce; Wood, David R. (2009). A linear-time algorithm to find a separator in a graph excluding a minor. ACM Transactions on Algorithms 5 (4): Article 39. doi:10.1145/1597036.1597043..
- Robertson, Neil; Seymour, Paul D. (1995). Graph Minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B 63 (1): 39–675. doi:10.1006/jctb.1995.1006..
- Thomas, Robin (1999). Recent excluded minor theorems for graphs. Surveys in combinatorics, 1999 (Canterbury). London Math. Soc. Lecture Note Ser. 267. Cambridge: Cambridge Univ. Press. с. 201–222. MR 1725004..
- Thomason, Andrew (1984). An extremal function for contractions of graphs. Mathematical Proceedings of the Cambridge Philosophical Society 95 (2): 261–265. doi:10.1017/S0305004100061521..
- Wagner, Klaus (1937a). Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114: 570–590. doi:10.1007/BF01594196..