Задача. Есть дом, вода из которого стекает в реку по водопроводу. Водопровод — это набор однонаправленных труб, концы которых соединены с домом, рекой или одним из $n$ соединительных узлов. Также для каждой трубы известна ее прочность — сколько воды она может выдержать. Необходимо найти максимальный объем воды, который может вытекать из дома в единицу времени.
Поставим задачу более формально. Есть граф в котором выделены две вершины, соответствующие дому $s$ и реке $t$, а остальные вершины соответствуют узлам. Ребра этого графа соответствуют трубам водопровода, и у каждого ребра есть пропускная способность — максимальное количество воды, которое может по нему течь. Обозначим за $c(v, u)$ пропускную способность ребра из $v$ в $u$, а $f(v, u)$ — количество воды, текущее по нему.
Заметим некоторые свойства воды, текущей в водопроводе. Например, для любой вершины, которая соответствует узлу, объем втекающей в неё воды равен объему вытекающей из неё воды:
$$ \sum_u f(u, v) = \sum_u f(v, u) $$Это значит, что вода не может появится из ниоткуда и исчезнуть в никуда.
Также удобно считать, что у любого ребра есть ровно одно обратное, и $f(v, u) = -f(u, v)$, то есть если по ребру из $v$ в $u$ перетекает $x$ потока, то по ребру из $u$ в $v$ перетекает $-x$ потока.
Теперь замечание о втекающем и вытекающем объеме звучит так, что для любой вершины $v$, кроме истока $s$ и стока $t$:
$$ \sum_u f(v, u) = 0 $$ Наша задача тогда — это найти такую функцию $f$, максимизирующую $\sum f(s, u) = \sum f(u, t)$, удовлетворяющую предыдущим равенствам, и при этом не превышающая ни одну пропускную способность: $$ f(v, u) \leq c(v, u) $$ Эта сложная задача имеет множество решений, которые мы разберем в этой главе.