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

Источник: e-maxx.ru/algo, страница PDF 204.

Definition

Пусть дан неориентированный graph

с

vertexми и

рёбрами.

Рёберной связностью

graphа

называется наименьшее number рёбер, которое нужно удалить, чтобы

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

Говорят, что множество

рёбер разделяет вершины

и

, если при удалении этих рёбер из graphа вершины

и

оказываются в разных компонентах связности. Ясно, что рёберная связность graphа равна минимуму от наименьшего числа рёбер, разделяющих две вершины

и

, взятому среди всевозможных пар

.

Свойства

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

Соотношение Уитни (Whitney) (1932 г.) между рёберной связностью

, вершинной связностью

и наименьшей из степеней вершин

: Докажем это утверждение. Докажем сначала первое неравенство:

. Рассмотрим этот набор из

рёбер, делающих graph несвязным. Если

мы возьмём от каждого из этих ребёр по одному концу (любому из двух) и удалим из graphа, то тем самым с помощью удалённых вершин (поскольку одна и та же vertex могла встретиться дважды) мы сделаем graph несвязным.

Таким образом,

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

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

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

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

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

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

Мы должны перебрать все пары вершин

, и между каждой парой find наибольшее number непересекающихся

по рёбрам путей. Эту величину можно find с помощью Algorithmа максимального потока: мы делаем

истоком,

— стоком, а пропускную способность каждого ребра кладём равной 1. Таким образом, псевдокод Algorithmа таков:

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);

} Asymptotic complexity Algorithmа при использовании \edmonds_karp{Algorithmа Эдмондса-Карпа нахождения максимального

потока} получается

, однако следует заметить, что скрытая в асимптотике

константа весьма мала, поскольку практически невозможно создать такой graph, чтобы Algorithm нахождения максимального потока работал медленно сразу при всех стоках и истоках. Особенно быстро такой Algorithm будет работать на случайных graphах.

Специальный Algorithm

Используя потоковую терминологию, данная Task — это Task поиска глобального минимального разреза. Для её решения разработаны специальные Algorithmы. На данном сайте представлен один из которых — Algorithm

Штор-Вагнера, работающий за время

или

.

References

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

● Фрэнк Харари. Теория graphов [2003]