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

2013-01-06T14:24:23Z

91.203.168.223: /* Операция разгрузки (discharge) */

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

== Допустимые ребра ==
<tex>G = (V, E)</tex> {{---}} [[Определение сети, потока#Определение сети|сеть]] с истоком <tex>s</tex> и стоком <tex>t</tex>, <tex>f</tex> {{---}} [[Метод проталкивания предпотока#Определения|предпоток]] в <tex>G</tex>, <tex>h</tex> {{---}} [[Метод проталкивания предпотока#Определения|функция высоты]].
{{Определение
|definition=
'''Допустимое ребро (admissible edge)''' {{---}} ребро <tex>uv</tex>, у которого <tex>c_{f}(u, v) > 0</tex> и <tex>h(u) = h(v) + 1</tex>. В противном случае <tex>uv</tex> называется '''недопустимым (inadmissible)'''.
}}

{{Определение
|definition=
'''Допустимая сеть (admissible network)''' {{---}} сеть <tex>G_{f, h} = (V, E_{f, h})</tex>, где <tex>E_{f, h}</tex> {{---}} множество допустимых ребер.
}}

{{Лемма
|id = Лемма1
|about = Допустимая сеть является ациклической
|statement =
Допустимая сеть <tex>G_{f, h} = (V, E_{f, h})</tex> является ациклической.
|proof =
Пусть в <tex>G_{f, h}</tex> существует [[Основные определения теории графов|циклический путь]] <tex>p = \left \langle v_0, v_1, \dots, v_k \right \rangle</tex>, где <tex>k > 0</tex>.

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

<tex>\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</tex>

Так как каждая вершина циклического пути <tex>p</tex> встречается при суммировании по одному разу это значит то, что <tex>k = 0</tex>, что противоречит первоначальному предположению. Значит, допустимая сеть является ациклической.
}}

{{Лемма
|id = Лемма2
|about = Об изменении допустимой цепи с помощью операции проталкивания
|statement =
Если вершина <tex>u</tex> переполнена и ребро <tex>(u, v)</tex> допустимое, то применяемая операция <tex>push(u, v)</tex> не создает новые допустимые ребра, но может привести к тому, что ребро <tex>(u, v)</tex> станет недопустимым.
|proof =
Так как ребро <tex>(u, v)</tex> допустимое то, по определению допустимого ребра, из <tex>u</tex> в <tex>v</tex> можно протолкнуть поток. Из-за того что <tex>u</tex> {{---}} переполнена, вызываем операцию <tex>push(u, v)</tex>. В результате выполнения операции может быть создано остаточное ребро <tex>(u, v)</tex>. Так ребро <tex>(u, v)</tex> допустимое то, <tex>h[v] = h[u] - 1</tex>, а это значит, что ребро <tex>(v, u)</tex> не может стать допустимым.

Если выполненная операция <tex>push(u, v)</tex> является насыщающим проталкиванием, то после ее выполнения <tex>c_{f}(u, v) = 0</tex> и ребро <tex>(u, v)</tex> становится недопустимым.
}}

{{Лемма
|id = Лемма3
|about = Об изменении допустимой цепи с помощью операции подъема
|statement =
Если вершина <tex>u</tex> переполнена, и не имеется допустимых ребер, выходящих из <tex>u</tex>, то применяется операция <tex>relabel(u)</tex>. После подъема появляется по крайней мере одно допустимое ребро, выходящее из <tex>u</tex>, но нет допустимых ребер, входящих в <tex>u</tex>.
|proof =
Рассмотрим вершину <tex>u</tex>. Если <tex>u</tex> переполнена, то, согласно [[Метод проталкивания предпотока#Лемма2|лемме (2)]], к ней может быть применима либо операция проталкивания, либо операция подъема. А так как не существует допустимых ребер для <tex>u</tex>, то протолкнуть поток не возможно, значит, применяется операция <tex>relabel(u)</tex>. После данного подъема <tex>h[u] = 1 + min \{ h[v]: (u, v) \in E_{f} \}</tex>. Значит, если <tex>u</tex> {{---}} вершина указанного множества, в которой реализуется минимум, то <tex>(u, v)</tex> становится допустимым. А это значит, что после подъема существует хотя бы одно допустимое ребро, выходящее из <tex>u</tex>.

Пусть после подъема существует такая вершина <tex>u</tex>, что ребро <tex>(u, v)</tex> допустимо. Тогда <tex>h[v] = h[u] + 1</tex>, значит, перед подъемом <tex>h[v] > h[u] + 1</tex>. Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных сетей. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро <tex>(v, u)</tex> не может находится в допустимой сети, так как оно не принадлежит остаточной сети.
}}

== Операция разгрузки (discharge) ==
{{Определение
|definition=
'''Разгрузка (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>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>.

'''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]

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

Докажем то, что когда операция '''discharge''' вызывает операции [[Метод проталкивания предпотока#Проталкивание (push)|push]] и [[Метод проталкивания предпотока#Подъем (relabel)|relable]], эти операции применимы.

{{Лемма
|about = О применимости операции push
|id = Лемма4
|statement =
Когда операция <tex>discharge</tex> вызывает в операцию <tex>push(u, v)</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>.
}}

{{Лемма
|about = О применимости операции relabel
|id = Лемма5
|statement =
Когда операция <tex>discharge</tex> вызывает в операцию <tex>relabel(u)</tex>, то для вершины <tex>u</tex> применим подъем.
|proof =
Из [[Алгоритм "поднять-в-начало"#Лемма3|леммы об изменении допустимой цепи (для операции relabel)]] и условия <tex>e(u) > 0</tex> следует, что для доказательства данной леммы необходимо показать, что все ребра выходящие из <tex>u</tex>, являются недопустимыми.

Каждый проход операции <tex>discharge(u)</tex> начинается с головы списка <tex>N[u]</tex> и оканчивается, когда <tex>current[u] = null</tex>. Именно тогда вызывается <tex>relabel(u)</tex> и начинается новый проход. К концу прохода все ребра, выходящие из <tex>u</tex>, станут недопустимыми, так как из [[Алгоритм "поднять-в-начало"#Лемма2|леммы об изменении допустимой цепи (для операции push)]] следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина <tex>u</tex> не подвергается подъему во время прохода, а любая другая вершина <tex>v</tex>, для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из [[Алгоритм "поднять-в-начало"#Лемма3|леммы об изменении допустимой цепи (для операции relabel)]]. Значит, в конце прохода все ребра, выходящие из <tex>u</tex>, останутся недопустимыми.
}}

== Алгоритм ==
Инициализируем предпоток и высоты, с помощью операции [[Метод проталкивания предпотока#Схема алгоритма|initializePreflow]], список <tex>L</tex> {{---}} список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель <tex>current</tex> каждой вершины <tex>u</tex>, чтобы он указывал на первую вершину в списке <tex>u</tex>.

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

'''relabelToFront(s, t)'''
initializePreflow(s)
L = V / {s, t}
'''for''' u <tex>\in</tex> 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]

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

<tex>nextVartex[u]</tex> возвращает вершину, следующую за <tex>u</tex> в списке <tex>L</tex>. Если <tex>u</tex> {{---}} последняя вершина в списке, то <tex>nextVartex[u] = null</tex>.

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

== Корректность алгоритма ==
Для доказательства корректности алгоритма, то есть чтобы показать что операция <tex>relabelToFront</tex> вычисляет поток, покажем, что она является реализацией универсального алгоритма [[Метод проталкивания предпотока|проталкивания предпотока]]. Для начала, заметим, что она выполняет операции <tex>push</tex> и <tex>relabel</tex> только тогда, когда они применимы, следует из [[Алгоритм "поднять-в-начало"#Лемма4|лемм о применимости операций push и relabel]]. Покажем, что когда операция <tex>relabelToFront</tex> завершится, не применима ни одна основная операция. Для этого подробно рассмотрим операцию <tex>relabelToFront</tex>:

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

== Оценка быстродействия ==
{{Теорема
|statement =
Время выполнения операции <tex>relabelToFront</tex> для любой сети <tex>G = (V, E)</tex> составляет <tex>O(V^{3})</tex>.
|proof =
Пусть '''фаза''' {{---}} время между двумя последовательными операциями подъема. Так как всего, по [[Метод проталкивания предпотока#Лемма6|лемме (6)]], выполняется <tex>O(V^{2})</tex> подъемов, значит, в алгоритме всего <tex>O(V^{2})</tex> фаз.

Если операция <tex>discharge</tex> не выполняет подъем, то следующий ее вызов происходит дальше по списку <tex>L</tex> <tex>(</tex>длина <tex>L</tex> меньше <tex>|V|)</tex>. Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более <tex>|V|</tex> вызовов <tex>discharge</tex>.

Таким образом, цикл '''while''' процедуры <tex>relabelToFront</tex> выполняет работу (без учета операций вызываемых в <tex>discharge</tex>), за <tex>O(V^{3})</tex>.

Оценим работу выполнения внутри операции <tex>discharge</tex>:

#Обновление указателя <tex>current[u]</tex> выполняется <tex>O(deg(u))</tex> в том случае, когда вершина <tex>u</tex> подвергается подъему. Значит, для всех вершин время составляет <tex>O(V deg(u))</tex>. Следовательно, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], время равно <tex>O(VE)</tex>.
#Пусть <tex>u</tex> {{---}} произвольная вершина сети. Она может быть поднята не более <tex>O(V)</tex> раз, время каждого подъема <tex>O(deg(u))</tex>. Значит, время всех подъемов ограничивается <tex>O(VE)</tex>.
#Из [[Метод проталкивания предпотока#Лемма8|леммы (8)]] следует, что количество насыщающих проталкиваний составляет <tex>O(VE)</tex>. Ненасыщающее проталкивание уменьшает избыток до <tex>0</tex>, после чего разрядка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов <tex>discharge</tex>, то есть <tex>O(V^{3})</tex>.

Таким образом, время выполнения операции <tex>relabelToFront</tex> составляет <tex>O(V^{3} + VE)</tex>, что эквивалентно <tex>O(V^{3})</tex>.
}}

== Источники ==
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785.
* [http://ru.wikipedia.org/wiki/Алгоритм_проталкивания_предпотока Алгоритм проталкивания предпотока — Википедия]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]

Викиконспекты - Вклад участника [ru]

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