338
правок
Изменения
м
→Допустимые ребра
Рассмотрим вершину <tex>u</tex>. Если <tex>u</tex> переполнена, то, согласно [[Метод проталкивания предпотока#Лемма2|лемме (2)]], к ней может быть применима либо операция проталкивания, либо операция подъема. А так как не существует допустимых ребер для <tex>u</tex>, то протолкнуть поток не возможно, значит, применяется операция <tex>relabel(u)</tex>. После данного подъема <tex>h[u] = 1 + min \{ h[v]: (u, v) \in E_{f} \}</tex>. Значит, если <tex>u</tex> {{---}} вершина указанного множества, в которой реализуется минимум, то <tex>(u, v)</tex> становится допустимым. А это значит, что после подъема существует хотя бы одно допустимое ребро, выходящее из <tex>u</tex>.
Пусть после подъема существует такая вершина <tex>u</tex>, что ребро <tex>(v, u, v)</tex> допустимо. Тогда после подъема <tex>h[v] = h[u] + 1</tex>, а перед ним <tex>h[v] > h[u] + 1</tex>. Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных сетей. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро <tex>(v, u)</tex> не может находится в допустимой сети, так как оно не принадлежит остаточной сети.
}}
