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