MAXimal

добавлено: 10 Jun 2008 23:07
редактировано: 31 Aug 2011 21:57

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

Определение

Пусть дан неориентированный граф 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]