Метод проталкивания предпотока

Метод проталкивая предпотока — обобщенный алгоритм нахождения максимального потока в транспортной сети. В отличии от алгоритма Эдмондса-Карпа и алгоритма Диница не является частным случаем метода Форда-Фалкерсона.

Определения

Определение:

Предпотоком (preflow) будем называть функцию [math] f: V \times V \rightarrow R [/math], удовлетворяющую следующим свойствам: 1) [math] f(uv) = -f(vu) [/math] (антисимметричность) 2) [math] f(uv) \leqslant c(uv) [/math] (ограничение пропускной способностью) 3) [math]\forall u \in V \setminus \{s, t\} \quad \sum\limits_{v \in V} f(vu) \geqslant 0 [/math] (ослабленное условие сохранения потока)

Как можно заметить, по своим свойствам предпоток очень похож на поток и отличается лишь тем, что для него не выполняется закон сохранения потока.

Определение:

Избыточным потоком (excess flow), входящим в вершину [math] u [/math], назовем величину [math] e(u) = \sum \limits_{v \in V} f(vu) [/math]. Тогда вершина [math] u \in V \setminus \{s, t\} [/math] будет называться переполненной, если [math] e(u) \gt 0 [/math].