Теорема Робертсона — Сеймура (також звана теоремою про мінори графа) стверджує, що будь-яке сімейство графів, замкнуте відносно операцій видалення і стягування ребер, можна визначити скінченним набором заборонених графів.
Наприклад, множина планарних графів замкнута за операціями видалення і стягування ребер; забороненими графами в цьому випадку є повний граф K5 і повний двочастковий граф K3,3. Останнє твердження називається теоремою Вагнера і тісно пов'язане з теоремою Понтрягіна — Куратовського.
Теорема широко відома елементарністю формулювання за відсутності простого доведення. Вона носить ім'я [en] і [en], які довели її в серії з двадцяти статей загальним обсягом 500 сторінок, що вийшли від 1983 до 2004 року. До доведення твердження теорема була відомою як гіпотеза Вагнера, хоча сам [ru] стверджував, що він ніколи не висловлював цієї гіпотези.
Слабше твердження для дерев випливає з [en]. Твердження 1937 року висловив у вигляді гіпотези угорський математик [en] і довели 1960 року незалежно [en] і С. Тарковським.
Твердження
Мінор неорієнтованого графа G — це будь-який граф, який можна отримати з G послідовністю (можливо, порожньою) стягування ребер і видалення ребер і вершин графа G. Відношення мінорності утворює частковий порядок на множині всіх різних скінченних неорієнтованих графів, оскільки це відношення задовольняє трьом аксіомам часткового порядку — відношення рефлексивне (будь-який граф є мінором себе), транзитивне (мінор мінора графа G сам є мінором графа G) і антисиметричне (якщо два графи G і H є мінорами один одного, вони повинні бути ізоморфними). Однак, якщо графи ізоморфні, вони, проте, можуть вважатися різними об'єктами, тоді впорядкування за мінорами утворює передпорядок, відношення, яке є рефлексивним і транзитивним, але не обов'язково антисиметричним.
Кажуть, що передпорядок утворює [en], якщо він не містить ні нескінченно спадного ланцюга, ні нескінченного антиланцюга. Наприклад, звичайне відношення невід'ємних цілих чисел цілком квазівпорядковане, але той самий порядок на множині всіх цілих чисел таким не буде, оскільки містить нескінченний спадний ланцюг 0, -1, -2, -3…
Теорема Робертсона — Сеймура стверджує, що скінченні неорієнтовані графи і мінори графів (як відношення) мають цілком квазівпорядкованість. Очевидно, що відношення мінорності не містить будь-якого нескінченного спадного ланцюга, оскільки будь-яке стягування або видалення зменшує число ребер або вершин графа (невід'ємні цілі числа). Нетривіальна частина теореми — що немає нескінченних антиланцюгів, тобто нескінченних множин графів, не пов'язаних один з одним відношенням мінорності. Якщо S — множина графів, а M — підмножина S, що містить по одному представницькому графу для кожного класу еквівалентності мінімальних елементів (графи, що належать S, але будь-який їхній власний мінор не належить S), то M утворює антиланцюг. Таким чином, еквівалентним твердженням теореми буде, що для будь-якої нескінченної множини S графів має існувати лише скінченне число неізоморфних мінімальних елементів.
Інше еквівалентне формулювання теореми стверджує, що в будь-якій нескінченній множині S графів має бути пара графів, один з яких є мінором іншого. Зі твердження, що будь-яка нескінченна множина має скінченну кількість мінімальних елементів, випливає це останнє формулювання, оскільки всі графи, що залишилися (немінімальні), утворюють таку пару. З іншого боку, з цього формулювання теореми випливає, що не може бути нескінченних антиланцюгів, оскільки нескінченний антиланцюг не містить елементів, пов'язаних відношенням мінорності.
Опис забороненими мінорами
Кажуть, що сімейство F графів замкнуте відносно операції взяття мінора, якщо будь-який мінор графа з F також належить F. Якщо F замкнуте за мінорами сімейство, нехай S — множина графів, що не належать F (доповнення множини F). Відповідно до теореми Робертсона — Сеймура існує скінченна множина H мінімальних елементів S. Ці мінімальні елементи утворюють характеризування забороненими графами множини F — графи з F є точно тими графами, які не мають якогось графа з H як мінора. Члени множини 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 графів.
Розпізнавання за поліноміальний час
Теорема Робертсона — Сеймура має важливий наслідок у теорії обчислювальної складності, оскільки Робертсон і Сеймур довели, що для кожного фіксованого графа G існує алгоритм поліноміального часу для перевірки, чи має більший граф G як мінор. Час роботи цього алгоритму виражається кубічним многочленом від розміру більшого графа (хоча в цьому многочлені є сталий множник, що залежить надполіноміально від розміру G), і цей час покращили до квадратичного Каварабаяші, Кобаяші і Рід. Отже, для будь-якого замкнутого за мінорами сімейства F існує алгоритм із поліноміальним часом роботи, який перевіряє, чи належить граф сімейству F — просто для всіх заборонених мінорів для F перевіряємо, чи не містить заданий граф цього забороненого мінора.
Однак, щоб скористатися цим методом, необхідно мати перешкоджальну скінченну множину, а теорема її не дає. Теорема показує, що така множина існує, і, якщо така множина відома, задача стає поліноміальною. На практиці ж алгоритм можна застосувати, тільки коли ми маємо множину. Як наслідок, теорема показує, що задачу можна розв'язати за поліноміальний час, але не наводить конкретного алгоритму поліноміального часу. Таке доведення поліноміальності неконструктивне. У багатьох конкретних випадках перевірку, що граф належить даному замкнутому за мінорами сімейству, можна здійснити ефективніше. Наприклад, планарність графа можна перевірити за лінійний час.
Фіксовано-параметрична розв'язність
Той самий метод можна застосовувати для інваріантів графа з властивістю, що для будь-якого k сімейство графів, для яких інваріант не перевищує k, мінорно замкнуте. Наприклад, згідно з цим результатом, деревна ширина, , шляхова ширина, вершинне покриття і мінімальний рід вкладення всі підлягають такому підходу і для будь-якого фіксованого k існує алгоритм поліноміального часу для перевірки, що даний інваріант не перевищує k, а експонента в часі роботи алгоритму від k не залежить. Задачі з поліноміальним часом розв'язування для будь-якого фіксованого k і експонентою в часі роботи, яка від k не залежить, відомі як [en].
Однак цей метод не дає прямо фіксовано-параметрично розв'язного алгоритму для обчислення значення параметра для даного графа за невідомого k, зважаючи на труднощі знаходження множини заборонених мінорів. Крім того, виникнення величезних сталих множників робить алгоритм мало придатним на практиці. Таким чином, розробка явних фіксовано-параметрично розв'язних алгоритмів для цих задач з поліпшенням залежності від k залишається важливим напрямком досліджень.
Кінцева форма теореми про мінори графа
Фрідман, Робертсон і Сеймур показали, що така теорема, недовідна в різних формальних системах, строгіших, ніж арифметика Пеано, але довідна в системах, істотно слабших, ніж теорія множин Цермело — Френкеля, демонструє феномен незалежності:
- Теорема: Для будь-якого додатного цілого n існує ціле m, таке, що якщо G1, …, Gm є послідовністю скінченних неорієнтованих графів, де кожен граф Gi має розмір, що не перевершує n+i, то Gj ≤ Gk для деякого j < k.
(Тут розмір графа — це загальне число його вершин, а ≤ означає впорядкування за мінорами.)
Див. також
Примітки
- Bienstock, Langston, 1995.
- Robertson, Seymour, 1983.
- Robertson, Seymour, 2004.
- Diestel, 2005, с. 333.
- Diestel, 2005, с. 355.
- Diestel, 2005, с. 335—336.
- Lovász, 2005, с. 78–79, Section 3.3.
- Diestel, 2005, с. 334.
- Lovász, 2005, с. 78.
- Bienstock, Langston, 1995, с. Corollary 2.1.1.
- Lovász, 2005, с. 78, Theorem 4.
- Lovász, 2005, с. 76—77.
- Chambers, 2002.
- Kawarabayashi, Kobayashi, Reed, 2012.
- Robertson, Seymour, 1995.
- Bienstock, Langston, 1995, с. Th. 2.1.4, C. 2.1.5.
- Lovász, 2005, с. 83, Theorem 11.
- Fellows, Langston, 1988.
- Bienstock, Langston, 1995, с. Section 6.
- Friedman, Robertson, Seymour, 1987.
Література
- Daniel Bienstock, Michael A. Langston. Network Models. — 1995. — Т. 7. — С. 481—502. — (Handbooks in Operations Research and Management Science) — DOI:
- 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 // . — 1988. — Т. 35, вип. 3. — С. 727—739. — DOI: .
- 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: .
- László Lovász. Graph Minor Theory // Bulletin of the American Mathematical Society (New Series). — 2005. — Т. 43, вип. 1. — С. 75—86. — DOI: .
- Neil Robertson, Paul Seymour. Graph Minors. I. Excluding a forest // Journal of Combinatorial Theory, Series B. — 1983. — Т. 35, вип. 1. — С. 39—61. — DOI: ..
- Neil Robertson, Paul Seymour. Graph Minors. XIII. The disjoint paths problem // Journal of Combinatorial Theory, Series B. — 1995. — Т. 63, вип. 1. — С. 65—110. — DOI: ..
- Neil Robertson, Paul Seymour. Graph Minors. XX. Wagner's conjecture // Journal of Combinatorial Theory, Series B. — 2004. — Т. 92, вип. 2. — С. 325—357. — DOI: ..
Посилання
- Weisstein, Eric W. Теорема Робертсона — Сеймура(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teorema Robertsona Sejmura takozh zvana teoremoyu pro minori grafa stverdzhuye sho bud yake simejstvo grafiv zamknute vidnosno operacij vidalennya i styaguvannya reber mozhna viznachiti skinchennim naborom zaboronenih grafiv Napriklad mnozhina planarnih grafiv zamknuta za operaciyami vidalennya i styaguvannya reber zaboronenimi grafami v comu vipadku ye povnij graf K5 i povnij dvochastkovij graf K3 3 Ostannye tverdzhennya nazivayetsya teoremoyu Vagnera i tisno pov yazane z teoremoyu Pontryagina Kuratovskogo Teorema shiroko vidoma elementarnistyu formulyuvannya za vidsutnosti prostogo dovedennya Vona nosit im ya en i en yaki doveli yiyi v seriyi z dvadcyati statej zagalnim obsyagom 500 storinok sho vijshli vid 1983 do 2004 roku Do dovedennya tverdzhennya teorema bula vidomoyu yak gipoteza Vagnera hocha sam ru stverdzhuvav sho vin nikoli ne vislovlyuvav ciyeyi gipotezi Slabshe tverdzhennya dlya derev viplivaye z en Tverdzhennya 1937 roku visloviv u viglyadi gipotezi ugorskij matematik en i doveli 1960 roku nezalezhno en i S Tarkovskim TverdzhennyaMinor neoriyentovanogo grafa G ce bud yakij graf yakij mozhna otrimati z G poslidovnistyu mozhlivo porozhnoyu styaguvannya reber i vidalennya reber i vershin grafa G Vidnoshennya minornosti utvoryuye chastkovij poryadok na mnozhini vsih riznih skinchennih neoriyentovanih grafiv oskilki ce vidnoshennya zadovolnyaye trom aksiomam chastkovogo poryadku vidnoshennya refleksivne bud yakij graf ye minorom sebe tranzitivne minor minora grafa G sam ye minorom grafa G i antisimetrichne yaksho dva grafi G i H ye minorami odin odnogo voni povinni buti izomorfnimi Odnak yaksho grafi izomorfni voni prote mozhut vvazhatisya riznimi ob yektami todi vporyadkuvannya za minorami utvoryuye peredporyadok vidnoshennya yake ye refleksivnim i tranzitivnim ale ne obov yazkovo antisimetrichnim Kazhut sho peredporyadok utvoryuye en yaksho vin ne mistit ni neskinchenno spadnogo lancyuga ni neskinchennogo antilancyuga Napriklad zvichajne vidnoshennya nevid yemnih cilih chisel cilkom kvazivporyadkovane ale toj samij poryadok na mnozhini vsih cilih chisel takim ne bude oskilki mistit neskinchennij spadnij lancyug 0 1 2 3 Teorema Robertsona Sejmura stverdzhuye sho skinchenni neoriyentovani grafi i minori grafiv yak vidnoshennya mayut cilkom kvazivporyadkovanist Ochevidno sho vidnoshennya minornosti ne mistit bud yakogo neskinchennogo spadnogo lancyuga oskilki bud yake styaguvannya abo vidalennya zmenshuye chislo reber abo vershin grafa nevid yemni cili chisla Netrivialna chastina teoremi sho nemaye neskinchennih antilancyugiv tobto neskinchennih mnozhin grafiv ne pov yazanih odin z odnim vidnoshennyam minornosti Yaksho S mnozhina grafiv a M pidmnozhina S sho mistit po odnomu predstavnickomu grafu dlya kozhnogo klasu ekvivalentnosti minimalnih elementiv grafi sho nalezhat S ale bud yakij yihnij vlasnij minor ne nalezhit S to M utvoryuye antilancyug Takim chinom ekvivalentnim tverdzhennyam teoremi bude sho dlya bud yakoyi neskinchennoyi mnozhini S grafiv maye isnuvati lishe skinchenne chislo neizomorfnih minimalnih elementiv Inshe ekvivalentne formulyuvannya teoremi stverdzhuye sho v bud yakij neskinchennij mnozhini S grafiv maye buti para grafiv odin z yakih ye minorom inshogo Zi tverdzhennya sho bud yaka neskinchenna mnozhina maye skinchennu kilkist minimalnih elementiv viplivaye ce ostannye formulyuvannya oskilki vsi grafi sho zalishilisya neminimalni utvoryuyut taku paru Z inshogo boku z cogo formulyuvannya teoremi viplivaye sho ne mozhe buti neskinchennih antilancyugiv oskilki neskinchennij antilancyug ne mistit elementiv pov yazanih vidnoshennyam minornosti Opis zaboronenimi minoramiKazhut sho simejstvo F grafiv zamknute vidnosno operaciyi vzyattya minora yaksho bud yakij minor grafa z F takozh nalezhit F Yaksho F zamknute za minorami simejstvo nehaj S mnozhina grafiv sho ne nalezhat F dopovnennya mnozhini F Vidpovidno do teoremi Robertsona Sejmura isnuye skinchenna mnozhina H minimalnih elementiv S Ci minimalni elementi utvoryuyut harakterizuvannya zaboronenimi grafami mnozhini F grafi z F ye tochno timi grafami yaki ne mayut yakogos grafa z H yak minora Chleni mnozhini H nazivayut nedopustimimi minorami abo zaboronenimi minorami dlya simejstva F a samu mnozhinu H nazivayut pereshkodzhalnoyu mnozhinoyu Napriklad planarni grafi zamknuti za utvorennyam minora styaguvannya rebra v planarnomu grafi abo vidalennya rebra abo vershini ne mozhe zrujnuvati planarnosti Takim chinom planarni grafi mayut harakterizaciyu zaboronenimi minorami yaki v comu vipadku viznachayutsya teoremoyu Vagnera mnozhina H minorno minimalnih neplanarnih grafiv mistit rivno dva grafi povnij graf K5 i povnij dvochastkovij graf K3 3 Planarni zh grafi ce tochno ti grafi yaki ne mayut minorami elementiv iz mnozhini K5 K3 3 Isnuvannya harakterizacij zaboronenimi minorami dlya vsih minorno zamknutih simejstv grafiv ye ekvivalentnim formulyuvannyam teoremi Robertsona Sejmura Pripustimo sho bud yake minorno zamknute simejstvo F maye skinchenu mnozhinu H minimalnih zaboronenih minoriv i nehaj S bud yaka mnozhna grafiv Viznachimo F dlya S yak simejstvo grafiv sho ne mayut minoriv u S Todi mnozhina F ye minorno zamknutoyu i maye skinchennu mnozhinu H minimalnih zaboronenih minoriv Nehaj C dopovnennya F S ye pidmnozhinoyu C oskilki S i F ne peretinayutsya Mnozhina H mistit minimalni grafi z C Vizmemo graf G iz H G ne mozhe mati vlasnih minoriv u S oskilki G ye minimalnim u C Razom z tim G povinen mati minor u S oskilki v inshomu vipadku G buv bi elementom F Takim chinom G ye elementom S sho oznachaye sho H ye pidmnozhinoyu S i vsi inshi grafi S mayut minori iz mnozhini grafiv H tak sho H ye skinchennoyu mnozhinoyu minimalnih elementiv S Z inshogo boku pripustimo sho bud yaka mnozhina grafiv maye skinchennu pidmnozhinu minimalnih grafiv i nehaj zadano zamknutu za minorami mnozhinu F Mi hochemo znajti mnozhinu H grafiv taku sho graf mistitsya v F todi j lishe todi koli vin ne maye minoriv iz mnozhini H Nehaj E mnozhina grafiv yaki ye minorami bud yakogo grafa z F i nehaj H skinchenna mnozhina minimalnih elementiv z E Nehaj teper zadano dovilnij graf G Nehaj G nalezhit F G ne mozhe mati minoriv z H oskilki G nalezhit F a H ye pidmnozhinoyu E Teper nehaj G ne nalezhit F Todi G ne ye minorom bud yakogo grafa z F oskilki F zamknuta za minorami Takim chinom G nalezhit E tak sho G maye minor z H Prikladi simejstv zamknutih za minoramiTaki mnozhini skinchennih grafiv zamknuti za minorami a tomu zgidno z teoremoyu Robertsona Sejmura mayut harakterizuvannya zaboronenimi grafami lisi linijni lisi diz yunktni ob yednannya shlyahiv psevdolisi ta kaktusi planarni grafi zovniplanarni grafi verhivkovi grafi utvoreni dodavannyam odniyeyi vershini do planarnogo grafa toroyidalni grafi ta grafi yaki mozhna vklasti v bud yakij fiksovanij dvovimirnij mnogovid grafi sho dopuskayut nezacheplene vkladennya v evklidiv trivimirnij prostir i grafi sho dopuskayut vkladennya bez vuzliv v evklidiv trivimirnij prostir grafi z obmezhenoyu za rozmirom deyakoyu fiksovanoyu staloyu grafi z invariantom Kolen de Verdyera obmezhenim deyakoyu fiksovanoyu staloyu grafi z derevnoyu shirinoyu shlyahovoyu shirinoyu abo shirinoyu galuzhennya obmezhenoyu deyakoyu fiksovanoyu staloyu Pereshkodzhalni mnozhiniPetersenove simejstvo pereshkodzhalna mnozhina dlya nezacheplennogo vkladennya grafa Deyaki prikladi kincevih pereshkodzhalnih mnozhin buli vidomi dlya deyakih klasiv she do dovedennya teoremi Robertsona Sejmura Napriklad pereshkodoyu vsim lisam ye petlya chi yaksho obmezhuyemosya prostimi grafami cikl iz troma vershinami Ce oznachaye sho graf ye lisom todi j lishe todi koli zhodnij jogo minor ne ye petleyu abo ciklom iz troma vershinami vidpovidno Yedinoyu pereshkodoyu dlya mnozhini shlyahiv ye derevo z chotirma vershinami odna z yakih maye stepin 3 U cih vipadkah pereshkoda skladayetsya z yedinogo elementa ale v zagalnomu vipadku elementiv mozhe buti bilshe Teorema Vagnera stverdzhuye sho graf planarnij todi j lishe todi koli vin ne mistit ni K5 ni K3 3 yak minor Inshimi slovami mnozhina K5 K3 3 ye pereshkodzhalnoyu mnozhinoyu dlya vsih planarnih grafiv i vona ye minimalnoyu pereshkodzhalnoyu mnozhinoyu Podibna teorema stverdzhuye sho K4 i K2 3 ye zaboronenimi minorami dlya mnozhini zovniplanarnih grafiv Hocha teorema Robertsona Sejmura poshiryuye ci rezultati na dovilni zamknuti za minorami simejstva grafiv vona ne pidminyaye cih rezultativ oskilki ne daye yavnogo opisu pereshkodzhalnoyi mnozhini dlya bud yakoyi rodini Napriklad teorema vkazuye sho mnozhina toroyidalnih grafiv maye skinchennu pereshkodzhalnu mnozhinu ale ne daye zhodnoyi takoyi mnozhini Povnij nabir zaboronenih minoriv dlya toroyidalnih grafiv zalishayetsya nevidomim i mistit prinajmni 16 000 grafiv Rozpiznavannya za polinomialnij chasTeorema Robertsona Sejmura maye vazhlivij naslidok u teoriyi obchislyuvalnoyi skladnosti oskilki Robertson i Sejmur doveli sho dlya kozhnogo fiksovanogo grafa G isnuye algoritm polinomialnogo chasu dlya perevirki chi maye bilshij graf G yak minor Chas roboti cogo algoritmu virazhayetsya kubichnim mnogochlenom vid rozmiru bilshogo grafa hocha v comu mnogochleni ye stalij mnozhnik sho zalezhit nadpolinomialno vid rozmiru G i cej chas pokrashili do kvadratichnogo Kavarabayashi Kobayashi i Rid Otzhe dlya bud yakogo zamknutogo za minorami simejstva F isnuye algoritm iz polinomialnim chasom roboti yakij pereviryaye chi nalezhit graf simejstvu F prosto dlya vsih zaboronenih minoriv dlya F pereviryayemo chi ne mistit zadanij graf cogo zaboronenogo minora Odnak shob skoristatisya cim metodom neobhidno mati pereshkodzhalnu skinchennu mnozhinu a teorema yiyi ne daye Teorema pokazuye sho taka mnozhina isnuye i yaksho taka mnozhina vidoma zadacha staye polinomialnoyu Na praktici zh algoritm mozhna zastosuvati tilki koli mi mayemo mnozhinu Yak naslidok teorema pokazuye sho zadachu mozhna rozv yazati za polinomialnij chas ale ne navodit konkretnogo algoritmu polinomialnogo chasu Take dovedennya polinomialnosti nekonstruktivne U bagatoh konkretnih vipadkah perevirku sho graf nalezhit danomu zamknutomu za minorami simejstvu mozhna zdijsniti efektivnishe Napriklad planarnist grafa mozhna pereviriti za linijnij chas Fiksovano parametrichna rozv yaznistToj samij metod mozhna zastosovuvati dlya invariantiv grafa z vlastivistyu sho dlya bud yakogo k simejstvo grafiv dlya yakih invariant ne perevishuye k minorno zamknute Napriklad zgidno z cim rezultatom derevna shirina shlyahova shirina vershinne pokrittya i minimalnij rid vkladennya vsi pidlyagayut takomu pidhodu i dlya bud yakogo fiksovanogo k isnuye algoritm polinomialnogo chasu dlya perevirki sho danij invariant ne perevishuye k a eksponenta v chasi roboti algoritmu vid k ne zalezhit Zadachi z polinomialnim chasom rozv yazuvannya dlya bud yakogo fiksovanogo k i eksponentoyu v chasi roboti yaka vid k ne zalezhit vidomi yak en Odnak cej metod ne daye pryamo fiksovano parametrichno rozv yaznogo algoritmu dlya obchislennya znachennya parametra dlya danogo grafa za nevidomogo k zvazhayuchi na trudnoshi znahodzhennya mnozhini zaboronenih minoriv Krim togo viniknennya velicheznih stalih mnozhnikiv robit algoritm malo pridatnim na praktici Takim chinom rozrobka yavnih fiksovano parametrichno rozv yaznih algoritmiv dlya cih zadach z polipshennyam zalezhnosti vid k zalishayetsya vazhlivim napryamkom doslidzhen Kinceva forma teoremi pro minori grafaFridman Robertson i Sejmur pokazali sho taka teorema nedovidna v riznih formalnih sistemah strogishih nizh arifmetika Peano ale dovidna v sistemah istotno slabshih nizh teoriya mnozhin Cermelo Frenkelya demonstruye fenomen nezalezhnosti Teorema Dlya bud yakogo dodatnogo cilogo n isnuye cile m take sho yaksho G1 Gm ye poslidovnistyu skinchennih neoriyentovanih grafiv de kozhen graf Gi maye rozmir sho ne perevershuye n i to Gj Gk dlya deyakogo j lt k Tut rozmir grafa ce zagalne chislo jogo vershin a oznachaye vporyadkuvannya za minorami Div takozhStrukturna teorema grafivPrimitkiBienstock Langston 1995 Robertson Seymour 1983 Robertson Seymour 2004 Diestel 2005 s 333 Diestel 2005 s 355 Diestel 2005 s 335 336 Lovasz 2005 s 78 79 Section 3 3 Diestel 2005 s 334 Lovasz 2005 s 78 Bienstock Langston 1995 s Corollary 2 1 1 Lovasz 2005 s 78 Theorem 4 Lovasz 2005 s 76 77 Chambers 2002 Kawarabayashi Kobayashi Reed 2012 Robertson Seymour 1995 Bienstock Langston 1995 s Th 2 1 4 C 2 1 5 Lovasz 2005 s 83 Theorem 11 Fellows Langston 1988 Bienstock Langston 1995 s Section 6 Friedman Robertson Seymour 1987 LiteraturaDaniel Bienstock Michael A Langston Network Models 1995 T 7 S 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 S 326 367 Michael R Fellows Michael A Langston Nonconstructive tools for proving polynomial time decidability 1988 T 35 vip 3 S 727 739 DOI 10 1145 44483 44491 Harvey Friedman Neil Robertson Paul Seymour Logic and Combinatorics S Simpson American Mathematical Society 1987 T 65 S 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 T 102 vip 2 S 424 435 DOI 10 1016 j jctb 2011 07 004 Laszlo Lovasz Graph Minor Theory Bulletin of the American Mathematical Society New Series 2005 T 43 vip 1 S 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 T 35 vip 1 S 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 T 63 vip 1 S 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 T 92 vip 2 S 325 357 DOI 10 1016 j jctb 2004 08 001 PosilannyaWeisstein Eric W Teorema Robertsona Sejmura angl na sajti Wolfram MathWorld