Мінор графа

В теорії графів неорієнтований граф Н називається мінором графа G, якщо H можна сформувати з G видаленням ребер і вершин або стягуванням ребер.

Теорія мінорів графів почалася з теореми Вагнера, в якій говориться, що граф є планарним, якщо і тільки якщо його мінори не мають (в собі) ні повний граф K₅, ні повний двочастковий граф K_3,3.. Теорема Робертсона — Сеймура передбачає, що аналогічна характеризація забороненими мінорами існує для кожної властивості графів, що зберігається шляхом видалення вершин і стягування ребер. Для кожного фіксованого графа H можна перевірити, чи є Н мінором вхідного графа G за поліноміальний час. Разом з характеризацією забороненими мінорами це означає, що кожна властивість графа, збережена при діленні та скороченнях, може бути розпізнана за поліноміальний час.

Інші результати і домисли за участю мінора графа включають теорему структури графа, відповідно до якої графи, в яких немає Н як мінору, можуть бути утворені шляхом склеювання більш простих частин. А гіпотеза Хадвігера описує неможливість пофарбувати графи згідно з існуючим великого повного графа, як і його мінор. Важливі варіанти мінорів графа включають топологічні мінори й занурені мінори.

Визначення

Операція стягування ребра видаляє ребро з графа при одночасному об'єднанні двох вершин, які воно з'єднувало. Неорієнтований граф H є мінором іншого неорієнтованого графа G, якщо граф, схожий до H може бути отриманий з G стягуванням деяких ребер, видаленням деяких ребер і видаленням деяких ізольованих вершин. Порядок, в якому послідовність таких скорочень і вилучень виконується з G, не впливає на отриманий граф H.

Мінори графів часто вивчаються в більш загальному контексті матроїдних мінорів. У зв'язку з цим, заведено вважати, що всі графи є більше мультиграфом, ніж простим графом. Ця точка зору має перевагу в тому, що крайові видалення залишають ранг графа без змін, а крайові сутички завжди зменшують ранг на одиницю.

Приклад

У наступному прикладі, граф Н — мінор графа G: H.

G.

Наступна діаграма ілюструє трансформацію із G в H: спочатку побудуємо підграф G, видаливши пунктирні ребра (і ізольовану вершину), а потім позначимо сіру кромку (об'єднання двох вершин, які вона з'єднує):

Основні гіпотези

Нескладно перевірити, що відношення мінора графа утворює частковий порядок для ізоморфних класів неорієнтованих графів: відношення транзитивно (мінор мінору G є мінором самого G), а G і H можуть бути мінорами один одного тільки якщо вони ізоморфні, тому що будь-яка нетривіальна операція над мінором видаляє незначні ребра і вершини. Глибоке дослідження Ніла Робертсона і Пола Сеймура стверджує, що цей частковий порядок насправді є квазівпорядкуванням: якщо дається нескінченний список G₁, G₂, … кінцевих графів, то завжди існують два індекси i < j такі, що G_i є мінором G_j. Інший еквівалентний спосіб завдання цього є те, що будь-який набір графів може мати лише кінцеве число мінімальних елементів під порядком мінорів. Цей результат довів гіпотезу, раніше відому як гіпотеза Вагнера (за Клаусом Вагнером); Вагнер припускав її задовго раніше, але опублікував тільки в 1970 році.

Об'єднання мінорно-замкнутих графів

Багато об'єднань графів мають таку властивість, що кожен мінор графа з F також знаходиться в F; такий клас називається мінорно-замкнутим. Наприклад, в будь-якому планарному графі або будь-якому вкладеному графі на фіксованій топологічної поверхні ні видалення ребер, ні стягування ребер не можуть збільшити рід вкладеного графа; Таким чином, планарні графи і їх вкладені графи на будь-який закріпленій поверхні формують мінорно-замкнуті об'єднання.

Алгоритм

Якщо Н є циклічним графом з такою ж кількістю вершин, як і G, то Н — мінор G тоді і тільки тоді, коли G містить гамільтонів цикл. Проте, коли G є частиною вхідного, але Н фіксований, це може бути вирішено за поліноміальний час. Шляхом застосування алгоритму поліноміального часу для перевірки на те, чи містить даний граф будь-який з вказаних мінорів, можна розпізнати члени будь-якого мінорно-замкнутого об'єднання за поліноміальний час. Однак для того, щоб конструктивно застосувати цей результат, необхідно знати заборонені мінори сімейства графів.

Див. також

• Мінор обмеженої глибини

Посилання

• Alon, Noga; Seymour, Paul; Thomas, Robin (1990), A separator theorem for nonplanar graphs, Journal of the American Mathematical Society, 3 (4): 801—808, doi:10.2307/1990903, JSTOR 1990903, MR 1065053, архів оригіналу за 14 лютого 2019, процитовано 27 березня 2016.
• Bollobás, B.; Catlin, P. A.; Erdős, Paul (1980), Hadwiger's conjecture is true for almost every graph (PDF), European Journal of Combinatorics, 1: 195—199, doi:10.1016/s0195-6698(80)80001-1, архів оригіналу (PDF) за 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, архів оригіналу за 20 вересня 2019, процитовано 27 березня 2016.
• Diestel, Reinhard (2005), Graph Theory (вид. 3rd), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, архів оригіналу за 28 липня 2011, процитовано 27 березня 2016.
• Ding, Guoli (1996), Excluding a long double path minor, Journal of Combinatorial Theory, Series B, 66 (1): 11—23, doi:10.1006/jctb.1996.0002, MR 1368512.
• Eppstein, David (2000), Diameter and treewidth in minor-closed graph families, Algorithmica, 27: 275—291, arXiv:math.CO/9907126, doi:10.1007/s004530010020, MR 2001c:05132 {{citation}}: Перевірте значення |mr= (довідка).
• 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, архів оригіналу за 24 лютого 2018, процитовано 27 березня 2016.
• 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, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
• Pegg, Ed, Jr. (2002), Book Review: The Colossal Book of Mathematics (PDF), Notices of the American Mathematical Society, 49 (9): 1084—1086, doi:10.1109/TED.2002.1003756, архів оригіналу (PDF) за 2 квітня 2019, процитовано 27 березня 2016.
• 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) (PDF), London Math. Soc. Lecture Note Ser., т. 267, Cambridge: Cambridge Univ. Press, с. 201—222, MR 1725004, архів оригіналу (PDF) за 3 серпня 2016, процитовано 27 березня 2016.
• 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.