403
правки
Изменения
→Оценка быстродействия
Количество насыщающих проталкиваний при выполнение алгоритма <tex> pushRealbelMaxFlow </tex> не превосходит <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex>
|proof =
Возьмем произвольную пару вершин <tex> u </tex> и <tex> v </tex> и рассмотрим насыщающие проталкивания по ребрам <tex> (u, v) </tex> и <tex> (v, u) </tex>. Предположим, что произошло насыщающее проталкивание по ребру <tex> (u, v) </tex>. Тогда во время проталкивания <tex> h(v) = h(u) - 1 </tex>. Для того, чтобы могло произойти еще одно насыщающее проталкивание по ребру <tex> (u, v) </tex>, мы должны для начала протолкнуть поток из <tex> v </tex> в <tex> u </tex>, чтобы ребро <tex> (u, v) </tex> снова появилось в остаточной сети. Но для этого должно выполняться условие <tex> h(v) = h(u) + 1 </tex>, то есть высота вершины <tex> u </tex> должна увеличится как минимум на 2. По [[#Лемма5|лемме(5)]] высота вершины не превышает <tex> 2 \cdot\left\vert V \right\vert - 1 </tex>, следовательно, количество раз, когда высота вершины может увеличится на 2, меньше <tex> \left\vert V \right\vert </tex>. Поскольку между двумя насыщающими проталкиваниями высота одной из вершин должна увеличится по меньшей мере на 2, то между вершинами <tex> u </tex> и <tex> v </tex> их будет не более <tex> 2 \cdot\left\vert V \right\vert </tex>. Тогда суммарно по всем ребрам во время работы алгоритма произойдут не более <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex> насыщающих проталкиваний.
}}
