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

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

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

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

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

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

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

Граф 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].