403
правки
Изменения
→Оценка быстродействия
|proof =
Так как высоты истока и стока не изменяются в процессе работы алгоритма, то только <tex> \left\vert V \right\vert - 2 </tex> вершин могут быть подняты. Пусть <tex> u \in V \setminus \{s, t\}</tex>. Изначально <tex> h(u) = 0 </tex>, и по [[#Лемма5|лемме(5)]] известно, что <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. А так как при выполнении операции <tex> relabel(u) </tex> высота вершины увеличивается как минимум на единицу, то максимальное количество подъемов вершины <tex> u </tex> также не превышает <tex> 2 \cdot \left\vert V \right\vert - 1 </tex>. Тогда суммарно число подъемов не превышает <tex> (\left\vert V \right\vert - 2 ) \cdot (2 \cdot \left\vert V \right\vert - 1) \leqslant 2 \cdot \left\vert V \right\vert ^2 </tex>.
}}
Следующие две леммы показывают верхнюю границу количества проталкиваний.
{{Лемма
|about = 7
|id = Лемма7
|statement =
Количество насыщающих проталкиваний при выполнение алгоритма <tex> pushRealbelMaxFlow </tex> не превосходит <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex>
|proof =
}}
{{Лемма
|about = 7
|id = Лемма7
|statement =
Количество ненасыщающих проталкиваний при выполнение алгоритма <tex> pushRealbelMaxFlow </tex> не превосходит <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>
|proof =
}}
