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

Усилим теорему Форда — Фалкерсона следующим образом. Будем доказывать для сети ${\displaystyle G(V,E)}$ с потоком f равносильность сразу трёх следующих фактов:

1° Поток f максимальный

2° Пропускная способность минимального разреза равна величине потока f

3° В графе ${\displaystyle G}$ нет дополняющего пути

1° → 3°. Предположив обратное, получим противоречие, описанное в информации по дополняющем пути в транспортном графе.

3° → 2°. Очевидно, что величина потока f не превышает пропускной способности минимального разреза ${\displaystyle (S,T)}$. Пусть ${\displaystyle c(S,T)>f}$. Тогда рассмотрим разрез, где во множестве${\displaystyle S}$ будут все вершины, кроме ${\displaystyle t}$. Тогда его пропускная способность не меньше пропускной способности минимального разреза, что, в свою очередь, больше величины потока f. Значит, существует направление ${\displaystyle (u,t)}$ из ${\displaystyle S}$ в ${\displaystyle T}$, что ${\displaystyle f(u,t)<c(u,t)}$. Теперь возьмём все такие ${\displaystyle u}$ и перенесём их в ${\displaystyle T}$. Рассмотрев получившийся разрез, заметим, что его пропускная способность тоже больше величины потока. Снова увеличиваем множество ${\displaystyle T}$ и делаем так до тех пор, пока в множестве ${\displaystyle S}$ не останется только вершина ${\displaystyle s}$. Она же будет первой вершиной в пути, который мы создаём. Теперь смотрим какую пару мы выбрали прошлым ходом. Пусть это пара ${\displaystyle (s,u)}$. Тогда к пути добавляем вершину ${\displaystyle u}$. Далее смотрим в паре с какой вершиной была на первом месте вершина ${\displaystyle u}$. Пусть это ${\displaystyle (u,v)}$. Тогда далее к пути добавляем вершину ${\displaystyle v}$. Делаем так до тех пор, пока не дойдём до вершины ${\displaystyle t}$. Однако по построению этот путь является остаточным, что противоречит предположению.

2° → 1°. Как уже говорилось, очевидно, что величина любого потока не превышает пропускной способности минимального разреза, а величина нашего потока ${\displaystyle f}$ равна. Тогда величина потока ${\displaystyle f}$ не меньше величины любого другого потока в нашей сети, то есть поток ${\displaystyle f}$ максимальный.

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

Сеть с 2 минимальными разрезами

Справа дана сеть с 6 вершинами ${\displaystyle V=\{s,o,p,q,r,t\}}$, и суммарный поток от истока ${\displaystyle s}$ к стоку ${\displaystyle t}$ равен 5. Этот поток является максимальным для данной сети.

В данной сети возможны 2 минимальных разреза:

Разрез	Поток
${\displaystyle S=\{s,o,p\},T=\{q,r,t\}}$	${\displaystyle c(o,q)+c(p,r)=3+2=5}$
${\displaystyle S=\{s,o,p,q,r\},T=\{t\}}$	${\displaystyle c(q,t)+c(r,t)=2+3=5}$

• Новиков Ф. А. Дискретная математика для программистов. — 3-е. — СПб.: Питер, 2009. — С. 277—279. — 384 с. — ISBN 978-5-91180-759-7.

• Алгоритм Форда-Фалкерсона на algolist.manual.ru.
• Сети, потоки в сетях. Теорема Форда — Фалкерсона на Mini-Soft.ru