Изменения

Для доказательства корректности алгоритма, то есть чтобы показать что операция <tex>relabelToFront</tex> вычисляет поток, покажем, что она является реализацией универсального алгоритма [[Метод проталкивания предпотока|проталкивания предпотока]]. Для начала, заметим, что она выполняет операции <tex>push</tex> и <tex>relabel</tex> только тогда, когда они применимы, следует из лемм о применимости операций [[Алгоритм "поднять-в-начало"#Лемма4|push]] и [[Алгоритм "поднять-в-начало"#Лемма5|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>.