Викиконспекты - Вклад участника [ru]

Лемма об эквивалентности свойства-потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети

2011-01-15T22:25:57Z

Ivan.Volkov:

{{Лемма
|statement=
Следующие утверждения эквивалентны:
*Поток <tex> f </tex> {{---}} минимальной стоимости.
*В остаточной сети <tex> G_f </tex> нет циклов отрицательного веса.
|proof=
*<tex>\Rightarrow </tex>
От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательного веса в <tex> G_f </tex>,
<tex> c_m </tex> {{---}} наименьшая остаточная пропускная способность среди рёбер <tex> C </tex>.

Пустим по <tex> C </tex> поток <tex> f_+ = c_m </tex>.
Так как сумма весов по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{u,v \in V} p(u,v) \cdot f_+(u,v) < 0</tex>

<tex>\Rightarrow </tex> <tex>\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) < \sum_{u,v \in V} p(u,v) \cdot f</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.
*<tex>\Leftarrow </tex>
От противного. Пусть <tex> f </tex> - не минимальной стоимости. Тогда существует <tex> f_m </tex> - поток минимальной стоимости и того же объема.
Существует поток <tex> f_- </tex>, такой что <tex> f_m = f + f_m</tex>.
По сохранению потока <tex> f_- </tex> идёт по пути <tex> P </tex> и верно одно из двух утверждений:
* <tex> P </tex> - из истока в сток.
* <tex> P </tex> - цикл.
Если из истока в сток - изменится объем потока, что противрочит условию.
<tex>\Rightarrow P - цикл</tex>
<tex>\sum_{u,v \in V} p(u,v) \cdot f_-(u,v) < 0 \Rightarrow P</tex> - цикл отрицательного веса. Противоречие.
}}

==Литература==
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. - Алгоритмы. Построение и анализ.

Лемма об эквивалентности свойства-потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети

2011-01-15T22:24:58Z

Ivan.Volkov:

Поток минимальной стоимости

2011-01-15T22:16:55Z

Ivan.Volkov:

== Определение задачи ==
{{Определение
|definition=Дано число <tex>f_0</tex> и транспортная сеть <tex>\,G(V,E)</tex> с источником <tex>s \in V</tex> и стоком <tex>t \in V</tex>, где ребра <tex>(u,v) \in E</tex> имеют пропускную способность <tex>\,c(u,v)</tex>, поток <tex>\,f(u,v)</tex> и цену <tex>\,p(u,v)</tex>.

Суть задачи — найти поток ''f''(''u'', ''v''):

:<tex>\sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </tex>.
:<tex>\sum_{u,v \in V} f(u,v) = f_0</tex>
}}

== Релевантные теоремы ==
*[[Теорема_Форда-Фалкерсона_о_потоке_минимальной_стоимости|Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
*[[Лемма_об_эквивалентности_свойства_потока_быть_минимальной_стоимости_и_отсутствии_отрицательных_циклов_в_остаточной_сети|Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]

== Алгоритмы решения ==
*Найти любой поток величины <tex>f_0</tex>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].

== Задача о назначениях ==
Популярная задача, которая легко сводится к потоку минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].

== Источники ==
*[http://ru.wikipedia.org/wiki/Поток_минимальной_стоимости Википедия]

Поток минимальной стоимости

2011-01-15T22:13:34Z

Ivan.Volkov:

== Определение задачи ==
{{Определение
|definition=Дано число <math>f_0</math> и транспортная сеть <math>\,G(V,E)</math> с источником <math>s \in V</math> и стоком <math>t \in V</math>, где ребра <math>(u,v) \in E</math> имеют пропускную способность <math>\,c(u,v)</math>, поток <math>\,f(u,v)</math> и цену <math>\,p(u,v)</math>.

Суть задачи — найти поток ''f''(''u'', ''v''):

:<math>\sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </math>.
:<math>\sum_{u,v \in V} f(u,v) = f_0</math>
}}

== Релевантные теоремы ==
*[[Теорема_Форда-Фалкерсона_о_потоке_минимальной_стоимости|Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
*[[Лемма_об_эквивалентности_свойства_потока_быть_минимальной_стоимости_и_отсутствии_отрицательных_циклов_в_остаточной_сети|Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]

== Алгоритмы решения ==
*Найти любой поток величины <math>f_0</math>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].

== Задача о назначениях ==
Популярная задача, которая легко сводится к потоку минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].

== Источники ==
*[http://ru.wikipedia.org/wiki/Поток_минимальной_стоимости Википедия]

Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети

2011-01-15T22:10:23Z

Ivan.Volkov:

{{Лемма
|about=
об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
|statement=
Следующие два утверждения эквивалентны:
* <math> f </math> - поток минимальной стоимости.
* В остаточной сети <math> G_f </math> нет циклов отрицательного веса.
|proof=
*<math>\Rightarrow </math>
От противного. Пусть существует <math> C </math> {{---}} цикл отрицательного веса в <math> G_f </math>,
<math> c_m </math> {{---}} наименьшая остаточная пропускная способность среди рёбер <math> C </math>.

Пустим по <math> C </math> поток <math> f_+ = c_m </math>.
Так как сумма весов по циклу отрицательна и поток по каждому ребру одинаков, то <math> \sum_{u,v \in V} p(u,v) \cdot f_+(u,v) < 0</math>

<math>\Rightarrow </math> <math>\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) < \sum_{u,v \in V} p(u,v) \cdot f</math> <math>\Rightarrow f </math> {{---}} не минимальный. Противоречие.
}}

Поток минимальной стоимости

2011-01-15T22:09:32Z

Ivan.Volkov:

== Определение задачи ==
{{Определение
|definition=Дано число f_0 и транспортная сеть <math>\,G(V,E)</math> с источником <math>s \in V</math> и стоком <math>t \in V</math>, где ребра <math>(u,v) \in E</math> имеют пропускную способность <math>\,c(u,v)</math>, поток <math>\,f(u,v)</math> и цену <math>\,p(u,v)</math>.

Суть задачи — найти поток ''f''(''u'', ''v''):

:<math>\sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </math>.
:<math>\sum_{u,v \in V} f(u,v) = f_0</math>
}}

== Релевантные теоремы ==
*[[Теорема_Форда-Фалкерсона_о_потоке_минимальной_стоимости|Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
*[[Лемма_об_эквивалентности_свойства_потока_быть_минимальной_стоимости_и_отсутствии_отрицательных_циклов_в_остаточной_сети|Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]

== Алгоритмы решения ==
*Найти любой поток величины <math>f_0</math>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].

== Задача о назначениях ==
Популярная задача, которая легко сводится к потоку минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].

== Источники ==
*[http://ru.wikipedia.org/wiki/Поток_минимальной_стоимости Википедия]

Поток минимальной стоимости

2011-01-15T22:06:39Z

Ivan.Volkov:

== Определение задачи ==
{{Определение
|definition=Дано число f_0 и транспортная сеть <math>\,G(V,E)</math> с источником <math>s \in V</math> и стоком <math>t \in V</math>, где ребра <math>(u,v) \in E</math> имеют пропускную способность <math>\,c(u,v)</math>, поток <math>\,f(u,v)</math> и цену <math>\,p(u,v)</math>.

Суть задачи — найти поток ''f''(''u'', ''v''):

:<math>\sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </math>.
:<math>\sum_{u,Лемма_об_эквивалентности_свойства_потока_быть_минимальной_стоимости_и_отсутствии_отрицательных_циклов_в_остаточной_сетиv \in V} f(u,v) = f_0</math>
}}

== Релевантные теоремы ==
*[[Теорема_Форда-Фалкерсона_о_потоке_минимальной_стоимости|Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
*[[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]

== Алгоритмы решения ==
*Найти любой поток величины <math>f_0</math>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].

== Задача о назначениях ==
Популярная задача, которая легко сводится к потоку минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].

== Источники ==
*[http://ru.wikipedia.org/wiki/Поток_минимальной_стоимости Википедия]

Поток минимальной стоимости

2011-01-15T22:06:10Z

Ivan.Volkov:

== Определение задачи ==
{{Определение
|definition=Дано число f_0 и транспортная сеть <math>\,G(V,E)</math> с источником <math>s \in V</math> и стоком <math>t \in V</math>, где ребра <math>(u,v) \in E</math> имеют пропускную способность <math>\,c(u,v)</math>, поток <math>\,f(u,v)</math> и цену <math>\,p(u,v)</math>.

Суть задачи — найти поток ''f''(''u'', ''v''):

:<math>\sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </math>.
:<math>\sum_{u,v \in V} f(u,v) = f_0</math>
}}

== Релевантные теоремы ==
*[[Теорема_Форда-Фалкерсона_о_потоке_минимальной_стоимости|Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
*[[Лемма_об_эквивалентности_свойства-потока_быть_минимальной_стоимости_и_отсутствии_отрицательных_циклов_в_остаточной_сети|Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]

== Алгоритмы решения ==
*Найти любой поток величины <math>f_0</math>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].

== Задача о назначениях ==
Популярная задача, которая легко сводится к потоку минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].

== Источники ==
*[http://ru.wikipedia.org/wiki/Поток_минимальной_стоимости Википедия]

Блокирующий поток

2011-01-15T22:00:16Z

Ivan.Volkov:

{{Определение
|definition=
Блокирующий поток - такой поток <tex>f</tex> в данной сети <tex>G</tex>, что любой <tex>s \leadsto t</tex> путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
}}

[[Файл:Блокпоток.png|thumb|right|Рис. 1]]
Блокирующий поток не обязательно максимален (пример: см. рис. 1). [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.

== См. также ==
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Схема алгоритма Диница]]

== Источники ==
[http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]

Схема алгоритма Диница

2011-01-15T21:56:28Z

Ivan.Volkov: /* Ассимптотика алгоритма */

== Постановка задачи ==
Пусть дана сеть, т.е. ориентированный граф <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(VE\log V)</tex>, если использовать динамические деревья Слетора и Тарьяна.

== Источники ==
*[http://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Алгоритм Диница на ru.wikipedia.org]

Блокирующий поток

2011-01-15T21:51:23Z

Ivan.Volkov:

{{Определение
|definition=
Блокирующий поток - такой поток <tex>f</tex> в данной сети <tex>G</tex>, что любой <tex>s \leadsto t</tex> путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
}}

[[Файл:Блокпоток.png|thumb|right|Рис. 1]]
Блокирующий поток не обязательно максимален (см. рис. 1). [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.

== См. также ==
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Схема алгоритма Диница]]

== Источники ==
[http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]

Файл:Блокпоток.png

2011-01-15T21:46:37Z

Ivan.Volkov: Блокирующий поток, не являющийся максимальным.

Блокирующий поток, не являющийся максимальным.

Обход в глубину, цвета вершин

2011-01-15T19:27:35Z

Ivan.Volkov:

'''Обход в глубину''' (поиск в глубину, англ. Depth-First Search, DFS) - один из основных методов обхода графа, часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].

== Алгоритм ==

=== Общая идея ===
Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' вершины необходимо найти все ''не пройденные'' смежные вершины и повторить поиск для них.

=== Пошаговое представление ===
#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как u.
#Запускаем процедуру DFS(u)
#*Помечаем вершину u как ''пройденную''
#*Для каждой ''не пройденной'' смежной с u вершиной (назовем ее v) запускаем DFS(v)
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.

=== Реализация ===
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах

void dfs(int u)
{
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}

int main()
{
... //задание графа G с количеством вершин n.
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}

== Цвета вершин ==
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей. 
Поэтому в процессе алгоритма вершинам задают некоторые цвета: 
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена''; 
:''серая'' - вершина ''проходится'' в текущей процедуре DFS; 
:''черная'' - вершина ''пройдена'', все итерации DFS от нее завершены. 

Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].

=== Реализация ===
Отличие реализации с цветами от предыдущей лишь в массиве visited, который мы назовем теперь color, и дополнительной ''черной'' "метки". При этом цвета вершин будут заданы следующим образом: ''белый'' - 0, ''серый'' - 1, ''черный'' - 2. Все отличия помечены '''жирным''' шрифтом.

vector<'''int'''> '''color'''; //вектор для хранения информации '''о цвете''' вершин

void dfs(int u)
{
'''color[u] = 1; //раскрашиваем вершину в ''серый'' цвет'''
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!color[v]) //проверяем, не находились ли мы ранее в выбранной вершине, '''условие не требует изменений,'''
dfs(v); '''//поскольку мы считаем вершину "не пройденной" только тогда, когда она ''белого'' цвета, т.е. когда color[v] = 0'''
'''color[u] = 2; //раскрашиваем вершину в ''черный'' цвет'''
}

int main()
{
... //задание графа G с количеством вершин n.
'''color.assign(n, 0);''' //в начале все вершины в графе ''не пройденные'', '''т.е. ''белые''.'''
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}

== Источники ==
*[http://ru.wikipedia.org/wiki/Поиск_в_глубину Обход в глубину на ru.wikipedia.org]
*[http://www.e-maxx.ru/algo/dfs Обход в глубину. Реализации.]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]

Схема алгоритма Диница

2011-01-15T19:21:34Z

Ivan.Volkov: Новая страница: «== Постановка задачи == Пусть дана сеть, т.е. ориентированный граф <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]

Блокирующий поток

2011-01-15T18:00:22Z

Ivan.Volkov: Новая страница: «{{Определение |definition= Блокирующий поток - такой поток <tex>f</tex> в данной сети <tex>G</tex>, что л…»

{{Определение
|definition=
Блокирующий поток - такой поток <tex>f</tex> в данной сети <tex>G</tex>, что любой <tex>s \leadsto t</tex> путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
}}

Блокирующий поток не обязательно максимален. [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.

== См. также ==
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Схема алгоритма Диница]]

== Источники ==
[http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]

Обход в глубину, цвета вершин

2010-11-10T13:44:40Z

Ivan.Volkov: Новая страница: «'''Обход в глубину''' (поиск в глубину, англ. Depth-First Search, DFS) - один из основных методов обхода г…»