КМиИсО

	0	4	4	4	4	4	1
	B	4	4	4	4	4	C
S4 =		4	2	4	4	4
	B						C
	B						C

BC

@	1	3	3	1	5	A
	2	2	2	2	2

5	0	12	9	5		7	6	1
	B	1	2	6		4	5	C
		5	2		2	1	1
	B							C
L =	B	8	5	1		3	2	C
		15	3			10
	B			8			9	C
	@							A

	0	4	4	4	4	4	1
	B	4	4	4	4	4	C
S5 =		4	4	4	4	4
	B						C
	B						C

BC

@	1	5	3	1	5	A
	2	2	2	2	2

Длина кратчайшей цепи, например, из узла 5 в узел 3 равна `553 = 8. Для определения узлов соответствующей цепи, обратимся к матрице S5. Нетруд-

но заметить, что s553 = 2; s523 = 4; s543 = 3.Следовательно, кратчайшая цепь из узла 5 в узел 3 определяется последовательностью узлов 5 ! 2 ! 4 ! 3.

Теорема 3.2 В ориентированном графе есть циклы отрицательной длины тогда и только тогда, когда существуют такие номера i и p, не превосходящие n, что liip < 0

Из теоремы следует, что алгоритм Флойда может быть использован для нахождения в графе циклов отрицательной длины. Если на k-ой итерации

21

в матрице Lk на диагонали появилось отрицательное число `kii < 0, то это означает, что в графе существует цикл отрицательной длины. Найти цикл можно, используя справочную матрицу Sk.

22

4Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона.

4.1Основные определения

Определение 4.1 Ориентированный граф G = (V; E) называется се-

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

Обычно источники обозначают fi, а стоки - tj.

Для каждой вершины 2 V выделим два множества дуг:

E+( ) = f( ; u) 2 Eg - дуги, выходящие из

E ( ) = f(u; ) 2 Eg - дуги, входящие в

Пусть f : E ! R - некоторая функция на множестве дуг. Дивиргенцией f в вершине называется число

XX

divf( ) = f(e) f(e)

e2E+( ) e2E ( )

Функция f : E ! R называется потоком в сети, если во всех внутренних вершинах выполнено равенство

divf( ) = 0:

Данное условие называется условием неразрывности. Оно означает (если интерпретировать f(e) как количество жидкости, протекающей по дуге в еди-

ницу времени), что для любой внутренней вершины количество жидкости, втекающей в эту вершину, равно количеству жидкости, вытекающей из нее.

23

Каждой дуге e = (x; y) 2 E сети поставим в соответствие положительное число, которое будем обозначать c(e) (èëè c(x; y)) и называть пропускной способностью дуги.

Определение 4.2 Поток f : E ! R в сети называется допустимым,

если величина потока, пропущенного по любой дуге сети, не превосходит ее пропускной способности, то есть 0 6 f(e) 6 c(e) для любого e 2 E:

Пропускную способность и величину пропущенного потока записывают над каждой дугой e = (x; y) графа следующим образом .

Пример

Пусть задан следующий граф G = (V; E).

b

3; 2 5; 3

s

1; 1

t

2; 2 4; 1

a

Âданном случае, например,для дуги (s; b) пропускная способность равна 3, а величина пропущенного потока равна 2.

Покажем, что в графе действительно пропущен допустимый поток f.

Âсамом деле, во внутренних вершинах сети a è b дивергенция равна нулю,

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

дуги выполняется условие 0 6 f 6 c.

Рассмотрим сеть со множеством вершин V . Пусть si; i = 1; m - источники,

à tj; j = 1; n - стоки.

Определение 4.3 Мощностью потока f, пропущенного в сети, называ-

ется число	m	m
	X	X
	M(f) =	divf(s) = divf(t)
	i=1	i=1

24

M(f) интерпретируется как количество жидкости, "создаваемое" ис-

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

Определение 4.4 Пусть X V - некоторое подмножество вершин,

удовлетворяющее условию si 2 X; i = 1; m; tj не принадлежит X; j = 1; n.

Пара (X; X), где X = V n X называется разрезом.

Определение 4.5 Элементарной цепью(без ориентации) в сети называется последовательность вершин ( 0; 1; :::; n), такая, что все i различны,0 = s; n = и вершины i 1; i - смежные. При этом, если ( i 1; i) 2 E, òî äóãà ( i 1; i) называется прямой, если ( i; i 1) 2 E - обратной.

Для разреза (X; X), введем множество

E(X; X) = fe = (u; ) 2 E : u 2 X; 2 Xg

дуг, идущих из X â X.

Пропускной способностью разреза (X; X) называется число

X

C(X; X) =

c(e)

e2E(X;X)

Лемма 4.1 Мощность любого допустимого потока не больше пропускной способности любого разреза.

Определение 4.6 Увеличивающей(или насыщающей) для потока f цепью в сети G называется элементарная цепь,если для любой прямой дуги e f(e) < c(e); а для любой ее обратной дуги - f(e) > 0:

Например, на рисунке, приведенном ниже

s

v1

v2

v3

v4

t

25

äóãè (s; 1); ( 3; 4); ( 4; t) прямые, а дуги ( 2; 1) è ( 3; 2)- обратные. Пусть f- некоторый допустимый поток в сети. Определим функцию f íà

дугах увеличивающих цепей:

(e) = c(e) f(e);

åñëè e прямая дуга и (e) = f(e), для каждой обратной дуги e. Определим

= min (e);

ãäå e - дуги элементарной (s; t) öåïè.

Очевидно, что, изменяя исходный поток f(вдоль пути s ! t) на прямых дугах на (+ ) и на обратных дугах на ( ), мы получим новый допустимый поток f, для которого

M(f) = M(f) + :

Теорема 4.1 (ФордаФалкерсона) Если для допустимого потока f

нет увеличивающих цепей, то существует разрез (X; X), такой, что

M(f) = C(X; X):

Следствие. Поток максимален , 9(X; X) : M(f) = C(X; X)

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

Пусть задана сеть с фиксированными пропускными способностями дуг с одним источником s и одним стоком t. Найти среди допусти-

мых потоков поток максимальной мощности.

Задачи о нахождении потока максимальной мощности встречаются в различных сферах. Одним из ярких иллюстративных примеров является задача об отправлении туристов.

Задача. Рейс Минск- Нью-Йорк был отменен из-за технической неисправности. Сможет ли туристическая компания сегодня отправить группу туристов из 50-ти человек, если в наличии имеются билеты в следующих направлениях и колличествах: Минск - Москва - 25 билетов, Минск - Киев

-11 б., Минск - Рига - 7 б., Минск - Варшава -10 б., Минск - Киев -8 б., Минск - Варшава - 4 б., Минск - Рига - 3 б., Варшава - Рига - 4 б., Москва

-Франфурт-на-Майне - 9 б., Рига - Франфурт-на-Майне - 4 б., Варшава -

26

Франфурт-на-Майне - 7 б., Рига - Вена - 11 б., Киев - Вена - 16 б., Варшава

-Вена - 8 б., Москва - Вена - 7 б., Минск - Лондон - 5 б., Варшава - Лондон

-5 б., Рига - Лондон - 2 б., Киев - Лондон - 5 б., Вена - Нью-Йорк - 28 б., Лондон - Нью-Йорк -11 б., Франкфурт-на-Майне - Нью-Йорк - 16б.?

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

4.3Алгоритм Форда-Фалкерсона

В процессе работы(на каждом этапе) каждая вершина относится к одному из трех множеств:

-неотмеченные вершины, -отмеченные, но не просмотренные

-отмеченные и просмотренные (окрашенные).

ШАГ 0. Пропускаем по сети некоторый допустимый поток( например, нулевой).

ШАГ 1. Отметим вершину s меткой (s+; +1). Остальные вершины не отмечены, s - отмечена, но не просмотрена.

ШАГ 2. Пусть - некоторая отмеченная, но не просмотренная вершина. Рассмотрим все смежные с неотмеченные вершины. Пусть u одна из таких вершин. Тогда, если

a)( ; u) 2 E è f( ; u) < c( ; u); вершина u получает метку ( +; );

ãäå = c( ; u) f( ; u)

á) (u; ) 2 E è f(u; ) > 0: Тогда вершина u получает метку ( ; ), ãäå = f(u; ):

В остальных случаях вершина u, смежная с , не получает метки.

ШАГ 3. Возможны следующие 3 ситуации:

1)Åñëè ñòîê t отмечен, то переходим к Шагу 4.

2)Если есть отмеченные, но не просмотренные вершины, повторяем Шаг 2.

27

3)Если отмеченные вершины просмотрены, а t метки не имеет, переходим к Шагу 5.

ØÀÃ 4. Åñëè ñòîê t имеет метку, то можно построить насыщающую (увеличивающую) цепь S = 0; 1; :::; k 1; k = t:

Выберем:

				" = min i;
	(f( ii; 1i 1i);					06i6k		2 E.
ãäå i =			i 1	i		åñëè ( i; i 1)
	C( ; )	f(		;	);	åñëè ( i 1	; i)	E
								2

Переходим к Шагу 1.

ШАГ 5. Рассмотрим множество X; состоящее их всех отмеченных вершин. Так как t 62X; рассмотрим X = V nX: Получим разрез (X; X). По построению для любой дуги e 2 E(X; X); f(e) = 0: Следовательно, M(f) = C(X; X); то есть построенный поток f имеет максимальную мощьность.

Замечание. Этот алгоритм может работать бесконечно долго и не давать ответа.

28

4.4Пример

Для сети с заданными пропускными спосоáíостями дуг построить поток мàê- симальной мощности и указать разрез (X; X), для которого M(f) = C(X; X):

a

(5; 2)

(2; 2)

(1; 0)

(4; 3)

s b t

(4; 4)

(1; 1)

(4; 4)

(5; 3)

d

(в данной сети изначально пропущен поток мощности M(f) = 9)

ØÀÃ 1.	Отмечаем источник s-(s+; 1).
ØÀÃ 2.	Рассмотрим узлы, смежные с S. Óçåë a получает метку (s+; 3), òàê êàê
	(s; a) - äóãà ñåòè,
	f(s; a) = 2 < c(s; a) = 5 è 3 = c f = 5 2:
	Óçåë b получает метку (s+; 1), òàê êàê â ñåòè åñòü äóãà (s; b),
	f(s; b) = 3 < c(s; b) = 4 è 1 = 4 3
	Óçåë d не отмечается, так как (s; d) - äóãà ñåòè,íî
	f(s; d) = 4 = c(c; d):

29

Óçåë s отнесем ко множеству просмотренных узлов.

a (s+;3)

(5; 2)

(2; 2)

(1; 0)

(s+;1)

(4; 3)

(s+;1) s b t

(4; 4)

(1; 1)

(4; 4)

(5; 3)

d

ШАГ 3. Рассмотрим узел a. Òàê êàê óçåë b уже имеет метку, можем рассмотреть только узел t, смежный с отмеченным и не просмотренным узлом a. Óçåë t не отмечается, так как (a; t) - äóãà ñåòè è f(a; t) = 2 = c(a; t). Óçåë a после этого отнесем ко множеству просмотренных узлов.

ШАГ 4. Рассмотрим неотмеченные узлы, смежные с узлом b: Óçåë t не отмеча- ется, так как f(b; t) = 4 = c(b; t). Óçåë d получает метку (b ; 1), òàê êàê

â ñåòè åñòü äóãà (d; b),

f(d; b) = 1 > 0 и, следовательно, = 1:

Óçåë b переходит во множество просмотренных узлов.

30