учебное пособие - теория графов

			0 5 13			9 12 0				0 5 13 9 12 0
				0 0 9		5 6 0				0 0 9 5 6 0
W 3				0 0 0		0 0 15				0 0 0 0 0 15
												W
	min		0 0 6			0 8 9				0 0 6 0 8 9
				0 0 0		0 0 0				0 0 0 0 0 0
				0 0 0		0 1 0				0 0 0 0 1 0
									W
	0		0	14	10	11	18			0 0 14 10 11		18 0 5 13 9 12			0
		0 0 11 0				13 14					0 0 11 0 13 14			0 0 9 5 6	0
		0 0 0 0				16 0					0 0 0 0 16	0		0 0 0 0 0	15
								W
	0 0 0 0					10 21				0 0 0 0 10		21 0 0 6 0 8			9
		0 0 0 0				0 0					0 0 0 0 0	0		0 0 0 0 0	0
		0 0 0 0				0 0					0 0 0 0 0	0		0 0 0 0 1	0
					W						W
	0		0	16	0	18	19
		0	0	0	0	15	26
		0	0	0	0	0	0	.
	0		0	0	0	21	0
		0	0	0	0	0	0
		0	0	0	0	0	0

3 этап. Так как w25 15 – наименьший элемент в матрице Wmin3 ,

то 15 – минимальный вес пути графа G, состоящий из 3 ребер, причем данный путь соединяет 2-ю и 5-ю вершины графа G. Найдем данный путь. Для этого восстановим процесс получения элемента w25 15 :

w	15 14 1 w	w , где	w	14	– элемент матрицы W ,
25	26	65	26

стоящий на пересечении 2-й строки и 6-го столбца, w65 1;

w26 14 5 9 w24 w46 .

151

Следовательно, w25 15 (5 9) 1 (w24 w46) w65 . Это означает, что искомый путь графа G веса 15 имеет вид: (a2 , a4 , a6 , a5 ) .

б) С помощью метода Шимбелла найдем в графе G один из путей максимального веса.

1 этап. Матрицу весов W графа G запишем в виде:

	0		5	13	9	12	0
		0	0	9	5	6	0
		0	0	0	0	0	15	.
W
	0		0	6	0	8	9
		0	0	0	0	0	0
		0	0	0	0	1	0

	2 этап. Найдем W 3								W W W , используя правило (*):
							max
	0		5	13	9	12	0	0			5	13	9	12	0
		0	0	9	5	6	0			0	0	9	5	6	0
W 3		0	0	0	0	0	15			0	0	0	0	0	15
																W
max	0		0	6	0	8	9	0			0	6	0	8	9
		0	0	0	0	0	0			0	0	0	0	0	0
		0	0	0	0	1	0			0	0	0	0	1	0

W

152

	0		0	15	10	17	28		0 0 15		10	17 28		0 5 13 9 12		0
		0 0 11 0 13					14			0 0 11	0	13 14			0 0 9 5 6	0
		0 0 0 0 16					0			0 0 0	0	16 0			0 0 0 0 0	15
									W
	0 0 0 0 10						21		0 0 0		0	10 21		0 0 6 0 8		9
		0 0 0 0 0					0			0 0 0	0	0 0			0 0 0 0 0	0
		0 0 0 0 0					0			0 0 0	0	0 0			0 0 0 0 1	0
					W						W
	0		0	16	0	29	30
		0	0	0	0	25	26
		0	0	0	0	0	0	.
	0		0	0	0	21	0
		0	0	0	0	0	0
		0	0	0	0	0	0

3 этап. Так как w16 30 – наибольший элемент в матрице Wmax3 ,

то 30 – максимальный вес пути графа G, состоящий из 3 ребер, причем данный путь соединяет 1-ю и 6-ю вершины графа G. Найдем данный путь. Для этого восстановим процесс получения элемента w16 30 :

w	30 15 15 w	w , где	w 15 – элемент	матрицы W ,
16	13	36	13
стоящий на пересечении 1-й строки и 3-го столбца, w36 15 ;
w	15 9 6 w w .
13	14	43
Следовательно, w16 30 (9 6) 15 (w14 w43) w36 .				Это означает,

что искомый путь графа G веса 30 имеет вид: (a1, a4 , a3 , a6 ) .

153

Задание 8.2. Для взвешенного связного орграфа G без контуров, заданного матрицей весов W:

	а) построить упорядочение вершин xi											, xi , , xi			;
										1		2		n
	б) с помощью алгоритма Дейкстры найти (xi														, xi ) -путь макси-
														1		n
	мального веса.
8.2.1.			4	8						8.2.6.				10		5	8	4	3
					3 10
			3		4	3								10
	W
												W
							4							18				9	7
			2		5		7						4						3
																11
8.2.2.		2 1			4					8.2.7.			2			7 1
							5										4
			4 6 2																5
	W											W	3			6
							1
					3														10
8.2.3.		2 8 8 1					6			8.2.8.			2			3 1			5
																1 8			1
			8																2
	W	14			9							W	10
							10												6
			7				5						3			4
			3

154

8.2.4.		4 2			1				8.2.9.	4			12 3 2
														6
							7									9
			6		6 4									8		5
	W									W			5
							2									1
																7
					1
8.2.5.			4	11	5	10			8.2.10.			2	9	4	1	5
			6		12 3
							14					8
										W
	W											12			7
				9		7	5									8
										6						2
													3
						2

Решение задания 8.2.1.

а) Упорядочим вершины графа G. Отметим, что под упорядочиванием вершин связного бесконтурного графа понимают такое разбиение его вершин на группы, при котором:

1)вершины первой группы не имеют предшествующих вершин, а вершины последней группы не имеют последующих вершин;

2)вершины любой группы не имеют предшествующих вершин в следующей группе;

3)вершины одной и той же группы не соединяются ребрами. Рассмотрим матрицу весов графа G:

		4	8
				3		10
		3		4	3		.
W
						4
		2		5		7

155

Из первого столбца матрицы W следует, что в вершину x1 графа G не входит ни одно ребро. Следовательно, вершина x1 является первой в упорядочении, т.е. (1) x1, … .

Вычеркнем в матрице W 1-ю строку и 1-й столбец:

		4	8
				3		10
		3		4	3		.
W
						4
		2		5		7

Из третьего столбца полученной матрицы следует, что в вершину x3 графа G не входит ни одно ребро, отличное от ребра (x1, x3). Следовательно, вершина x3 является второй в упорядочении, т.е. (1) x1, x3, … .

Вычеркнем в матрице W 3-ю строку и 3-й столбец:

		4	8
				3		10
		3		4	3		.
W
						4
		2		5		7

Из пятого столбца полученной матрицы следует, что в вершину x5 не входит ни одно ребро, отличное от ребра (x3, x5). Следовательно, вершина x5 является третьей в упорядочении, т.е. (1) x1, x3, x5, … .

Вычеркнем в матрице W 5-ю строку и 5-й столбец:

		4	8
				3		10
		3		4	3		.
W
						4
		2		5		7

156

Из второго столбца полученной матрицы следует, что в вершину x2 не входит ни одно ребро, отличное от ребер (x1, x2), (x1, x3), (x1, x5). Следовательно, вершина x2 является следующей в упорядочении, т.е.

(1) x1, x3, x5, x2, … .

Вычеркнем в матрице W 2-ю строку и 2-й столбец:

		4	8
				3		10
		3		4	3		.
W
						4
		2		5		7

Из четвертого столбца полученной матрицы следует, что в вершину x4 не входит ни одно ребро, отличное от ребер (x2, x4), (x3, x4), (x5, x4). Следовательно, вершина x4 является следующей в упорядочении, т.е.

(1) x1, x3, x5, x2, x4, … .

Поскольку G – граф 6-го порядка, то последней в упорядочение (1) запишем вершину x6: (1) x1, x3, x5, x2, x4, x6.

б) С помощью алгоритма Дейкстры найдем в графе G (x1,x6)-путь максимального веса.

Алгоритм Дейкстры нахождения во взвешенном связном орграфе без контуров (x1,xn)-пути максимального веса состоит из следующих этапов:

1 этап. Находят максимальный вес (x1,xn)-пути, последовательно вычисляя wi – максимальный из весов всех (x1,xi)-путей графа G,

i 2, n.

2этап. Находят (x1,xn)-путь в графе G, вес которого равен wn.

1этап. Найдем максимальный вес (x1,x6)-пути. Так как упорядочение вершин графа G имеет вид (1) x1, x3, x5, x2, x4, x6, то находим последо-

вательно w1, w3, w5, w2, w4, w6:

157

w3 max{ w13} 8 ;

w5 max{ w15, w3 w35} 11;

нет 8 3

w2 max{ w12, w3 w32, w5 w52} 13 ;

4

11

13

w4 max{ w14, w3 w34, w5 w54, w2 w24} 16 ;

нет

12

16

16

w6 max{ w16, w3 w36, w5 w56, w2 w26, w4 w46} 23 .

нет

нет

18

23

20

Таким образом, 23 – минимальный вес (x1,x6)-пути графа G.

2 этап. Найдем (x1,x6)-путь графа G веса 23. Для этого рассмотрим процесс получения числа w6=23:

w6	23 w2	w26 ;
	13		10
w2	13 w5	w52 ;
	11		2
w5	11 w3	w35 ;
	8		3
w3 8 w13 .
Следовательно,			w6	23 ((w13	w35) w52 ) w26			. Это означает, что
				8	3	2	10

искомый путь веса 23 имеет вид: (x1, x3, x5, x2, x6).

Задание 8.3. Для взвешенного связного орграфа G, не содержащего контуров отрицательного веса, заданного матрицей весов W с помощью алгоритма Беллмана – Мура найти (x1, xn ) -путь минимального веса.

158

8.3.1.			15		12			10
				4	6			2
								4	2 3
	W			10 7							9
									5		5
											6
8.3.2.			7	9		3
				2		6			3
						5			10		1
	W					4			6 7
				4					2 11
											9
8.3.3.			4			3
				2			6
					5			2
	W		1							1
									4
										3
8.3.4.			2				5
				5					8
					3		4
	W		1							6
			7							2
					2					1
							159

8.3.5.				5	2	5	4			3
							4			3
						1
	W	3				8			3
										2
			6	7	1
8.3.6.				3
						2
							7		11
			4		5		3
	W								13
				1	4		9
					6				3
8.3.7.			10		3	5
				6	1	4
						2	2
	W
				8		9
							5
8.3.8.				5		3		8		9
					10				4
									13
	W			5		15 7
										2
			12	11	2
						160