Изменения
→Источники информации
'''Разгрузка''' (англ. ''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) ~ </tex> ребро <tex>(u, v) \in E</tex> или <tex>(v, u) \in E</tex>.
На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex> \varnothing</tex>, если <tex>w</tex> {{---}} последняя вершина в списке.
<tex>\mathtt{initializePreflow(s)}</tex>
<tex>L = V \setminus \{ s, t \}</tex>
'''for''' <tex>u \in V </tex> <tex>\setminus</tex> <tex>\{ s, t \}</tex>
<tex>current[u] = head[N[u]]</tex>
<tex>u = head[L]</tex>
<tex>nextVertex[u]</tex> хранит вершину, следующую за <tex>u</tex> в списке <tex>L</tex>. Если <tex>u</tex> {{---}} последняя вершина в списке, то <tex>nextVertex[u] = null</tex>.
'''Инвариант цикла''': "при каждом выполнении условия вхождения в цикл '''<tex>\mathtt{while''' }</tex> вершины в списке <tex>L</tex> топологически упорядочены в допустимой сети <tex>G_{f, h} = (V, E_{f, h})</tex>, и ни одна вершина, стоящая в списке перед <tex>u</tex>, не имеет избыточного потока".
== Корректность алгоритма ==
Для доказательства корректности алгоритма, то есть чтобы показать что операция <tex>\mathtt{relabelToFront}</tex> вычисляет поток, покажем, что она является реализацией универсального алгоритма [[Метод проталкивания предпотока|проталкивания предпотока]]. Для начала, заметим, что она выполняет операции <tex>push</tex> и <tex>relabel</tex> только тогда, когда они применимы, следует из [[Алгоритм "поднять-в-начало"#Лемма4|лемм о применимости операций push и relabel]]. Покажем, что когда операция <tex>\mathtt{relabelToFront}</tex> завершится, не применима ни одна основная операция. Для этого подробно рассмотрим операцию <tex>\mathtt{relabelToFront}</tex>:
#После вызова <tex>\mathtt{initializePreflow}</tex> <tex>h[s] = |V|</tex> и <tex>h[u] = 0</tex> для всех <tex>u \in V \setminus {s}</tex>. Так как <tex>|V| \ge geqslant 2</tex>, то ни одно ребро не является допустимым. Значит, <tex>E_{f, h} = \varnothing</tex> и любой порядок множества <tex>V \setminus \{s, t\}</tex> является топологическим упорядочением <tex>G_{f, h}</tex>.#Проверим, что топологическое упорядочение сохранится при проведении итераций цикла '''<tex>\mathtt{while'''}</tex>. Для начала заметим, что сеть может изменится только из-за операций проталкивания и подъема. Из [[Алгоритм "поднять-в-начало"#Лемма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>\mathtt{discharge}</tex> не выполняет подъем, то следующий ее вызов происходит дальше по списку <tex>L</tex> <tex>(</tex>длина <tex>L</tex> меньше <tex>|V|)</tex>. Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более <tex>|V|</tex> вызовов <tex>\mathtt{discharge}</tex>.
Таким образом, цикл '''<tex>\mathtt{while''' }</tex> процедуры <tex>\mathtt{relabelToFront}</tex> выполняет работу (без учета операций вызываемых в <tex>\mathtt{discharge}</tex>), за <tex>O(V^{3})</tex>.
Оценим работу выполнения внутри операции <tex>\mathtt{discharge}</tex>:
Таким образом, время выполнения операции <tex>\mathtt{relabelToFront}</tex> составляет <tex>O(V^{3} + VE)</tex>, что эквивалентно <tex>O(V^{3})</tex>.
}}
==См. также==
* [[Метод проталкивания предпотока]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Схема алгоритма Диница]]
* [[Алоритм Эдмондса-Карпа]]
== Источники информации ==
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785.
* [http://ru.wikipedia.org/wiki/Алгоритм_проталкивания_предпотока Алгоритм проталкивания предпотока — Википедия]
*[http://e-maxx.ru/algo/preflow_push_faster MAXimal::algo::Модификация метода Проталкивания предпотока для нахождения максимального потока за O (N3)]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
