200
правок
Изменения
м
→Нахождение реберной связности
Пусть он равен <tex>l</tex>. По утверждению, граф является <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>.
