В новом графе запустим алгоритм нахождения реберной связности.
== Нахождение реберной связности. ver 2.0 ==
Для нахождения реберной связности воспользуемся В статье про [[Теорема Менгера, альтернативное доказательство|следующей теоремой:K-связность]]было сформулировано следующее утверждение:{{Теорема|about=Теорема Менгера для <tex>k</tex>-реберной связностиУтверждение
|statement=
Пусть Граф <tex>G</tex> - конечный, неориентированный граф, является '''реберно <tex>\lambda(G) = kl </tex> - связным''' <tex>\Leftrightarrow</tex> для всех пар любая пара его вершин соединена по крайней мере <tex>x, y \in G</tex> существует <tex>kl </tex> - реберно непересекающихся путей из <tex>x</tex> в <tex>y</tex>непересекающимися путями.
}}
Алгоритм следует непосредственно из теоремыТам же было дано определение реберной связности через <tex> l </tex>-связность:{{Определение|definition=[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью]] графа называется <tex> \lambda(G) = \max \{ l | G </tex> реберно <tex> l </tex> - связен <tex> \} </tex>, для тривиального графа считаем <tex> \lambda (K_1) = 0 </tex>. Нужно }} Для нахождения реберной связности нужно перебрать все пары вершин <tex>s</tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s</tex> в <tex>t</tex> и выбрать минимум.Пусть он равен <tex>l</tex>. По утверждению, граф является <tex>l</tex> - связным, причем такое <tex>l</tex> - максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна <tex>l</tex>.
Для нахождения количества непересекающихся путей из <tex>s</tex> в <tex>t</tex> воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную <tex>1</tex> и найдем максимальный поток.
