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