Сводимость некоторых
задач о максимальном потоке в сети к
рассматриваемой.
Большинство
разнообразных сетей и условий существования потока в них, которые могут
возникнуть при рассмотрении различных приложений задачи о максимальном потоке,
сводятся к поиску максимального потока в ориентированной сети с одним
источником и стоком, и заданными вещественными верхними границами пропускных
способностей дуг сети. Рассмотрим наиболее распространенные частные случаи,
которые могут быть приведены к оригинальной постановке задачи.
Случай
нескольких источников и стоков.
В
этом случае все узлы сети делятся на 3 группы: S - множество
источников, T –
множество стоков и R -
множество промежуточных узлов. Поток может следовать из любого источника в
любой сток. В этом случае сеть модифицируется следующим образом:
Добавим
новую вершину S*
и соединим ее дугами со всеми вершинами из множества S. Вершина S* называется суперисточником. Добавим новую вершину T* и соединим ее дугами со
всеми вершинами из множества T.
Вершина T*
называется суперстоком. Пропускные способности всех
новых дуг положим равными ∞.
Очевидно,
что поиск максимального потока из вершин множества S в вершины множества T равносилен поиску максимального потока
из S* в T*.
Случай
ограниченной пропускной способности вершин.
Если
пропускные способности наряду с дугами имеют и узлы сети, то каждую вершину v, имеющую пропускную
способность c(v), следует заменить двумя (v’ и v’’), соединенными дугой (v’, v’’) и c(v’, v’’)
= c(v).
Случай
существования нижних границ пропускных способностей дуг.
Если
рассматриваемой задаче поток, проходящий по дуге u, может принимать значения l(u) ≤ f(u) ≤ c(u), то функция l(u) рассматривается как уже имеющийся в
сети поток и поиск максимального потока следует начинать не с нулевого потока,
а с потока l(u).
Случай
неориентированных и смешанных сетей.
Поток
по неориентированной дуге (v,
w) должен удовлетворять
следующим условиям:
f(v, w) ≤ c(v, w)
f(w, v) ≤ c(v, w)
f(v, w)*f(w, v) = 0
В
этом случае замена неориентированной дуги двумя противоположно направленными
ориентированными дугами с одинаковой пропускной способностью c(c, w)
сведет задачу к эквивалентной задаче на орграфе, что доказано в [3].
Аналогично ориентированные сети сводятся к неориентированным.
(Кроме сетей с единичными пропускными способностями)
Пропускные
способности различных типов.
Различаются
случаи целочисленных, вещественных и единичных пропускных способностей.
Предполагается, что приводимые далее алгоритмы рассматриваются на сетях с
вещественными пропускными способностями, кроме специально оговоренных случаев.
