Изменения
→Операция разгрузки (discharge)
Будем хранить для каждой вершины <tex>u</tex> список <tex>N[u]</tex> (список вершин, смежных с ней). То есть список <tex>N[u]</tex> содержит каждую вершину <tex>v</tex> такую, что в сети <tex>G = (V, E) ~ (u, v) \in E</tex> или <tex>(v, u) \in E</tex>.
На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex>null\varnothing</tex>, если <tex>w</tex> {{---}} последняя вершина в списке.
Для каждой вершины <tex>u</tex> указатель <tex>current[u]</tex> {{---}} указатель на текущую вершину списка. Изначально <tex>current[u] = head[N[u]]</tex>.
'''while''' <tex>e[u] > 0 </tex>
<tex>v = current[u]</tex>
'''if''' <tex>v = null \varnothing</tex>
<tex>\mathtt{relabel}(u)</tex>
<tex>current[u] = head[N[u]]</tex>
Из [[Алгоритм "поднять-в-начало"#Лемма3|леммы об изменении допустимой цепи (для операции relabel)]] и условия <tex>e(u) > 0</tex> следует, что для доказательства данной леммы необходимо показать, что все ребра, выходящие из <tex>u</tex>, являются недопустимыми.
Каждый проход операции <tex>\mathtt{discharge}(u)</tex> начинается с головы списка <tex>N[u]</tex> и оканчивается, когда <tex>current[u] = null \varnothing</tex>. Именно тогда вызывается <tex>relabel(u)</tex>, и начинается новый проход. К концу прохода все ребра, выходящие из <tex>u</tex>, станут недопустимыми, так как из [[Алгоритм "поднять-в-начало"#Лемма2|леммы об изменении допустимой цепи (для операции push)]] следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина <tex>u</tex> не подвергается подъему во время прохода, а любая другая вершина <tex>v</tex>, для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из [[Алгоритм "поднять-в-начало"#Лемма3|леммы об изменении допустимой цепи (для операции relabel)]]. Значит, в конце прохода все ребра, выходящие из <tex>u</tex>, останутся недопустимыми.
}}
