Алгоритм "поднять-в-начало" — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Допустимые ребра)
м (Операция разгрузки (discharge))
Строка 32: Строка 32:
  
 
== Операция разгрузки (discharge) ==
 
== Операция разгрузки (discharge) ==
'''Разгрузка (discharge)''' - операция, которая применяется к переполненной вершине <tex>u</tex>, для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая <tex>u</tex>, делая недопустимые ребра, выходящие из вершины <tex>u</tex>, допустимыми.
+
'''Разгрузка (discharge)''' {{---}} операция, которая применяется к переполненной вершине <tex>u</tex>, для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая <tex>u</tex>, делая недопустимые ребра, выходящие из вершины <tex>u</tex>, допустимыми.
  
 
Будем хранить для каждой вершины <tex>u</tex> список <tex>N[u]</tex> (список вершин смежных с ней). То есть список <tex>N[u]</tex> содержит каждую вершину <tex>v</tex> такую, что в сети <tex>G = (V, E) ~ (u, v) \in E</tex> или <tex>(v, u) \in E</tex>.  
 
Будем хранить для каждой вершины <tex>u</tex> список <tex>N[u]</tex> (список вершин смежных с ней). То есть список <tex>N[u]</tex> содержит каждую вершину <tex>v</tex> такую, что в сети <tex>G = (V, E) ~ (u, v) \in E</tex> или <tex>(v, u) \in E</tex>.  
  
На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex>null</tex> если <tex>w</tex> - последняя вершина в списке.
+
На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex>null</tex>, если <tex>w</tex> {{---}} последняя вершина в списке.
  
Для каждой вершины <tex>u</tex> указатель <tex>current[u]</tex> - указатель на текущую вершину списка. Изначально <tex>current[u] = head[N[u]]</tex>.
+
Для каждой вершины <tex>u</tex> указатель <tex>current[u]</tex> {{---}} указатель на текущую вершину списка. Изначально <tex>current[u] = head[N[u]]</tex>.
  
 
  '''discharge'''(u)
 
  '''discharge'''(u)

Версия 02:05, 27 декабря 2012

Алгоритм "поднять-в-начало" (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] — множество допустимых ребер.


Лемма (Допустимая сеть является ациклической):
Если [math]G = (V, E)[/math] — сеть с истоком [math]s[/math] и стоком [math]t[/math], [math]f[/math] — предпоток в [math]G[/math], а [math]h[/math] — функция высоты, тогда допустимая сеть [math]G_{f, h} = (V, E_{f, h})[/math] является ациклической.
Доказательство:
[math]\triangleright[/math]

Пусть в [math]G_{f, h}[/math] существует циклический путь [math]p = \left \langle v_0, v_1, \dots, v_k \right \rangle[/math], где [math]k \gt 0[/math].

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

[math]\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[/math]

Так как каждая вершина циклического пути [math]p[/math] встречается при суммировании по одному разу это значит то, что [math]k = 0[/math], что противоречит первоначальному предположению. Значит, допустимая сеть является ациклической.
[math]\triangleleft[/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] применим подъем.

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

Анализ

Источники