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

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

Определения

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

Предпотоком (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|;

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

pushRelabelMaxFlow(s, t)
    initialazePreflow(s);
    while существует применимая операция push или relabel
        выбрать операцию и выполнить ее

Корректность алгоритма

Для доказательства корректности алгоритма докажем несколько вспомогательных лемм.

Лемма (1):

Во время выполнения алгоритма [math] pushRelabelMaxFlow [/math] никакие свойства высоты не нарушаются.

Доказательство:

[math]\triangleright[/math]

Доказательство проведем по числу выполненных операций проталкивания и подъема. Для начала покажем, что после выполнения операции [math] initialazePreflow [/math] [math] h [/math] является функцией высоты. Для всех ребер, не инцидентных [math] s [/math], высота обоих концов равна нулю, что удовлетворяет условиям. Единственными ребрами [math] (u, v) [/math], для которых не выполняются условия, налагаемые на функцию высоты, то есть для которых [math] h(u) \gt h(v) + 1 [/math], являются ребра, у которых [math] u = s [/math]. Но после операции [math] initialazePreflow [/math] ребра являются насыщенными и не принадлежат остаточной сети. Это будет базой нашей индукции. Теперь докажем переход: если перед выполнением операции проталкивания или подъема [math] h [/math] является функцией высоты, то и после выполнения операции она останется функцией высоты. Для этого рассмотрим проталкивание и подъем отдельно. Покажем, что после окончания операции проталкивания утверждение верно. После выполнения операции [math] push(u, v) [/math] в [math] E_f [/math] может появиться ребро [math] (v, u) [/math], если до операции по ребру [math] (u, v) [/math] протекал нулевой поток, или же ребро [math] (u, v) [/math] может насытиться, и тогда оно перестанет принадлежать остаточной сети. В первом случае [math] h(v) = h(u) - 1 \lt h(u) + 1 [/math], и, следовательно, [math] h [/math] остается функцией высоты. Во втором же случае при удалении ребра [math] (u, v) [/math] из остаточной сети происходит лишь удаление соответствующих ограничений на высоты [math] u [/math] и [math] v [/math], так что [math] h [/math] остается функцией высоты. Теперь рассмотрим операцию подъема вершины [math] u [/math]. По определению данной операции гарантируется, что после ее выполнения для любого ребра [math] (u, v) \in E_f [/math] выполняется условие [math] h(u) \leqslant h(v) + 1 [/math], то есть все выходящие ребра удовлетворяют условиям, накладываемым на функцию высоты. Рассмотрим какое-то входящее ребро [math] (w, u) [/math]. Так как до операции [math] h [/math] являлась функцией высоты, то справедливо [math] h(w) \leqslant h(u) + 1 [/math]. После подъема высота вершины [math] u [/math] увеличивается как минимум на единицу, следовательно, после выполнения данной операции [math] h(w) \lt h(u) + 1 [/math]. Таким образом, [math] h [/math] и после выполнения операции [math] relabel(u) [/math] остается функций высоты.

[math]\triangleleft[/math]

Лемма (2):

Пусть [math] f [/math] — предпоток в сети [math] G [/math]. Тогда для любой переполненной вершины можно выполнить операцию проталкивания либо операцию подъема.

Доказательство:

[math]\triangleright[/math]

Рассмотрим вершину [math] u [/math], для которой [math] e(u) \gt 0 [/math]. Для любого ребра [math] (u, v) \in E_f [/math] справедливо [math] h(u) \leqslant h(v) + 1 [/math] по свойствам функции высоты. Если к вершине [math] u [/math] применима операция проталкивания, то лемма доказана. Иначе, для всех ребер [math] (u, v) \in E_f [/math] выполняется соотношение [math] h(u) \lt h(v) + 1 [/math]. Следовательно, [math] h(u) \leqslant h(v) [/math]. Но тогда данная вершина удовлетворяет условиям операции подъема, следовательно, к вершине [math] u [/math] можно применить эту операцию.

[math]\triangleleft[/math]

Лемма (3):

Пусть [math] G [/math] — сеть с истоком [math] s [/math] и стоком [math] t [/math]. [math] f [/math] и [math] h [/math] — предпоток и функция высоты соответственно. Тогда в остаточной сети [math] G_f [/math] нет пути из [math] s [/math] в [math] t [/math].

Доказательство:

[math]\triangleright[/math]

Докажем от противного. Предположим, что в [math] G_f [/math] существует путь из [math] s [/math] в [math] t [/math]. И пусть [math] p = \left \langle v_0, v_1, \dots, v_k \right \rangle [/math] — простой путь, где [math] v_0 = s [/math] и [math] v_k = t [/math]. Раз [math] p [/math] простой, то [math] k \lt \left\vert V \right\vert [/math]. Поскольку [math] h [/math] — функций высоты, то [math] \forall i \in \{0, 1, \dots, k - 1 \} [/math] справедливо [math] h(v_i) \leqslant h(v_{i+1}) + 1 [/math]. Следовательно, [math] h(s) \leqslant h(t) + k [/math]. А так как по определению функции высоты [math] h(t) = 0 [/math], то [math] h(s) \leqslant k \lt \left\vert V \right\vert [/math], что противоречит условию функции высоты, что [math] h(s) = \left\vert V \right\vert [/math].

[math]\triangleleft[/math]

Теорема:

Если алгоритм [math] pushRelabelMaxFlow [/math] завершается, то вычисленный им предпоток [math] f [/math] является максимальным потоком.

Доказательство:

[math]\triangleright[/math]

Для доказательства покажем, что перед каждой проверкой условия в цикле while [math] f [/math] является предпотоком. Перед началом цикла, после завершения операции [math] initializePreflow [/math], [math] f [/math] является предпотоком. Внутри цикла выполняются лишь операции проталкивания и подъема. Операция подъема не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъема не зависит, будет ли [math] f [/math] предпотоком. Операция [math] push(u, v) [/math] применяется, если [math] e(u) \gt 0 [/math], увеличивая поток через ребро [math] (u, v) [/math] на величину, не превышающую избыточный поток вершины [math] u [/math] и остаточную пропускную способность ребра [math] (u, v) [/math]. Следовательно, если перед выполнением операции проталкивания [math] f [/math] являлся предпотоком, то и после выполнения проталкивания [math] f [/math] останется предпотоком. После завершения алгоритма для каждой вершины [math] u \in V \setminus \{s, t\} [/math] справедливо, что [math] e(u) = 0 [/math], что следует непосредственно из леммы(1), леммы(2) и того, что перед выполнением операции проталкивания или подъема [math] f [/math] является предпотоком. Но тогда [math] f [/math] удовлетворяет условию сохранения потока, то есть сам является потоком. Поскольку из леммы(1) следует, что [math] h [/math] является функцией высоты и после завершения алгоритма, то по лемме(3) в остаточной сети [math] G_f [/math] нет пути из [math] s [/math] в [math] t [/math]. Но тогда по теореме Форда-Фалкерсона [math] f [/math] — максимальный поток.

[math]\triangleleft[/math]

Оценка быстродействия

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

Лемма (4):

Пусть [math] G [/math] — сеть со стоком [math] s [/math] и истоком [math] t [/math], и [math] f [/math] — предпоток в [math] G [/math]. Тогда из любой переполненной вершины [math] u [/math] существует путь в [math] s [/math] в остаточной сети [math] G_f [/math].

Доказательство:

[math]\triangleright[/math]

Докажем лемму методом от противного. Пусть для вершины [math] u [/math] верно, что [math] e(u) \gt 0 [/math]. Пусть также [math] U = \{v: u \leadsto v [/math] в [math] G_f \} [/math] и [math] \bar{U} = V \setminus U [/math]. Предположим, что [math] s \in \bar{U} [/math]. Покажем, что для любой пары вершин [math] v \in U [/math] и [math] w \in \bar{U} [/math] верно, что [math] f(w, v) \leqslant 0 [/math]. Если [math] f(w, v) \gt 0 [/math], то [math] f(v, w) \lt 0 [/math]. Но тогда из этого утверждения следует, что [math] c_f(v, w) = c(v, w) - f(v, w) \gt 0 [/math], что не может быть верным, так как в таком случае существует путь [math] u \leadsto v \to w [/math] в остаточной сети [math] G_f [/math], что противоречит выбору вершины [math] w [/math]. Следовательно, для каждой пары вершин [math] v \in U [/math] и [math] w \in \bar{U} [/math] верно, что [math] f(w, v) \leqslant 0 [/math]. Тогда верно и [math] f(\bar{U}, U) \leqslant 0 [/math]. Следовательно [math] e(U) = f(V, U) = f(U, U) + f(\bar{U}, U) = f(\bar{U}, U) \leqslant 0 [/math]. Но по определению избыток потока неотрицателен, из чего следует, что для любой вершины [math] v \in U [/math] [math] e(v) = 0 [/math], в том числе [math] e(u) = 0 [/math], что противоречит условию переполненности вершины [math] u [/math].

[math]\triangleleft[/math]

Лемма (5):

Пусть [math] G [/math] — сеть с истоком [math] s [/math] и стоком [math] t [/math]. Тогда во время выполнения алгоритма [math] pushRealbelMaxFlow [/math] для любой вершины [math] u [/math] в сети [math] G [/math] верно, что [math] h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 [/math]

Доказательство:

[math]\triangleright[/math]

По определению функции высоты [math] h(s) = \left\vert V \right\vert [/math] и [math] h(t) = 0 [/math], следовательно для истока и стока условие леммы выполнено. Рассмотрим вершину [math] u [/math] отличную от истока и стока. Изначально [math] h(u) = 0 \leqslant 2 \cdot \left\vert V \right\vert - 1 [/math]. Покажем, что после любой операции подъема [math] h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 [/math]. Для того, чтобы мы имели право произвести операцию [math] relabel(u) [/math], вершина [math] u [/math] должна быть переполнена. Тогда по лемме(4) существует простой путь [math] p [/math] из [math] u [/math] в [math] s [/math] в остаточной сети [math] G_f [/math]. Рассмотрим этот путь. Пусть [math] p = \left\langle v_0, v_1, \dots, v_k \right\rangle [/math], где [math] v_0 = u [/math] и [math] v_k = s [/math]. Так как путь [math] p [/math] простой, то [math] k \leqslant \left\vert V \right\vert - 1 [/math]. По определению функции высоты имеем, что [math] \forall i \in \{0, 1, \dots, k - 1\} [/math] [math] h(v_i) \leqslant h(v_{i+1}) + 1[/math]. Но тогда для вершин [math] u [/math] и [math] v [/math] верно, что [math] h(u) \leqslant h(s) + \left\vert V \right\vert - 1 = 2 \cdot \left\vert V \right\vert - 1 [/math]

[math]\triangleleft[/math]

На основании предыдущей леммы покажем верхнюю границу числа подъемов.

Лемма (6):

Пусть [math] G [/math] — сеть с истоком [math] s [/math] и стоком [math] t [/math]. Тогда во время выполнения алгоритма [math] pushRealbelMaxFlow [/math] общее число подъемов не превышает [math] 2 \cdot \left\vert V \right\vert ^2 [/math]

Доказательство:

[math]\triangleright[/math]

Так как высоты истока и стока не изменяются в процессе работы алгоритма, то только [math] \left\vert V \right\vert - 2 [/math] вершин могут быть подняты. Пусть [math] u \in V \setminus \{s, t\}[/math]. Изначально [math] h(u) = 0 [/math], и по лемме(5) известно, что [math] h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 [/math]. А так как при выполнении операции [math] relabel(u) [/math] высота вершины увеличивается как минимум на единицу, то максимальное количество подъемов вершины [math] u [/math] также не превышает [math] 2 \cdot \left\vert V \right\vert - 1 [/math]. Тогда суммарно число подъемов не превышает [math] (\left\vert V \right\vert - 2 ) \cdot (2 \cdot \left\vert V \right\vert - 1) \leqslant 2 \cdot \left\vert V \right\vert ^2 [/math].

[math]\triangleleft[/math]

Следующие две леммы показывают верхнюю границу количества проталкиваний.

Лемма (7):

Количество насыщающих проталкиваний при выполнение алгоритма [math] pushRealbelMaxFlow [/math] не превосходит [math] 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert [/math]

Лемма (8):

Количество ненасыщающих проталкиваний при выполнение алгоритма [math] pushRealbelMaxFlow [/math] не превосходит [math] 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) [/math]