403
правки
Изменения
→Оценка быстродействия
Количество ненасыщающих проталкиваний при выполнение алгоритма <tex> pushRealbelMaxFlow </tex> не превосходит <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>
|proof =
Пусть <tex> \Phi = \sum \limits_{u: e(u) > 0} h(u)</tex>. Так как после завершения алгоритма ни одна из вершин не является переполненной, то и величина <tex> \Phi </tex> после выполнения алгоритма должна равняться нулю.
Для начала рассмотрим, каким образом может увеличиваться величина <tex> \Phi </tex>.
}}
