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

В 1955 г. Форд и Фалкерсон доказали следующую теорему о максимальном потоке и минимальном разрезе.

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

Доказательство. Докажем сначала, что величина любого потока не превосходит пропускной способности любого разреза: . Просуммируем уравнения сохранения (2) по всем вершинам . Получим

, (3)

где значения коэффициентов зависят от расположения концов дуги относительно множеств и . На рис. 2 показаны шесть возможных вариантов такого расположения.

5 1

6 4

Рис. 2. Возможные расположения концов произвольной дуги

1°. . В этом случае в ходит в складываемые уравнения дважды: со знаком ”+” для вершины и со знаком ”–” для вершины . Следовательно, .

2°. . В этом случае в ходит только в уравнение сохранения для вершины , поэтому .

3°. . В этом случае в ходит только в уравнение сохранения для вершины , поэтому .

4°. . В этом случае , т. к. нет в складываемых уравнениях.

5°. . Результат аналогичен п. 3°.

6°. . Результат аналогичен п. 4°.

Для дуг шестого типа в сумму (3) добавим и вычтем . Тогда для дуг, выходящих из источника (), и дуг, идущих против разреза ; для дуг разреза ; для остальных дуг.

Перепишем уравнение (3) в виде

,

откуда для любого потока и любого разреза

. (4)

Отсюда следует, что максимальное значение потока в сети равно минимальному значению пропускных способностей разрезов этой сети:

.