Вершинна, реберна зв’язність, зв’язок між ними тамінімальним ступенем вершини

Нехай мінімальний рівень вершини графа [math]G[/math] позначається буквою [math]\delta[/math] . Тоді:

Перевіримо другу нерівність. Якщо графі [math]G[/math] немає ребер, то [math] \lambda = 0 [/math] . Якщо ребра є, то нескладний граф отримуємо з цього, видаляючи всі ребра, інцидентні вершині з найменшим ступенем. У будь-якому випадку [math] \lambda \leqslant \delta [/math] .
Щоб перевірити першу нерівність, потрібно розглянути кілька випадків.

Якщо [math]G[/math] - незв'язний чи тривіальний граф, то [math] \kappa = \lambda = 0 [/math] .
Якщо [math]G[/math] зв'язаний і має міст [math]x[/math] , то [math] lambda = 1 [/math] . У разі [math] \kappa = 1 [/math] , оскільки або граф [math]G[/math] має точку зчленування, інцидентну ребру [math]x[/math] , або ж [math]G=K_2[ / Math] .
Нарешті, припустимо, що граф [math]G[/math] містить безліч з [math] \lambda \geqslant 2 [/math] ребер, видалення яких робить його нескладним. Зрозуміло, що видаляючи [math]\lambda - 1 [/math] ребер із цієї множини отримуємо граф, що має міст [math]x = uv[/math] . Для кожного з цих [math] \ lambda - 1 [/math] ребер виберемо якусь інцидентну з ним вершину відмінну від [math] u [/ math] і [math] v [/ math]. Видалення вибраних вершин призводить до видалення [math]\lambda - 1 [/math] (а можливо, і більшого числа) ребер. Якщо граф, що отримується після такого видалення, не зв'язаний, то [math]\kappa \lt \lambda[/math] ; якщо ж він зв'язаний, то в ньому є міст [math]x[/math], і тому видалення вершини [math]u[/math] або [math]v[/math] призводить або до незв'язного, або до тривіального графа. У будь-якому випадку [math] \kappa \leqslant \lambda[/math] .

Розглянемо граф [math]G[/math] , що є об'єднанням двохповних графів [math]G_1[/math] та [math]G_2[/math] , що містять [math]c + 1[/math] вершину. Зазначимо [math]b[/math] вершин, що належать підграфу [math]G_1[/math] і [math]a[/math] вершин, що належать підграфу [math]G_2[/math]. Додамо до графа [math]G[/math] [math]b[/math] ребер так, щоб кожне ребро було інцидентно позначеною вершині, що лежить у підграфі [math]G_1[/math] і поміченою вершині, що лежить у підграфі [math ]G_2[/math] , причому не залишилося жодної поміченої вершини, у якої не з'явилося хоча б одне нове ребро, інцидентне їй. Тоді:

Оскільки [math]b \leqslant c[/math] , було як мінімум дві непомічені вершини, тому [math] \delta = c[/math] , оскільки мінімальні ступеня вершин графів [math]G_1[/math] і [ math]G_2[/math] дорівнювали [math]c[/math] , а ступеня їх вершин не зменшувалися.
Зауважимо, що між двома вершинами графа [math]G[/math] існує не менше [math]a[/math] вершинно-непересічних простих ланцюгів, отже за теоремою Менгера [math]\kappa \geqslant a[/math] . Однак якщо видалити з графа [math]G[/math] позначені вершини його підграфа [math]G_2[/math], то граф [math]G[/math] втратить зв'язність. Отже, [math] \ kappa = a [/math] .
Аналогічно міркуванню пункту 2 легко переконається, що [math]\lambda = b[/math] .

Для знаходження реберної зв'язності потрібно перебрати всі пари вершин [math]s[/math] і [math]t[/math] , знайти кількість шляхів, що не перетинаються з [math]s[/math] в [math]t[/math] і вибрати мінімум. Нехай він дорівнює [math]l[/math]. За твердженням, граф є [math]l[/math]-зв'язковим, причому таке [math]l[/math] - максимально (адже ми явно знайшли кількість шляхів). Отже, за визначенням, реберна зв'язність дорівнює [math]l[/math] .

Для знаходження кількості непересічнихшляхів з [math]s[/math] до [math]t[/math] скористаємося алгоритмом знаходження максимального потоку. Порівняємо кожному ребру пропускну здатність, рівну [math]1[/math] і знайдемо максимальний потік (наприклад, алгоритм Едмондса-Карпа). Він і дорівнюватиме кількості шляхів. Справді, якщо провести декомпозицію потоку, то отримаємо набір шляхів, що реберно не перетинаються, з [math]s[/math] в [math]t[/math] , за якими потік невід'ємний і дорівнює [math]1[/math] (т.к. пропускна здатність всіх ребер дорівнює [math] 1 [/ math]). Отже, якщо потік дорівнює [math]flow[/math] , те й кількість шляхів дорівнює [math]flow[/math] .

Час роботи дорівнює [math]V^2 \times O(find\_max\_flow)[/math] . При використанні алгоритму Едмондса-Карпа час дорівнює [math]V^2 \times O(V E^2)[/math] або [math]O(V^3 E^2)[/math]

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

Розіб'ємо кожну вершину [math]v[/math] графа на дві вершини [math]v_1[/math] і [math]v_2[/math]. Всі ребра, які входили до [math]v[/math] будуть входити до [math]v_1[/math] . Усі ребра, які виходили з [math]v[/math], будуть виходити з [math]v_2[/math] . Також додамо ребро [math](v_1, v_2)[/math] з пропускною здатністю [math]1[/math] .

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

Тим самим звівши завдання знайти реберної зв'язності.