Теорема о максимальном потоке и минимальном разрезе — как её понять и доказать?

Разрез $(S,T)$ — это разбиение вершин на две части так, что $s \in S$, $t \in T$. Пропускная способность разреза — это сумма пропускных способностей рёбер, идущих из $S$ в $T$ (обратные не считаем). Минимальный разрез — разрез наименьшей пропускной способности.

Теорема (Форд-Фалкерсон): величина максимального потока равна пропускной способности минимального разреза.

Набросок доказательства через три эквивалентных утверждения:

1. $f$ максимален $\Rightarrow$ в остаточной сети нет пути $s\to t$. Если бы путь был, можно увеличить поток — противоречие.
2. Нет пути $s\to t$ в остаточной сети $\Rightarrow$ существует разрез величины $|f|$. Возьмём $S$ = множество вершин, достижимых из $s$ в остаточной сети. Тогда $t\in T$. Все рёбра из $S$ в $T$ насыщены (иначе была бы остаточная пропускная и достижимость), а все рёбра из $T$ в $S$ несут нулевой поток. Значит поток через разрез = сумма пропускных рёбер $S\to T$ = пропускная этого разреза.
3. Любой поток $\le$ любой разрез (слабая двойственность): поток через любой разрез равен $|f|$, и он $\le$ пропускной разреза.

Из (1)+(2): нашли разрез величины $|f|$. Из (3): $|f| \le$ min-cut. Значит этот разрез минимальный, а поток максимальный.

Зачем на олимпиаде: многие задачи на «минимальную стоимость разделить/разбить» сводятся к минимальному разрезу, который считается как максимальный поток. Project selection, image segmentation, минимальное вершинное покрытие в двудольном — всё это min-cut в маскировке.