105
правок
Изменения
м
Дмитрий Мурзин переименовал страницу Вершинная, реберная связность, связь между ними и минимальной степенью вершины в [[Вершинная, рёб…
Пусть он равен <tex>l</tex>. По утверждению, граф является [[k-связность#def_2|<tex>l</tex>-связным]], причем такое <tex>l</tex> {{---}} максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна <tex>l</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>.
'''for''' <tex>s \in V:</tex>
'''for''' <tex>t \in V:</tex>
flow = find_flowfind_max_flow(s, t) <font color=darkgreen>// максимальный поток {{---}} количество путей из <tex>s</tex> в <tex>t</tex> </font>
ans = min(ans, flow)
'''return''' ans
'''Оценка работы'''
Время работы равно <tex>V^2 \times O(find\_max\_flow)</tex>. При использовании [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] время равно <tex>V^2 \times O(V E^2)</tex> или <tex>O(V^3 E^2)</tex>
== Нахождение вершинной связности ==
