MAXimal | |
добавлено: 10 Jun 2008 23:07 Содержание [скрыть] Рёберная связность. Свойства и нахождениеОпределениеПусть дан неориентированный граф Рёберной связностью Например, для несвязного графа рёберная связность равна нулю. Для связного графа с единственным мостом рёберная связность равна единице. Говорят, что множество Ясно, что рёберная связность графа равна минимуму от наименьшего числа рёбер, разделяющих две вершины СвойстваСоотношение УитниСоотношение Уитни (Whitney) (1932 г.) между рёберной связностью Докажем это утверждение. Докажем сначала первое неравенство: Докажем второе неравенство: Интересно, что неравенство Уитни нельзя улучшить: т.е. для любых троек чисел, удовлетворяющих этому неравенству, существует хотя бы один соответствующий граф. См. задачу "Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин". Теорема Форда-ФалкерсонаТеорема Форда-Фалкерсона (1956 г.): Для любых двух вершин наибольшее число рёберно-непересекающихся цепей, соединяющих их, равно наименьшему числу рёбер, разделяющих эти вершины. Нахождение рёберной связностиПростой алгоритм на основе поиска максимального потокаЭтот способ основан на теореме Форда-Фалекрсона. Мы должны перебрать все пары вершин Таким образом, псевдокод алгоритма таков: 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{алгоритма Эдмондса-Карпа нахождения максимального потока} получается Особенно быстро такой алгоритм будет работать на случайных графах. Специальный алгоритмИспользуя потоковую терминологию, данная задача — это задача поиска глобального минимального разреза. Для её решения разработаны специальные алгоритмы. На данном сайте представлен один из которых — алгоритм Штор-Вагнера, работающий за время Литература
|