403
правки
Изменения
м
→Оценка быстродействия
Для начала рассмотрим, каким образом может увеличиваться величина <tex> \Phi </tex>.
Первое, что может увеличить <tex> \Phi </tex>, это подъем, поскольку, осуществляя данную операцию, мы не изменяем избыточный поток ни у одной вершины, а лишь увеличиваем высоту одной из них. При каждой операции подъема <tex> \Phi </tex> увеличивается менее чем на <tex> 2 \cdot \left\vert V \right\vert </tex>, так как подъем не может увеличить высоту вершины больше, чем ее максимальная высота, которая согласно [[#Лемма5|лемме (5)]] может быть не более <tex> 2 \cdot \left\vert V \right\vert - 1 </tex>. А так как поскольку из [[#Лемма6|леммы (6)]] известно, что число подъемов не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 </tex>, то суммарно подъемы всех вершин могут увеличить <tex> \Phi </tex> не более чем на <tex> 4 \cdot \left\vert V \right\vert^3 </tex>.
Во-вторых, величина <tex> \Phi </tex> может увеличится при насыщающем проталкивании из <tex> u </tex> в <tex> v </tex>, потому что <tex> e(u) > 0 </tex> и после насыщающего проталкивания, а вершина <tex> v </tex> может стать переполненной. Увеличение меньше <tex> 2 \cdot \left\vert V \right\vert </tex>, так как изменения высот не происходит, а высота вершины <tex> v </tex> не превосходит <tex> 2 \cdot \left\vert V \right\vert - 1 </tex>. Но по [[#Лемма8|лемме (8)]] известно, что количество насыщающих проталкиваний за все время выполнения алгоритма не превосходит <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex>, следовательно, за счет насыщающих проталкиваний <tex> \Phi </tex> увеличится не более чем на <tex> 4 \cdot \left\vert V \right\vert^2 \cdot \left\vert E \right\vert </tex>.
