Метод Форда-Фалкерсона

Постановка задачи о максимальном потоке на сети.

На сети, что задается графом (I,U), где I — множество вершин, U — множество дуг, с определенной на ней функцией пропускных способностей r_ij ((і,j) — дуга с U), зафиксированные две вершины — i1 и in. Вершина i1 (источник) имеет интенсивность d, вершина in (стек) — интенсивность –d, все другие вершины нейтральные. Нужно найти максимальную интенсивность источника d, при которой сеть допускает поток. Поток, что отвечает такому максимальному значению интенсивности d*, называется максимальным потоком, а именно значение d* — величиной этого потока.

Алгоритм Форда-Фалкерсона применяется для построения максимального потока на сети из заданной начальной вершины-источника в заданную конечную вершину-сток.

Будем считать, что вершиной-источником является 1-я вершина, вершиной-стоком — вершина с номером n.

Входные данные.

Для работы алгоритма необходимо задать следующую информацию:

1. Число вершин сети.

2. Матрицу смежности С, элементы которой с_іj определяются соотношениями:

с_ij=1, если существует дуга (і,j);

с_ij=0, если дуга (і,j) отсутствует.

3. Величины r_ij пропускных способностей дуг (і,j).

4. Начальный поток на сети, то есть величины x_ij, которые удовлетворяют условия:

a) 0 £ x_ij £ r_ij;

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

Изложение алгоритма Форда-Фалкерсона.

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

В каждой итерации можно выделить два этапа.

Этап 1 (этап выставления отметок).

1. В каждый момент времени каждая вершина может находиться в одном из трех положений:

а) не обозначенная;

б) обозначенная, но не рассмотрена;

в) обозначена и рассмотрена.

Общий вид отметки j-ї вершины: [ i+qj ], или [ и–,qj ], где и — номер некоторой обозначенной вершины, при просмотре которой была обозначена вершина j. Вершина 1 всегда обозначена и имеет отметку [ 1+q1 ], где q1 равное + ¥ (бесконечности).

2. Просмотр произвольной обозначенной вершины j заключается в следующем:

a) произвольная необозначенная вершина k, для которой существует дуга (j,k) и имеет место неравенство x_jk<r_jk, получает отметку вида [ j+qk ], где

qk=min { qj, r_jk – x_jk };

б) произвольная необозначенная вершина k, для которой существует дуга (k,j) и имеет место условие x_kj>0, получает отметку вида [ j–,qk ], где

qk=min { qj, x_kj }.

3. Процесс выставления отметок заканчивается в одном из двух случаев:

а) вершина с номером n обозначена;

б) условие а) не выполняется, но ни одну вершину больше пометить нельзя.

В первом случае переходим к этапу изменения потока на сети. Во втором — до определения минимального разреза сети и максимального потока.

Этап 2 (этап изменения потока).

Поток в сети изменяется на величину qn согласно правила.

Если вершина n имеет отметку [ k+qn ], где k — номер некоторой вершины, то x_kn=x_kn+qn. Если отметка имеет вид [ k–,qn ], то x_nk=x_nk–qn. Переходим к вершине с номером k. Если отметка вершины k имеет вид [ j+qk ], то x_jk=x_jk+qn; если она равняется [ j–,qk ], то x_kj=x_kj–qn. Подобные действия продолжаем до тех пор, пока не будет достигнута начальная вершина. В этом случае все старые отметки вытираем и возвращаемся к первому этапу.

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

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

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

Программное обеспечение.

Обучающий модуль, с помощью которого задача о максимальном потоке на сети Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ – МО.

Задание.

Решить методом Форда-Фалкерсона задачи о максимальном потоке на сети, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи, в каждой из которых сеть задается матрицами смежности C и пропускных способностей R. Во всех задачах источником считается вершина 1, а стоком — вершина 6.

1)		0	1	1	0	0	0			0	10	18	0	0	0
		0	0	0	0	1	1			0	0	0	0	14	1
	C =	0	1	0	1	0	0	,	R =	0	10	0	17	0	0	;
		0	1	0	0	1	1			0	9	0	0	22	12
		0	0	0	0	0	1			0	0	0	0	0	18
		0	0	0	0	0	0			0	0	0	0	0	0

2)		0	1	1	0	0	0			0	11	33	0	0	0
		0	0	0	1	1	0			0	0	0	14	4	0
	C =	0	1	0	1	1	0	,	R =	0	5	0	15	23	0	;
		0	0	0	0	0	1			0	0	0	0	0	23
		0	0	0	1	0	1			0	0	0	11	0	22
		0	0	0	0	0	0			0	0	0	0	0	0

3)		0	1	1	1	0	0			0	20	21	22	0	0
		0	0	1	1	1	0			0	0	5	13	14	0
	C =	0	0	0	0	1	1	,	R =	0	0	0	0	12	28	;
		0	0	1	0	1	1			0	0	12	0	11	10
		0	0	0	0	0	1			0	0	0	0	0	17
		0	0	0	0	0	0			0	0	0	0	0	0

4)		0	1	1	1	0	0			0	5	19	27	0	0
		0	0	0	0	1	1			0	0	0	0	17	15
	C =	0	1	0	0	1	1	,	R =	0	23	0	0	7	8	;
		0	1	1	0	1	0			0	5	12	0	11	0
		0	0	0	0	0	1			0	0	0	0	0	28
		0	0	0	0	0	0			0	0	0	0	0	0

5)		0	1	1	1	1	0			0	24	33	6	12	0
		0	0	1	1	1	0			0	0	10	15	7	0
	C =	0	0	0	1	1	1	,	R =	0	0	0	11	15	17	;
		0	0	0	0	1	1			0	0	0	0	12	26
		0	0	0	0	0	1			0	0	0	0	0	25
		0	0	0	0	0	0			0	0	0	0	0	0

6)		0	1	1	1	1	0			0	19	16	8	18	0
		0	0	1	1	0	0			0	0	20	1	0	0
	C =	0	0	0	0	1	1	,	R =	0	0	0	0	32	42	.
		0	0	1	0	0	1			0	0	45	0	0	2
		0	0	0	1	0	1			0	0	0	31	0	20
		0	0	0	0	0	0			0	0	0	0	0	0

Ответы:

1) d* = 28. 2) d* = 44. 3) d* = 55. 4) d* = 51. 5) d* = 68. 6) d* = 61.

Лабораторная работа 9.