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

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

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

Мінор графу 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-вільних графів.

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

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

Якщо H не планарний, структурна теорема графів може розглядатися як сильне узагальнення теореми Понтрягіна — Куратовського. Версія цієї теореми, доведена Вагнером[3], стверджує, що якщо граф 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-вільний граф. Вагнер[3] визначив точну структуру 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-вільний граф має деревну декомпозицію обмеженої ширини. Еквівалентно його можна подати як суму за клікою графів сталого розміру[4]. Якщо один з графів H можна намалювати в площині з одним перетином, то H-мінорно-вільні графи допускають розкладання на клікову суму графів сталого розміру і графів з обмеженим родом (не використовуючи вихори)[5][6]). Відомі також різні посилення, якщо один з графів H є верхівковим графом[7].

Див. також
  • Теорема Робертсона - Сеймура

Примітки
  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. Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09). — Springer-Verlag, 2009. — Т. 5555. — С. 316–327. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-02927-1_27..
  • 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 // Graphs and Combinatorics. — 2007. — Т. 23, вип. 1 (21 січня). — С. 1–46. — DOI:10.1007/s00373-006-0684-x..
  • Lovász. Graph minor theory // Bulletin of the American Mathematical Society. — 2006. — Т. 43, вип. 1 (21 січня). — С. 75–86. — DOI:10.1090/S0273-0979-05-01088-8..
  • Neil Robertson, P. D. Seymour. Graph minors. I. Excluding a forest // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 1995. — Т. 65, вип. 1 (1 листопада). — С. 23–50. — (Series B). — DOI:10.1006/jctb.1995.1042..
  • Neil Robertson, P. D. Seymour. Graph minors. XV. Giant steps // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — . — Т. 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 // Journal of Combinatorial Theory. — . — Т. 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 // Journal of Combinatorial Theory. — . — Т. 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — 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 // Journal of Combinatorial Theory. — . — Т. 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 // Journal of Combinatorial Theory. — . — Т. 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 // Journal of Combinatorial Theory. — . — Т. 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 (21 січня). — С. 280–285..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.