Изменения

'''function''' push('''Node''' u, '''Node''' v): d = min(e(u), c(u, v) - f(u, v)); f(u, v) += d; f(v, u) = -f(u, v); e(u) -= d; e(v) += d;

По своему результату все проталкивания можно разделить на <tex>2 </tex> группы. Будем называть проталкивание из вершины <tex> u </tex> в вершину <tex> v </tex> '''насыщающим''', если после него остаточная пропускная способность ребра <tex> (u, v) </tex> стала равна нулю. Все остальные проталкивания будем называть '''ненасыщающими'''. Подобная классификация проталкиваний понадобится нам при оценке их количества.

=== подъём Подъём (relabel) ===

'''function''' relabel('''Node''' u): h(u) = min({h(v): f(u, v) - c(u, v) < 0) } + 1;

-c(u, v, u), & v = s \\

'''function''' initializePreflow('''Node''' s): '''for''' u <tex> u \in V </tex>V h(u) = 0; e(u) = 0; '''for''' <tex> (u, v) <tex>\in E </tex>E f(u, v) = 0; f(v, u) = 0; '''for''' <tex> u: (s, u) <tex>\in E </tex>E f(s, u) = c(s, u); f(u, s) = -c(s, u); e(u) = c(s, u); e(s) -= c(s, u); h(s) = |V|;

'''function''' pushRelabelMaxFlow('''Node''' s, '''Node''' t) initializePreflow(s); '''while''' e(u) > 0 '''and''' (h(u) = h(v) + 1 '''or''' <tex> \forall </tex> (u, v) <tex> \exists in E_f </tex> применимая операция h(u) <tex> \leqslant</tex> h(v)) '''if''' e(u) > 0 '''and''' h(u) = h(v) + 1 push(u, v) '''if''' e(u) > 0 '''and''' <tex> \forall </tex> (u, v) <tex>\in E_f </tex> h(u) <tex> \leqslant</tex> h(v) relabel(u)[[Файл:OrGraphPush0.png|545px|left|Пример сети.]] [[Файл:OrGraphPush1.png|545px|right|Сеть после запуска потока, остаточная сеть, применение операции <tex> \mathrm{pushrelabel} </tex> или .]][[Файл:OrGraphPush2.png|545px|left|Применение операции <tex> \mathrm{relabelpush} </tex>.]]                                      выбрать операцию и выполнить её

|about = <tex>1</tex>

|about = <tex>2</tex>

|about = <tex>3</tex>

После завершения алгоритма для каждой вершины <tex> u \in V \setminus \{s, t\} </tex> справедливо, что <tex> e(u) = 0 </tex>, что следует непосредственно из [[#Лемма1|леммы (<tex>1</tex>)]], [[#Лемма2|леммы (<tex>2</tex>)]] и того, что перед выполнением операций проталкивания или подъёма <tex> f </tex> является предпотоком. Но тогда <tex> f </tex> удовлетворяет условию сохранения потока, то есть сам является потоком.

Поскольку из [[#Лемма1|леммы (<tex>1</tex>)]] следует, что <tex> h </tex> является функцией высоты и после завершения алгоритма, то по [[#Лемма3|лемме (<tex>3</tex>)]] в остаточной сети <tex> G_f </tex> нет пути из <tex> s </tex> в <tex> t </tex>. Но тогда по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] <tex> f </tex> {{---}} максимальный поток.

Чтобы показать, что алгоритм завершает свою работу, найдем найдём максимальное количество операций проталкивания и подъёма. Для того этого докажем несколько вспомогательных лемм.

|about = <tex>4</tex>

|about = <tex>5</tex>

Рассмотрим вершину <tex> u </tex> отличную от истока и стока. Изначально <tex> h(u) = 0 \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. Покажем, что после любой операции подъёма <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. Для того, чтобы мы имели право произвести операцию <tex> \mathrm{relabel}</tex><tex>(u) </tex>, вершина <tex> u </tex> должна быть переполнена. Тогда по [[#Лемма4|лемме (<tex>4)</tex>]] существует простой путь <tex> p </tex> из <tex> u </tex> в <tex> s </tex> в остаточной сети <tex> G_f </tex>. Рассмотрим этот путь. Пусть <tex> p = \left\langle v_0, v_1, \dots, v_k \right\rangle </tex>, где <tex> v_0 = u </tex> и <tex> v_k = s </tex>. Так как путь <tex> p </tex> простой, то <tex> k \leqslant \left\vert V \right\vert - 1 </tex>. По определению функции высоты имеем, что <tex> \forall i \in \{0, 1, \dots, k - 1\} </tex> <tex> h(v_i) \leqslant h(v_{i+1}) + 1</tex>. Но тогда для вершин <tex> u </tex> и <tex> v </tex> верно, что <tex> h(u) \leqslant h(s) + \left\vert V \right\vert - 1 = 2 \cdot \left\vert V \right\vert - 1 </tex>

|about = <tex>6</tex>

Так как высоты истока и стока не изменяются в процессе работы алгоритма, то только <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>

|about = <tex>8</tex>

Возьмем произвольную пару вершин <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>

Количество ненасыщающих проталкиваний при выполнение алгоритма <tex> \mathrm{pushRealbelMaxFlowpushRelabelMaxFlow}</tex> не превосходит <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </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>. Согласно [[#Лемма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> G </tex> {{---}} сеть. Тогда любая реализация метода <tex> \mathrm{pushRealbelMaxFlowpushRelabelMaxFlow}</tex> для <tex> G </tex> завершает свою работу, и число основных операций составляет <tex> O(V^2E) </tex>

Из [[#Лемма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>. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.