Cormen, Leiserson, Rivest, Stein. Introduction to algorithms 2ed, MIT, 2001 ISBN 0070131511 984s Chapter 26
В этом разделе мы излагаем метод проталкивания предпотока для вычисления максимального потока. Нужно отметить, что наиболее асимптотически быстрые алгоритмы решения задачи о максимальном потоке используют идею данного метода, наиболее быстрые реальные реализации алгоритма поиска максимального потока основаны на методе проталкивания предпотока. Этот метод применим и к другим задачам, например к задаче о поиске потока наименьшей стоимости. В этом разделе представлен основной метод Гольдберга для поиска максимального потока. Уже простейшая его реализация требует всего лишь O(V^2E) шагов и, таким образом, опережает алгоритм Эдмондса-Карпа, время выполнения которого O(VE^2). В разделе 26.5 мы покажем, как улучшить основной алгоритм до оценки O(V^3).
В отличие от алгоритма Эдмондса-Карпа, мы не просматриваем всю всю остаточную сеть на каждом шаге, а действуем локально в окрестности одной вершины. Кроме того, мы не требуем, выполнения закона сохранения потока в процессе работы алгоритма, довольствуясь выполнением свойств предпотока. Мы будем называть предпотоком функцию f: VxV -> R, которая кососимметрична, удовлетворяет ограничениям, связанным с пропускными способностями, а также следующему ослабленному закону сохранения: f(V; u) > 0 для всех вершин u E V-s. Мы назовем это число избыточным потоком в вершине u: e(u)=f(V,u). Будем говорить, что вершина u E V-{s,t} переполнена, если e(u)>0.
Мы начнем этот раздел с описания интуитивных соображений по поводу работы метода проталкивания предпотока. Затем опишем две основные операции: проталкивание предпотока и подъем вершины. И в завершение, докажем правильность общего алгоритма проталкивания предпотока и оценим время его работы.
Наилучшее интуитивное понимание метода проталкивания предпотока достигается в терминах потоков жидкости: мы представим сеть G=(V;E) в виде системы соединенных труб заданной пропускной способности. Применяя эту аналогию к методу Форда-Фалкерсона, нужно сказать, что каждый путь в остаточной сети дает увеличение на дополнительный не разветвляющийся поток жидкости от истока к стоку. Метод Форда-Фалкерсона итеративно добавляет увеличивающие пути, пока это возможно.
Общий алгоритм проталкивания предпотока реализует другую идею. Как раньше, направленные ребра соответствуют трубам. Вершины, являющиеся точками разветвления труб, имеют также два интересных свойства. Первое - накапливать избыточный поток: каждая вершина имеет дополнительную трубу, ведущую в достаточно большую емкость, которая может накапливать жидкость. Второе - каждая вершина, ее резервуар и все соединения с трубами находятся на платформе, высота которой увеличивается по мере выполнении алгоритма.
Высота вершины определяет как поток проталкивается: мы проталкиваем поток только вниз, то есть из более высокой вершины в более низкую. Поток из более низкой вершины в более высокую может быть положительным, тем не менее, операции, выполняющие проталкивание потока, применяются только к вершинам, которые расположены выше, в вершины, расположенную ниже. Высота истока является фиксированной, равна |V|, высота стока также фиксирована и равна 0. Высота остальных вершин изначально равна 0 и по мере выполнения алгоритма увеличивается. Алгоритм сначала проталкивает как можно больший поток вниз от истока к стоку. Исток обладает тем свойством, что все исходящие из него трубы могут быть заполнены до своей пропускной способности, то есть, исток может обеспечить поток равный пропускной способности разреза (s,V-s). Сначала, когда поток попадает в вершину, он собирается в резервуаре вершины. Отсюда он, в конечном итоге, проталкивается ниже.
Может получиться так, что все ненасыщенные трубы, выходящие из вершины u входят в вершины, которые имеют туже или большую высоту, чем u. В этом случае для того, что бы протолкнуть избыточный поток, необходимо увеличить высоту вершины u - операция, называемая подъем. Высота увеличивается до значения, которое на 1 больше, чем высота наиболее нижнего соседа, смежного с u через ненасыщенное ребро. Таким образом, после выполнения подъема, существует как минимум одна труба, через которую можно проталкивать поток.
В итоге весь поток, который может достичь стока, достигает его. Поток не может получиться больше, потому что учитываются ограничения пропускной способности труб; поток через любой разрез по-прежнему остается ограниченным пропускной способностью разреза. Для того, чтобы предпоток превратился в поток, алгоритм отправляет избыток, собранный в резервуарах переполненных вершин, обратно к истоку, продолжая поднимать вершины выше фиксированной высоты истока |V|. Как будет показано ниже, когда все резервуары освобождены, предпоток станет не просто потоком, а в добавок максимальным потоком.
Итак, алгоритм проталкивания предпотока использует две основные операции: проталкивание потока из вершины в соседнюю и подъем вершины. Возможность выполнить ту или иную операцию зависит от высот вершин, требования к которым мы сейчас определим более точно.
Пусть G = (V;E) - сеть с истоком s и стоком t, а f - предпоток в G. Функция h: V -> N называется высотной функцией, если h(s) = |V|, h(t) = 0 и h(u) < h(v) + 1 для любого остаточного ребра (u;v) E Ef. Следующая лемма дает очевидную переформулировку этого условия:
Пусть f - предпоток в сети G = (V;E)и h - высотная функция. Тогда если для вершин u,v E V , выполнено h(u) > h(v) + 1, то остаточная сеть не содержит ребра (u; v).
Процедура Push(u; v) применима, если вершина u переполнена(то есть c(u; v) > 0) и если h(u) = h(v)+1. Приведенный ниже псевдокод обновляет предпоток в сети G=(V;E). Избыточный поток, находящийся в вершине u представлен в виде атрибута e[u], высота вершины - в виде h[u], df(u;v) - временная переменная, содержащая поток, который можно протолкнуть из u в v.
Push(u,v) 1. Applies when: u is overflowing, cf(u,,v)>0, and h[u]=h[v]+1 2. Action: Push df(u,v)=min(e[u],cf(u,n)) units of flow fuom u to v 3. df(u,v)=min(e[u],cf(u,v)) 4. f[u,v]=f[u,v]+df(u,v) 5. f[v,t]=-f[u,v] 6. e[u]=e[u]-df(u,v) 7. e[v]=e[v]+df(u,v)
Код операции Rush выполняет следующие действия:
Считается, что избыток в вершине равен e[u] > 0, и что остаточная пропускная способность ребра (u;v) также положительна. Поэтому мы можем направить min(e[u];cf(u; v)) > 0 единиц потока из u в v, не превысив пропускной способности и не сделав избыток отрицательным. Строка 3 вычисляет значение df(u;v), затем в строках 4-5 обновляется предпоток и в строках 6-7 обновляется избыточный поток в вершинах. Следовательно, функция f останется предпотоком(если она им была).Отметим, что в коде операции Push не учитывается высота вершин u и v, поэтому она не должна быть выполнена до тех пор, когда h[u]=h[v]+1. Таким образом, избыточный поток проталкивается вниз только при разности высот в 1.
Согласно лемме 26.13 не существует остаточных ребер между вершинами, высоты которых отличаются более чем на 1, поэтому пока h действительно является функцией высоты, разрешение проталкивать предпоток при разности высот более чем в 1, не даст ни какого результата.
Операция Push(u; v) называется проталкиванием из вершины u в вершину v. Если проталкивание применяется к ребру (u;v), выходящему из вершины u, мы также будем говорить, что операция проталкивания применена к вершине u. Проталкивание называется насыщающим, если в результате ребро (u; v) становится насыщенным, то есть если cf(u; v) обращается в нуль(ребро исчезает из остаточной сети); в противном случае проталкивание считают ненасыщающим. Если ребро насыщенно, оно не появляется остаточной сети. Далее приведена простая лемма, описывающая результат выполнения ненасыщающего проталкивания.
После ненасыщающего проталкивания из u в v, u более не является переполненной.
Т.к. проталкивание было ненасыщающим, количество проталкиваемого предпотока равно e[u]. Таким образом, e[u] становится равным 0.
Операция подъема применяется, если вершина u переполнена и h[v]>h[u] для всех (u;v;)E Ef. Другими словами, мы можем поднять переполненную вершину u, если любая вершина v, для которой существует остаточное ребро (u;v), имеет высоту не меньшею, чем u. (Вспомним, что по определению ни источник, ни сток не могут быть переполнены, из чего следует, что ни исток ни сток не могут быть подняты)
Relabel(u)
1. Applies when: u is overflowing and for all v E V such that (u,v) E Ef, we have h[v]>=f[u]
2. Action: Increase the height of u.
3. h[u]=1+min{h[v]: (u,v) E Ef}
Когда мы вызываем операцию Relabel(u), мы говорим, что выполняется подъем вершины u. Заметим, что если вершина u поднята, то в Ef найдёется по крайней мере одно ребро, выходящее из u, т.о. минимум в коде берется по непустому множеству. Это свойство следует из предположения, что u переполнена. Таким образом, e[u]>0, далее f[V; u] = e[u] > 0, поэтому существует по крайней мере одна такая вершина v, для которой f(v; u) > 0. Получаем
cf(u,v) = c(u,v) - f[u,v] = = c(u,v) + f[v,u] > > 0
Что подразумевает, что (u;v) E Ef. Т.о. операция подъема дает u наибольшую высоту, допускаемую ограничениями, накладываемыми на функцию высоты.
Общий алгоритм проталкивания предпотока использует следующую подпрограмму для создания начального предпотока в сети:
Imitialize-Preflow(G,s) 1. for each vertex u E V[G] 2. do h[u]=0 3. e[u]=0 4. for each edge (u,v) E E[G] 5. do f[u,v]=0 6. f[v,u]=0 7. h[s]=|V[G]| 8. for each vertex r E Adj[s] 9. do f[s,u]=c(s,u) 10. f[u,s]=-c(s,u) 11. e[u]=c(s,u) 12. e[s]=e[s]-c(s,u)
Initialize-Preflow создает начальный предпоток согласно формуле:
c(u,v) if u=s;
f[u,v]= -c(v,u) if v=s;
0 otherwise
То есть, каждое ребро, выходящее из истока, заполняется до своей пропускной способности, оставшиеся ребра не содержат потока. Для каждой вершины v, инцидентной истоку, мы изначально имеем e[v]=c(s;v), e[s] инициализируется суммой этих пропускных способностей со знаком минус. Общий алгоритм использует следующие начальные значения функции высоты:
h[u]=|V| if u=s;
0 otherwise
Это функция высоты, так как неравенство h[u]>h[v]+1 выполняется только для u=s, таким образом, все ребра (u;v) насыщены, то есть не принадлежат остаточной сети. После инициализации выполняется последовательность операций проталкивания и подъема, при этом порядок выполнения значения не имеет:
Gemeric-Push-Relabel(G) 1. Initialize-Preflow(G,s) 2. while можно выполнить проталкивание или подъем 3. do выполнить допустимую операцию проталкивания или подъема