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