Изменения
Новая страница: «== Определение задачи == {{Определение |definition=Дано число f_0 и транспортная сеть <math>\,G(V,E)</math> с …»
== Определение задачи ==
{{Определение
|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>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].
== Задача о назначениях ==
Популярная задача, которая легко сводится к потоку минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].
{{Определение
|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>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].
== Задача о назначениях ==
Популярная задача, которая легко сводится к потоку минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].
