Поиск максимального потока в транспортной сети: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) Нет описания правки |
ASA (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
{{level-p}} | |||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 15: | Строка 17: | ||
:<math> | :<math> | ||
\ | \left \vert f \right \vert = \sum_{e = (s, v)} f(e). | ||
</math> | </math> | ||
'''Задача о максимальном потоке в транспортной сети.''' Требуется найти поток максимальной величины: | '''Задача о максимальном потоке в транспортной сети.''' Требуется найти поток максимальной величины: | ||
:<math>\ | :<math>\left \vert f \right \vert \to \max.</math> | ||
== Свойства задачи == | == Свойства задачи == | ||
Текущая версия от 14:03, 6 марта 2018
Постановка задачи
Транспортной сетью называется ориентированный граф [math]\displaystyle{ G = (V, E) }[/math], каждому ребру [math]\displaystyle{ e \in E }[/math] которого приписана неотрицательная пропускная способность [math]\displaystyle{ c(e) \ge 0 }[/math]. Будем считать, что вместе с каждым ребром [math]\displaystyle{ e = (v, w) \in E }[/math] граф содержит и обратное к нему [math]\displaystyle{ e^R = (w, v) }[/math] (при необходимости приписывая ему нулевую пропускную способность).
Пусть в графе [math]\displaystyle{ G }[/math] выделены две вершины: источник [math]\displaystyle{ s }[/math] и сток [math]\displaystyle{ t }[/math]. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из [math]\displaystyle{ s }[/math] в [math]\displaystyle{ t }[/math]. Потоком называется функция [math]\displaystyle{ f: E \to \mathbb{R} }[/math], удовлетворяющая следующим требованиям:
- ограничение по пропускной способности: [math]\displaystyle{ f(e) \le c(e) }[/math];
- антисимметричность: [math]\displaystyle{ f(e^R) = -f(e) }[/math];
- закон сохранения потока:
- [math]\displaystyle{ \forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e). }[/math]
Величиной потока называется суммарный поток из источника:
- [math]\displaystyle{ \left \vert f \right \vert = \sum_{e = (s, v)} f(e). }[/math]
Задача о максимальном потоке в транспортной сети. Требуется найти поток максимальной величины:
- [math]\displaystyle{ \left \vert f \right \vert \to \max. }[/math]
Свойства задачи
Суммарный поток из источника равен суммарному потоку в сток:
- [math]\displaystyle{ \forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e). }[/math]
(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)
Варианты задачи
В зависимости от ограничений на значения пропускной способности:
- произвольная положительная пропускная способность;
- целая пропускная способность;
- единичная пропускная способность (в этом случае максимальный поток равен рёберной связности графа).
Алгоритмы решения задачи
- Алгоритм Форда-Фалкерсона[1] и его варианты[2][3] со сложностью [math]\displaystyle{ O(n^2m) }[/math] (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих [math]\displaystyle{ K }[/math], сложность [math]\displaystyle{ O(Km) }[/math].
- Алгоритм проталкивания предпотока[4] со сложностью [math]\displaystyle{ O(mn \ln n) }[/math] (при использовании динамических деревьев Тарьяна-Слитора[5][6]).
Обозначения: [math]\displaystyle{ m }[/math] – число рёбер, [math]\displaystyle{ n }[/math] – число вершин.
Ссылки
- ↑ Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.
- ↑ Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.
- ↑ Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.
- ↑ Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.
- ↑ Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.
- ↑ Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.