Изменения
→Корректность алгоритма
== Корректность алгоритма ==
Для доказательства корректности алгоритма, то есть чтобы показать что операция <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 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> на следующей итерации.
