Поиск максимального потока в транспортной сети

1 Постановка задачи

Транспортной сетью называется ориентированный граф $G = (V, E)$, каждому ребру $e \in E$ которого приписана неотрицательная пропускная способность $c(e) \ge 0$. Будем считать, что вместе с каждым ребром $e = (v, w) \in E$ граф содержит и обратное к нему $e^R = (w, v)$ (при необходимости приписывая ему нулевую пропускную способность).

Пусть в графе $G$ выделены две вершины: источник $s$ и сток $t$. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из $s$ в $t$. Потоком называется функция $f: E \to \mathbb{R}$, удовлетворяющая следующим требованиям:

• ограничение по пропускной способности: $f(e) \le c(e)$;
• антисимметричность: $f(e^R) = -f(e)$;
• закон сохранения потока:

$\forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e).$

Величиной потока называется суммарный поток из источника:

$\left \vert f \right \vert = \sum_{e = (s, v)} f(e).$

Задача о максимальном потоке в транспортной сети. Требуется найти поток максимальной величины:

$\left \vert f \right \vert \to \max.$

2 Свойства задачи

Суммарный поток из источника равен суммарному потоку в сток:

$\forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e).$

(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)

3 Варианты задачи

В зависимости от ограничений на значения пропускной способности:

• произвольная положительная пропускная способность;
• целая пропускная способность;
• единичная пропускная способность (в этом случае максимальный поток равен рёберной связности графа).

4 Алгоритмы решения задачи

• Алгоритм Форда-Фалкерсона и его варианты со сложностью $O(n^2m)$ (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих $K$, сложность $O(Km)$.
• Алгоритм проталкивания предпотока со сложностью $O(mn \ln n)$ (при использовании динамических деревьев Тарьяна-Слитора).

Обозначения: $m$ – число рёбер, $n$ – число вершин.