Алгоритм "поднять-в-начало"

Алгоритм "поднять-в-начало" (relabel-to-front) основан на методе проталкивание предпотока, но из-за тщательного выбора порядка выполнения операций проталкивания и подъема, время выполнения данного алгоритма составляет $O(V^{3})$, что асимптотически не хуже, чем $O(V^{2}E)$.

Допустимые ребра

$G = (V, E)$ — сеть с истоком $s$ и стоком $t$, $f$ — предпоток в $G$, $h$ — функция высоты.

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

Допустимое ребро (admissible edge) — ребро $uv$, у которого $c_{f}(u, v) \gt 0$ и $h(u) = h(v) + 1$. В противном случае $uv$ называется недопустимым (inadmissible).

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

Допустимая сеть (admissible network) — сеть $G_{f, h} = (V, E_{f, h})$, где $E_{f, h}$ — множество допустимых ребер.

Лемма (Допустимая сеть является ациклической):

Допустимая сеть $G_{f, h} = (V, E_{f, h})$ является ациклической.

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

$\triangleright$

Пусть в $G_{f, h}$ существует циклический путь $p = \left \langle v_0, v_1, \dots, v_k \right \rangle$, где $k \gt 0$. $~ ~ h(v_{i - 1}) = h(v_{i}) + 1$ для $i = 1, 2, \dots, k$, так как каждое ребро данного пути допустимое. Просуммировав равенства вдоль циклического пути, получаем: $\sum \limits_{i = 1}^{k} h(v_{i - 1}) = \sum \limits_{i = 1}^{k} (h(v_{i}) + 1) = \sum \limits_{i = 1}^{k} h(v_{i}) + k$ Так как каждая вершина циклического пути $p$ встречается при суммировании по одному разу это значит то, что $k = 0$, что противоречит первоначальному предположению. Значит, допустимая сеть является ациклической.

$\triangleleft$

Лемма (Об изменении допустимой цепи, с помощью операции проталкивания):

Если вершина $u$ переполнена и ребро $(u, v)$ допустимое, то применяемая операция $push(u, v)$ не создает новые допустимые ребра, но может привести к тому, что ребро $(u, v)$ станет недопустимым.

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

$\triangleright$

Так как ребро $(u, v)$ допустимое то, по определению допустимого ребра, из $u$ в $v$ можно протолкнуть поток. Из-за того что $u$ — переполнена, вызываем операцию $push(u, v)$. В результате выполнения операции может быть создано остаточное ребро $(u, v)$. Так ребро $(u, v)$ допустимое то, $h[v] = h[u] - 1$, а это значит, что ребро $(v, u)$ не может стать допустимым. Если выполненная операция $push(u, v)$ является насыщающим проталкиванием, то после ее выполнения $c_{f}(u, v) = 0$ и ребро $(u, v)$ становится недопустимым.

$\triangleleft$

Лемма (Об изменении допустимой цепи, с помощью операции подъема):

Если вершина $u$ переполнена и не имеется допустимых ребер, выходящих из $u$, то применяется операция $relabel(u)$. После подъема появляется по крайней мере одно допустимое ребро, выходящее из $u$, но нет допустимых ребер, входящих в $u$.

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

$\triangleright$

Рассмотрим вершину $u$. Если $u$ переполнена, то, согласно лемме (2), к ней может быть применима либо операция проталкивания, либо операция подъема. А так как не существует допустимых ребер для $u$, то протолкнуть поток не возможно, значит, применяется операция $relabel(u)$. После данного подъема $h[u] = 1 + min \{ h[v]: (u, v) \in E_{f} \}$. Значит, если $u$ — вершина указанного множества, в которой реализуется минимум, то $(u, v)$ становится допустимым. А это значит, что после подъема существует хотя бы одно допустимое ребро, выходящее из $u$. Пусть существует такая вершина $u$, после подъема, что ребро $(u, v)$ допустимо. Тогда $h[v] = h[u] + 1$, значит, перед подъемом $h[v] \gt h[u] + 1$. Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных сетей. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро $(v, u)$ не может находится в допустимой сети, так как оно не принадлежит остаточной сети.

$\triangleleft$

Операция разгрузки (discharge)

Разгрузка (discharge) — операция, которая применяется к переполненной вершине $u$, для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая $u$, делая недопустимые ребра, выходящие из вершины $u$, допустимыми.

Будем хранить для каждой вершины $u$ список $N[u]$ (список вершин смежных с ней). То есть список $N[u]$ содержит каждую вершину $v$ такую, что в сети $G = (V, E) ~ (u, v) \in E$ или $(v, u) \in E$.

На первую вершину в списке указывает указатель $head[N[u]]$. Для перехода к следующей вершине в списке за $w$, поддерживается указатель $next[w]$. Он равен $null$, если $w$ — последняя вершина в списке.

Для каждой вершины $u$ указатель $current[u]$ — указатель на текущую вершину списка. Изначально $current[u] = head[N[u]]$.

discharge(u)
    while e[u] > 0
        v = current[u]
        if v = null
            relabel(u)
            current[u] = head[N[u]]
        else
            if c(u, v) - f(u, v) > 0 and h[u] = h[v] + 1
                push(u, v)
            else
                current[u] = next[v]

Операция завершится только тогда, когда избыток $e(u)$ станет равным нулю, и ни подъем, ни перемещение указателя $current[u]$ не влияет на значение $e(u)$.

Докажем то, что когда операция discharge вызывает операции push и relable, эти операции применимы.

Лемма (О применимости операции push):

Когда операция $discharge$ вызывает в операцию $push(u, v)$, то для пары вершин $(u, v)$ применима операция проталкивания.

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

$\triangleright$

Проверки операции $discharge$, сделанные до вызова операции проталкивания, гарантируют то, что операция $push$ будет вызвана только тогда, когда она применима. То есть $e(u) \gt 0$, $c_{f}(u, v) \gt 0$ и $h(u) = h(v) + 1$.

$\triangleleft$

Лемма (О применимости операции relabel):

Когда операция $discharge$ вызывает в операцию $relabel(u)$, то для вершины $u$ применим подъем.

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

$\triangleright$

Из леммы об изменении допустимой цепи (для операции relabel) и условия $e(u) \gt 0$ следует, что для доказательства данной леммы необходимо показать, что все ребра выходящие из $u$, являются недопустимыми. Каждый проход операции $discharge(u)$ начинается с головы списка $N[u]$ и оканчивается, когда $current[u] = null$. Именно тогда вызывается $relabel(u)$ и начинается новый проход. К концу прохода все ребра, выходящие из $u$, станут недопустимыми. Так как из леммы об изменении допустимой цепи (для операции push) следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина $u$ не подвергается подъему во время прохода, а любая другая вершина $v$, для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из леммы об изменении допустимой цепи (для операции relabel). Значит, в конце прохода все ребра, выходящие из $u$, останутся недопустимыми.

$\triangleleft$

Алгоритм

Инициализируем предпоток и высоты, с помощью операции initializePreflow, список $L$ — список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель $current$ каждой вершины $u$, чтобы он указывал на первую вершину в списке $u$.

Пройдем по списку $L$ разгружая вершины, начиная с первой вершины. И если операция $discharge$ изменила высоту вершины, то перемещаем ее в начало списка $L$. Передвинем указатель на следующую вершину списке $L$, если после разгрузки была изменена высота, то берем следующую вершину в новом списке $L$.

 relabelToFront(s, t)
     initializePreflow(s)
     L = V / {s, t}
     for u $\in$ V / {s, t}
         current[u] = head[N[u]]
     u = head[L]
     while u != null
         oldHeight = h[u]
         discharge(u)
         if h[u] > oldHeight
             передвинуть u в начало списка L
         u = nextVartex[u]

В приведенном псевдокоде предполагается, что для каждой вершины $u$ уже создан список $N[u]$.

$nextVartex[u]$ возвращает вершину, следующую за $u$ в списке $L$. Если $u$ — последняя вершина в списке, то $nextVartex[u] = null$.

Инвариант цикла: "при каждом выполнении проверки условия вхождения в цикл while, список $L$ является топологическим упорядочением вершин допустимой сети $G_{f, h} = (V, E_{f, h})$, и ни одна вершина, стоящая в списке перед $u$, не имеет избыточного потока".

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

Для доказательства корректности алгоритма, то есть чтобы показать что операция $relabelToFront$ вычисляет поток, покажем, что она является реализацией универсального алгоритма проталкивания предпотока. Для начала, заметим, что она выполняет операции $push$ и $relabel$ только тогда, когда они применимы, следует из лемм о применимости операций push и relabel. Покажем, что когда операция $relabelToFront$ завершится, не применима ни одна основная операция. Для этого подробно рассмотрим операцию $relabelToFront$:

1. После вызова $initializePreflow$ $h[s] = |V|$ и $h[u] = 0$ для всех $u \in V / {s}$. Так как $|V| \ge 2$, то ни одно ребро не является допустимым. Значит, $E_{f, h} = \varnothing$ и любой порядок множества $V \setminus \{s, t\}$ является топологическим упорядочением $G_{f, h}$.
2. Проверим, что топологическое упорядочение сохранится при проведении итераций цикла while. Для начала заметим, что сеть может изменится только из-за операций проталкивания и подъема. Из леммы об изменении допустимой цепи нам известно, что после операции проталкивания новые допустимые ребра не появляются, а это значит, что они могли появится только во время выполнения операции подъема. После того как для вершины $u$ применили операцию подъема больше не существует допустимых ребер, входящих в $u$, но могут быть допустимые ребра, выходящие из нее. Таким образом, перемещая $u$ в начало списка $L$, все допустимые ребра, выходящие из $u$, удовлетворяют условию топологического упорядочения.
3. Проверим, что ни одна вершина, предшествующая $u$ в списке $L$, не имеет избытка потока. Пусть вершина $u'$ — вершина $u$ на следующей итерации.
   1. Если $u$ подверглась подъему, то вершин предшествующих $u'$ на следующей итерации, кроме $u$, нет или если высота $u$ не изменилась, то там остались те же вершины, что и ранее. Так как $u$ подверглась разгрузке, то она не содержит избытка потока. Значит, если $u$ подверглась подъему в процессе разгрузки, то ни одна вершина, предшествующая $u'$, не содержит избытка потока.
   2. Если высота $u$ не поменялась, в процессе разгрузки, то вершины, стоящие в списке $L$ перед ней, не получили избыток потока, так как $L$ топологически упорядочен все время в процессе разгрузки, поэтому каждая операция проталкивания продвигает поток только по вершинам дальше по списку. В этом случае ни одна вершина, предшествующая $u'$, также не имеет избытка потока.
4. После завершения цикла $u = null$, поэтому избыток всех вершин равен $0$ (инвариант цикла). Значит, ни одна основная операция неприменима.

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

Теорема:

Время выполнения операции $relabelToFront$ для любой сети $G = (V, E)$ составляет $O(V^{3})$.

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

$\triangleright$

Пусть фаза — время между двумя последовательными операциями подъема. Так как всего, по лемме (6), выполняется $O(V^{2})$ подъемов, значит, в алгоритме всего $O(V^{2})$ фаз. Если операция $discharge$ не выполняет подъем, то следующий ее вызов происходит дальше по списку $L$ $($длина $L$ меньше $|V|)$. Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более $|V|$ вызовов $discharge$. Таким образом, цикл while процедуры $relabelToFront$ выполняет работу (без учета операций вызываемых в $discharge$), за $O(V^{3})$. Оценим работу выполнения внутри операции $discharge$: Обновление указателя $current[u]$ выполняется $O(deg(u))$ в том случае, когда вершина $u$ подвергается подъему. Значит, для всех вершин время составляет $O(V deg(u))$. Следовательно, согласно лемме о рукопожатиях, время равно $O(VE)$. Пусть $u$ — произвольная вершина сети. Она может быть поднята не более $O(V)$ раз, время каждого подъема $O(deg(u))$. Значит, время всех подъемов ограничивается $O(VE)$. Из леммы (8) следует, что количество насыщающих проталкиваний составляет $O(VE)$. Ненасыщающее проталкивание уменьшает избыток до $0$, после чего разрядка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов $discharge$, то есть $O(V^{3})$. Таким образом, время выполнения операции $relabelToFront$ составляет $O(V^{3} + VE)$, что эквивалентно $O(V^{3})$.

$\triangleleft$

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785.
• Алгоритм проталкивания предпотока — Википедия