Алгоритм Форда – Фалкерсона

Суть алгоритма: предположим, что в сети имеется некоторый поток и путь из s в t, состоящий из ненасыщенных дуг. Тогда очевидно, что поток в сети можно увеличить на величину , равную минимальной из остаточных пропускных способностей дуг, входящих в этот путь.

1. Перебираем все возможные “прямые” пути из s в t и проводим процедуру увеличения потока пока это возможно.

2. Не обращая внимания на ориентацию дуг, находим все возможные цепи, соединяющие вершины s и t. Возвращаясь к ориентации дуг, проводим процедуру увеличения потока, пока это возможно, для этих “ противоположных” путей.

3. В результате получим полный поток , т.е. поток, для которого каждый путь из s в t содержит по крайней мере одну насыщенную дугу.

4. Выбираем разрез сети, состоящий из насыщенных дуг, с минимальной пропускной способностью, значение которой равно значению максимального потока сети G .

Замечание. Для быстрого нахождения требуемого разреза рекомендуется изображать сеть с минимальным числом пересечений дуг.

Пример. Найти максимальный поток через сеть, заданную матрицей пропускных способностей дуг

v₁ v₂ v₃ v₄ v₅ v₆

□ Построим сеть G :

Исток (вершина входа сети) s = v₁ , сток (вершина выхода сети) t = v₆ .

1. Выбираем произвольно путь из вершины v₁ в вершину v₆ . Например, путь

.

Минимальную пропускную способность, равную 12, имеет дуга , т.е. . Увеличим по этому пути поток до 12 единиц. Дуга становится насыщенной. Дуги имеют на данный момент пропускную способность, равную 12.

Путь

, .

Здесь, согласно рассмотренному первому пути, пропускная способность дуги равна 12, но по условию ее пропускная способность равна 15. Значит, мы можем увеличить ее пропускную способность на 15 – 12 = =3 единицы. Следовательно, поток можно увеличить на 3 единицы. Дуга становится насыщенной. Дуга теперь имеет пропускную способность, равную 3.

Путь

. Поток можно увеличить на 7 единиц. Дуга становится насыщенной. Потоки на дугах примут вид:

, .

Больше “прямых “ путей нет, т.к. остальные пути проходят через насыщенные дуги.

2. Рассмотрим теперь “противоположные” пути. Отвлекаясь от ориентации дуг, выберем цепь, соединяющую вершины v₁ и v₆ без насыщенных дуг, например, цепь . Возвращаясь к ориентации дуг, получим “противоположный” путь:

,

. Следовательно, поток

можно увеличить на 1 единицу. Дуга становится насыщенной, .

Других маршрутов нет (другие маршруты проходят через насыщенные дуги).

3. Получен полный поток и он максимален.

4. Делаем разрез вокруг вершины v₆ по насыщенным дугам и получаем его величину единицы. Разрез и насыщенные дуги сети G показаны на рис. 6.1

Рис. 6.1

■