Реберна зв'язність / Вершинна зв'язність

Означення

Нехай задано неорієнтований граф $G$ з $n$ вершинами та $m$ ребрами. І реберна зв'язність, і вершинна зв'язність є характеристиками, що описують граф.

Реберна зв'язність

Реберна зв'язність $\lambda$ графа $G$ — це мінімальна кількість ребер, які потрібно видалити, щоб граф $G$ став незв'язним.

Наприклад, уже незв'язний граф має реберну зв'язність $0$, зв'язний граф щонайменше з одним мостом має реберну зв'язність $1$, а зв'язний граф без мостів має реберну зв'язність щонайменше $2$.

Ми кажемо, що множина $S$ ребер розділяє вершини $s$ і $t$, якщо після видалення з графа $G$ усіх ребер з $S$ вершини $s$ і $t$ опиняються в різних компонентах зв'язності.

Зрозуміло, що реберна зв'язність графа дорівнює мінімальному розміру такої множини, що розділяє дві вершини $s$ і $t$, узятому серед усіх можливих пар $(s, t)$.

Вершинна зв'язність

Вершинна зв'язність $\kappa$ графа $G$ — це мінімальна кількість вершин, які потрібно видалити, щоб граф $G$ став незв'язним.

Наприклад, уже незв'язний граф має вершинну зв'язність $0$, а зв'язний граф із точкою зчленування має вершинну зв'язність $1$. Ми вважаємо, що повний граф має вершинну зв'язність $n-1$. Для всіх інших графів вершинна зв'язність не перевищує $n-2$, бо можна знайти пару вершин, не з'єднаних ребром, і видалити всі інші $n-2$ вершини.

Ми кажемо, що множина $T$ вершин розділяє вершини $s$ і $t$, якщо після видалення з графа $G$ усіх вершин з $T$ ці вершини опиняються в різних компонентах зв'язності.

Зрозуміло, що вершинна зв'язність графа дорівнює мінімальному розміру такої множини, що розділяє дві вершини $s$ і $t$, узятому серед усіх можливих пар $(s, t)$.

Властивості

Нерівності Вітні

Нерівності Вітні (1932) дають зв'язок між реберною зв'язністю $\lambda$, вершинною зв'язністю $\kappa$ та мінімальним степенем будь-якої вершини в графі $\delta$:

$$\kappa \le \lambda \le \delta$$

Інтуїтивно, якщо ми маємо множину ребер розміру $\lambda$, яка робить граф незв'язним, ми можемо вибрати по одному з кінців кожного ребра і створити множину вершин, що також робить граф незв'язним. І ця множина має розмір $\le \lambda$.

А якщо ми візьмемо вершину з мінімальним степенем $\delta$ і видалимо всі ребра, з нею з'єднані, то ми також отримаємо незв'язний граф. Звідси випливає друга нерівність $\lambda \le \delta$.

Цікаво зауважити, що нерівності Вітні не можна покращити: тобто для будь-якої трійки чисел, яка задовольняє цю нерівність, існує принаймні один відповідний граф. Один такий граф можна побудувати таким чином: граф складатиметься з $2(\delta + 1)$ вершин, перші $\delta + 1$ вершин утворюють кліку (усі пари вершин з'єднані ребром), а другі $\delta + 1$ вершин утворюють другу кліку. Крім того, ми з'єднуємо дві кліки $\lambda$ ребрами так, щоб вони використовували $\lambda$ різних вершин у першій кліці й лише $\kappa$ вершин у другій кліці. Отриманий граф матиме всі три характеристики.

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

Теорема Форда — Фалкерсона стверджує, що найбільша кількість реберно-неперетинних шляхів, які з'єднують дві вершини, дорівнює найменшій кількості ребер, що розділяють ці вершини.

Обчислення значень

Реберна зв'язність через максимальний потік

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

Ми перебираємо всі пари вершин $(s, t)$ і для кожної пари знаходимо найбільшу кількість неперетинних шляхів між ними. Це значення можна знайти за допомогою алгоритму максимального потоку: ми використовуємо $s$ як джерело, $t$ як стік і призначаємо кожному ребру пропускну здатність $1$. Тоді максимальний потік і є кількістю неперетинних шляхів.

Складність алгоритму з використанням Едмондса — Карпа дорівнює $O(V^2 V E^2) = O(V^3 E^2)$. Але слід зауважити, що сюди входить прихований множник, оскільки практично неможливо побудувати граф такий, щоб алгоритм максимального потоку працював повільно для всіх джерел і стоків. Зокрема, для випадкових графів алгоритм працюватиме доволі швидко.

Спеціальний алгоритм для реберної зв'язності

Задача знаходження реберної зв'язності рівносильна задачі знаходження глобального мінімального розрізу.

Для цієї задачі розроблено спеціальні алгоритми. Один із них — алгоритм Штера — Вагнера, який працює за час $O(V^3)$ або $O(V E)$.

Вершинна зв'язність

Знову ж таки, ми перебираємо всі пари вершин $s$ і $t$ і для кожної пари знаходимо мінімальну кількість вершин, що розділяє $s$ і $t$.

Роблячи це, ми можемо застосувати той самий підхід через максимальний потік, описаний у попередніх розділах.

Ми розщеплюємо кожну вершину $x$ з $x \neq s$ та $x \neq t$ на дві вершини $x_1$ і $x_2$. Ми з'єднуємо ці дві вершини орієнтованим ребром $(x_1, x_2)$ з пропускною здатністю $1$ і замінюємо всі ребра $(u, v)$ двома орієнтованими ребрами $(u_2, v_1)$ та $(v_2, u_1)$, обидва з пропускною здатністю $1$. Тоді за побудовою значення максимального потоку дорівнюватиме мінімальній кількості вершин, необхідних для розділення $s$ і $t$.

Цей підхід має ту саму складність, що й потоковий підхід для знаходження реберної зв'язності.

Відеоматеріали