403
правки
Изменения
→Оценка быстродействия
{{Лемма
|about = 7
|id = Лемма7
|statement =
После ненасыщающего проталкивания из <tex> u </tex> в <tex> v </tex> вершина <tex> u </tex> перестает быть переполненной.
|proof =
}}
Следующие две леммы показывают верхнюю границу количества проталкиваний.
{{Лемма
|about = 8
|id = Лемма8
|statement =
Количество насыщающих проталкиваний при выполнение алгоритма <tex> pushRealbelMaxFlow </tex> не превосходит <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex>
{{Лемма
|about = 89|id = Лемма8Лемма9
|statement =
Количество ненасыщающих проталкиваний при выполнение алгоритма <tex> pushRealbelMaxFlow </tex> не превосходит <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>
