Поток минимальной стоимости — различия между версиями
| Строка 6: | Строка 6: | ||
:<math>\sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </math>. | :<math>\sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </math>. | ||
| − | :<math>\sum_{u, | + | :<math>\sum_{u,v \in V} f(u,v) = f_0</math> |
}} | }} | ||
== Релевантные теоремы == | == Релевантные теоремы == | ||
*[[Теорема_Форда-Фалкерсона_о_потоке_минимальной_стоимости|Теорема Форда-Фалкерсона о потоке минимальной стоимости]] | *[[Теорема_Форда-Фалкерсона_о_потоке_минимальной_стоимости|Теорема Форда-Фалкерсона о потоке минимальной стоимости]] | ||
| − | *[[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] | + | *[[Лемма_об_эквивалентности_свойства_потока_быть_минимальной_стоимости_и_отсутствии_отрицательных_циклов_в_остаточной_сети|Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] |
Версия 01:09, 16 января 2011
Содержание
Определение задачи
| Определение: |
| Дано число f_0 и транспортная сеть с источником и стоком , где ребра имеют пропускную способность , поток и цену .
Суть задачи — найти поток f(u, v):
|
Релевантные теоремы
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
Алгоритмы решения
- Найти любой поток величины , после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости.
- Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма).
Задача о назначениях
Популярная задача, которая легко сводится к потоку минимальной стоимости - задача о назначениях.
