117
правок
Изменения
→Нахождение реберной связности
== Нахождение реберной связности ==
''' Описание '''
Для нахождения реберной связности воспользуемся [[Теорема Менгера, альтернативное доказательство|следующей теоремой:]]
{{Теорема
Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из <tex>s</tex> в <tex>t</tex>, по которым поток неотрицателен и равен 1 (т.к. пропускная способность всех ребер равна <tex>1</tex>). А значит, если поток равен <tex>flow</tex>, то и количество путей равно <tex>flow</tex>.
ans = INF
for <tex>(s, \in V:</tex> for <tex>t) \in EV:</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) = O(V^3 E^2)</tex>
== Нахождение вершинной связности ==
