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

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

Определения

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

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

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

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

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

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

Функция [math] h: V \rightarrow \mathbb{Z}_+[/math] называется высотой вершины (vertex label), если она удовлетворяет условиям: 1) [math] h(s) = \left\vert V \right\vert [/math] 2) [math] h(t) = 0 [/math] 3) [math] \forall (u, v) \in E_f \quad h(u) \leqslant h(v) + 1[/math]

Идея

Для понимания идеи алгоритма представим, что наша сеть — система из резервуаров, находящихся на определенной высоте, и соединяющих их труб с заданными пропускными способностями, соответствующих вершинам и ребрам в исходной сети. Сам алгоритм можно представить как процесс поочередного "переливания" жидкости (операция проталкивания) из одного резервуара в другие, находящиеся на меньшей высоте, до тех пор пока будет существовать резервуар, соответствующей переполненной вершине. Может случиться ситуация, что все трубы, выходящие из переполненной вершины [math] u [/math], ведут к вершинам, находящимся на такой же высоте что и [math] u [/math] или выше ее. В таком случае поднимем резервуар (операция подъема), соответствующий данной вершине, таким образом, чтобы его высота стала на единицу больше, чем высота самого низкого из смежных резервуаров. После подъема будет существовать по крайней мере одна труба, по которой можно попустить жидкость.

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

Операции

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

Проталкивание (push)

Операция проталкивания из вершины [math] u [/math] в вершину [math] v [/math] может применяться тогда, когда [math] e(u) \gt 0 [/math], то есть вершина [math] u [/math] является переполненной, [math] c_f(u, v) \gt 0 [/math] и [math] h(u) = h(v) + 1 [/math].

Данная операция работает следующим образом: по ребру [math] (u, v) [/math] пропускается максимально возможный поток, то есть минимум из избытка вершины [math] u [/math] и остаточной пропускной способности ребра [math] (u, v) [/math], вследствие чего избыток вершины [math] u [/math], остаточная пропускная способность ребра [math] (u, v) [/math] и поток по обратному ребру [math] (v, u) [/math] уменьшается на величину потока, а избыток вершины [math] v [/math], поток по ребру [math] (u, v) [/math] и остаточная пропускная способность обратного ребра [math] (v, u) [/math] увеличивается на эту же величину.

push(u, v)
    d = min(e(u), c(u, v) - f(u, v));
    f(u, v) += d;
    f(v, u) = -f(u, v);
    e(u) -= d;
    e(v) += d;

По своему результату все проталкивания можно разделить на 2 группы. Будем называть проталкивание из вершины [math] u [/math] в вершину [math] v [/math] насыщающим, если после него остаточная пропускная способность ребра [math] (u, v) [/math] стала равна нулю. Все остальные проталкивания будем называть ненасыщающими. Подобная классификация проталкиваний понадобится нам при оценке времени работы алгоритма.

Подъем (relabel)

Операция подъема применима для вершины [math] u [/math], если [math] e(u) \gt 0 [/math] и [math] \forall (u, v) \in E_f \quad h(u) \leqslant h(v) [/math].

То есть, для переполненной вершины [math] u [/math] применима операция подъема, если все вершины, для которых в остаточной сети есть ребра из [math] u [/math], расположены не ниже [math] u [/math]. Следовательно, операцию проталкивания для вершины [math] u [/math] произвести нельзя.

В результате подъема высота текущей вершины становится на единицу больше высоты самый низкой смежной вершины в остаточной сети, вследствие чего появляется как минимум одно ребро, по которому можно протолкнуть поток.

relabel(u)
    h(u) = min(h(v): f(u, v) - c(u, v) > 0) + 1;

Схема алгоритма

Для начала проинициализируем предпоток. Пропустим максимально возможный поток по ребрам, инцидентным стоку, увеличив избыточный поток для каждой смежной со стоком вершиной на соответствующую величину. Все остальные потока не несут, следовательно, для вершин не смежных с истоком избыточный поток изначально будет нулевым. Так же для всех вершин, кроме, естественно, истока, установим высоту, равную нулю.

Более формально это можно записать так:

[math] f(u, v) = \begin{cases} c(u, v), & u = s \\ -c(v, u), & v = s \\ 0, & u \neq s \text{ and } v \neq s \end{cases} [/math]

[math] h(u) = \begin{cases} \left\vert V \right\vert, & u = s \\ 0, & u \neq s \end{cases} [/math]

initialazePreflow(s)
    for [math] \forall u \in  V [/math]
        h(u) = 0;
        e(u) = 0;
    for [math] \forall (u, v) \in  E [/math]
        f(u, v) = 0;
        f(v, u) = 0;     
    for [math] \forall  u: (s, u) \in E [/math]
        f(s, u) = c(s, u);
        f(u, s) = -c(s, u);
        e(u) = c(s, u);
        e(s) -= c(s, u);
    h(s) = |V|;