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

Алгоритм "поднять-в-начало" (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) - ребро [math]uv[/math], у которого [math]c_{f}(u, v) \gt 0[/math] и [math]h(u) = h(v) + 1[/math]. В противном случае [math]uv[/math] называется недопустимым (inadmissible).

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

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

Операция разгрузки (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) > 0 and h[u] = h[v] + 1
                push(u, v)
            else
                current[u] = next[v]

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

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

Источники

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