Вікіпедія

Теорема Робертсона — Сеймура

твердження в теорії графів

Теорема Робертсона — Сеймура (також звана теоремою про мінори графа[1]) стверджує, що будь-яке сімейство графів, замкнуте відносно операцій видалення і стягування ребер, можна визначити скінченним набором заборонених графів.

Наприклад, множина планарних графів замкнута за операціями видалення і стягування ребер; забороненими графами в цьому випадку є повний граф K5 і повний двочастковий граф K3,3. Останнє твердження називається теоремою Вагнера і тісно пов'язане з теоремою Понтрягіна — Куратовського.

Теорема широко відома елементарністю формулювання за відсутності простого доведення. Вона носить ім'я Нейла Робертсона[en] і Пола Сеймура[en], які довели її в серії з двадцяти статей загальним обсягом 500 сторінок, що вийшли від 1983 до 2004 року[2][3][4]. До доведення твердження теорема була відомою як гіпотеза Вагнера, хоча сам Вагнер[ru] стверджував, що він ніколи не висловлював цієї гіпотези[5].

Слабше твердження для дерев випливає з теореми Краскала про дерева[en]. Твердження 1937 року висловив у вигляді гіпотези угорський математик Ендрю Важоньї[en] і довели 1960 року незалежно Джозеф Краскал[en] і С. Тарковським[6][7].

Твердження ред.

Мінор неорієнтованого графа G — це будь-який граф, який можна отримати з G послідовністю (можливо, порожньою) стягування ребер і видалення ребер і вершин графа G. Відношення мінорності утворює частковий порядок на множині всіх різних скінченних неорієнтованих графів, оскільки це відношення задовольняє трьом аксіомам часткового порядку — відношення рефлексивне (будь-який граф є мінором себе), транзитивне (мінор мінора графа G сам є мінором графа G) і антисиметричне (якщо два графи G і H є мінорами один одного, вони повинні бути ізоморфними). Однак, якщо графи ізоморфні, вони, проте, можуть вважатися різними об'єктами, тоді впорядкування за мінорами утворює передпорядок, відношення, яке є рефлексивним і транзитивним, але не обов'язково антисиметричним[1].

Кажуть, що передпорядок утворює цілком квазівпорядковане відношення[en], якщо він не містить ні нескінченно спадного ланцюга, ні нескінченного антиланцюга[8]. Наприклад, звичайне відношення невід'ємних цілих чисел цілком квазівпорядковане, але той самий порядок на множині всіх цілих чисел таким не буде, оскільки містить нескінченний спадний ланцюг 0, -1, -2, -3…

Теорема Робертсона — Сеймура стверджує, що скінченні неорієнтовані графи і мінори графів (як відношення) мають цілком квазівпорядкованість. Очевидно, що відношення мінорності не містить будь-якого нескінченного спадного ланцюга, оскільки будь-яке стягування або видалення зменшує число ребер або вершин графа (невід'ємні цілі числа)[9]. Нетривіальна частина теореми — що немає нескінченних антиланцюгів, тобто нескінченних множин графів, не пов'язаних один з одним відношенням мінорності. Якщо S — множина графів, а M — підмножина S, що містить по одному представницькому графу для кожного класу еквівалентності мінімальних елементів (графи, що належать S, але будь-який їхній власний мінор не належить S), то M утворює антиланцюг. Таким чином, еквівалентним твердженням теореми буде, що для будь-якої нескінченної множини S графів має існувати лише скінченне число неізоморфних мінімальних елементів.

Інше еквівалентне формулювання теореми стверджує, що в будь-якій нескінченній множині S графів має бути пара графів, один з яких є мінором іншого[9]. Зі твердження, що будь-яка нескінченна множина має скінченну кількість мінімальних елементів, випливає це останнє формулювання, оскільки всі графи, що залишилися (немінімальні), утворюють таку пару. З іншого боку, з цього формулювання теореми випливає, що не може бути нескінченних антиланцюгів, оскільки нескінченний антиланцюг не містить елементів, пов'язаних відношенням мінорності.

Опис забороненими мінорами ред.

Кажуть, що сімейство F графів замкнуте відносно операції взяття мінора, якщо будь-який мінор графа з F також належить F. Якщо F замкнуте за мінорами сімейство, нехай S — множина графів, що не належать F (доповнення множини F). Відповідно до теореми Робертсона — Сеймура існує скінченна множина H мінімальних елементів S. Ці мінімальні елементи утворюють характеризування забороненими графами множини F — графи з F є точно тими графами, які не мають якогось графа з H як мінора[10][11]. Члени множини H називають недопустимими мінорами (або забороненими мінорами) для сімейства F, а саму множину H називають перешкоджальною множиною.

Наприклад, планарні графи замкнуті за утворенням мінора — стягування ребра в планарному графі або видалення ребра або вершини не може зруйнувати планарності. Таким чином, планарні графи мають характеризацію забороненими мінорами, які, в цьому випадку, визначаються теоремою Вагнера — множина H мінорно мінімальних непланарних графів містить рівно два графи, повний граф K5 і повний двочастковий граф K3,3. Планарні ж графи — це точно ті графи, які не мають мінорами елементів із множини {K5, K3,3}.

Існування характеризацій забороненими мінорами для всіх мінорно замкнутих сімейств графів є еквівалентним формулюванням теореми Робертсона — Сеймура. Припустимо, що будь-яке мінорно замкнуте сімейство F має скінчену множину H мінімальних заборонених мінорів, і нехай S — будь-яка множна графів. Визначимо F для S як сімейство графів, що не мають мінорів у S. Тоді множина F є мінорно замкнутою і має скінченну множину H мінімальних заборонених мінорів. Нехай C — доповнення F. S є підмножиною C, оскільки S і F не перетинаються. Множина H містить мінімальні графи з C. Візьмемо граф G із H. G не може мати власних мінорів у S, оскільки G є мінімальним у C. Разом з тим, G повинен мати мінор у S, оскільки в іншому випадку G був би елементом F. Таким чином, G є елементом S, що означає, що H є підмножиною S і всі інші графи S мають мінори із множини графів H, так що H є скінченною множиною мінімальних елементів S.

З іншого боку, припустимо, що будь-яка множина графів має скінченну підмножину мінімальних графів і нехай задано замкнуту за мінорами множину F. Ми хочемо знайти множину H графів, таку, що граф міститься в F тоді й лише тоді, коли він не має мінорів із множини H. Нехай E — множина графів, які є мінорами будь-якого графа з F, і нехай H — скінченна множина мінімальних елементів з E. Нехай тепер задано довільний граф G. Нехай G належить F. G не може мати мінорів з H, оскільки G належить F, а H є підмножиною E. Тепер нехай G не належить F. Тоді G не є мінором будь-якого графа з F, оскільки F замкнута за мінорами. Таким чином, G належить E, так що G має мінор з H.

Приклади сімейств, замкнутих за мінорами ред.

Такі множини скінченних графів замкнуті за мінорами, а тому (згідно з теоремою Робертсона — Сеймура) мають характеризування забороненими графами:

Перешкоджальні множини ред.

 
Петерсенове сімейство, перешкоджальна множина для незачепленного вкладення графа

Деякі приклади кінцевих перешкоджальних множин були відомі для деяких класів ще до доведення теореми Робертсона — Сеймура. Наприклад, перешкодою всім лісам є петля (чи, якщо обмежуємося простими графами, цикл із трьома вершинами). Це означає, що граф є лісом тоді й лише тоді, коли жодний його мінор не є петлею (або циклом із трьома вершинами, відповідно). Єдиною перешкодою для множини шляхів є дерево з чотирма вершинами, одна з яких має степінь 3. У цих випадках перешкода складається з єдиного елемента, але в загальному випадку елементів може бути більше. Теорема Вагнера стверджує, що граф планарний тоді й лише тоді, коли він не містить ні K5, ні K3,3 як мінор. Іншими словами, множина {K5, K3,3} є перешкоджальною множиною для всіх планарних графів, і вона є мінімальною перешкоджальною множиною. Подібна теорема стверджує, що K4 і K2,3 є забороненими мінорами для множини зовніпланарних графів.

Хоча теорема Робертсона — Сеймура поширює ці результати на довільні замкнуті за мінорами сімейства графів, вона не підміняє цих результатів, оскільки не дає явного опису перешкоджальної множини для будь-якої родини. Наприклад, теорема вказує, що множина тороїдальних графів має скінченну перешкоджальну множину, але не дає жодної такої множини. Повний набір заборонених мінорів для тороїдальних графів залишається невідомим і містить принаймні 16 000 графів[13].

Розпізнавання за поліноміальний час ред.

Теорема Робертсона — Сеймура має важливий наслідок у теорії обчислювальної складності, оскільки Робертсон і Сеймур довели, що для кожного фіксованого графа G існує алгоритм поліноміального часу для перевірки, чи має більший граф G як мінор. Час роботи цього алгоритму виражається кубічним многочленом від розміру більшого графа (хоча в цьому многочлені є сталий множник, що залежить надполіноміально від розміру G), і цей час покращили до квадратичного Каварабаяші, Кобаяші і Рід[14]. Отже, для будь-якого замкнутого за мінорами сімейства F існує алгоритм із поліноміальним часом роботи, який перевіряє, чи належить граф сімейству F — просто для всіх заборонених мінорів для F перевіряємо, чи не містить заданий граф цього забороненого мінора[15][16][17].

Однак, щоб скористатися цим методом, необхідно мати перешкоджальну скінченну множину, а теорема її не дає. Теорема показує, що така множина існує, і, якщо така множина відома, задача стає поліноміальною. На практиці ж алгоритм можна застосувати, тільки коли ми маємо множину. Як наслідок, теорема показує, що задачу можна розв'язати за поліноміальний час, але не наводить конкретного алгоритму поліноміального часу. Таке доведення поліноміальності неконструктивне[18][19]. У багатьох конкретних випадках перевірку, що граф належить даному замкнутому за мінорами сімейству, можна здійснити ефективніше. Наприклад, планарність графа можна перевірити за лінійний час.

Фіксовано-параметрична розв'язність ред.

Той самий метод можна застосовувати для інваріантів графа з властивістю, що для будь-якого k сімейство графів, для яких інваріант не перевищує k, мінорно замкнуте. Наприклад, згідно з цим результатом, деревна ширина, гілкова ширина, шляхова ширина, вершинне покриття і мінімальний рід вкладення всі підлягають такому підходу і для будь-якого фіксованого k існує алгоритм поліноміального часу для перевірки, що даний інваріант не перевищує k, а експонента в часі роботи алгоритму від k не залежить. Задачі з поліноміальним часом розв'язування для будь-якого фіксованого k і експонентою в часі роботи, яка від k не залежить, відомі як фіксовано-параметрично розв'язні[en].

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

Кінцева форма теореми про мінори графа ред.

Фрідман, Робертсон і Сеймур[20] показали, що така теорема, недовідна в різних формальних системах, строгіших, ніж арифметика Пеано, але довідна в системах, істотно слабших, ніж теорія множин Цермело — Френкеля, демонструє феномен незалежності:

Теорема: Для будь-якого додатного цілого n існує ціле m, таке, що якщо G1, …, Gm є послідовністю скінченних неорієнтованих графів, де кожен граф Gi має розмір, що не перевершує n+i, то Gj ≤ Gk для деякого j < k.

(Тут розмір графа — це загальне число його вершин, а ≤ означає впорядкування за мінорами.)

Див. також ред.

Примітки ред.

  1. ↑ а б Bienstock, Langston, 1995.
  2. ↑ Robertson, Seymour, 1983.
  3. ↑ Robertson, Seymour, 2004.
  4. ↑ Diestel, 2005, с. 333.
  5. ↑ Diestel, 2005, с. 355.
  6. ↑ Diestel, 2005, с. 335–336.
  7. ↑ Lovász, 2005, с. 78–79, Section 3.3.
  8. ↑ Diestel, 2005, с. 334.
  9. ↑ а б Lovász, 2005, с. 78.
  10. ↑ Bienstock, Langston, 1995, с. Corollary 2.1.1.
  11. ↑ Lovász, 2005, с. 78, Theorem 4.
  12. ↑ а б Lovász, 2005, с. 76–77.
  13. ↑ Chambers, 2002.
  14. ↑ Kawarabayashi, Kobayashi, Reed, 2012.
  15. ↑ Robertson, Seymour, 1995.
  16. ↑ Bienstock, Langston, 1995, с. Th. 2.1.4, C. 2.1.5.
  17. ↑ Lovász, 2005, с. 83, Theorem 11.
  18. ↑ Fellows, Langston, 1988.
  19. ↑ Bienstock, Langston, 1995, с. Section 6.
  20. ↑ Friedman, Robertson, Seymour, 1987.

Література ред.

  • Daniel Bienstock, Michael A. Langston. Network Models. — 1995. — Т. 7. — С. 481—502. — (Handbooks in Operations Research and Management Science) — DOI:10.1016/S0927-0507(05)80125-2.
  • J. Chambers. Hunting for torus obstructions. — Department of Computer Science, University of Victoria, 2002. — (M.Sc. thesis)
  • Reinhard Diestel. Graph Theory. — Electronic Edition 2005. — Springer, 2005. — С. 326—367.
  • 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.
  • Harvey Friedman, Neil Robertson, Paul Seymour. Logic and Combinatorics / S. Simpson. — American Mathematical Society, 1987. — Т. 65. — С. 229—261. — (Contemporary Mathematics)
  • 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.
  • László Lovász. Graph Minor Theory // Bulletin of the American Mathematical Society (New Series). — 2005. — Т. 43, вип. 1. — С. 75—86. — DOI:10.1090/S0273-0979-05-01088-8.
  • 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 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 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..

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Теорема_Робертсона_—_Сеймура&oldid=41941419