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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроїди

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

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

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

Алгоритм

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

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

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

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

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

Примітки

1. Whitney, 1932.
2. Robbins, 1939.
3. Gross, Yellen, 2006.
4. Cheriyan, Maheshwari, 1988.
5. Schmidt, 2013b.
6. Lovász, 1972.
7. Frank, 1993.
8. Khuller, 1989.
9. Eppstein, 1992.
10. Szegedy, Szegedy, 2006.
11. Schmidt, 2013a.
12. Lovász, 1985.
13. Maon, Schieber, Vishkin, 1986.
14. Miller, Ramachandran, 1986.
15. Coullard, Hellerstein, 1996.

Література

• 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.
• Олександр Шрайвер^[en]. Combinatorial Optimization. Polyhedra and efficiency. Vol A. — Springer-Verlag, 2003. — ISBN 978-3-540-44389-6.
• Balázs Szegedy^[en], Christian Szegedy. Symplectic spaces and ear-decomposition of matroids // Combinatorica. — 2006. — Т. 26, вип. 3. — С. 353–377. — DOI:10.1007/s00493-006-0020-3.
• H. Whitney^[en]. Non-separable and planar graphs // Transactions of the American Mathematical Society. — 1932. — Т. 34. — С. 339–362. — DOI:10.1090/S0002-9947-1932-1501641-2.