Вушна декомпозиція

Приклад вушної декомпозиції графа, що містить 3 вуха.

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

Вушну декомпозицію можна використати для опису деяких важливих класів графів, і як частину ефективних алгоритмів на графах. Вушну декомпозицію можна узагальнити для матроїдів.

Опис класів графів

Деякі важливі класи графів можна описати певним типом вушних декомпозицій.

Зв'язність графа

Граф k-вершинно-зв'язний, якщо видалення будь-яких (k − 1) вершин залишає зв'язний підграф, і k-реберно-зв'язний, якщо видалення будь-яких (k − 1) ребер залишає зв'язний підграф.

Гесслер Вітні отримав такий результат:

Граф $G=(V,E)$ з $|E|\geq 2$ 2-вершинно-зв'язний тоді й лише тоді, коли для нього існує відкрита вушна декомпозиція.

Інший результат належить Герберту Робінсу:

Граф 2-реберно-зв'язний тоді й лише тоді, коли для нього існує вушна декомпозиція.

В обох випадках число вух обов'язково дорівнює контурному рангу графа. Роббінс застосував вушну декомпозицію 2-реберно-зв'язних графів як засіб доведення теореми Роббінса, що це точно графи, яким можна задати сильно зв'язну орієнтацію. Оскільки Вітні і Роббінс першими досліджували вушну декомпозицію, її іноді називають си́нтезом Ві́тні — Ро́ббінса.

Нерозподі́льна вушна́ декомпози́ція — це відкрита вушна декомпозиція, така, що для кожної вершини v, за винятком однієї, v має сусідню вершину, яка з'являється в декомпозиції пізніше від вершини v. Цей тип декомпозиції можна використати для узагальнення результату Вітні:

Граф $G=(V,E)$ з $|V|\geq 2$ є 3-вершинно-зв'язним тоді й лише тоді, коли G має нерозподільну вушну декомпозицію.

Якщо така декомпозиція існує, її можна вибрати відносно ребра uv графа G так, що u належить першому вуху, v є новою вершиною в останньому вусі з більш ніж одним ребром і uv є вухом, що складається з одного ребра. Цей результат вперше висловили явно Чер'ян і Махешварі, але, як пише Шмідт, він еквівалентний результату тез Ph.D. дисертації 1971 року Лі Мондшейна. Структури, тісно пов'язані з нерозподільними вушними декомпозиціями максимальних планарних графів, звані канонічними упорядкуваннями, є також стандартним засобом візуалізації графів.

Сильна зв'язність орієнтованих графів

Визначення, наведені вище, можна перенести також на орієнтовані графи. Вухом тоді буде орієнтований шлях, у якому всі внутрішні вершини мають напівстепінь входу і напівстепінь виходу, рівні 1. Орієнтований граф є сильно зв'язним, якщо він містить орієнтований шлях із будь-якої вершини в будь-яку іншу вершину. Тоді виконується така теорема:

Орієнтований граф є сильно зв'язним тоді й лише тоді, коли він має вушну декомпозицію.

Аналогічно, орієнтований граф є двозв'язним, якщо для будь-яких двох вершин існує простий цикл, що містить обидві вершини. Тоді: Орієнтований граф є двозв'язним тоді й лише тоді, коли він має відкриту вушну декомпозицію.

Фактор-критичні графи

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

Граф G є фактор-критичним графом тоді й лише тоді, коли G має непарну вушну декомпозицію.

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

Паралельно-послідовні графи

Деревна вушна декомпозиція — це правильна вушна декомпозиція, в якій перше вухо є окремим ребром і для кожного наступного вуха $P_{i}$ існує єдине вухо $P_{j}$, $i>j$, в якому обидві кінцеві точки $P_{i}$ лежать на $P_{j}$. Укладена вушна декомпозиція — це деревна вушна декомпозиція, така, що всередині кожного вуха $P_{j}$ множина пар кінцевих точок інших вух $P_{i}$, що лежать усередині $P_{j}$, утворює множину вкладених інтервалів. Паралельно-послідовний граф — це граф із двома виділеними різними кінцями s і t, який можна утворити рекурсивно, комбінуючи менші паралельно-послідовні графи одним із двох способів — послідовним з'єднанням (ототожнюємо один кінець одного з графів з одним кінцем іншого графа, а інші два кінці обох графів стають кінцями об'єднання) і паралельним з'єднанням (ототожнюємо обидві пари кінців обох менших графів).

Девід Епштейн отримав такий результат:

2-вершинно-зв'язний граф є паралельно-послідовним графом тоді й лише тоді, коли він має вкладену вушну декомпозицію.

Більш того, будь-яка відкрита вушна декомпозиція 2-вершинно-зв'язного паралельно-послідовного графа має бути вкладеною. Результат можна узагальнити на паралельно-послідовні графи, які не є 2-вершинно-зв'язними, за допомогою відкритої вушної декомпозиції, яка стартує зі шляху між двома кінцями.

Матроїди

Концепцію вушної декомпозиції можна узагальнити з графів на матроїди. Вушна декомпозиція матроїда визначається як послідовність циклів матроїда, що має дві властивості:

• кожен цикл у послідовності має непорожній перетин з попередніми циклами.
• кожен цикл у послідовності залишається циклом, навіть якщо всі попередні цикли в послідовності стягнути.

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

Алгоритм

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

Ловас, Маон, Шибер і Вишкін, а також Міллер і Рамачандран навели ефективні паралельні алгоритми для побудови вушних декомпозицій різних типів. Наприклад, щоб знайти вушну декомпозицію 2-реберно-зв'язного графа, алгоритм Маона, Шибера і Вишкіна проходить такі кроки:

1. Знаходимо кістякове дерево заданого графа і вибираємо корінь дерева.
2. Для кожного ребра uv, що не є частиною дерева, визначаємо відстань між коренем і найменшим спільним предком u і v.
3. Для кожного ребра uv, що є частиною дерева, знаходимо відповідне «головне ребро», ребро wx не з дерева, таке, що цикл, утворений додаванням wx до дерева, проходить через uv і таке, що серед усіх ребер w і x має найнижчого предка, якомога ближчого до кореня.
4. Утворюємо вухо для кожного ребра не з дерева, що складається з цього ребра і ребер дерева, для яких це ребро є головним. Упорядковуємо вуха за відстанями головного ребра від кореня.

Цей алгоритм можна використати як процедуру для інших задач, зокрема для перевірки зв'язності, розпізнавання послідовно-паралельних графів і побудови st-нумерації графів (важлива процедура для перевірки планарності).

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

Література

• J. Cheriyan, S. N. Maheshwari. Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs // Journal of Algorithms. — 1988. — Т. 9, вип. 4. — С. 507–537. — DOI:10.1016/0196-6774(88)90015-6.
• Collette R. Coullard, Lisa Hellerstein. Independence and port oracles for matroids, with an application to computational learning theory // Combinatorica. — 1996. — Т. 16, вип. 2. — С. 189–208. — DOI:10.1007/BF01844845.
• D. Eppstein. Parallel recognition of series-parallel graphs // Information & Computation. — 1992. — Т. 98, вип. 1. — С. 41–55. — DOI:10.1016/0890-5401(92)90041-D.
• András Frank. Conservative weightings and ear-decompositions of graphs // Combinatorica. — 1993. — Т. 13, вип. 1. — С. 65–81. — DOI:10.1007/BF01202790.
• Jonathan L. Gross, Jay Yellen. Graph theory and its applications. — 2nd. — Chapman &Hall/CRC, Boca Raton, FL, 2006. — С. 498–499. — (Discrete Mathematics and its Applications (Boca Raton)) — ISBN 978-1-58488-505-4. Архівовано з джерела 3 грудня 2021
• Samir Khuller. Ear decompositions // SIGACT News. — 1989. — Т. 20, вип. 1. — С. 128.
• László Lovász. A note on factor-critical graphs // Studia Sci. Math. Hung.. — 1972. — Т. 7. — С. 279–280.
• László Lovász. 26th Annual Symposium on Foundations of Computer Science. — 1985. — С. 464–467. — DOI:10.1109/SFCS.1985.16.
• Y. Maon, B. Schieber, U. Vishkin. Parallel ear decomposition search (EDS) and ST-numbering in graphs // Theoretical Computer Science. — 1986. — Т. 47, вип. 3. — DOI:10.1016/0304-3975(86)90153-2.
• G. Miller, V. Ramachandran. Efficient parallel ear decomposition with applications. — Unpublished manuscript, 1986.
• H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control // The American Mathematical Monthly. — 1939. — Т. 46. — С. 281–283. — DOI:10.2307/2303897..
• Jens M. Schmidt. A Simple Test on 2-Vertex- and 2-Edge-Connectivity // Information Processing Letters. — 2013a. — Т. 113, вип. 7. — С. 241–244. — DOI:10.1016/j.ipl.2013.01.016.
• Jens M. Schmidt. The Mondshein sequence. — 2013b.
• Олександр Шрайвер. Combinatorial Optimization. Polyhedra and efficiency. Vol A. — Springer-Verlag, 2003. — ISBN 978-3-540-44389-6.
• Balázs Szegedy, Christian Szegedy. Symplectic spaces and ear-decomposition of matroids // Combinatorica. — 2006. — Т. 26, вип. 3. — С. 353–377. — DOI:10.1007/s00493-006-0020-3.
• H. Whitney. Non-separable and planar graphs // Transactions of the American Mathematical Society. — 1932. — Т. 34. — С. 339–362. — DOI:10.1090/S0002-9947-1932-1501641-2.