Рёберная связность. Свойства и нахождение

Определение

Пусть дан неориентированный граф $G$ с $n$ вершинами и $m$ рёбрами.

Рёберной связностью $\lambda$ графа $G$ называется наименьшее число рёбер, которое нужно удалить, чтобы граф перестал быть связным.

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

Говорят, что множество $S$ рёбер разделяет вершины $s$ и $t$ , если при удалении этих рёбер из графа вершины $u$ и $v$ оказываются в разных компонентах связности.

Ясно, что рёберная связность графа равна минимуму от наименьшего числа рёбер, разделяющих две вершины $s$ и $t$ , взятому среди всевозможных пар $(s,t)$ .

Свойства

Соотношение Уитни

Соотношение Уитни (Whitney) (1932 г.) между рёберной связностью $\lambda$ , вершинной связностью $\kappa$ и наименьшей из степеней вершин $\delta$ :

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

Докажем это утверждение.

Докажем сначала первое неравенство: $\kappa \le \lambda$ . Рассмотрим этот набор из $\lambda$ рёбер, делающих граф несвязным. Если мы возьмём от каждого из этих ребёр по одному концу (любому из двух) и удалим из графа, то тем самым с помощью $\le \lambda$ удалённых вершин (поскольку одна и та же вершина могла встретиться дважды) мы сделаем граф несвязным. Таким образом, $\kappa \le \lambda$ .

Докажем второе неравенство: $\lambda \le \delta$ . Рассмотрим вершину минимальной степени, тогда мы можем удалить все $\delta$ смежных с ней рёбер и тем самым отделить эту вершину от всего остального графа. Следовательно, $\lambda \le \delta$ .

Интересно, что неравенство Уитни нельзя улучшить: т.е. для любых троек чисел, удовлетворяющих этому неравенству, существует хотя бы один соответствующий граф. См. задачу "Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин".

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

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

Для любых двух вершин наибольшее число рёберно-непересекающихся цепей, соединяющих их, равно наименьшему числу рёбер, разделяющих эти вершины.

Нахождение рёберной связности

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

Этот способ основан на теореме Форда-Фалекрсона.

Мы должны перебрать все пары вершин $(s,t)$ , и между каждой парой найти наибольшее число непересекающихся по рёбрам путей. Эту величину можно найти с помощью алгоритма максимального потока: мы делаем $s$ истоком, $t$ — стоком, а пропускную способность каждого ребра кладём равной 1.

Таким образом, псевдокод алгоритма таков:

int ans = INF;
for (int s=0; s<n; ++s)
	for (int t=s+1; t<n; ++t) {
		int flow = ... величина максимального потока из s в t ...
		ans = min (ans, flow);
	}

Асимптотика алгоритма при использовании \edmonds_karp{алгоритма Эдмондса-Карпа нахождения максимального потока} получается $O (n^2 \cdot n m ^2) = O (n^3 m^2)$ , однако следует заметить, что скрытая в асимптотике константа весьма мала, поскольку практически невозможно создать такой граф, чтобы алгоритм нахождения максимального потока работал медленно сразу при всех стоках и истоках.

Особенно быстро такой алгоритм будет работать на случайных графах.

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

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

Для её решения разработаны специальные алгоритмы. На данном сайте представлен один из которых — алгоритм Штор-Вагнера, работающий за время $O (n^3)$ или $O (n m)$ .

Литература

Hassler Whitney. Congruent Graphs and the Connectivity of Graphs [1932]
Фрэнк Харари. Теория графов [2003]