Гілкова декомпозиція

Матеріал з testwiki
Перейти до навігації Перейти до пошуку
Гілкова декомпозиція ґратки. Показано e-поділ. Поділ, декомпозиція і сам граф мають ширину три.

У теорії графів гілкова декомпозиція неорієнтованого графа G — це ієрархічна кластеризація ребер графа G, представлена некореневим двійковим деревом T з ребрами з G як листками. Видалення будь-якого ребра з T поділяє ребра графа G на два підграфи, а шириною декомпозиції вважають найбільшу кількість спільних вершин у будь-якому підграфі, отриманому в такий спосіб. Ширина галуження графа G це найменша ширина будь-якої гілкової декомпозиції графа G.

Ширина галуження тісно пов'язана з деревною шириною — для всіх графів вони лежать у межах сталого множника одна від одної, і обидві величини можна описати забороненими мінорами. Як і для деревної ширини, багато задач оптимізації на графах можна ефективно розв'язати на графах із малою шириною галуження. Проте, на відміну деревної ширини, ширину галуження планарного графа можна обчислити точно за поліноміальний час. Гілкову декомпозицію та ширину галуження можна узагальнити з графів на матроїди.

Визначення

Некореневе двійкове дерево — це зв'язний неорієнтований граф без циклів, у якому кожен нелистовий вузол має рівно три сусіди. Гілкову декомпозицію можна подати як некореневе двійкове дерево T разом з бієкцією між листками дерева T та ребрами даного графа G = (V, E). Якщо e — будь-яке ребро дерева T, то видалення e з T ділить його на два піддерева T1 і T2. Цей поділ дерева T на піддерева породжує поділ ребер, асоційованих з листками дерева T на два підграфи графа G, G1 і G2. Такий поділ графа G на два підграфи називають e-поділом.

Ширина e-поділу — це число вершин графа G, інцидентних як ребрам з E1, так і ребрам з E2. Тобто це множина вершин, спільних для підграфів G1 і G2. Ширина гілкової декомпозиції — це найбільша ширина будь-якого e-поділу. Ширина галуження графа G — це найменша ширина гілкових декомпозицій графа G.

Зв'язок із деревною шириною

Гілкова декомпозиція графа тісно пов'язана з деревною декомпозицією, а ширина галуження тісно пов'язана з деревною шириною. Дві ці величини відрізняються лише сталим множником. Зокрема, в статті, в якій вони запропонували ширину галуження, Шаблон:Не перекладено і Шаблон:НпШаблон:Sfn показали, що для графа G з деревною шириною k і шириною галуження Шаблон:Nobr

b−1≤k≤⌊32b⌋−1.

Ширина нарізки

Ширина нарізки — це концепція, визначена аналогічно ширині галуження, з тією різницею, що у визначеннях вершини та ребра міняють місцями. Декомпозиція нарізкою — це некореневе двійкове дерево, в якому кожен листок представляє вершину початкового графа, а ширина розрізу — це число (або повна вага у зважених графах) ребер, інцидентних вершині в обох піддеревах.

Алгоритми визначення ширини галуження зазвичай працюють зведенням до еквівалентної задачі визначення ширини нарізки. Зокрема, ширина нарізки серединного графа рівно вдвічі більша за ширину галуження вихідного графаШаблон:Sfn.

Алгоритми та складність

Задача визначення, чи має граф G гілкову декомпозицію із шириною, що не перевищує k, є NP-повною, якщо G і k є вхідними даними задачіШаблон:Sfn. Однак графи зі шириною галуження не більшою від k, утворюють сімейство графів, замкнене за мінорамиШаблон:Sfn, звідки випливає, що обчислення ширини галуження є Шаблон:Не перекладено задачею: існує алгоритм для обчислення оптимальної гілкової декомпозиції, час роботи якого на графах із шириною галуження, що не перевищує k для деякого сталого k, лінійно залежить від розміру графа[1].

Для планарних графів ширину галуження можна обчислити за лінійний час. Це контрастує із деревною шириною, для якої складність обчислення на планарних графах є добре відомою відкритою проблемою[2]. Початковий алгоритм Пола Сеймура і Шаблон:Нп для обчислення ширини галуження планарних графів розв'язував задачу за час O(n2) на графі з n вершинами, а їхній алгоритм для побудови гілкової декомпозиції працював за час O(n4)Шаблон:Sfn. Пізніше останній покращено до O(n3)Шаблон:Sfn.

Як і в разі деревної ширини, ширину галуження можна використати як базис алгоритмів динамічного програмування для багатьох NP-складних задач оптимізації, і в цих алгоритмах час розв'язування буде експоненціальним від ширини вхідного графа або матроїдаШаблон:SfnШаблон:Sfn. Наприклад, Кук і СеймурШаблон:Sfn застосували заснований на ширині галуження метод динамічного програмування до задачі злиття часткових розв'язків задачі комівояжера в один глобальний розв'язок шляхом формування розрідженого графа з об'єднання часткових розв'язків, де використали евристичне спектральне кластерування для знаходження хорошої гілкової декомпозиції, після чого до неї застосували динамічне програмування. Фомін і ТілікосШаблон:Sfn запевняють, що при розробці фіксовано-параметрично розв'язуваних алгоритмів на планарних графах ширина галуження працює краще, ніж деревна ширина, з багатьох причин — ширина галуження може бути тісніше обмеженою функцією параметра, ніж обмеження деревної ширини, її можна обчислити за поліноміальний час і алгоритм обчислення ширини галуження не має великих прихованих констант.

Узагальнення для матроїдів

Поняття гілкової декомпозиції можна також визначити для матроїдів, що узагальнює гілкову декомпозицію графівШаблон:Sfn. Гілкова декомпозиція матроїда є ієрархічною кластеризацією елементів матроїда, подана як некореневе двійкове дерево з елементами матроїда як листками. Для матроїдів e-поділ можна визначити в той самий спосіб, що й для графів, а результатом буде поділ множини M елементів матроїда на дві підмножини A і B. Якщо через ρ позначити функцію рангу матроїда, то ширина e-поділу визначається як Шаблон:Nobr, а ширина декомпозиції та ширина галуження матроїда визначаються аналогічно до визначень для графа. Ширина галуження графа та ширина галуження відповідного Шаблон:Не перекладено відрізняються. Наприклад, шлях із трьох ребер і зірка з трьох ребер мають різні ширини галуження, 2 і 1 відповідно, але графовий матроїд у них однаковий і має ширину галуження 1Шаблон:Sfn. Однак для графів, що не є деревами, ширина галуження графа дорівнює ширині галуження пов'язаного графового матроїдаШаблон:SfnШаблон:Sfn. Ширина галуження матроїда дорівнює ширині галуження його Шаблон:Не перекладено, і з цього випливає, що ширина галуження будь-якого планарного графа, який не є деревом, дорівнює ширині галуження його двоїстого графаШаблон:Sfn.

Ширина галуження — важлива складова спроб розширити теорію мінорів графа на Шаблон:Не перекладено — хоча деревну ширину можна також узагальнити на матроїдиШаблон:Sfn і її роль у теорії графів більша, ніж ширини галуження, ширина галуження має зручніші властивостіШаблон:Sfn. Робертсон і Сеймур висловили припущення, що матроїди, подані будь-яким конкретним скінченним полем, Шаблон:Не перекладено , що є аналогією теореми Робертсона — Сеймура для графів, але гіпотезу доведено тільки для матроїдів із обмеженою шириною галуженняШаблон:SfnШаблон:Sfn. Крім того, якщо сімейство матроїдів, замкнене за мінорами і подане скінченним полем, не включає графових матроїдів усіх планарних графів, існує стала, яка обмежує ширину галуження в сімействі, що узагальнює відповідне твердження для сімейств графів, замкнутих за мінорамиШаблон:SfnШаблон:Sfn.

Для будь-якого фіксованого k матроїди з шириною галуження, що не перевищує k, можна розпізнати за поліноміальний час алгоритмом, який отримує доступ до матроїда через Шаблон:Не перекладеноШаблон:Sfn.

Заборонені мінори

Чотири заборонені мінори для графів із шириною галуження три.

За теоремою Робертсона — Сеймура графи з шириною галуження k можна схарактеризувати скінченною множиною заборонених мінорів. Графи з шириною галуження 0 — це парування, а найменші заборонені мінори в цьому випадку — це шлях із двох дуг та трикутний граф (а також цикл із двох дуг, якщо розглядаються мультиграфи)Шаблон:Sfn. Графи з шириною галуження 1 — це графи, в яких кожна компонента зв'язності є зіркою, а найменші заборонені мінори для графів з шириною галуження 1 — це трикутний граф (або цикл із двох дуг, якщо розглядаються мультиграфи) і шляхи з трьох дугШаблон:Sfn. Графи з шириною галуження 2 — це графи, в яких кожна двозв'язна компонента є паралельно-послідовним графом, а єдиним найменшим забороненим мінором є повний граф K4 з чотирьох вершинШаблон:Sfn. Граф має ширину галуження три тоді й лише тоді, коли його деревна ширина дорівнює трьом і він не має мінором графа гіперкубу. Таким чином, чотири заборонені мінори — це три з чотирьох заборонених мінорів графів з деревною шириною три (граф октаедра, повний граф K5 і граф Вагнера) разом із графом куба[3].

Заборонені мінори вивчаються також і для ширини галуження матроїда, попри відсутність повної аналогії теореми Робертсона — Сеймура у цьому разі. Матроїд має ширину галуження одиниця тоді й лише тоді, коли будь-який елемент є або петлею, або копетлею, так що єдиним найменшим забороненим мінором є Шаблон:Не перекладено U(2,3), графовий матроїд трикутного графа. Матроїд має ширину галуження два тоді й лише тоді, коли він є графовим матроїдом графа з шириною галуження два, так що мінімальними забороненими мінорами є графові матроїди графа K4 і неграфовий матроїд U(2,4). Матроїди з шириною галуження три не цілком квазівпорядковані без додаткового припущення щодо подання над скінченним полем, але, тим не менш, матроїди з будь-якою обмеженою шириною галуження мають скінченне число найменших заборонених мінорів, які мають число елементів, що залежать від ширини галуження не більш ніж експоненційноШаблон:SfnШаблон:Sfn.

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

  1. ↑ Шаблон:Harvtxt. Фомін, Мацойт і Тодінка Шаблон:Harvtxt описують алгоритм із покращеною залежністю від k, (2√3)k, але залежність від числа вершин зростає від лінійної до квадратичної.
  2. ↑ Шаблон:Citation
  3. ↑ Шаблон:Harvtxt. Четвертий заборонений мінор для деревної ширини три, граф п'ятикутної призми, має граф куба як мінор, так що він не є найменшим для ширини галуження три.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Гілкова_декомпозиція&oldid=9671