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