338
правок
Изменения
→Допустимые ребра
Так как каждая вершина циклического пути <tex>p</tex> встречается при суммировании по одному разу это значит то, что <tex>k = 0</tex>, что противоречит первоначальному предположению. Значит, допустимая сеть является ациклической.
}}
{{Лемма
|id = Лемма2
|about = Об изменении допустимой цепи, с помощью операции проталкивания.
|statement =
Если <tex>G = (V, E)</tex> {{---}} сеть с истоком <tex>s</tex> и стоком <tex>t</tex>, <tex>f</tex> {{---}} предпоток в <tex>G</tex>, а <tex>h</tex> {{---}} функция высоты. Если вершина <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>(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> становится недопустимым.
}}
