7.3. Поиск максимального потока

Задача о максимальном потоке состоит в поиске способа пересылки максимального количества единиц потока из источника в сток.

Алгоритм 6. Алгоритм поиска максимального потока.

Шаг 1. Выбрать любой начальный поток в графе G=(V,E) из источника s в сток t, то есть выбрать любой набор величин f(x,y), удовлетворяющий соотношениям 7.1-7.4.

Шаг 2. Применить к графу G=(V,E) алгоритм поиска увеличивающей цепи (алгоритм 5).

Шаг 3. Если увеличивающая цепь найдена, то увеличить поток вдоль найденной цепи по правилам, приводимым в разд. 7.2, и вернуться к шагу 2. В противном случае закончить алгоритм поиска максимального потока. Максимальный поток найден.

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

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

7.4. Поиск потока минимальной стоимости

Припишем каждой дуге (x,y) графа G=(V,E) число a(x,y), равное стоимости прохождения единицы потока по дуге (x,y).

В задаче о потоке минимальной стоимости требуется переслать фиксированное число единиц потока (v) из источника (s) в сток (t) с минимальной стоимостью. То есть требуется найти

min{  a(x,y)f(x,y) }

(x,y)E

при ограничениях 7.1-7.4.

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

Идея алгоритма поиска потока минимальной стоимости состоит в следующем:

- вначале из вершины s в вершину t пересылается как можно больше единиц потока, полная стоимость прохождения по сети каждой из которых равна нулю (p=0);

- затем из s в t пересылается как можно больше единиц потока, полная стоимость прохождения по сети каждой из которых равна единице (p=1) и так далее;

- процесс заканчивается, когда будет передано заданное число (v) единиц потока или поток достигнет своего максимального значения.

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

Это осуществляется с помощью приписывания каждой вершине x целого числа p(x). Эти числа выбираются так, что p(s)=0; p(t)=p; 0p(x)p, (xs,xt). При этом изменение потока допускается только в тех дугах (x,y), для которых

p(y)-p(x)=a(x,y) (7.5)

Таким образом, если найдена увеличивающая цепь, состоящая из дуг, удовлетворяющих соотношению 7.5, то стоимость единицы потока по ней равна p.

С учетом этих соображений сформулируем алгоритм поиска потока минимальной стоимости.

Алгоритм 7. Поиск потока минимальной стоимости.

Шаг 1. Задать нулевой поток в графе G=(V,E), то есть для всех дуг (x,y)E положить f(x,y)=0. Для всех вершин xV положить p(x)=0.

Шаг 2. Сформировать множество I, включив в него дуги (x,y), для которых p(y)-p(x)=a(x,y) и f(x,y)<c(x,y). Сформировать множество R, включив в него дуги (x,y), для которых p(y)-p(x)=a(x,y) и f(x,y)>0. Дуги, не вошедшие ни в множество I, ни в множество R, включить в множество N.

Шаг 3. Выполнить шаги 2, 3 и 4 алгоритма 5.

Шаг 4. Если увеличивающая цепь найдена, то увеличить поток вдоль найденной цепи (см. разд.7.2). В противном случае увеличить на единицу числа p(x) для всех неокрашенных (шаг 3 алгоритма 5) вершин x.

Шаг 5. Если из вершины s в вершину t передано v единиц потока или поток достиг своего максимального значения v<v, то перейти к шагу 6. В противном случае перейти к шагу 2.

Шаг 6. Если из вершины s в вершину t передано v единиц потока, то поток минимальной стоимости найден. Если поток из вершины s в вершину t достиг своего максимального значения v<v, то из вершины s в вершину t не может быть передано заданное число единиц потока.

Рассмотрим работу алгоритма поиска потока минимальной стоимости для графа, изображенного на рис.7.4.

Если из вершины s в вершину t требуется переслать v2 единиц потока, то работа алгоритма завершается за три итерации, представленные в табл.7.1. После третьей итерации вершина t оказалась окрашенной. Две единицы потока из s в t посылаются по цепи (s,a), (a,b), (b,t), см. рис. 7.5.

Если v>2, то работа алгоритма поиска потока минимальной стоимости завершается за шесть итераций (табл. 7.2). После шестой итерации вершина t снова оказалась окрашенной. Одна единица потока из s в t посылается по цепи (s,b), (a,b), (a,t) (см. рис. 7.6), и суммарный поток из s в t достигает своего максимального значения, равного трем.

Таблица 7.1. Этапы поиска потока минимальной стоимости из вершины s в вершину t в графе, изображенном на рис. 7.4, согласно алгоритму 7

№ итерации	p(s)	p(a)	p(b)	p(t)	Окрашенные
					Дуги	вершины
0	0	0	0	0	-	s
1	0	1	1	1	(s,a)	s,a
2	0	1	2	2	(s,a),(a,b)	s,a,b
3	0	1	2	3	(s,a),(a,b),(b,t)	s,a,b,t

Таблица 7.2. Продолжение таблицы 7.1

№ итерации	p(s)	p(a)	p(b)	p(t)	Окрашенные
					дуги	Вершины
4	0	1	2	3	-	S
5	0	2	3	4	(s,b),(a,b)	s,a,b
6	0	2	3	5	(s,b),(a,b),(a,t)	s,a,b,t

Упражнения:

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

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

3. При формулировке алгоритма 7 не уточнялось, как контролировать, достиг или нет поток своего максимального значения (шаг 5). Предложите, как можно осуществлять такой контроль.

4. Реализуйте алгоритмы поиска максимального потока и поиска потока минимальной стоимости. Оцените трудоемкость алгоритмов.