16
правок
Изменения
Новая страница: «== Постановка задачи == Пусть дана сеть, т.е. ориентированный граф <tex>G</tex>, в котором каждому …»
== Постановка задачи ==
Пусть дана сеть, т.е. ориентированный граф <tex>G</tex>, в котором каждому ребру <tex>(u,v)</tex> приписана пропускная способность <tex>c(u,v)</tex>, а также выделены две вершины — исток <tex>s</tex> и сток <tex>t</tex>. Требуется найти в этой сети поток <tex>f(u,v)</tex> из <tex>s</tex> в <tex>t</tex> максимальной величины.
== Используемые определения ==
#[[Дополняющая сеть, дополняющий путь]]
#[[Блокирующий поток]]
#Вспомогательная(слоистая) сеть.
::Для начала определим для каждой вершины <tex>v</tex> данной сети <tex>G</tex> длину кратчайшего <tex>s \leadsto v</tex> пути и обозначим ее <tex>d[v]</tex> (для этого можно воспользоваться [[Обход в глубину, цвета вершин|обходом в глубину]]). Тогда во вспомогательную сеть включают все те ребра <tex>(u,v)</tex> исходной сети, для которых <tex>d[u] + 1 = d[v]</tex>.
::Очевидно, полученная сеть ациклична. При этом любой <tex>s \leadsto t</tex> путь во вспомогательной сети является кратчайшим путём в исходной.
== Алгоритм ==
=== Схема алгоритма ===
#Для каждого ребра <tex>(u,v)</tex> данной сети <tex>G</tex> зададим <tex>f(u,v) = 0</tex>.
#Построим вспомогательную сеть <tex>G_L</tex> из дополняющей сети <tex>G_f</tex> данного графа <tex>G</tex>. Если <tex>d[t] = \infty</tex>, остановиться и вывести <tex>f</tex>.
#Найдем блокирующий поток <tex>f'</tex> в <tex>G_L</tex>. См. [[Алгоритм поиска блокирующего потока в ациклической сети]].
#Дополним поток <tex>f</tex> найденным потоком <tex>f'</tex> и перейдем к шагу 2.
=== Корректность алгоритма ===
Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.
В самом деле, предположим, что в какой-то момент во вспомогательной сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток вообще не достижим во вспомогательной сети из истока . Но поскольку она содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя [[Теорема Форда-Фалкерсона|теорему Форда-Фалкерсона]], получаем, что текущий поток в самом деле максимален.
=== Ассимптотика алгоритма ===
{{Утверждение
|statement=
Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е <tex>d'[t] > d[t]</tex>, где <tex>d'[t]</tex> - значение, полученное на следующей фазе алгоритма.
|proof=
От противного. Рассмотрим кратчайший путь из истока в сток; по предположению, его длина должна сохраниться неизменной. Однако остаточная сеть на следующей фазе содержит только рёбра остаточной сети перед выполнением текущей фазы, либо обратные к ним. Таким образом, пришли к противоречию: нашёлся <tex>s \leadsto t</tex> путь, который не содержит насыщенных рёбер, и имеет ту же длину, что и кратчайший путь. Этот путь должен был быть "заблокирован" блокирующим потоком, чего не произошло, в чём и заключается противоречие, что и требовалось доказать.
}}
Поскольку длина кратчайшего <tex>s \leadsto t</tex> пути не может превосходить <tex>n - 1</tex>, то, следовательно, алгоритм Диница совершает не более <tex>n - 1</tex> фазы.
Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за <tex>O(VE^2)</tex> или за <tex>O(V^2E)</tex>. Также возможно достичь ассимптотики <tex>O(VElogV)</tex>, если использовать динамические деревья Слетора и Тарьяна.
== Источники ==
*[http://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Алгоритм Диница на ru.wikipedia.org]
Пусть дана сеть, т.е. ориентированный граф <tex>G</tex>, в котором каждому ребру <tex>(u,v)</tex> приписана пропускная способность <tex>c(u,v)</tex>, а также выделены две вершины — исток <tex>s</tex> и сток <tex>t</tex>. Требуется найти в этой сети поток <tex>f(u,v)</tex> из <tex>s</tex> в <tex>t</tex> максимальной величины.
== Используемые определения ==
#[[Дополняющая сеть, дополняющий путь]]
#[[Блокирующий поток]]
#Вспомогательная(слоистая) сеть.
::Для начала определим для каждой вершины <tex>v</tex> данной сети <tex>G</tex> длину кратчайшего <tex>s \leadsto v</tex> пути и обозначим ее <tex>d[v]</tex> (для этого можно воспользоваться [[Обход в глубину, цвета вершин|обходом в глубину]]). Тогда во вспомогательную сеть включают все те ребра <tex>(u,v)</tex> исходной сети, для которых <tex>d[u] + 1 = d[v]</tex>.
::Очевидно, полученная сеть ациклична. При этом любой <tex>s \leadsto t</tex> путь во вспомогательной сети является кратчайшим путём в исходной.
== Алгоритм ==
=== Схема алгоритма ===
#Для каждого ребра <tex>(u,v)</tex> данной сети <tex>G</tex> зададим <tex>f(u,v) = 0</tex>.
#Построим вспомогательную сеть <tex>G_L</tex> из дополняющей сети <tex>G_f</tex> данного графа <tex>G</tex>. Если <tex>d[t] = \infty</tex>, остановиться и вывести <tex>f</tex>.
#Найдем блокирующий поток <tex>f'</tex> в <tex>G_L</tex>. См. [[Алгоритм поиска блокирующего потока в ациклической сети]].
#Дополним поток <tex>f</tex> найденным потоком <tex>f'</tex> и перейдем к шагу 2.
=== Корректность алгоритма ===
Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.
В самом деле, предположим, что в какой-то момент во вспомогательной сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток вообще не достижим во вспомогательной сети из истока . Но поскольку она содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя [[Теорема Форда-Фалкерсона|теорему Форда-Фалкерсона]], получаем, что текущий поток в самом деле максимален.
=== Ассимптотика алгоритма ===
{{Утверждение
|statement=
Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е <tex>d'[t] > d[t]</tex>, где <tex>d'[t]</tex> - значение, полученное на следующей фазе алгоритма.
|proof=
От противного. Рассмотрим кратчайший путь из истока в сток; по предположению, его длина должна сохраниться неизменной. Однако остаточная сеть на следующей фазе содержит только рёбра остаточной сети перед выполнением текущей фазы, либо обратные к ним. Таким образом, пришли к противоречию: нашёлся <tex>s \leadsto t</tex> путь, который не содержит насыщенных рёбер, и имеет ту же длину, что и кратчайший путь. Этот путь должен был быть "заблокирован" блокирующим потоком, чего не произошло, в чём и заключается противоречие, что и требовалось доказать.
}}
Поскольку длина кратчайшего <tex>s \leadsto t</tex> пути не может превосходить <tex>n - 1</tex>, то, следовательно, алгоритм Диница совершает не более <tex>n - 1</tex> фазы.
Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за <tex>O(VE^2)</tex> или за <tex>O(V^2E)</tex>. Также возможно достичь ассимптотики <tex>O(VElogV)</tex>, если использовать динамические деревья Слетора и Тарьяна.
== Источники ==
*[http://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Алгоритм Диница на ru.wikipedia.org]
