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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Наступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Створено шляхом перекладу сторінки «Структурная теорема графов»
(Немає відмінностей)

Версія за 12:37, 4 грудня 2020

Структурна теорема графів — фундаментальний результат у теорії графів. Результат встановлює тісний зв'язок між теорією мінорів графів і топологічними вкладеннями. Теорему сформульовано в сімнадцяти статтях серії з 23 статей Нейла Робертсона[en] і Пола Сеймура[ru]. Доведення теореми дуже довге і заплутане. Каварабаяші і Мохар[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-вільних графів.

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

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

Література

Отримано з https://uk.wikipedia.org/w/index.php?title=Структурна_теорема_графів&oldid=30213395