Теорія мінорів графів почалася з теореми Вагнера, в якій говориться, що граф є планарним, якщо і тільки якщо його мінори не мають (в собі) ні повний графK5, ні повний двочастковий графK3,3.[1]. Теорема Робертсона — Сеймура передбачає, що аналогічна характеризація забороненими мінорами існує для кожної властивості графів, що зберігається шляхом видалення вершин і стягування ребер.[2] Для кожного фіксованого графа H можна перевірити, чи є Н мінором вхідного графа G за поліноміальний час. Разом з характеризацією забороненими мінорами це означає, що кожна властивість графа, збережена при діленні та скороченнях, може бути розпізнана за поліноміальний час.[3]
Інші результати і домисли за участю мінора графа включають теорему структури графа, відповідно до якої графи, в яких немає Н як мінору, можуть бути утворені шляхом склеювання більш простих частин. А гіпотеза Хадвігера описує неможливість пофарбувати графи згідно з існуючим великого повного графа, як і його мінор. Важливі варіанти мінорів графа включають топологічні мінори й занурені мінори.
Визначення
Операція стягування ребра видаляє ребро з графа при одночасному об'єднанні двох вершин, які воно з'єднувало. Неорієнтований граф H є мінором іншого неорієнтованого графа G, якщо граф, схожий до H може бути отриманий з G стягуванням деяких ребер, видаленням деяких ребер і видаленням деяких ізольованих вершин. Порядок, в якому послідовність таких скорочень і вилучень виконується з G, не впливає на отриманий граф H.
Мінори графів часто вивчаються в більш загальному контексті матроїдних мінорів. У зв'язку з цим, заведено вважати, що всі графи є більше мультиграфом, ніж простим графом. Ця точка зору має перевагу в тому, що крайові видалення залишають ранг графа без змін, а крайові сутички завжди зменшують ранг на одиницю.
Приклад
У наступному прикладі, граф Н — мінор графа G: H.
G.
Наступна діаграма ілюструє трансформацію із G в H: спочатку побудуємо підграф G, видаливши пунктирні ребра (і ізольовану вершину), а потім позначимо сіру кромку (об'єднання двох вершин, які вона з'єднує):
Основні гіпотези
Нескладно перевірити, що відношення мінора графа утворює частковий порядок для ізоморфних класів неорієнтованих графів: відношення транзитивно (мінор мінору G є мінором самого G), а G і H можуть бути мінорами один одного тільки якщо вони ізоморфні, тому що будь-яка нетривіальна операція над мінором видаляє незначні ребра і вершини. Глибоке дослідження Ніла Робертсона і Пола Сеймура стверджує, що цей частковий порядок насправді є квазівпорядкуванням: якщо дається нескінченний список G1, G2, … кінцевих графів, то завжди існують два індекси i < j такі, що Gi є мінором Gj. Інший еквівалентний спосіб завдання цього є те, що будь-який набір графів може мати лише кінцеве число мінімальних елементів під порядком мінорів[4]. Цей результат довів гіпотезу, раніше відому як гіпотеза Вагнера (за Клаусом Вагнером); Вагнер припускав її задовго раніше, але опублікував тільки в 1970 році.
Об'єднання мінорно-замкнутих графів
Багато об'єднань графів мають таку властивість, що кожен мінор графа з F також знаходиться в F; такий клас називається мінорно-замкнутим. Наприклад, в будь-якому планарному графі або будь-якому вкладеному графі на фіксованій топологічної поверхні ні видалення ребер, ні стягування ребер не можуть збільшити рід вкладеного графа; Таким чином, планарні графи і їх вкладені графи на будь-який закріпленій поверхні формують мінорно-замкнуті об'єднання.
Алгоритм
Якщо Н є циклічним графом з такою ж кількістю вершин, як і G, то Н — мінор G тоді і тільки тоді, коли G містить гамільтонів цикл. Проте, коли G є частиною вхідного, але Н фіксований, це може бути вирішено за поліноміальний час. Шляхом застосування алгоритму поліноміального часу для перевірки на те, чи містить даний граф будь-який з вказаних мінорів, можна розпізнати члени будь-якого мінорно-замкнутого об'єднання за поліноміальний час. Однак для того, щоб конструктивно застосувати цей результат, необхідно знати заборонені мінори сімейства графів.[3]
Diestel, Reinhard (2005), Graph Theory (вид. 3rd), Berlin, New York: Springer-Verlag, ISBN978-3-540-26183-4, архів оригіналу за 28 липня 2011, процитовано 27 березня 2016.
Kostochka, Alexandr V. (1982), The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret. Analiz. (Russian) , 38: 37—58.
Mader, Wolfgang (1967), Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Mathematische Annalen, 174 (4): 265—268, doi:10.1007/BF01364272.
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.
