Поиск максимального потока в транспортной сети

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

Транспортной сетью называется ориентированный граф [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]

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

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

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

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

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

• Алгоритм Форда-Фалкерсона и его варианты со сложностью [math]\displaystyle{ O(n^2m) }[/math] (для алгоритма Диница). В случае целых пропускных способностей, не превосходящих [math]\displaystyle{ K }[/math], сложность [math]\displaystyle{ O(Km) }[/math].
• Алгоритм проталкивания предпотока со сложностью [math]\displaystyle{ O(mn \ln n) }[/math] (при использовании динамических деревьев Тарьяна-Слитора).

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