338
правок
Изменения
м
Так как каждая вершина Вершина циклического пути <tex>p</tex> встречается при суммировании по одному разу это значит то. Значит, что <tex>k = 0</tex>, что противоречит первоначальному предположению. ЗначитСледовательно, допустимая сеть является ациклической.
Так как ребро Из <tex>(u, v)</tex> допустимое то, по определению допустимого ребра, из в <tex>uv</tex> в можно протолкнуть поток, так как ребро <tex>(u, v)</tex> можно протолкнуть потокдопустимое, по определению. Из-за того что <tex>u</tex> {{---}} переполнена, вызываем операцию <tex>push(u, v)</tex>. В результате выполнения операции может быть создано остаточное ребро <tex>(v, u)</tex>. Поскольку ребро <tex>(u, v)</tex> допустимое , то, <tex>h[v] = h[u] - 1</tex>, а это значит, что ребро <tex>(v, u)</tex> не может стать допустимым.
→Допустимые ребра
<tex>\sum \limits_{i = 1}^{k} h(v_{i - 1}) = \sum \limits_{i = 1}^{k} (h(v_{i}) + 1) = \sum \limits_{i = 1}^{k} h(v_{i}) + k</tex>
}}
Если вершина <tex>u</tex> переполнена и ребро <tex>(u, v)</tex> допустимое, то применяемая операция <tex>push(u, v)</tex> не создает новые допустимые ребра, но может привести к тому, что ребро <tex>(u, v)</tex> станет недопустимым.
|proof =
Если выполненная операция <tex>push(u, v)</tex> является насыщающим проталкиванием, то после ее выполнения <tex>c_{f}(u, v) = 0</tex> и ребро <tex>(u, v)</tex> становится недопустимым.
|about = Об изменении допустимой цепи с помощью операции подъема
|statement =
Если вершина <tex>u</tex> переполнена, и не имеется допустимых ребер, выходящих из <tex>u</tex>, то применяется операция <tex>relabel(u)</tex>. После подъема появляется по крайней мере одно допустимое ребро, выходящее из <tex>u</tex>, но нет допустимых ребер, входящих в <tex>u</tex>.
|proof =
Рассмотрим вершину <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)</tex> допустимо. Тогда после подъема <tex>h[v] = h[u] + 1</tex>, а перед ним <tex>h[v] > h[u] + 1</tex>. Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных ребер. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро <tex>(v, u)</tex> не может находится в допустимой сети, так как оно не принадлежит остаточной сети.
}}
