Изменения

'''Метод проталкивая проталкивания предпотока''' {{---}} обобщенный алгоритм нахождения максимального [[Определение сети, потока#Определение потока|потока]] в [[Определение сети, потока#Определение сети|сети]]. В отличии отличие от [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] и [[Схема алгоритма Диница|алгоритма Диница]] не является частным случаем [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|метода Форда-Фалкерсона]].

'''Предпотоком''' ('англ. ''preflow''') будем называть функцию <tex> f: V \times V \rightarrow \mathbb{R} </tex>, удовлетворяющую следующим свойствам:

'''Избыточным потоком''' ('англ. ''excess flow'''), входящим в вершину <tex> u </tex>, назовем величину <tex> e(u) = \sum \limits_{v \in V} f(v, u) </tex>.<br>Тогда вершина <tex> u \in V \setminus \{s, t\} </tex> будет называться '''переполненной''' ('англ. ''overflowing'''), если <tex> e(u) > 0 </tex>.

Функция <tex> h: V \rightarrow \mathbb{Z}_+</tex> называется '''высотой вершины''' ('англ. ''vertex label'''), если она удовлетворяет условиям:

Для понимания идеи алгоритма представим, что наша сеть {{---}} система из резервуаров, находящихся на определенной высоте, и соединяющих их труб с заданными пропускными способностями, соответствующих вершинам и ребрам рёбрам в исходной сети. Сам алгоритм можно представить как процесс поочередного "переливания" жидкости (операция проталкивания) из одного резервуара в другие, находящиеся на меньшей высоте, до тех пор пока будет не перестанет существовать резервуар, соответствующей соответствующий переполненной вершине. Может случиться ситуация, что все трубы, выходящие из переполненной вершины <tex> u </tex>, ведут к вершинам, находящимся на такой же высоте что и <tex> u </tex> или выше еееё. В таком случае поднимем резервуар (операция подъемаподъёма), соответствующий данной вершине, таким образом, чтобы его высота стала на единицу больше, чем высота самого низкого из смежных резервуаров. После подъема подъёма будет существовать по крайней мере одна труба, по которой можно попустить пропустить жидкость. В итоге, у нас не останется ни одной переполненной вершины, та часть потока, которая могла пройти к стоку, окажется там, остальная же вернется в исток. В такой ситуации предпоток превращается в обычный поток, так как для каждой вершины выполняется условие сохранения потока. Как будет показано далее, предпоток становится не только обычным, но и максимальным потоком.

В итоге, у нас не останется ни одной переполненной вершины, та часть потока, которая могла пройти к стоку, окажется там, остальная же вернется в сток<!-----[[Файл:OrGraphAlgoPreflow. В такой ситуации предпоток превращается в обычный поток, так как для каждой вершины выполняется условие сохранения потока. Как будет показано далее, предпоток становится не только обычным, но и максимальным потокомpng|550px|thumb|left|Пример]][[Файл:OrGraphAlgoPreflow.png|550px|thumb|left|something poxozhee]]---->

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

Данная операция работает следующим образом: по ребру <tex> (u, v) </tex> пропускается максимально возможный поток, то есть минимум из избытка вершины <tex> u </tex> и остаточной пропускной способности ребра <tex> (u, v) </tex>, вследствие чего избыток вершины <tex> u </tex>, остаточная пропускная способность ребра <tex> (u, v) </tex> и поток по обратному ребру <tex> (v, u) </tex> уменьшается уменьшаются на величину потока, а избыток вершины <tex> v </tex>, поток по ребру <tex> (u, v) </tex> и остаточная пропускная способность обратного ребра <tex> (v, u) </tex> увеличивается увеличиваются на эту же величину.

'''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) ===Операция подъема подъёма применима для вершины <tex> u </tex>, если <tex> e(u) > 0 </tex> и <tex> \forall (u, v) \in E_f \quad h(u) \leqslant h(v) </tex>.

То есть, для переполненной вершины <tex> u </tex> применима операция подъемаподъёма, если все вершины, для которых в остаточной сети есть ребра рёбра из <tex> u </tex>, расположены не ниже <tex> u </tex>. Следовательно, операцию проталкивания для вершины <tex> u </tex> произвести нельзя.

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

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

Для начала проинициализируем предпоток. Пропустим максимально возможный поток по ребрамрёбрам, инцидентным стокуистоку, увеличив избыточный поток для каждой смежной со стоком с истоком вершиной на соответствующую величину. Все остальные потока не несут, следовательно, для вершин не смежных с истоком избыточный поток изначально будет нулевым. Так же Также для всех вершин, кроме, естественно, истока, установим высоту, равную нулю.

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

'''initialazePreflowfunction'''initializePreflow('''Node''' s) '''for''' u <tex> \forall u \in V </tex>V h(u) = 0; e(u) = 0; '''for''' <tex> \forall (u, v) <tex>\in E </tex>E f(u, v) = 0; f(v, u) = 0; '''for''' <tex> \forall 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>\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{relabel}</tex>.]][[Файл:OrGraphPush2.png|545px|left|Применение операции <tex>\mathrm{push}</tex>.]]                                    

|about = <tex>1</tex>

Во время выполнения алгоритма <tex> \mathrm{pushRelabelMaxFlow } </tex> никакие свойства высоты не нарушаются.

Доказательство проведем по числу выполненных операций проталкивания и подъемаподъёма.

Для начала покажем, что после выполнения операции <tex> initialazePreflow \mathrm{initializePreflow} </tex> <tex> h </tex> является функцией высоты. Для всех реберрёбер, не инцидентных <tex> s </tex>, высота обоих концов равна нулю, что удовлетворяет условиям. Единственными ребрами рёбрами <tex> (u, v) </tex>, для которых не выполняются условия, налагаемые на функцию высоты, то есть для которых <tex> h(u) > h(v) + 1 </tex>, являются ребрарёбра, у которых <tex> u = s </tex>. Но после операции <tex> initialazePreflow \mathrm{initializePreflow} </tex> ребра рёбра являются насыщенными и не принадлежат остаточной сети.

Теперь докажем переход: если перед выполнением операции проталкивания или подъема подъёма <tex> h </tex> является функцией высоты, то и после выполнения операции она останется функцией высоты. Для этого рассмотрим проталкивание и подъем подъём отдельно.

Покажем, что после окончания операции проталкивания утверждение верно. После выполнения операции <tex> \mathrm{push}</tex><tex>(u, v) </tex> в <tex> E_f </tex> может появиться ребро <tex> (v, u) </tex>, если до операции по ребру <tex> (u, v) </tex> протекал нулевой поток, или же ребро <tex> (u, v) </tex> может насытиться, и тогда оно перестанет принадлежать остаточной сети. В первом случае <tex> h(v) = h(u) - 1 < h(u) + 1 </tex>, и, следовательно, <tex> h </tex> остается функцией высоты. Во втором же случае при удалении ребра <tex> (u, v) </tex> из остаточной сети происходит лишь удаление соответствующих ограничений на высоты <tex> u </tex> и <tex> v </tex>, так что <tex> h </tex> остается функцией высоты.

Теперь рассмотрим операцию подъема подъёма вершины <tex> u </tex>. По определению данной операции гарантируется, что после ее её выполнения для любого ребра <tex> (u, v) \in E_f </tex> выполняется условие <tex> h(u) \leqslant h(v) + 1 </tex>, то есть все выходящие ребра рёбра удовлетворяют условиям, накладываемым на функцию высоты. Рассмотрим какое-то входящее ребро <tex> (w, u) </tex>. Так как до операции <tex> h </tex> являлась функцией высоты, то справедливо <tex> h(w) \leqslant h(u) + 1 </tex>. После подъема подъёма высота вершины <tex> u </tex> увеличивается как минимум на единицу, следовательно, после выполнения данной операции <tex> h(w) < h(u) + 1 </tex>. Таким образом, <tex> h </tex> и после выполнения операции <tex> \mathrm{relabel}</tex><tex>(u) </tex> остается функций высоты.

|about = <tex>2</tex>

Пусть <tex> f </tex> {{---}} предпоток в сети <tex> G </tex>. Тогда для любой переполненной вершины можно выполнить операцию проталкивания либо операцию подъемаподъёма.

Рассмотрим вершину <tex> u </tex>, для которой <tex> e(u) > 0 </tex>. Для любого ребра <tex> (u, v) \in E_f </tex> справедливо <tex> h(u) \leqslant h(v) + 1 </tex> по свойствам функции высоты. Если к вершине <tex> u </tex> применима операция проталкивания, то лемма доказана. Иначе, для всех ребер рёбер <tex> (u, v) \in E_f </tex> выполняется соотношение <tex> h(u) < h(v) + 1 </tex>. Следовательно, <tex> h(u) \leqslant h(v) </tex>. Но тогда данная вершина удовлетворяет условиям операции подъемаподъёма, следовательно, к вершине <tex> u </tex> можно применить эту операцию.

|about = <tex>3</tex>

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

Если алгоритм <tex> \mathrm{pushRelabelMaxFlow }</tex> завершается, то вычисленный им предпоток <tex> f </tex> является максимальным потоком.

Перед началом цикла, после завершения операции <tex> \mathrm{initializePreflow }</tex>, <tex> f </tex> является предпотоком.

Внутри цикла выполняются лишь операции проталкивания и подъемаподъёма. Операция подъема подъёма не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъема подъёма не зависит, будет ли <tex> f </tex> предпотоком. Операция <tex> \mathrm{push}</tex><tex>(u, v) </tex> применяется, если <tex> e(u) > 0 </tex>, увеличивая поток через ребро <tex> (u, v) </tex> на величину, не превышающую избыточный поток вершины <tex> u </tex> и остаточную пропускную способность ребра <tex> (u, v) </tex>. Следовательно, если перед выполнением операции проталкивания <tex> f </tex> являлся предпотоком, то и после выполнения проталкивания <tex> f </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>

Пусть <tex> G </tex> {{---}} сеть со стоком с истоком <tex> s </tex> и истоком стоком <tex> t </tex>, и <tex> f </tex> {{---}} предпоток в <tex> G </tex>. Тогда из любой переполненной вершины <tex> u </tex> существует путь в <tex> s </tex> в остаточной сети <tex> G_f </tex>.

|about = <tex>5</tex>

Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. Тогда во время выполнения алгоритма <tex> pushRealbelMaxFlow \mathrm{pushRelabelMaxFlow}</tex> для любой вершины <tex> u </tex> в сети <tex> G </tex> верно, что <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>

По определению функции высоты <tex> h(s) = \left\vert V \right\vert </tex> и <tex> h(t) = 0 </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> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. Тогда во время выполнения алгоритма <tex> pushRealbelMaxFlow \mathrm{pushRelabelMaxFlow}</tex> общее число подъемов подъёмов не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 </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>|id = Лемма7|statement = После ненасыщающего проталкивания из <tex> u </tex> в <tex> v </tex> вершина <tex> u </tex> перестает быть переполненной.|proof =Поскольку проталкивание ненасыщающее, то величина потока, проталкиваемого через ребро <tex> (u, v) </tex> должна быть равна <tex> e(u) </tex>. После выполнения проталкивания избыточный поток вершины должен уменьшится на величину проталкиваемого потока, следовательно, после ненасыщающего проталкивания из <tex> u </tex> в <tex> v </tex> величина <tex> e(u) = 0 </tex>.

|about = 7<tex>8</tex>|id = Лемма7Лемма8

Количество насыщающих проталкиваний при выполнение алгоритма <tex> pushRealbelMaxFlow \mathrm{pushRelabelMaxFlow}</tex> не превосходит <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </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 = 8<tex>9</tex>|id = Лемма8Лемма9

Количество ненасыщающих проталкиваний при выполнение алгоритма <tex> pushRealbelMaxFlow \mathrm{pushRelabelMaxFlow}</tex> не превосходит <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>