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