Изменения
Нет описания правки
Оценим работу выполнения внутри операции <tex>\mathtt{discharge}</tex>:
#Обновление указателя <tex>current[u]</tex> выполняется <tex>O(\deg(u))</tex> в том случае, когда вершина <tex>u</tex> подвергается подъему. Значит, для всех вершин время составляет <tex>O(V \deg(u))</tex>. Следовательно, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], время равно <tex>O(VE)</tex>.#Пусть <tex>u</tex> {{---}} произвольная вершина сети. Она может быть поднята не более <tex>O(V)</tex> раз, время каждого подъема <tex>O(\deg(u))</tex>. Значит, время всех подъемов ограничивается <tex>O(VE)</tex>.
#Из [[Метод проталкивания предпотока#Лемма8|леммы (8)]] следует, что количество насыщающих проталкиваний составляет <tex>O(VE)</tex>. Ненасыщающее проталкивание уменьшает избыток до <tex>0</tex>, после чего разгрузка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов <tex>\mathtt{discharge}</tex>, то есть <tex>O(V^{3})</tex>.
}}
== Источники Информации информации ==
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785.
* [http://ru.wikipedia.org/wiki/Алгоритм_проталкивания_предпотока Алгоритм проталкивания предпотока — Википедия]
