117
правок
Изменения
→Нахождение реберной связности
Пусть <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>.
}}
Алгоритм следует непосредственно из теоремы. Нужно перебрать все пары вершин <tex>s </tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s </tex> в <tex>t </tex> и выбрать минимум.
Для нахождения количества непересекающихся путей из <tex>s </tex> в <tex>t </tex> воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную <tex>1 </tex> и найдем максимальный поток.Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из <tex>s </tex> в <tex>t</tex>, по которым поток неотрицателен и равен 1 (т.к. пропускная способность всех ребер равна <tex>1</tex>). А значит, если поток равен <tex>flow</tex>, то и количество путей равно <tex>flow</tex>.
==== Псевдокод алгоритма ====
