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

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

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

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

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

Допустимое ребро (admissible edge) — ребро , у которого и . В противном случае называется недопустимым (inadmissible).

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

Допустимая сеть (admissible network) — сеть , где — множество допустимых ребер.

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

Допустимая сеть является ациклической.

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

Пусть в [math]G_{f, h}[/math] существует циклический путь , где [math]k \gt 0[/math].

для [math]i = 1, 2, \dots, k[/math], так как каждое ребро данного пути допустимое. Просуммировав равенства вдоль циклического пути, получаем:

Так как каждая вершина циклического пути встречается при суммировании по одному разу это значит то, что , что противоречит первоначальному предположению. Значит, допустимая сеть является ациклической.

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

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

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

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

Если выполненная операция является насыщающим проталкиванием, то после ее выполнения и ребро становится недопустимым.

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

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

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

Рассмотрим вершину [math]u[/math]. Если [math]u[/math] переполнена, то, согласно лемме (2), к ней может быть применима либо операция проталкивания, либо операция подъема. А так как не существует допустимых ребер для [math]u[/math], то протолкнуть поток не возможно, значит, применяется операция [math]relabel(u)[/math]. После данного подъема . Значит, если [math]u[/math] — вершина указанного множества, в которой реализуется минимум, то [math](u, v)[/math] становится допустимым. А это значит, что после подъема существует хотя бы одно допустимое ребро, выходящее из [math]u[/math].

Пусть существует такая вершина , после подъема, что ребро допустимо. Тогда , значит, перед подъемом . Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных сетей. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро не может находится в допустимой сети, так как оно не принадлежит остаточной сети.

Идея

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

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

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

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

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

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]

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

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

Лемма:

Когда операция вызывает в операцию , то для пары вершин применима операция проталкивания.

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

Проверки операции , сделанные до вызова операции проталкивания, гарантируют то, что операция будет вызвана только тогда, когда она применима. То есть , и .

Лемма:

Когда операция вызывает в операцию , то для вершины применим подъем.

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

Из леммы об изменении допустимой цепи (для операции relabel) и условия [math]e(u) \gt 0[/math] следует, что для доказательства данной леммы необходимо показать, что все ребра выходящие из [math]u[/math], являются недопустимыми.

Каждый проход операции начинается с головы списка и оканчивается, когда . Именно тогда вызывается и начинается новый проход. К концу прохода все ребра, выходящие из , станут недопустимыми. Так как из леммы об изменении допустимой цепи (для операции push) следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина не подвергается подъему во время прохода, а любая другая вершина , для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из леммы об изменении допустимой цепи (для операции relabel). Значит, в конце прохода все ребра, выходящие из , останутся недопустимыми.