2. Теорема Форда-Фалкерсона

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

Алгоритм Форда – Фалкерсона построения максимального потока и минимального разреза.

Основан на следующих обстоятельствах.

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

2. Рассмотрим произвольный маршрут (неориентированный путь) из s в t. Дуги, образующие этот маршрут, естественным образом делятся на два типа: прямые (ориентированные от s к t) и обратные (ориентированные от t к s). Пусть существует путь, в котором прямые дуги не насыщены, а потоки на обратных дугах положительны; ∆₁ – минимальная из остаточных пропускных способностей прямых дуг, а ∆₂ – минимальная из вершин потоков обратных дуг. Тогда в сети можно увеличить на величину ∆=min{∆₁, ∆₂}, прибавляя ∆ к потокам на прямых дугах и вычитая ∆ из потоков на обратных дугах.

Рис. 71

Очевидно, что при этом условие баланса (условие сохра

нения потока)

для узлов, входящих в рассматриваемый маршрут, не нарушится.

Замечание 1. Если множество обратных дуг не пусто, то при такой процедуре увеличения потока в сети фактического перемещения объектов вдоль рассматриваемого маршрута не происходит, т.к. оно, в принципе, нереально. Однако, эта процедура уменьшает потоки на некоторых дугах, которые, возможно, были перед этим насыщенными, образуя, таким образом, новые пути из ненасыщенных дуг, вдоль которых и происходит фактическое перемещение потока ∆.

Замечание 2. Первая процедура является частным случаем второй.

Пример. Пропускные способности дуг заданы следующей матрицей.

Построить максимальный поток от s к t и указать минимальный разрез, отделяющий s от t.

Рис. 72

Решение.

Этап 1. Пусть .

Увеличим по этому пути поток до 12 единиц, ребро становится насыщенным. Поставим величину потока на дугах .

Путь Поток можно увеличить на 3 единицы. Дуга станет насыщенной.

Можно увеличить поток на 7 единиц; дуга станет насыщенной, потоки на дугах примут вид, как на рисунке: больше нет путей. Конец 1-го этапа.

Этап 2. Рассмотрим теперь маршруты, содержащие противоположные дуги. Маршрут Поток можно увеличить на одну единицу на дуге . Тогда потоки по дугам этого маршрута станут такими: Дуга стала насыщенной. Больше маршрутов нет. Поток максимальный. Делаем разрез вокруг t по насыщенным дугам и получаем его величину 15+8 = 23 единицы.