1.5 Обобщенные задачи о потоке

Рассмотрим некоторые обобщения задачи о нахождении максимального потока заданной сети, которые также могут быть решены с помощью рассматриваемого базового алгоритма Форда-Фалкерсона.

1.5.1 Построение потока в сети с двойным ограничением потока по дугам

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

для любой дуги .

Очевидно, что в данной ситуации уменьшение потока на обратных дугах будет ограничено нижней границей для потока на рассматриваемой дуге.

Упражнения

1. Определить допустимый поток в данной модифицированной сети и привести формулировку задачи о нахождении максимального потока. Сформулировать условия существования допустимого потока.

2. Модифицировать алгоритм Форда-Фалкерсона для построения максимального потока в сети с двойным ограничением потока по дугам.

1.5.2 Построение потока в сети с пропускными способностями узлов

Такой сетью является сеть, в которой узлы (вершины) могут также обладать пропускной способностью, т.е. когда дополнительно заданы числа c(x) для некоторых . Для того, чтобы свести данную задачу к базовой, необходимо представить, что каждая вершина x, обладающая пропускной способностью, «растягивается» в дополнительную дугу (x1, x2), которой присваивается пропускная способность вершины x, т.е. .

Упражнения

1. Определить допустимый поток в данной модифицированной сети и привести формулировку задачи о нахождении максимального потока.

2. Модифицировать алгоритм Форда-Фалкерсона

Для построения максимального потока в сети с пропускными способностями узлов.

1.5.3 Построение потока в сети с несколькими источниками-стоками

Данная модификация предполагает, что в сети заданы n источников s1, s2, …, sn и m стоков t1, t2, …, tm.

Чтобы свести данную задачу к базовой, вводят в рассмотрение фиктивные источники – главный источник S и главный сток T, а также фиктивные дуги (S, s1), …, (S, sn) и (t1, T), …, (tm, T) и полагают пропускную способность дуг, выходящих из S и соответственно входящих в T, равной .

1.5.4 Построение потока в сети с неориентированными ребрами

В данной модификации предполагается, что в сети имеются ребра, т.е. дуги без заданной ориентации, но с заданными пропускными способностями. Для приведения данной сети к базовой каждое ребро заменяется на две дуги противоположной ориентации, но с теми же вершинами и пропускной способностью, равной пропускной способности ребра.

Упражнения

1. Определить допустимый поток в данной модифицированной сети и привести формулировку задачи о нахождении максимального потока.

2. Модифицировать алгоритм Форда-Фалкерсона для построения максимального потока в сети с неориентированными ребрами.

1.6 Определение потока заданной величины минимальной стоимости. Алгоритмы Басакера-Гоуэна, Клейна

В предыдущем разделе рассматривалась сеть , каждой дуге (x, y) которой соответствовала пропускная способность дуги , указывающая максимальное количество потока, которое по ней можно пропустить.

Для данной задачи нахождения потока заданной величины минимальной стоимости необходимо, каждой дуге было поставлено в соответствие неотрицательное действительное число , называемое стоимостью доставки единицы потока по дуге . Если в сети пропущен поток f, то стоимостью потока называется число

.

Постановка задачи. Пусть — сеть с заданными пропускными способностями , и стоимостями , дуг. Среди допустимых потоков (т.е. потоков, удовлетворяющих условиям ) заданной мощности , найти поток минимальной стоимости .

При этом подразумевается, что величина не превышает максимальной мощности допустимого потока из s в t, иначе задача не имеет решения.

В излагаемых далее алгоритмах построения потока минимальной стоимости существенную роль играет так называемый граф модифицированных стоимостей .

Пусть дан граф , в котором пропущен допустимый поток f. Граф строится следующим образом: множество вершин совпадает с множеством вершин графа G, т.е. ; множество определяется правилами:

1. Если и , то в графе рисуется одна дуга , имеющая длину (модифицированную стоимость) .

2. Если и , то в графе рисуется одна дуга , имеющая длину (модифицированную стоимость) .

3. Если и , то в графе рисуется две дуги и имеющие соответственно длины и

Пример. Пусть задан граф , в котором пропущен допустимый поток f (см. Рис.1.22).

В данном графе над каждой дугой числа показывают соответственно пропускную способность, пропущенный по дуге поток и стоимость единицы потока. Тогда граф имеет вид (см. Рис. 1.23)

Рис. 1.22

Рис. 1.23