693
правки
Изменения
→Оценка быстродействия
{{Лемма
|about = <tex>4</tex>
|id = Лемма4
|statement =
{{Лемма
|about = <tex>5</tex>
|id = Лемма5
|statement =
{{Лемма
|about = <tex>6</tex>
|id = Лемма6
|statement =
Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. Тогда во время выполнения алгоритма <tex> \mathrm{pushRelabelMaxFlow}</tex> общее число подъёмов не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 </tex>
|proof =
Так как высоты истока и стока не изменяются в процессе работы алгоритма, то только <tex> \left\vert V \right\vert - 2 </tex> вершин могут быть подняты. Пусть <tex> u \in V \setminus \{s, t\}</tex>. Изначально <tex> h(u) = 0 </tex>, и по [[#Лемма5|лемме (<tex>5</tex>)]] известно, что <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. А так как при выполнении операции <tex> \mathrm{relabel}</tex><tex>(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 = <tex>7</tex>
|id = Лемма7
|statement =
Следующие две леммы показывают верхнюю границу количества проталкиваний.
{{Лемма
|about = <tex>8</tex>
|id = Лемма8
|statement =
Количество насыщающих проталкиваний при выполнение алгоритма <tex> \mathrm{pushRelabelMaxFlow}</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> должна увеличится как минимум на <tex>2</tex>. По [[#Лемма5|лемме (<tex>5</tex>)]] высота вершины не превышает <tex> 2 \cdot\left\vert V \right\vert - 1 </tex>, следовательно, количество раз, когда высота вершины может увеличится на <tex>2</tex>, меньше <tex> \left\vert V \right\vert </tex>. Поскольку между двумя насыщающими проталкиваниями высота одной из вершин должна увеличится по меньшей мере на <tex>2</tex>, то между вершинами <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> насыщающих проталкиваний.
}}
{{Лемма
|about = <tex>9</tex>
|id = Лемма9
|statement =
Для начала рассмотрим, каким образом может увеличиваться величина <tex> \Phi </tex>.
Первое, что может увеличить <tex> \Phi </tex>, это подъём, поскольку, осуществляя данную операцию, мы не изменяем избыточный поток ни у одной вершины, а лишь увеличиваем высоту одной из них. При каждой операции подъёма <tex> \Phi </tex> увеличивается менее чем на <tex> 2 \cdot \left\vert V \right\vert </tex>, так как подъём не может увеличить высоту вершины больше, чем её максимальная высота, которая согласно [[#Лемма5|лемме (<tex>5</tex>)]] может быть не более <tex> 2 \cdot \left\vert V \right\vert - 1 </tex>. А поскольку из [[#Лемма6|леммы (<tex>6</tex>)]] известно, что число подъёмов не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 </tex>, то суммарно подъёмы всех вершин могут увеличить <tex> \Phi </tex> не более чем на <tex> 4 \cdot \left\vert V \right\vert^3 </tex>.
Во-вторых, величина <tex> \Phi </tex> может увеличится при насыщающем проталкивании из <tex> u </tex> в <tex> v </tex>, потому что <tex> e(u) > 0 </tex> и после насыщающего проталкивания, а вершина <tex> v </tex> может стать переполненной. Увеличение меньше <tex> 2 \cdot \left\vert V \right\vert </tex>, так как изменения высот не происходит, а высота вершины <tex> v </tex> не превосходит <tex> 2 \cdot \left\vert V \right\vert - 1 </tex>. Но по [[#Лемма8|лемме (8)]] известно, что количество насыщающих проталкиваний за все время выполнения алгоритма не превосходит <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex>, следовательно, за счет насыщающих проталкиваний <tex> \Phi </tex> увеличится не более чем на <tex> 4 \cdot \left\vert V \right\vert^2 \cdot \left\vert E \right\vert </tex>.
Итого, получаем, что величина <tex> \Phi </tex> не может быть больше <tex> 4 \cdot \left\vert V \right\vert ^2 \cdot (\left\vert V \right\vert + \left\vert E \right\vert) </tex>.
Теперь покажем, что ненасыщающее проталкивание уменьшает <tex> \Phi </tex> как минимум на единицу. Пусть произошло ненасыщающее проталкивание из вершины <tex> u </tex> в <tex> v </tex>. Согласно [[#Лемма7|лемме (<tex>7)</tex>]] после ненасыщающего проталкивания вершина <tex> u </tex> перестает быть переполненной, следовательно, <tex> \Phi </tex> уменьшается на величину её высоты. После проталкивания вершина <tex> v </tex> является переполненной, и поэтому <tex> \Phi </tex> могла увеличится на <tex> h(v) </tex>. Поскольку <tex> h(u) = h(v) - 1 </tex>, то при каждом ненасыщающем проталкивании <tex> \Phi </tex> уменьшается по меньшей мере на единицу.
Зная верхнюю границу величины <tex> \Phi </tex>, её значение после выполнения алгоритма и то, что при каждом ненасыщающем проталкивании <tex> \Phi </tex> уменьшается минимум на единицу, то можно сделать вывод, что количество ненасыщающих проталкиваний не больше чем <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>.
Пусть <tex> G </tex> {{---}} сеть. Тогда любая реализация метода <tex> \mathrm{pushRealbelMaxFlow}</tex> для <tex> G </tex> завершает свою работу, и число основных операций составляет <tex> O(V^2E) </tex>
|proof =
Из [[#Лемма6|леммы (<tex>6)</tex>]], [[#Лемма8|леммы (<tex>8)</tex>]] и [[#Лемма9|леммы (<tex>9)</tex>]] следует, что число операций подъёма и проталкиваний не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 + 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert + 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) = O(V^2E) </tex>. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.
}}
