Уровень задачи

Поиск максимального потока в транспортной сети: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][выверенная версия]
(Описание задачи)
 
 
(не показаны 3 промежуточные версии 3 участников)
Строка 1: Строка 1:
 +
{{level-p}}
 +
 
== Постановка задачи ==
 
== Постановка задачи ==
  
''Транспортной сетью'' называется ориентированный граф <math>G = (V, E)</math>, каждому ребру <math>e \in E</math> которого приписана положительная пропускная способность <math>c(e)</math>.
+
''Транспортной сетью'' называется ориентированный граф <math>G = (V, E)</math>, каждому ребру <math>e \in E</math> которого приписана неотрицательная пропускная способность <math>c(e) \ge 0</math>. Будем считать, что вместе с каждым ребром <math>e = (v, w) \in E</math> граф содержит и обратное к нему <math>e^R = (w, v)</math> (при необходимости приписывая ему нулевую пропускную способность).
  
Пусть в графе <math>G</math> выделены две вершины: источник <math>s</math> и сток <math>t</math>. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из <math>s</math> в <math>t</math>. ''Потоком'' называется функция <math>E \to \mathbb{R}</math>, удовлетворяющая следующим требованиям:
+
Пусть в графе <math>G</math> выделены две вершины: источник <math>s</math> и сток <math>t</math>. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из <math>s</math> в <math>t</math>. ''Потоком'' называется функция <math>f: E \to \mathbb{R}</math>, удовлетворяющая следующим требованиям:
 
* ограничение по пропускной способности: <math>f(e) \le c(e)</math>;
 
* ограничение по пропускной способности: <math>f(e) \le c(e)</math>;
 +
* антисимметричность: <math>f(e^R) = -f(e)</math>;
 
* закон сохранения потока:
 
* закон сохранения потока:
  
Строка 14: Строка 17:
  
 
:<math>
 
:<math>
         \lvert f \rvert = \sum_{e = (s, v)} f(e).
+
         \left \vert f \right \vert = \sum_{e = (s, v)} f(e).
 
</math>
 
</math>
  
 
'''Задача о максимальном потоке в транспортной сети.''' Требуется найти поток максимальной величины:
 
'''Задача о максимальном потоке в транспортной сети.''' Требуется найти поток максимальной величины:
:<math>\lvert f \rvert \to \max.</math>
+
:<math>\left \vert f \right \vert \to \max.</math>
  
 
== Свойства задачи ==
 
== Свойства задачи ==
Строка 45: Строка 48:
  
 
<references />
 
<references />
 +
 +
[[Категория:Статьи в работе]]

Текущая версия на 17:03, 6 марта 2018


1 Постановка задачи

Транспортной сетью называется ориентированный граф [math]G = (V, E)[/math], каждому ребру [math]e \in E[/math] которого приписана неотрицательная пропускная способность [math]c(e) \ge 0[/math]. Будем считать, что вместе с каждым ребром [math]e = (v, w) \in E[/math] граф содержит и обратное к нему [math]e^R = (w, v)[/math] (при необходимости приписывая ему нулевую пропускную способность).

Пусть в графе [math]G[/math] выделены две вершины: источник [math]s[/math] и сток [math]t[/math]. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из [math]s[/math] в [math]t[/math]. Потоком называется функция [math]f: E \to \mathbb{R}[/math], удовлетворяющая следующим требованиям:

  • ограничение по пропускной способности: [math]f(e) \le c(e)[/math];
  • антисимметричность: [math]f(e^R) = -f(e)[/math];
  • закон сохранения потока:
[math] \forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e). [/math]

Величиной потока называется суммарный поток из источника:

[math] \left \vert f \right \vert = \sum_{e = (s, v)} f(e). [/math]

Задача о максимальном потоке в транспортной сети. Требуется найти поток максимальной величины:

[math]\left \vert f \right \vert \to \max.[/math]

2 Свойства задачи

Суммарный поток из источника равен суммарному потоку в сток:

[math] \forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e). [/math]

(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)

3 Варианты задачи

В зависимости от ограничений на значения пропускной способности:

  • произвольная положительная пропускная способность;
  • целая пропускная способность;
  • единичная пропускная способность (в этом случае максимальный поток равен рёберной связности графа).

4 Алгоритмы решения задачи

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин.

5 Ссылки

  1. 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.
  2. 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.
  3. Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.
  4. 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.
  5. 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.
  6. 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.