Изменения

==Жадный алгоритм==Идея заключается в том, чтобы по одному находить пути из [[Определение_сети,_потока|истока]] <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>O(E)</tex>, где <tex>E</tex> — число рёбер в графе. Поскольку каждый путь насыщает как минимум одно ребро, всего будет <tex>O(E)</tex> путей. Итого общая асимптотика составляет <tex>O(E^2)</tex>. ==Удаляющий обход==Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.   '''int''' dfs('''int''' <tex>v</tex>, '''int''' flow) '''if''' (flow == 0) '''return''' 0 '''if''' (<tex>v</tex> == <tex>t</tex>) '''return''' flow '''for''' (<tex>u</tex> = ptr[<tex>v</tex>] '''to''' n) '''if''' (<tex>vu \in E</tex>) pushed = dfs(<tex>u</tex>, min(flow, c(<tex>vu</tex>) - f(<tex>vu</tex>))) f(<tex>vu</tex>) += pushed f(<tex>uv</tex>) -= pushed '''return''' pushed ptr[<tex>v</tex>]++ '''return''' 0  '''main'''() '''...''' flow = 0 '''for''' ('''int''' i = 1 '''to''' n) ptr[i] = 0 '''do''' pushed = dfs(<tex>s</tex>, <tex>\infty</tex>) flow += pushed '''while''' (pushed > 0)  Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <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>sp</tex> в . Затем пускается поток величины <tex>tp</tex>из истока в сток, пока проходящий через эту вершину. При этом если [[Дополняющая сеть, дополняющий путь|остаточная пропускная способность]] ребра равна нулю, то это возможноребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные рёбра удаляются.

===КорректностьПодробное описание===Данная идея корректна, поскольку * Для каждой вершины <tex>dfsv</tex> найдёт все пути из вычислим входящий и исходящий потенциал: <tex>sp_{in}=\sum \limits_{u} c(u, v)</tex> в и <tex>tp_{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}(uv), p_{out}(v))</tex>. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через неё проходить. Ясно, что через вершины с <tex>p(v)=0</tex> поэтомупоток проходить не может. Следовательно, их можно удалить из [[Дополняющая сеть, насыщая рёбрадополняющий путь|вспомогательной сети]]. Удалим эти вершины и дуги, мы хотя бы единожды достигнем стока им инцидентные, обновив должным образом потенциалы вершин, смежных с удалёнными. Если в результате появятся новые вершины с <tex>tp(v)=0</tex>, следовательно блокирующий поток всегда найдётсяудалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с <tex>p(v)\ne0</tex>.

===Асимптотика===Используя * После этого приступим к построению [[Блокирующий поток|блокирующего потока]]. Пусть вершина <tex>v</tex> принадлежит <tex>dfsk</tex> каждый путь находится за -ому слою и <tex>Op(v)=min (Ep(w), w \in L_k)</tex>, где <tex>L_k</tex> — <tex>k</tex>-й слой. Поскольку каждый путь насыщает как минимум одно ребро, всего будет Протолкнем <tex>Op(Ev)</tex> путейединиц потока из вершины <tex>v</tex> в смежные с ней вершины по исходящим дугам с [[Дополняющая сеть, дополняющий путь | остаточной пропускной способностью]] <tex>c_f \ne 0</tex>. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. Итого общая асимптотика составляет В результате, весь (в виду минимальности потенциала вершины <tex>v</tex>) проталкиваемый поток соберется в вершинах <tex>O(E^2k+1)</tex>-го слоя.

==Удаляющий обход=====Идея===По-прежнему по одному находятся пути * Повторим процесс отправки потока из вершин <tex>s(k+1)</tex> -го слоя, содержащих избыток потока, в смежные им вершины <tex>t(k+2)</tex>-го слоя. И так до тех пор, но применяется следующая оптимизация: пока весь поток не соберется в процессе обхода последнем слое, в глубину удаляются котором содержится только сток <tex>t</tex>, ибо все ребраостальные вершины, ранее ему принадлежащие, вдоль которых нельзя дойти до стокабыли удалены, поскольку их потенциалы нулевые. То естьСледовательно, весь поток величины <tex>p(v)</tex>, если для текущей отправленный из вершины <tex>v</tex> выполнено , где <tex>dfsp(v) = false</tex>, нужно удалить из графа эту вершину и все инцидентные ей ребра. С точки зрения реализации, надо просто поддерживать - минимальный полностью соберется в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину<tex>t</tex>.

===Асимптотика===Если обход в глубину достигает стока* На втором этапе вновь, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за начиная с вершины <tex>O(V + K)v</tex>, где осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам <tex>K(k-1)</tex> - число продвижения указателей. Учитываяго слоя, что всего запусков обхода в глубину в рамках поиска одного [[Блокирующий поток|блокирующего потока]] будет затем <tex>O(Pk-2)</tex>-го. И так до тех пор, где пока весь поток величины <tex>Pp(v)</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за отправленный в вершину <tex>O(PV + \sum\limits_i{K_i})v</tex>, что, учитывая, что все указатели в сумме прошли расстояние где <tex>Op(Ev)</tex>- минимальный, дает асимптотику не соберется в истоке <tex>O(PV + E)s</tex>. В худшем случаеТаким образом, когда блокирующий поток насыщает все ребра, асимптотика получается и во вспомогательной и в основной сети увеличится на величину <tex>O(VE)p</tex>.

==Алгоритм узкого места== MPM algorithm(<tex>s, t</tex>)===Идея=== {Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина foreach <tex>r(uv) \in E</tex> с минимальным потенциалом <tex>f(uv) \rholeftarrow 0 </tex>; Вычисляем остаточную сеть <tex>R</tex>; Найдём вспомогательный граф <tex>L</tex>. Затем пускается поток величины для <tex>R</tex>; while (<tex>t \rhoin L</tex>) { while (<tex>t</tex> достижима из истока <tex>s</tex> в сток<tex>L</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>L</tex> из <tex>R</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>Замечание<==Источники информации==* [http:/b> /e-maxx.ru/algo/dinic MAXimal :: algo :: Алгоритм Малхотры — Кумара — Диница]*[http://www.facweb.iitkgp.ernet.in/~arijit/courses/autumn2006/cs60001/lec-flow-4.pdf The MPM Algorithm]*[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%B0%D0%BB%D1%85%D0%BE%D1%82%D1%80%D1%8B_%E2%80%94_%D0%9A%D1%83%D0%BC%D0%B0%D1%80%D0%B0_%E2%80%94_%D0%9C%D0%B0%D1%85%D0%B5%D1%88%D0%B2%D0%B0%D1%80%D0%B8 Алгоритм Малхотры — Кумара — Махешвари]*[http://eprints.utas.edu.au/160/1/iplFlow.pdf Оригинальная публикация алгоритма Малхотры — Кумара — Махешвари для поиска блокирующего потока использует алгоритм узкого места.]

==Источники==* http://ru.wikipedia.org* http[[Категория://e-maxx.ruАлгоритмы и структуры данных]]* http[[Категория://algolist.manual.ruЗадача о максимальном потоке]]