Изменения

Пусть <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> 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 = \left\langle v_0, v_1, \dots, v_k \right\rangle </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>