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

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

Есть дом, вода из которого стекает в реку по водопроводу. Водопровод - это набор однонаправленных труб, концы которых соединены с домом, рекой или одним из 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$. Это значит, что вода не может появится из ниоткуда и исчезнуть в никуда. =='"`UNIQ--h-0--QINU`"'Основные определения== <div style="padding-top: 70px;margin-top:-70px;" id=".D0.A1.D0.B5.D1.82.D1.8C"></div> <div style="margin-left: 5px; border-left: solid 1px black; padding-left: 7px"> <u>''Определение:''</u><br>'''Сеть''' —это ориентированный граф $G = (V, E)$, в котором выделены две вершины s, t $-$ исток и сток, а так же функция $c(v, u)$, которая переводит ребра в неотрицательные числа </div> <div style="padding-top: 70px;margin-top:-70px;" id=".D0.9F.D0.BE.D1.82.D0.BE.D0.BA"></div> <div style="margin-left: 5px; border-left: solid 1px black; padding-left: 7px"> <u>''Определение:''</u><br>'''Поток''' —это функция $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)$ - ограничение пропускной способности </div> Для более удобной записи суммы вида $\sum\limits_{v \in A}\sum\limits_{u \in B}$ можно записать как $f(A, B)$, аналогично определим $c(A, B)$ <div style="padding-top: 70px;margin-top:-70px;" id=".D0.92.D0.B5.D0.BB.D0.B8.D1.87.D0.B8.D0.BD.D0.B0_.D0.BF.D0.BE.D1.82.D0.BE.D0.BA.D0.B0"></div> <div style="margin-left: 5px; border-left: solid 1px black; padding-left: 7px"> <u>''Определение:''</u><br>'''Величина потока''' —это '"`UNIQ--nowiki-00000000-QINU`"' </div> <div style="padding-top: 70px;margin-top:-70px;" id=".D0.9E.D1.81.D1.82.D0.B0.D1.82.D0.BE.D1.87.D0.BD.D0.B0.D1.8F_.D1.81.D0.B5.D1.82.D1.8C"></div> <div style="margin-left: 5px; border-left: solid 1px black; padding-left: 7px"> <u>''Определение:''</u><br>'''Остаточная сеть''' —это такая сеть $G_f$, порожденная потоком $f$ в сети $G$, что $\forall{(v, u)}: c_f(v, u) = c(v, u) - f(v, u)$ </div> <div style="padding-top: 70px;margin-top:-70px;" id=".D0.A3.D0.B2.D0.B5.D0.BB.D0.B8.D1.87.D0.B8.D0.B2.D0.B0.D1.8E.D1.89.D0.B8.D0.B9_.D0.BF.D1.83.D1.82.D1.8C"></div> <div style="margin-left: 5px; border-left: solid 1px black; padding-left: 7px"> <u>''Определение:''</u><br>'''Увеличивающий путь''' —это путь $P$ из $s$ в $t$, что $\forall{(v, u)} \in P: c_f(v, u) > 0$ </div> <div style="padding-top: 70px;margin-top:-70px;" id=".24s-t.24_.D1.80.D0.B0.D0.B7.D1.80.D0.B5.D0.B7"></div> <div style="margin-left: 5px; border-left: solid 1px black; padding-left: 7px"> <u>''Определение:''</u><br>'''$s-t$ разрез''' —это разбиение вершин сети $G$ на два множества $S$ и $T$, что выполняются следующий свойства: * $S \cap T \equiv \emptyset$ * $S \cup T \equiv V$ * $s \in S, t \in T$

---

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

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