338
правок
Изменения
м
Нет описания правки
{{Лемма
|about = О применимости операции push
|id = Лемма4
|statement =
{{Лемма
|about = О применимости операции relabel
|id = Лемма5
|statement =
<tex>nextVartex[u]</tex> возвращает вершину, следующую за <tex>u</tex> в списке <tex>L</tex>. Если <tex>u</tex> - последняя вершина в списке, то <tex>nextVartex[u] = null</tex>.
== Корректность алгоритма ==
Для доказательства корректности алгоритма, то есть чтобы показать что операция <tex>relabelToFront</tex> вычисляет поток, покажем, что она является реализацией универсального алгоритма [[Метод проталкивания предпотока|проталкивания предпотока]]. Для начала, заметим, что она выполняет операции <tex>push</tex> и <tex>relabel</tex> только тогда, когда они применимы, следует из лемм о применимости операций [[Алгоритм "поднять-в-начало"#Лемма4|push]] и [[Алгоритм "поднять-в-начало"#Лемма5|relabel]]. Покажем, что когда операция <tex>relabelToFront</tex> завершится, не применима ни одна основная операция.
== Анализ ==
