Доказательство корректности алгоритма Форда–Фалкерсона

Доказательство корректности алгоритма Форда–Фалкерсона. Так как количество различных (целочисленных) потоков в фиксированной транспортной сети конечно, максимальный поток существует. Поскольку в результате каждой итерации алгоритма Форда-Фалкерсона величина потока увеличивается по меньшей мере на 1, алгоритм работает конечное время, т.е. рано или поздно прекратит свою работу. Осталось доказать, что поток, который он строит, является максимальным.
Пусть B - некоторое множество вершин орграфа G = <V;A>, не содержащее источник и содержащее сток ( ). Разрезом сети <G; c> относительно B называется множество A дуг, исходящих из вершин, не принадлежащих B, и заходящих в вершины из B: . Сумма пропускных способностей всех дуг разреза называется пропускной способностью разреза: . Разрез с минимальной пропускной способностью называют минимальным разрезом. Из физических соображений кажется почти очевидным, что величина потока в сети не превосходит пропускной способности любого разреза (значит, и минимального).
Лемма. Для любого множества B вершин орграфа G, среди которых есть сток и нет источника, справедливо следующее равенство: (1), где , .
Доказательство. Прибавив к уменьшаемому и вычитаемому в разности (1) сумму потоков по всем дугам, исходящим из B и заходящим в B, получим равенство, равносильное (1):
(2)
Вклад стока vn в левую часть (2) равен W(), а вклад каждой из остальных вершин из множества B (так как среди них нет и источника, все они - промежуточные) равен 0 в силу условия 2) потока. Соотношение (2), а вместе с ним и (1), доказано.
Дальнейшее рассуждение очевидно:

После окончания работы алгоритма Форда-Фалкерсона в сети не существует цепи v1… vn, вдоль которой возможно увеличение потока. Пусть B - множество вершин, которые не получают (конечной) пометки на последней итерации алгоритма. Заметим, что v1  B; vn  B. Рассмотрим разрез сети относительно B.