117
правок
Изменения
м
Нет описания правки
}}
== Нахождение реберной связности ==
Для нахождения реберной связности воспользуемся [[Теорема Менгера, альтернативное доказательство|следующей теоремой:]]
{{Теорема
|about=
Теорема Менгера для <tex>k</tex>-реберной связности
|statement=
Пусть <tex>G</tex> - конечный, неориентированный граф, <tex>\lambda(G) = k</tex> <tex>\Leftrightarrow</tex> для всех пар вершин <tex>x, y \in G</tex> существует <tex>k</tex> реберно непересекающихся путей из <tex>x</tex> в <tex>y</tex>.
}}
Алгоритм следует непосредственно из теоремы. Нужно перебрать все пары вершин <tex>s</tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s</tex> в <tex>t</tex> и выбрать минимум.
Для нахождения количества непересекающихся путей из <tex>s</tex> в <tex>t</tex> воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную <tex>1</tex> и найдем максимальный поток.
Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из <tex>s</tex> в <tex>t</tex>, по которым поток неотрицателен и равен <tex>1</tex> (т.к. пропускная способность всех ребер равна <tex>1</tex>). А значит, если поток равен <tex>flow</tex>, то и количество путей равно <tex>flow</tex>.
''' Псевдокод алгоритма '''
ans = INF
for <tex>s \in V:</tex>
for <tex>t \in V:</tex>
flow = find_flow(s, t)
ans = min(ans, flow)
'''Оценка работы'''
Время работы равно <tex>V^2 \times O(find\_flow)</tex>. При использовании [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] время равно <tex>V^2 \times O(V E^2)</tex> или <tex>O(V^3 E^2)</tex>
== Нахождение вершинной связности ==
Нахождение вершинной связности сводится к задаче нахождения реберной связности следующим образом.
Разобьем каждую вершину <tex>v</tex> графа на две вершины <tex>v_1</tex> и <tex>v_2</tex>. Все ребра, которые входили в <tex>v</tex> будут входить в <tex>v_1</tex>. Все ребра, которые выходили из <tex>v</tex> будут выходить из <tex>v_2</tex>. Так же добавим ребро <tex>(v_1, v_2)</tex>.
[[Файл:Vertex-2vertex.png|300px|left|thumb|Иллюстрация]]
<br clear="all"/>
В новом графе запустим алгоритм нахождения реберной связности.
== Нахождение реберной связности ==
Для нахождения реберной связности воспользуемся [[Теорема Менгера, альтернативное доказательство|следующей теоремой:]]
