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