Вікіпедія

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

Структурна теорема графів — фундаментальний результат у теорії графів. Результат встановлює тісний зв'язок між теорією мінорів графів і топологічними вкладеннями. Теорему сформульовано в сімнадцяти статтях серії з 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=36499293