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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Операция разгрузки (discharged))
(Операция разгрузки (discharge))
Строка 23: Строка 23:
 
На первую вершину в списке указывает указатель <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[u]</tex>.
+
Для каждой вершины <tex>u</tex> указатель <tex>current[u]</tex> - указатель на текущую вершину списка. Изначально <tex>current[u] = head[N[u]]</tex>.
  
 
  '''discharge'''(u)
 
  '''discharge'''(u)
Строка 38: Строка 38:
  
 
Докажем то, что когда операция '''discharge''' вызывает операции [[Метод проталкивания предпотока#Проталкивание (push)|push]] и [[Метод проталкивания предпотока#Подъем (relabel)|relable]], эти операции применимы.
 
Докажем то, что когда операция '''discharge''' вызывает операции [[Метод проталкивания предпотока#Проталкивание (push)|push]] и [[Метод проталкивания предпотока#Подъем (relabel)|relable]], эти операции применимы.
 +
 +
{{Лемма
 +
|id = Лемма1
 +
|statement =
 +
Когда операция <tex>discharge</tex> вызывает в операцию <tex>push</tex>, то для пары вершин <tex>(u, v)</tex> применима операция проталкивания.
 +
|proof =
 +
Проверки операции <tex>discharge</tex>, сделанные до вызова операции проталкивания, гарантируют то, что операция <tex>push</tex> будет вызвана только тогда, когда она применима. То есть <tex>e(u) > 0</tex>, <tex>c_{f}(u, v) > 0</tex> и <tex>h(u) = h(v) + 1</tex>.
 +
}}
  
 
== Схема алгоритма ==
 
== Схема алгоритма ==

Версия 23:02, 26 декабря 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] - множество допустимых ребер.


Идея

Операция разгрузки (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[/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]

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

Анализ

Источники