147
правок
Изменения
Нет описания правки
==Поток минимальной стоимости==
{{Определение
|definition='''Стоимость потока'''. Дана сеть <tex>G(V,E)</tex>. <tex>S, T \in V</tex> {{---}} источник и сток. <tex>\forall (u,v) \in E</tex> <tex>\exists c(u, v), f(u,v)</tex> {{---}} стоимость пересылки единицы потока и пропускная способность. Тогда '''общая стоимость потока''' из <tex>S</tex> в <tex>T</tex>:
:<tex>p(u,v) = \sum_{u,v \in V, f(u,v)>0} c(u,v) \cdot f(u,v)</tex>
}}
===Свойства стоимости===
==Задача о потоке минимальной стоимости==
===Формулировка===
{{Задача
|definition = Дано число <tex>f_0</tex> и транспортная Дана сеть <tex>\,G(V,E)</tex> с источником . <tex>s S, T \in V</tex> {{---}} источник и стоком сток. <tex>t \in V</tex>, где ребра <tex>forall (u,v) \in E</tex> имеют пропускную способность <tex>\,exists c(u,v)</tex> и цену <tex>\,pf(u,v)</tex>{{---}} стоимость пересылки единицы потока и пропускная способность.Требуется найти максимальный поток <tex>f(u, v)</tex>:суммарная стоимость которого минимальна.}}
=== Алгоритмы решения ===
*Найти любой поток величины <tex>f_0</tex>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом [[Алгоритм Форда-Беллмана|Форда-Беллмана]].
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
