403
правки
Изменения
→Оценка быстродействия
После ненасыщающего проталкивания из <tex> u </tex> в <tex> v </tex> вершина <tex> u </tex> перестает быть переполненной.
|proof =
Так как проталкивание ненасыщающее, то величина потока, проталкиваемого через ребро <tex> (u, v) </tex> должна быть равна <tex> e(u) </tex>. После выполнения проталкивания избыточный поток вершины должен уменьшится на величину проталкиваемого потока, следовательно после ненасыщающего проталкивания из <tex> u </tex> в <tex> v </tex> величина <tex> e(u) = 0 </tex>.
}}
