Изменения

Перейти к: навигация, поиск

Метод проталкивания предпотока

605 байт добавлено, 00:36, 10 декабря 2012
Оценка быстродействия
После ненасыщающего проталкивания из <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>.
}}
403
правки

Навигация