17. Потоки и разрезы в сетях. Алгоритм Форда-Фалкерсона

Сеть – это четверка(G,c,s,t), G – орграф, s,t – две его вершины(источник и сток), c:A(G) -> R+, c(e) – пропускная способность дуги e. deg_-(s) = 0, deg₊(t) = 0

Разрез – это разбиение (S,T) мн-ва вершин сети, такое что sÎ S, tÎ T

δ₊(S,T) = {uvÎ A: uÎ S,vÎ T} –прямые ребра

δ_-(S,T) = {uvÎ A: uÎ T,vÎ S} –обратн ребра

δ(S,T) = δ₊ (S,T)δ_-(S,T) –прямые ребра

с(S,T) =

- величина потока f

Утверждение. Пусть (S,T)-разрез. Тогда

Утверждение. Для любого потока f и любого разреза (S,T)

s(f)£c(S,T) .

Утверждение. Пусть f – поток, а (S,T)- разрез. Если s(f) = c(S,T), то f- максимальный поток, а (S,T)-минимальный

разрез.

Т-ма Форда-Фалкерсона. Для любой сети величина max потока равна пропускной способности min разреза.

Алгоритм: вход: сеть G = (V, E, s, t, c(e)).

Выход: поток f наибольшей мощности в сети G.

1. Обнуляем все потоки.Остаточная сет изначально совпадает с исходной сетью.

2. В остаточной сети находим любой путь из источника в сток.Если такого пути нет, останавливаемся.

3. Пускаем через найденный путь max-возможный поток:

a. На найденном пути в остаточной сети ищем ребро с min пропускной способностью с_min

б. Для каждого ребра на найденном пути, увеличиваем поток на с_min а в противоположному ему – уменьшаем на с_min

в. Модифицируем остаточнуюд часть.Для всех ребер на найденном пути, а также для противоположных им ребер, вычисляем новую пропускную способность.Если она стала ненулевой, добавляем ребро к остатоной сети, а если обнунлилась, стираем его.

4. Возвращаемся на шаг 2.

Утверждение. Поток f является максимальным тогда и только тогда, когда относительно него нет увеличивающей цепи

Замечание. Если пропускные способности – целые

числа, то найденный алгоритмом Форда-Фалкерсона

поток тоже будет целочисленным