403
правки
Изменения
→Оценка быстродействия
Покажем, что для любой пары вершин <tex> v \in U </tex> и <tex> w \in \bar{U} </tex> верно, что <tex> f(w, v) \leqslant 0 </tex>. Если <tex> f(w, v) > 0 </tex>, то <tex> f(v, w) < 0 </tex>. Но тогда из этого утверждения следует, что <tex> c_f(v, w) = c(v, w) - f(v, w) > 0 </tex>, что не может быть верным, так как в таком случае существует путь <tex> u \leadsto v \to w </tex> в остаточной сети <tex> G_f </tex>, что противоречит выбору вершины <tex> w </tex>. Следовательно, для каждой пары вершин <tex> v \in U </tex> и <tex> w \in \bar{U} </tex> верно, что <tex> f(w, v) \leqslant 0 </tex>. Тогда верно и <tex> f(\bar{U}, U) \leqslant 0 </tex>. Следовательно <tex> e(U) = f(V, U) = f(U, U) + f(\bar{U}, U) = f(\bar{U}, U) \leqslant 0 </tex>.
Но по определению избыток потока неотрицателен, из чего следует, что для любой вершины <tex> v \in U </tex> <tex> e(v) = 0 </tex>, в том числе <tex> e(u) = 0 </tex>, что противоречит условию переполненности вершины <tex> u </tex>.}} {{Лемма|about = 5|id = Лемма5|statement = Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. Тогда во время выполнения алгоритма <tex> pushRealbelMaxFlow </tex> для любой вершины <tex> u </tex> в сети <tex> G </tex> верно, что <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>|proof = По определению функции высоты <tex> h(s) = \left\vert V \right\vert </tex> и <tex> h(t) = 0 </tex>, следовательно для истока и стока условие леммы выполнено. Рассмотрим вершину <tex> u </tex> отличную от истока и стока. Изначально <tex> h(u) = 0 \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. Покажем, что после любой операции подъема <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. Для того, чтобы мы имели право произвести операцию <tex> relabel(u) </tex>, вершина <tex> u </tex> должна быть переполнена. Тогда по [[#Лемма4|лемме(4)]] существует простой путь <tex> p </tex> из <tex> u </tex> в <tex> s </tex> в остаточной сети <tex> G_f </tex>. Рассмотрим этот путь. Пусть <tex> p = (v_0, v_1, \dots, v_k)</tex>, где <tex> v_0 = u </tex> и <tex> v_k = s </tex>. Так как путь <tex> p </tex> простой, то <tex> k \leqslant \left\vert V \right\vert - 1 </tex>. По определению функции высоты имеем, что <tex> \forall i \in \{0, 1, \dots, k - 1\} </tex> <tex> h(v_i) \leqslant h(v_{i+1}) + 1</tex>. Но тогда для вершин <tex> u </tex> и <tex> v </tex> верно, что <tex> h(u) \leqslant h(s) + \left\vert V \right\vert - 1 = 2 \cdot \left\vert V \right\vert - 1 </tex>
}}
