Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Структурна теорема графів фундаментальний результат у теорії графів Результат встановлює тісний зв язок між теорією міно

Структурна теорема графів

Структурна теорема графів

Структурна теорема графів — фундаментальний результат у теорії графів. Результат встановлює тісний зв'язок між теорією мінорів графів і топологічними вкладеннями. Теорему сформульовано в сімнадцяти статтях серії з 23 статей [en] і [ru]. Доведення теореми дуже довге і заплутане. Каварабаяші і Мохар і Ловаш підготували огляд теореми в доступному для нефахівців вигляді, описавши теорему і її наслідки.

Початки і мотивація теореми

Мінор графу G — це будь-який граф H, ізоморфний графу, який можна отримати з підграфу графу G стягуванням деяких ребер. Якщо G не має графу H мінором, то ми говоримо, що G є H-вільним. Нехай H — фіксований граф. Інтуїтивно, якщо G є великим H-вільним графом, то повинна бути якась «хороша причина» для цього. Структурна теорема графів дає таку «хорошу причину» у формі грубого опису структури графу G. По суті, будь-який H-вільний граф G має один або два структурних дефекти — або G «занадто тонкий», щоб містити H як мінор, або G може бути (майже) топологічно вкладеним у поверхню, яка занадто проста для вкладення мінора H. Перша причина виникає, коли H планарний, а обидві причини виникають у разі непланарності H. Спочатку уточнимо ці поняття.

Деревна ширина

Деревна ширина графу G — це додатне ціле число, яке визначає «тонкість» графу G. Наприклад, зв'язний граф G має деревну ширину одиниця тоді й лише тоді, коли він є деревом, і G має деревну ширину два тоді і тільки тоді, коли він є паралельно-послідовним графом. Інтуїтивно зрозуміло, що великий граф G має малу деревну ширину тоді й лише тоді, коли G має структуру великого дерева, в якому вузли і ребра замінено маленькими графами. Ми дамо точне визначення деревної ширини в підрозділі про суми за кліками. Існує теорема, що якщо H є мінором графу G, то деревна ширина H не перевищує деревної ширини G. Таким чином, «хорошою причиною» для G бути H-вільним є не дуже велика деревна ширина G. Структурна теорема графів має наслідком, що ця причина завжди застосовна в разі планарності H.

Наслідок 1. Для будь-якого планарного графу H існує додатне ціле k, таке, що будь-який H-вільний граф має деревну ширину, меншу від k.

Значення k в наслідку 1, як правило, набагато більше від деревної ширини H (є чудовий виняток, коли H = K4, тобто H дорівнює повному графу з чотирьох вершин, для якого k=3). Це одна з причин, з якої кажуть, що структурна теорема описує «грубу структуру» H-вільних графів.

Вкладення в поверхні

Грубо кажучи, поверхня — це множина точок з локальною топологічною структурою у вигляді диска. Поверхні розпадаються на два нескінченних сімейства — орієнтовні поверхні включають сферу, тор, [en] і т. д. Неорієнтовні поверхні включають дійсну проєктивну площину, пляшку Кляйна і т. д. Граф вкладається в поверхню, якщо його можна намалювати на поверхні у вигляді множини точок (вершин) і дуг (ребер) так, що вони не перетинають і не торкаються одна одну, за винятком випадків, коли вершини і ребра інцидентні або суміжні. Граф планарний, якщо він вкладається у сферу. Якщо граф G вкладається в певну поверхню, то будь-який мінор графу G також вкладається в ту ж поверхню. Таким чином, «хорошою причиною» для графу G бути H-вільним є можливість вкладення графу G у поверхню, в яку H вкласти не можна.

Якщо H не планарний, структурна теорема графів може розглядатися як сильне узагальнення теореми Понтрягіна — Куратовського. Версія цієї теореми, доведена Вагнером, стверджує, що якщо граф G є як K5-вільний, так і K3,3-вільним, то G планарний. Ця теорема дає «хорошу причину» для графу G не містити мінорів K5 або K3,3. Конкретніше, G вкладається в сферу, тоді як ні K5, ні K3,3 в сферу вкласти не можна. Поняття «хороша причина» недостатньо для структурної теореми графів. Потрібні ще два поняття — сума за клікою і вихори.

Сума за клікою

Докладніше: Сума за клікою

Кліка в графі G — це будь-яка множина вершин, які попарно суміжні одна з одною в G. Для невід'ємного цілого k k-клікова сума двох графів G і K — це будь-який граф, отриманий вибором у графах G і K клік розміром m ≤ k для деякого невід'ємного m, ототожненням цих двох клік в одну кліку (розміром m) і видаленням деякого (можливо, нульового) числа ребер у цій новій кліці.

Якщо G1, G2, ..., Gn — список графів, можна отримати новий граф об'єднанням графів зі списку за допомогою сум за k-кліками. Тобто створюємо k-клікову суму графів G1 і G2, потім створюємо k-клікову суму графу G3 з попереднім результуючим графом і т. д. Граф має деревну ширину, яка не перевищує k, якщо його можна отримати як k-клікову суму деякого списку графів, у якому кожен граф має максимум k + 1 вершин.

Наслідок 1 показує, що k-клікові суми малих графів описують грубу структуру H-вільних графів у разі планарності H. Якщо H непланарний, ми змушені розглядати також k-клікові суми графів, кожен з яких вкладається в поверхню. Наступний приклад з H = K5 ілюструє цей момент. Граф K5 можна вкласти в будь-яку поверхню, за винятком сфери. Однак існують K5-вільні графи, які далеко не планарні. Зокрема, 3-клікова сума будь-якого списку планарних графів дає K5-вільний граф. Вагнер визначив точну структуру K5-вільних графів як частину групи результатів, відомих під назвою теорема Вагнера:

Теорема 2. Якщо G вільний від K5, то G можна отримати як 3-клікові суми списку планарних графів і копій деякого специфічного непланарного графу з 8 вершинами.

Зауважимо, що Теорема 2 є точною структурною теоремою, оскільки точно визначає структуру K5-вільних графів. Такі результати рідкісні в теорії графів. Структурна теорема графів не є точною в тому сенсі, що для більшості графів H структурний опис H-вільних графів включає деякі графи, які не є H-вільними.

Вихори (грубий опис)

Є спокуса припустити, що виконується аналог теореми 2 для графів H, відмінних від K5. Можливо, це звучало б так: Для будь-якого непланарного графу H існує додатне число k, таке, що кожен H-вільний граф можна отримати у вигляді k-клікової суми списку графів, кожен з яких або має не більше k вершин, або вкладається в деяку поверхню, в яку H вкласти не можна. Це твердження занадто просте, щоб бути правдою. Ми повинні дозволити кожному вкладеному графу G i «шахраювати» двома обмеженими способами. По-перше, ми маємо дозволити в обмеженому числі місць на поверхні додавання деяких нових вершин і ребер, яким дозволено перетинатися в деякій обмеженій складності. Такі місця називаються вихорами. «Складність» вихору обмежена параметром, званим його глибиною, яка тісно пов'язана з шляховою шириною графу. По-друге, ми маємо дозволити додавати обмежене число нових вершин для вкладених графів з вихорами.

Вихори (точне визначення)

Грань вкладеного графу — це відкрита 2-комірка поверхні, яка не перетинається з графом, але межі якої є об'єднанням деяких ребер вкладеного графу. Нехай F — грань вкладеного графу G і нехай v0,v1, …, vn -1,vn = v0 — вершини, що лежать на межі F (у порядку циклу). Цикловий інтервал для F — це набір вершин вигляду {va,va +1, …, va + s}, де a і s — цілі числа, і де індекс береться за модулем n. Нехай Λ — це скінченний список циклових інтервалів для F. Побудуємо новий граф таким чином. Для кожного циклового інтервалу L з Λ додаємо нову вершину vL, з'єднану з деяким числом (можливо, нульовим) вершин з L. Для кожної пари {L, M} інтервалів у Λ ми можемо додати ребро, що з'єднує vL з vM, якщо L і M мають непорожній перетин. Кажуть, що утворений граф отримано з графу G доданням вихору глибини, що не перевищує k (до межі F), якщо ніяка вершина на межі F не з'являється в більш ніж k інтервалах з Λ.

Твердження структурної теореми графів

Структурна теорема графів. Для будь-якого графу H існує додатне ціле k, таке, що будь-який H-вільний граф можна отримати таким чином:

  1. починаємо зі списку графів, де кожен граф зі списку вкладений у поверхню, в яку H вкласти не можна;
  2. до кожного вкладеного графу зі списку додаємо не більше k вихорів і кожен вихор має глибину, яка не перевищує k;
  3. до кожного отриманого графу додаємо не більше k нових вершин (званих верхівками) і додаємо деяке число ребер, які мають, принаймні, один кінець у верхівці.
  4. нарешті, з'єднуємо за допомогою k-клікових сум отриманий список графів.

Зауважимо, що кроки 1 і 2 дають порожні графи, якщо граф H планарний, але обмежене число вершин, що додаються на етапі 3, робить твердження сумісним зі Наслідком 1.

Уточнення

Посилені версії структурної теореми графів можливі залежно від множини H заборонених мінорів. Наприклад, якщо один з графів у H планарний, то будь-який H-вільний граф має деревну декомпозицію обмеженої ширини. Еквівалентно його можна подати як суму за клікою графів сталого розміру. Якщо один з графів H можна намалювати в площині з одним схрещенням, то H-мінорно-вільні графи допускають розкладання на клікову суму графів сталого розміру і графів з обмеженим родом (не використовуючи вихори)). Відомі також різні посилення, якщо один з графів H є верхівковим графом.

Див. також

Примітки

  1. Kawarabayashi, Mohar, 2007.
  2. Lovász, 2006.
  3. Wagner, 1937.
  4. Robertson, Seymour та 1986 V.
  5. Robertson, Seymour, 1993.
  6. Demaine, Hajiaghayi, Thilikos, 2002.
  7. Demaine, Hajiaghayi, Kawarabayashi, 2009.

Література

  • Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi. [1] — Springer-Verlag, 2009. — Т. 5555. — С. 316–327. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-02927-1_27. з джерела 2 квітня 2013.
  • Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos. Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002). — Springer-Verlag, 2002. — Т. 2462. — С. 67–80. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-45753-4_8..
  • Ken-ichi Kawarabayashi, Bojan Mohar. Some recent progress and applications in graph minor theory // . — 2007. — Т. 23, вип. 1 (17 червня). — С. 1–46. — DOI:10.1007/s00373-006-0684-x..
  • Lovász. Graph minor theory // Bulletin of the American Mathematical Society. — 2006. — Т. 43, вип. 1 (17 червня). — С. 75–86. — DOI:10.1090/S0273-0979-05-01088-8..
  • Neil Robertson, P. D. Seymour. Graph minors. I. Excluding a forest // . — 1983. — Т. 35, вип. 1 (1 січня). — С. 39–61. — (Series B). — DOI:10.1016/0095-8956(83)90079-5..
  • Neil Robertson, P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width // Journal of Algorithms. — 1986. — Т. 7, вип. 3 (1 лютого). — С. 309–322. — DOI:10.1016/0196-6774(86)90023-4..
  • Neil Robertson, P. D. Seymour. Graph minors. III. Planar tree-width // . — 1984. — Т. 36, вип. 1 (1 березня). — С. 49–64. — (Series B). — DOI:10.1016/0095-8956(84)90013-3..
  • Neil Robertson, P. D. Seymour. Graph minors. IV. Tree-width and well-quasi-ordering // . — 1990. — Т. 48, вип. 2 (1 квітня). — С. 227–254. — (Series B). — DOI:10.1016/0095-8956(90)90120-O..
  • Neil Robertson, P. D. Seymour. Graph minors. V. Excluding a planar graph // . — 1986. — Т. 41, вип. 1 (1 травня). — С. 92–114. — (Series B). — DOI:10.1016/0095-8956(86)90030-4..
  • Neil Robertson, P. D. Seymour. Graph minors. VI. Disjoint paths across a disc // . — 1986. — Т. 41, вип. 1 (1 червня). — С. 115–138. — (Series B). — DOI:10.1016/0095-8956(86)90031-6..
  • Neil Robertson, P. D. Seymour. Graph minors. VII. Disjoint paths on a surface // . — 1988. — Т. 45, вип. 2 (1 липня). — С. 212–254. — (Series B). — DOI:10.1016/0095-8956(88)90070-6..
  • Neil Robertson, P. D. Seymour. Graph minors. VIII. A Kuratowski theorem for general surfaces // . — 1990. — Т. 48, вип. 2 (1 серпня). — С. 255–288. — (Series B). — DOI:10.1016/0095-8956(90)90121-F..
  • Neil Robertson, P. D. Seymour. Graph minors. IX. Disjoint crossed paths // . — 1990. — Т. 49, вип. 1 (1 вересня). — С. 40–77. — (Series B). — DOI:10.1016/0095-8956(90)90063-6..
  • Neil Robertson, P. D. Seymour. Graph minors. X. Obstructions to tree-decomposition // . — 1991. — Т. 52, вип. 2 (1 жовтня). — С. 153–190. — (Series B). — DOI:10.1016/0095-8956(91)90061-N..
  • Neil Robertson, P. D. Seymour. Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors / Neil Robertson, Paul Seymour. — American Mathematical Society, 1993. — Т. 147. — С. 669–675. — (Contemporary Mathematics) — DOI:10.1090/conm/147/01206..
  • Neil Robertson, P. D. Seymour. Graph minors. XI. Circuits on a surface // . — 1994. — Т. 60, вип. 1 (1 листопада). — С. 72–106. — (Series B). — DOI:10.1006/jctb.1994.1007..
  • Neil Robertson, P. D. Seymour. Graph minors. XII. Distance on a surface // . — 1995. — Т. 64, вип. 2 (1 грудня). — С. 240–272. — (Series B). — DOI:10.1006/jctb.1995.1034..
  • Neil Robertson, P. D. Seymour. Graph minors. XIII. The disjoint paths problem // . — 1995. — Т. 63, вип. 1 (30 листопада). — С. 65–110. — (Series B). — DOI:10.1006/jctb.1995.1006..
  • Neil Robertson, P. D. Seymour. Graph minors. XIV. Extending an embedding // . — 1995. — Т. 65, вип. 1 (1 листопада). — С. 23–50. — (Series B). — DOI:10.1006/jctb.1995.1042..
  • Neil Robertson, P. D. Seymour. Graph minors. XV. Giant steps // . — 1996. — Т. 68, вип. 1 (1 жовтня). — С. 112–148. — (Series B). — DOI:10.1006/jctb.1996.0059.
  • Neil Robertson, P. D. Seymour. Graph minors. XVI. Excluding a non-planar graph // . — . — Т. 89, вип. 1. — С. 43–76. — (Series B). — DOI:10.1016/S0095-8956(03)00042-X..
  • Neil Robertson, P. D. Seymour. Graph minors. XVII. Taming a vortex // . — . — Т. 77, вип. 1. — С. 162–210. — (Series B). — DOI:10.1006/jctb.1999.1919..
  • Neil Robertson, Paul Seymour. Graph minors. XVIII. Tree-decompositions and well-quasi-ordering // . — . — Т. 89, вип. 1. — С. 77–108. — (Series B). — DOI:10.1016/S0095-8956(03)00067-4..
  • Neil Robertson, P. D. Seymour. Graph minors. XIX. Well-quasi-ordering on a surface // . — 2004. — Т. 90, вип. 2 (1 листопада). — С. 325–385. — (Series B). — DOI:10.1016/j.jctb.2003.08.005..
  • Neil Robertson, P. D. Seymour. Graph minors. XX. Wagner's conjecture // . — 2004. — Т. 92, вип. 2 (1 жовтня). — С. 325–357. — (Series B). — DOI:10.1016/j.jctb.2004.08.001..
  • Neil Robertson, Paul Seymour. Graph minors. XXI. Graphs with unique linkages // . — . — Т. 99, вип. 3. — С. 583–616. — (Series B). — DOI:10.1016/j.jctb.2008.08.003..
  • Neil Robertson, Paul Seymour. Graph minors. XXII. Irrelevant vertices in linkage problems // . — . — Т. 102, вип. 2. — С. 530–563. — (Series B). — DOI:10.1016/j.jctb.2007.12.007..
  • Neil Robertson, Paul Seymour. Graph minors XXIII. Nash-Williams' immersion conjecture // . — . — Т. 100, вип. 2. — С. 181–205. — (Series B). — DOI:10.1016/j.jctb.2009.07.003..
  • Klaus Wagner. Über eine Erweiterung des Satzes von Kuratowski // Deutsche Mathematik. — 1937. — Т. 2 (17 червня). — С. 280–285..

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Strukturna teorema grafiv fundamentalnij rezultat u teoriyi grafiv Rezultat vstanovlyuye tisnij zv yazok mizh teoriyeyu minoriv grafiv i topologichnimi vkladennyami Teoremu sformulovano v simnadcyati stattyah seriyi z 23 statej en i ru Dovedennya teoremi duzhe dovge i zaplutane Kavarabayashi i Mohar i Lovash pidgotuvali oglyad teoremi v dostupnomu dlya nefahivciv viglyadi opisavshi teoremu i yiyi naslidki Pochatki i motivaciya teoremiMinor grafu G ce bud yakij graf H izomorfnij grafu yakij mozhna otrimati z pidgrafu grafu G styaguvannyam deyakih reber Yaksho G ne maye grafu H minorom to mi govorimo sho G ye H vilnim Nehaj H fiksovanij graf Intuyitivno yaksho G ye velikim H vilnim grafom to povinna buti yakas horosha prichina dlya cogo Strukturna teorema grafiv daye taku horoshu prichinu u formi grubogo opisu strukturi grafu G Po suti bud yakij H vilnij graf G maye odin abo dva strukturnih defekti abo G zanadto tonkij shob mistiti H yak minor abo G mozhe buti majzhe topologichno vkladenim u poverhnyu yaka zanadto prosta dlya vkladennya minora H Persha prichina vinikaye koli H planarnij a obidvi prichini vinikayut u razi neplanarnosti H Spochatku utochnimo ci ponyattya Derevna shirina Derevna shirina grafu G ce dodatne cile chislo yake viznachaye tonkist grafu G Napriklad zv yaznij graf G maye derevnu shirinu odinicya todi j lishe todi koli vin ye derevom i G maye derevnu shirinu dva todi i tilki todi koli vin ye paralelno poslidovnim grafom Intuyitivno zrozumilo sho velikij graf G maye malu derevnu shirinu todi j lishe todi koli G maye strukturu velikogo dereva v yakomu vuzli i rebra zamineno malenkimi grafami Mi damo tochne viznachennya derevnoyi shirini v pidrozdili pro sumi za klikami Isnuye teorema sho yaksho H ye minorom grafu G to derevna shirina H ne perevishuye derevnoyi shirini G Takim chinom horoshoyu prichinoyu dlya G buti H vilnim ye ne duzhe velika derevna shirina G Strukturna teorema grafiv maye naslidkom sho cya prichina zavzhdi zastosovna v razi planarnosti H Naslidok 1 Dlya bud yakogo planarnogo grafu H isnuye dodatne cile k take sho bud yakij H vilnij graf maye derevnu shirinu menshu vid k Znachennya k v naslidku 1 yak pravilo nabagato bilshe vid derevnoyi shirini H ye chudovij vinyatok koli H K4 tobto H dorivnyuye povnomu grafu z chotiroh vershin dlya yakogo k 3 Ce odna z prichin z yakoyi kazhut sho strukturna teorema opisuye grubu strukturu H vilnih grafiv Vkladennya v poverhni Grubo kazhuchi poverhnya ce mnozhina tochok z lokalnoyu topologichnoyu strukturoyu u viglyadi diska Poverhni rozpadayutsya na dva neskinchennih simejstva oriyentovni poverhni vklyuchayut sferu tor en i t d Neoriyentovni poverhni vklyuchayut dijsnu proyektivnu ploshinu plyashku Klyajna i t d Graf vkladayetsya v poverhnyu yaksho jogo mozhna namalyuvati na poverhni u viglyadi mnozhini tochok vershin i dug reber tak sho voni ne peretinayut i ne torkayutsya odna odnu za vinyatkom vipadkiv koli vershini i rebra incidentni abo sumizhni Graf planarnij yaksho vin vkladayetsya u sferu Yaksho graf G vkladayetsya v pevnu poverhnyu to bud yakij minor grafu G takozh vkladayetsya v tu zh poverhnyu Takim chinom horoshoyu prichinoyu dlya grafu G buti H vilnim ye mozhlivist vkladennya grafu G u poverhnyu v yaku H vklasti ne mozhna Yaksho H ne planarnij strukturna teorema grafiv mozhe rozglyadatisya yak silne uzagalnennya teoremi Pontryagina Kuratovskogo Versiya ciyeyi teoremi dovedena Vagnerom stverdzhuye sho yaksho graf G ye yak K5 vilnij tak i K3 3 vilnim to G planarnij Cya teorema daye horoshu prichinu dlya grafu G ne mistiti minoriv K5 abo K3 3 Konkretnishe G vkladayetsya v sferu todi yak ni K5 ni K3 3 v sferu vklasti ne mozhna Ponyattya horosha prichina nedostatno dlya strukturnoyi teoremi grafiv Potribni she dva ponyattya suma za klikoyu i vihori Suma za klikoyu Dokladnishe Suma za klikoyu Klika v grafi G ce bud yaka mnozhina vershin yaki poparno sumizhni odna z odnoyu v G Dlya nevid yemnogo cilogo k k klikova suma dvoh grafiv G i K ce bud yakij graf otrimanij viborom u grafah G i K klik rozmirom m k dlya deyakogo nevid yemnogo m ototozhnennyam cih dvoh klik v odnu kliku rozmirom m i vidalennyam deyakogo mozhlivo nulovogo chisla reber u cij novij klici Yaksho G1 G2 Gn spisok grafiv mozhna otrimati novij graf ob yednannyam grafiv zi spisku za dopomogoyu sum za k klikami Tobto stvoryuyemo k klikovu sumu grafiv G1 i G2 potim stvoryuyemo k klikovu sumu grafu G3 z poperednim rezultuyuchim grafom i t d Graf maye derevnu shirinu yaka ne perevishuye k yaksho jogo mozhna otrimati yak k klikovu sumu deyakogo spisku grafiv u yakomu kozhen graf maye maksimum k 1 vershin Naslidok 1 pokazuye sho k klikovi sumi malih grafiv opisuyut grubu strukturu H vilnih grafiv u razi planarnosti H Yaksho H neplanarnij mi zmusheni rozglyadati takozh k klikovi sumi grafiv kozhen z yakih vkladayetsya v poverhnyu Nastupnij priklad z H K5 ilyustruye cej moment Graf K5 mozhna vklasti v bud yaku poverhnyu za vinyatkom sferi Odnak isnuyut K5 vilni grafi yaki daleko ne planarni Zokrema 3 klikova suma bud yakogo spisku planarnih grafiv daye K5 vilnij graf Vagner viznachiv tochnu strukturu K5 vilnih grafiv yak chastinu grupi rezultativ vidomih pid nazvoyu teorema Vagnera Teorema 2 Yaksho G vilnij vid K5 to G mozhna otrimati yak 3 klikovi sumi spisku planarnih grafiv i kopij deyakogo specifichnogo neplanarnogo grafu z 8 vershinami Zauvazhimo sho Teorema 2 ye tochnoyu strukturnoyu teoremoyu oskilki tochno viznachaye strukturu K5 vilnih grafiv Taki rezultati ridkisni v teoriyi grafiv Strukturna teorema grafiv ne ye tochnoyu v tomu sensi sho dlya bilshosti grafiv H strukturnij opis H vilnih grafiv vklyuchaye deyaki grafi yaki ne ye H vilnimi Vihori grubij opis Ye spokusa pripustiti sho vikonuyetsya analog teoremi 2 dlya grafiv H vidminnih vid K5 Mozhlivo ce zvuchalo b tak Dlya bud yakogo neplanarnogo grafu H isnuye dodatne chislo k take sho kozhen H vilnij graf mozhna otrimati u viglyadi k klikovoyi sumi spisku grafiv kozhen z yakih abo maye ne bilshe k vershin abo vkladayetsya v deyaku poverhnyu v yaku H vklasti ne mozhna Ce tverdzhennya zanadto proste shob buti pravdoyu Mi povinni dozvoliti kozhnomu vkladenomu grafu G i shahrayuvati dvoma obmezhenimi sposobami Po pershe mi mayemo dozvoliti v obmezhenomu chisli misc na poverhni dodavannya deyakih novih vershin i reber yakim dozvoleno peretinatisya v deyakij obmezhenij skladnosti Taki miscya nazivayutsya vihorami Skladnist vihoru obmezhena parametrom zvanim jogo glibinoyu yaka tisno pov yazana z shlyahovoyu shirinoyu grafu Po druge mi mayemo dozvoliti dodavati obmezhene chislo novih vershin dlya vkladenih grafiv z vihorami Vihori tochne viznachennya Gran vkladenogo grafu ce vidkrita 2 komirka poverhni yaka ne peretinayetsya z grafom ale mezhi yakoyi ye ob yednannyam deyakih reber vkladenogo grafu Nehaj F gran vkladenogo grafu G i nehaj v0 v1 vn 1 vn v0 vershini sho lezhat na mezhi F u poryadku ciklu Ciklovij interval dlya F ce nabir vershin viglyadu va va 1 va s de a i s cili chisla i de indeks beretsya za modulem n Nehaj L ce skinchennij spisok ciklovih intervaliv dlya F Pobuduyemo novij graf takim chinom Dlya kozhnogo ciklovogo intervalu L z L dodayemo novu vershinu vL z yednanu z deyakim chislom mozhlivo nulovim vershin z L Dlya kozhnoyi pari L M intervaliv u L mi mozhemo dodati rebro sho z yednuye vL z vM yaksho L i M mayut neporozhnij peretin Kazhut sho utvorenij graf otrimano z grafu G dodannyam vihoru glibini sho ne perevishuye k do mezhi F yaksho niyaka vershina na mezhi F ne z yavlyayetsya v bilsh nizh k intervalah z L Tverdzhennya strukturnoyi teoremi grafivStrukturna teorema grafiv Dlya bud yakogo grafu H isnuye dodatne cile k take sho bud yakij H vilnij graf mozhna otrimati takim chinom pochinayemo zi spisku grafiv de kozhen graf zi spisku vkladenij u poverhnyu v yaku H vklasti ne mozhna do kozhnogo vkladenogo grafu zi spisku dodayemo ne bilshe k vihoriv i kozhen vihor maye glibinu yaka ne perevishuye k do kozhnogo otrimanogo grafu dodayemo ne bilshe k novih vershin zvanih verhivkami i dodayemo deyake chislo reber yaki mayut prinajmni odin kinec u verhivci nareshti z yednuyemo za dopomogoyu k klikovih sum otrimanij spisok grafiv Zauvazhimo sho kroki 1 i 2 dayut porozhni grafi yaksho graf H planarnij ale obmezhene chislo vershin sho dodayutsya na etapi 3 robit tverdzhennya sumisnim zi Naslidkom 1 UtochnennyaPosileni versiyi strukturnoyi teoremi grafiv mozhlivi zalezhno vid mnozhini H zaboronenih minoriv Napriklad yaksho odin z grafiv u H planarnij to bud yakij H vilnij graf maye derevnu dekompoziciyu obmezhenoyi shirini Ekvivalentno jogo mozhna podati yak sumu za klikoyu grafiv stalogo rozmiru Yaksho odin z grafiv H mozhna namalyuvati v ploshini z odnim shreshennyam to H minorno vilni grafi dopuskayut rozkladannya na klikovu sumu grafiv stalogo rozmiru i grafiv z obmezhenim rodom ne vikoristovuyuchi vihori Vidomi takozh rizni posilennya yaksho odin z grafiv H ye verhivkovim grafom Div takozhTeorema Robertsona SejmuraPrimitkiKawarabayashi Mohar 2007 Lovasz 2006 Wagner 1937 Robertson Seymour ta 1986 V Robertson Seymour 1993 Demaine Hajiaghayi Thilikos 2002 Demaine Hajiaghayi Kawarabayashi 2009 LiteraturaErik D Demaine Mohammad Taghi Hajiaghayi Ken ichi Kawarabayashi 1 Springer Verlag 2009 T 5555 S 316 327 Lecture Notes in Computer Science DOI 10 1007 978 3 642 02927 1 27 z dzherela 2 kvitnya 2013 Erik D Demaine Mohammad Taghi Hajiaghayi Dimitrios M Thilikos Proc 5th International Workshop on Approximation Algorithms for Combinatorial Optimization APPROX 2002 Springer Verlag 2002 T 2462 S 67 80 Lecture Notes in Computer Science DOI 10 1007 3 540 45753 4 8 Ken ichi Kawarabayashi Bojan Mohar Some recent progress and applications in graph minor theory 2007 T 23 vip 1 17 chervnya S 1 46 DOI 10 1007 s00373 006 0684 x Lovasz Graph minor theory Bulletin of the American Mathematical Society 2006 T 43 vip 1 17 chervnya S 75 86 DOI 10 1090 S0273 0979 05 01088 8 Neil Robertson P D Seymour Graph minors I Excluding a forest 1983 T 35 vip 1 1 sichnya S 39 61 Series B DOI 10 1016 0095 8956 83 90079 5 Neil Robertson P D Seymour Graph minors II Algorithmic aspects of tree width Journal of Algorithms 1986 T 7 vip 3 1 lyutogo S 309 322 DOI 10 1016 0196 6774 86 90023 4 Neil Robertson P D Seymour Graph minors III Planar tree width 1984 T 36 vip 1 1 bereznya S 49 64 Series B DOI 10 1016 0095 8956 84 90013 3 Neil Robertson P D Seymour Graph minors IV Tree width and well quasi ordering 1990 T 48 vip 2 1 kvitnya S 227 254 Series B DOI 10 1016 0095 8956 90 90120 O Neil Robertson P D Seymour Graph minors V Excluding a planar graph 1986 T 41 vip 1 1 travnya S 92 114 Series B DOI 10 1016 0095 8956 86 90030 4 Neil Robertson P D Seymour Graph minors VI Disjoint paths across a disc 1986 T 41 vip 1 1 chervnya S 115 138 Series B DOI 10 1016 0095 8956 86 90031 6 Neil Robertson P D Seymour Graph minors VII Disjoint paths on a surface 1988 T 45 vip 2 1 lipnya S 212 254 Series B DOI 10 1016 0095 8956 88 90070 6 Neil Robertson P D Seymour Graph minors VIII A Kuratowski theorem for general surfaces 1990 T 48 vip 2 1 serpnya S 255 288 Series B DOI 10 1016 0095 8956 90 90121 F Neil Robertson P D Seymour Graph minors IX Disjoint crossed paths 1990 T 49 vip 1 1 veresnya S 40 77 Series B DOI 10 1016 0095 8956 90 90063 6 Neil Robertson P D Seymour Graph minors X Obstructions to tree decomposition 1991 T 52 vip 2 1 zhovtnya S 153 190 Series B DOI 10 1016 0095 8956 91 90061 N Neil Robertson P D Seymour Graph Structure Theory Proc AMS IMS SIAM Joint Summer Research Conference on Graph Minors Neil Robertson Paul Seymour American Mathematical Society 1993 T 147 S 669 675 Contemporary Mathematics DOI 10 1090 conm 147 01206 Neil Robertson P D Seymour Graph minors XI Circuits on a surface 1994 T 60 vip 1 1 listopada S 72 106 Series B DOI 10 1006 jctb 1994 1007 Neil Robertson P D Seymour Graph minors XII Distance on a surface 1995 T 64 vip 2 1 grudnya S 240 272 Series B DOI 10 1006 jctb 1995 1034 Neil Robertson P D Seymour Graph minors XIII The disjoint paths problem 1995 T 63 vip 1 30 listopada S 65 110 Series B DOI 10 1006 jctb 1995 1006 Neil Robertson P D Seymour Graph minors XIV Extending an embedding 1995 T 65 vip 1 1 listopada S 23 50 Series B DOI 10 1006 jctb 1995 1042 Neil Robertson P D Seymour Graph minors XV Giant steps 1996 T 68 vip 1 1 zhovtnya S 112 148 Series B DOI 10 1006 jctb 1996 0059 Neil Robertson P D Seymour Graph minors XVI Excluding a non planar graph T 89 vip 1 S 43 76 Series B DOI 10 1016 S0095 8956 03 00042 X Neil Robertson P D Seymour Graph minors XVII Taming a vortex T 77 vip 1 S 162 210 Series B DOI 10 1006 jctb 1999 1919 Neil Robertson Paul Seymour Graph minors XVIII Tree decompositions and well quasi ordering T 89 vip 1 S 77 108 Series B DOI 10 1016 S0095 8956 03 00067 4 Neil Robertson P D Seymour Graph minors XIX Well quasi ordering on a surface 2004 T 90 vip 2 1 listopada S 325 385 Series B DOI 10 1016 j jctb 2003 08 005 Neil Robertson P D Seymour Graph minors XX Wagner s conjecture 2004 T 92 vip 2 1 zhovtnya S 325 357 Series B DOI 10 1016 j jctb 2004 08 001 Neil Robertson Paul Seymour Graph minors XXI Graphs with unique linkages T 99 vip 3 S 583 616 Series B DOI 10 1016 j jctb 2008 08 003 Neil Robertson Paul Seymour Graph minors XXII Irrelevant vertices in linkage problems T 102 vip 2 S 530 563 Series B DOI 10 1016 j jctb 2007 12 007 Neil Robertson Paul Seymour Graph minors XXIII Nash Williams immersion conjecture T 100 vip 2 S 181 205 Series B DOI 10 1016 j jctb 2009 07 003 Klaus Wagner Uber eine Erweiterung des Satzes von Kuratowski Deutsche Mathematik 1937 T 2 17 chervnya S 280 285

Дата публікації:
Топ