Изменения

Прежде всего было бы правильно начать с определения [[Блокирующий поток|блокирующего потока]]==Жадный Алгоритм=====Идея=алгоритм==Идея заключается в том, чтобы по одному находить пути из [[Определение_сети,_потока|истока ]] <tex>s</tex> в [[Определение_сети,_потока|сток ]] <tex>t</tex>, пока это возможно. [[Обход в глубину, цвета вершин| Обход в глубину]] найдёт все пути из <tex>s</tex> в <tex>t</tex>, если из <tex>s</tex> достижима <tex>t</tex>, а [[Определение_сети,_потока|пропускная способность]] каждого ребра <tex>c(u, v)>0</tex> поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока <tex>t</tex>, следовательно блокирующий поток всегда найдётся.

===Корректность===Данная идея корректна, поскольку Используя <tex>dfs</tex> найдёт все пути из , каждый путь находится за <tex>s</tex> в <tex>tO(E)</tex>, если из где <tex>s</tex> достижима <tex>tE</tex>— число рёбер в графе. Поскольку каждый путь насыщает как минимум одно ребро, а пропускная способность каждого ребра всего будет <tex>cO(u, vE)>0</tex> поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока путей. Итого общая асимптотика составляет <tex>tO(E^2)</tex>, следовательно блокирующий поток всегда найдётся.

==Удаляющий обход=Асимптотика=Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.   '''int''' dfs('''int''' <tex>v</tex>, '''int''' flow) '''if''' (flow ==0) '''return''' 0Используя '''if''' (<tex>dfsv</tex> == <tex>t</tex>) '''return''' flow '''for''' (<tex>u</tex> каждый путь находится за = ptr[<tex>v</tex>O] '''to''' n) '''if''' (<tex>vu \in E</tex>) pushed = dfs(<tex>u</tex>. Поскольку каждый путь насыщает как минимум одно ребро, всего будет min(flow, c(<tex>vu</tex>O) - f(E<tex>vu</tex>))) f(<tex>vu</tex> путей. Итого общая асимптотика составляет ) += pushed f(<tex>uv</tex>O(E^2)-= pushed '''return''' pushed ptr[<tex>v</tex>.]++ '''return''' 0

==Удаляющий обход== '''main'''()===Идея===По-прежнему по одному находятся пути из <tex>s</tex> в <tex>t</tex>, но применяется следующая оптимизация: в процессе обхода в глубину удаляются все ребра, вдоль которых нельзя дойти до стока '''. То есть, если для текущей вершины <tex>v</tex> выполнено <tex>dfs(v) = false</tex>, нужно удалить из графа эту вершину и все инцидентные ей ребра. С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. int dfs (int v, int flow) {''' if (!flow) return = 0; if (v == t) return flow; '''for ''' ('''int & to''' i =ptr[v]; 1 '''to<''' n; ++to) { if (d ptr[toi] != d[v] + 1) continue;0 '''do''' int pushed = dfs (to<tex>s</tex>, min (flow, c[v][to] - f[v][to])<tex>\infty</tex>); if (pushed) { f[v][to] flow += pushed; return pushed; } } return 0; } ..................................... '''while ''' (pushed = dfs(s, INF)> 0) flow += pushed;

===Асимптотика===Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>V</tex> — число вершин в графе, а <tex>K</tex> - — число продвижения указателей. УчитываяВвиду того, что всего запусков обхода в глубину в рамках поиска одного [[Блокирующий поток|блокирующего потока]] будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + \sum\limits_i{K_i})</tex>, что, учитывая, что все указатели в сумме прошли расстояние <tex>O(E)</tex>, дает асимптотику <tex>O(PV + E)</tex>. В худшем случае, когда блокирующий поток насыщает все ребрарёбра, асимптотика получается <tex>O(VE)</tex>.

<b>Замечание:</b> Если в [[Схема алгоритма Диница|алгоритме Диница]] искать блокирующий поток удаляющим обходом, то его эффективность составит <tex>O(V^2E)</tex>, что уже лучше эффективности [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа ]] <tex>O(VE^2)</tex>.

==Алгоритм узкого местаМалхотры — Кумара — Махешвари==

Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует запускаем цикл. На , на каждой его итерации определяется вершина которого определяем вершину <tex>v</tex> с минимальным потенциалом <tex>p</tex>. Затем пускается поток величины <tex>p</tex> из истока в сток, проходящий через эту вершину. При этом если [[Дополняющая сеть, дополняющий путь|остаточная пропускная способность ]] ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра рёбра удаляются.

* Для каждой вершины <tex>v</tex> вычислим входящий и исходящий потенциал вершин — сумму пропускных способностей : <tex>p_{in}=\sum \limits_{u} c(u, v)</tex> дуг сети Диницаи <tex>p_{out}=\sum \limits_{u} c(v, входящих и исходящих из вершины соответственноu)</tex>. Входящий потенциал истока Пусть <tex>p_{in}(s)=\infty</tex> и исходящий потенциал стока положим равными бесконечности<tex>p_{out}(t)=\infty</tex>. Определим потенциал или пропускную способность вершины в [[Определение сети как минимум из ее входящего и исходящего потенциалов, потока|сети]] <tex>p(v)=min(p_{in}(v), p_{out}(v))</tex>. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через нее неё проходить. Ясно, что через вершины с нулевым потенциалом <tex>p(v)=0</tex> поток проходить не может. Следовательно, их можно удалить из [[Дополняющая сеть, дополняющий путь|вспомогательной сети]]. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удаленнымиудалёнными. Если в результате появятся новые вершины с нулевым потенциалом<tex>p(v)=0</tex>, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с ненулевым потенциалом<tex>p(v)\ne0</tex>. * После этого приступим к построению [[Блокирующий поток|блокирующего потока]]. Пусть вершина <tex>v</tex> принадлежит <tex>k</tex>-ому слою и <tex>p(v)=min (p(w), w \in L_k)</tex>, где <tex>L_k</tex> — <tex>k</tex>-й слой. Протолкнем <tex>p(v)</tex> единиц потока из вершины <tex>v</tex> в смежные с ней вершины по исходящим дугам с [[Дополняющая сеть, дополняющий путь | остаточной пропускной способностью]] <tex>c_f \ne 0</tex>. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины <tex>v</tex>) проталкиваемый поток соберется в вершинах <tex>(k+1)</tex>-го слоя.  * Повторим процесс отправки потока из вершин <tex>(k+1)</tex>-го слоя, содержащих избыток потока, в смежные им вершины <tex>(k+2)</tex>-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое, в котором содержится только сток <tex>t</tex>, ибо все остальные вершины, ранее ему принадлежащие, были удалены, поскольку их потенциалы нулевые. Следовательно, весь поток величины <tex>p(v)</tex>, отправленный из вершины <tex>v</tex>, где <tex>p(v)</tex> - минимальный полностью соберется в <tex>t</tex>.

После этого приступим к построению блокирующего потока. Пусть вершина * На втором этапе вновь, начиная с вершины <tex>v</tex> принадлежит <tex>k</tex>-ому слою. Протолкнем <tex>p</tex> единиц , осуществляется подвод потока из вершины с минимальным потенциалом в смежные с ней вершины уже по исходящим входящим дугам с ненулевой остаточной пропускной способностью. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины <tex>v</tex>) проталкиваемый поток соберется в вершинах на первом шаге недостаток потока переадресуется к узлам <tex>(k+1)</tex>-го слоя. Повторим процесс отправки потока из вершин <tex>(k+1)</tex>-го слоя, содержащих избыток потока, в смежные им вершины затем <tex>(k+-2)</tex>-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое. Заметим, что в этом слое содержится только сток, ибо все остальные вершины, ранее ему принадлежащие, были удалены из сети Диница, как вершины, имеющие нулевой потенциал. Следовательно, весь поток величины <tex>p(v)</tex>, отправленный из вершины с минимальным потенциалом полностью соберется в стоке. На втором этапе вновь, начиная с вершины вершину <tex>v</tex>, осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам <tex>(k-1)</tex>-го слоя, затем где <tex>p(k-2v)</tex>-го. И так до тех порминимальный, пока весь потока величины не соберется в истоке <tex>ps</tex>, отправленные из вершины с минимальным потенциалом, не соберется в истоке. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину <tex>p</tex>.

MPM algorithm(<tex>MPM algorithm(s, t)</tex>) { foreach <tex>for each (uv) \in E</tex> <tex>f(uv)\leftarrow 0 </tex> = 0; Вычисляем остаточную сеть <tex>R</tex>; Найдём вспомогательный граф <tex>L</tex> для <tex>R</tex>; while (<tex>while (t \in L)</tex>) <tex>begin</tex> { <tex> while</tex> (<tex>t</tex> достижима из <tex>s</tex> в <tex>L</tex>) <tex>begin</tex> { найдём <tex>v</tex> с миниальной минимальной пропускной способностью <tex>g</tex>; проталкиваем <tex>g</tex> единиц потока из <tex>v</tex> в <tex>t</tex>; проталкиваем <tex>g</tex> единиц потока из <tex>s</tex> в <tex>v</tex>; изменяем <tex>f</tex>, <tex>L</tex> и <tex>R</tex>; <tex>end</tex> } вычисляем новый вспомогательный граф <tex>L</tex> из <tex>R</tex>; } <tex>end</tex>}

Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(V K + E_i)</tex> действий, где <tex>K = O(V)</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых реберрёбер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum\limits_i{O(VK+E_i)} = O(VK^2)</tex> действий.

<b>Замечание</b> Алгоритм Малхотры — Кумара — Махешвари для поиска блокирующего потока использует алгоритм узкого места== См.также ==* [[Блокирующий поток]]* [[Схема алгоритма Диница]]

==Источникиинформации==*[http://e-maxx.ru/algo/dinic#8 e-maxx MAXimal :: algo :: Алгоритм Диница]