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>.
}}
Алгоритм следует непосредственно из теоремы. Нам нужно перебрать все пары вершин s и t, найти количество непересекающихся путей из s в t и выбрать минимум.
== Нахождение вершинной связности ==
