338
правок
Изменения
м
→Допустимые ребра
Если вершина <tex>u</tex> переполнена и ребро <tex>(u, v)</tex> допустимое, то применяемая операция <tex>push(u, v)</tex> не создает новые допустимые ребра, но может привести к тому, что ребро <tex>(u, v)</tex> станет недопустимым.
|proof =
Так как ребро <tex>(u, v)</tex> допустимое то, по определению допустимого ребра, из <tex>u</tex> в <tex>v</tex> можно протолкнуть поток. Из-за того что <tex>u</tex> {{---}} переполнена, вызываем операцию <tex>push(u, v)</tex>. В результате выполнения операции может быть создано остаточное ребро <tex>(v, u, v)</tex>. Поскольку ребро <tex>(u, v)</tex> допустимое то, <tex>h[v] = h[u] - 1</tex>, а это значит, что ребро <tex>(v, u)</tex> не может стать допустимым.
Если выполненная операция <tex>push(u, v)</tex> является насыщающим проталкиванием, то после ее выполнения <tex>c_{f}(u, v) = 0</tex> и ребро <tex>(u, v)</tex> становится недопустимым.
