Поток минимальной стоимости — различия между версиями
| Строка 1: | Строка 1: | ||
== Определение задачи == | == Определение задачи == | ||
{{Определение | {{Определение | ||
| − | |definition=Дано число < | + | |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''): | Суть задачи — найти поток ''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> |
}} | }} | ||
| Строка 15: | Строка 15: | ||
== Алгоритмы решения == | == Алгоритмы решения == | ||
| − | *Найти любой поток величины < | + | *Найти любой поток величины <tex>f_0</tex>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. |
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]. | *[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]. | ||
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]]. | *[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]]. | ||
Версия 01:16, 16 января 2011
Содержание
Определение задачи
| Определение: |
| Дано число и транспортная сеть с источником и стоком , где ребра имеют пропускную способность , поток и цену .
Суть задачи — найти поток f(u, v):
|
Релевантные теоремы
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
Алгоритмы решения
- Найти любой поток величины , после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости.
- Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма).
Задача о назначениях
Популярная задача, которая легко сводится к потоку минимальной стоимости - задача о назначениях.
