Реберна зв’язність. Властивості та знаходження

Визначення

Нехай дано неорієнтований граф з вершинами та ребрами.

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

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

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

Зрозуміло, що реберна зв'язність графа дорівнює мінімуму від найменшого числа ребер, що розділяють дві вершини і взятому серед різних пар.

Співвідношення Вітні

Співвідношення Уітні (Whitney)(1932 р.) між реберною зв'язністю, вершинною зв'язністю і найменшою зі ступенів вершин:

Доведемоце твердження.

Доведемо спочатку першу нерівність: . Розглянемо цей набір з ребер, які роблять граф нескладним. Якщо ми візьмемо від кожного з цих ребрів по одному кінці (будь-якому з двох) і видалимо з графа, то цим за допомогою віддалених вершин (оскільки одна і та ж вершина могла зустрітися двічі) ми зробимо граф незв'язним. Таким чином, .

Доведемо друге нерівність: . Розглянемо вершину мінімального ступеня, тоді ми можемо видалити всі суміжні з нею ребер і тим самим відокремити цю вершину від решти графа. Отже, .

Цікаво, що нерівність Уітніне можна поліпшити: тобто. для будь-яких трійок чисел, що задовольняють цю нерівність, існує хоча б один відповідний граф. Див. задачу "Побудова графа із зазначеними величинами вершинної та реберної зв'язків та найменшої зі ступенів вершин".

Теорема Форда-Фалкерсона

Теорема Форда-Фалкерсона(1956 р.):

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

Знаходження реберної зв'язності

Простий алгоритм на основі пошуку максимального потоку

Цей спосіб ґрунтується на теоремі Форда-Фалекрсона.

Ми повинні перебрати всі пари вершин, і між кожною парою знайти найбільшу кількість шляхів, що не перетинаються по ребрах. Цю величину можна знайти за допомогою алгоритму максимального потоку: ми робимо витоком - стоком, а пропускну здатність кожного ребра кладемо рівною 1.

Таким чином, псевдокод алгоритму такий:

p align="justify"> Асимптотика алгоритму при використанні \ edmonds_karp виходить, проте слід зауважити, що прихована в асимптотиці константа дуже мала, оскільки практично неможливо створити такий граф, щоб алгоритм знаходження максимального потоку працював повільно відразу при всіх стоках і витоках.

Особливо швидко такий алгоритм працюватиме на випадкових графах.

Спеціальний алгоритм

Використовуючи потокову термінологію, це завдання — це завданняглобального мінімального розрізу.

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

Література

Hassler Whitney.Congruent Graphs and Connectivity of Graphs[1932]

Френк Харарі.Теорія графів[2003]

---