403
правки
Изменения
→Оценка быстродействия
Итого, получаем, что величина <tex> \Phi </tex> не может быть больше <tex> 4 \cdot \left\vert V \right\vert ^2 \cdot (\left\vert V \right\vert + \left\vert E \right\vert) </tex>.
Теперь покажем, что ненасыщающее проталкивание уменьшает <tex> \Phi </tex> как минимум на единицу. Пусть произошло ненасыщающее проталкивание из вершины <tex> u </tex> в <tex> v </tex>. Согласно [[#Лемма7|лемме (7)]] после ненасыщающего проталкивания вершина <tex> u </tex> перестает быть переполненной, следовательно, <tex> \Phi </tex> уменьшается на величину ее высоты. После проталкивания вершина <tex> v </tex> является переполненной, и поэтому <tex> \Phi </tex> могла увеличится на <tex> h(v) </tex>. Поскольку <tex> h(u) = h(v) - 1 </tex>, то при каждом ненасыщающем проталкивании <tex> \Phi </tex> уменьшается по меньшей мере на единицу.
Зная верхнюю границу величины <tex> \Phi </tex>, ее значение после выполнения алгоритма и то, что при каждом ненасыщающем проталкивании <tex> \Phi </tex> уменьшается минимум на единицу, то можно сделать вывод, что количество ненасыщающих проталкиваний не больше чем <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>.
}}
