Задача о максимальном потоке

Рассмотрим следующую задачу:

Есть дом, вода из которого стекает в реку по водопроводу. Водопровод - это набор однонаправленных труб, концы которых соединены с домом, рекой или одним из n соединительных узлов. Также для каждой трубы известна ее прочность - сколько воды в ней она может выдержать. Необходимо найти максимальный объем воды, который может вытекать из дома.

Поставим задачу более формально, есть граф в котором выделены две вершины, соответствующие дому и реке, а остальные вершины соответствуют узлам. Ребра этого графа соответствуют трубам водопровода, и у каждого ребра есть ограничение на количество воды, которое может по нему течь. Обозначим за $c(v, u) -$ прочность трубы из $v$ в $u$. А $f(v, u) -$ количество воды, текущее по ребру из $v$ в $u$.

Заметим некоторые свойства воды, текущей в водопроводе. Например, для любой вершины, которая соответствует узлу, объем втекающей в неё воды равен объему вытекающей из неё воды. Также удобно считать, что $f(v, u) = -f(u, v)$, то есть если по ребру из $v$ в $u$ перетекает $x$ потока, то по ребру из $u$ в $v$ перетекает $-x$ потока. Теперь замечание о втекающем и вытекающем объеме звучит так: для любой вершины $v$, кроме истока и стока(в данной выше формулировке это дом и река соответственно), вода, вытекающая из $v$, равна $0$. Это значит, что вода не может появится из ниоткуда и исчезнуть в никуда.

Основные определения

Определение:
Сеть —это ориентированный граф $G = (V, E)$, в котором выделены две вершины s, t $-$ исток и сток, а так же функция $c(v, u)$, которая переводит ребра в неотрицательные числа

Определение:
Поток —это функция $f(v, u)$ переводящая ребра сети $G$ в действительные числа и обладающая следующими свойствами:

$f(v, u) = -f(u, v)$ - антисимметричность
$\forall v \in V \setminus \{s, t\} \sum\limits_{u \in V} = 0$ - сохранение потока
$f(v, u) \leq c(v, u)$ - ограничение пропускной способности

Для более удобной записи суммы вида $\sum\limits_{v \in A}\sum\limits_{u \in B} f(v, u)$ можно записать как $f(A, B)$, аналогично определим $c(A, B)$

Определение:
Величина потока —это $|f| = f(s, V) = \sum\limits_{u \in V}f(s, u)$

Определение:
Остаточная сеть —это такая сеть $G_f$, порожденная потоком $f$ в сети $G$, что $\forall{(v, u)}: c_f(v, u) = c(v, u) - f(v, u)$

Определение:
Увеличивающий путь —это путь $P$ из $s$ в $t$, что $\forall{(v, u)} \in P: c(v, u) > 0$

Определение:
$s-t$ разрез —это разбиение вершин сети $G$ на два множества $S$ и $T$, что выполняются следующий свойства:

$S \cap T \equiv \emptyset$
$S \cup T \equiv V$
$s \in S, t \in T$

Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana