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

8.3.9.			3	6
					7		9
			4			7	5		9
	W			5					4
			9		10		6		3
								7
8.3.10.				12		10	2
				4	8		2		8
			2		3	7
	W			10		7			9
					5		3
					5				8

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

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

Введем обозначения: пусть Qi – последовательность вершин графа G

(очередь), wi – временная метка (x1, xi ) -пути, i 2, n.

Пусть Q1 {x1}, w1 0, wi , i 2, n.

Рассмотрим действие (1):

удаляем из очереди Qi первую вершину, например, x j , и получаем множество Qi 1 , т.е. Qi 1 Qi \{x j } ;

записываем последователи удаленной вершины x j : xs , (2);

161

корректируем		метки	всех вершин из (2) по	правилу:
ws	min{ws	, wj	wjs}, где wjs – вес (метка)	ребра, со-
новая	пред пред

единяющего j-ю и s-ю вершины;

если wsновая wsпред , то вершину xs заносим в очередь Qi 1 , – в конец очереди, если вершина xs впервые входит в очередь, в начало очереди, в противном случае;

таким образом, получаем корректировку очереди Qi 1 .

Действие (1) повторяем до тех пор, пока в результате корректировки очереди не получим пустую очередь, т.е. Qk для некоторого натурального k.

С помощью алгоритма Беллмана – Мура найдем в графе G, заданном матрицей весов W, (x1,x7)-путь минимального веса:

		15		12	10
			4	6	2
					4 2		3
								.
W		10			7		9
						5	5
							6

		1. Пусть Q1 {x1}, w1 0,				wi ,		i 2,7.
		2. Рассмотрим Q2			Q1 \{x1} ;
запишем последователи вершины x1 : x2 , x4 , x5 ;
корректируем метки вершин x2 , x4 , x5 :
w2	новая	min{w2	пред	, w1	w12} 15			Q2 {x2} ,
				пред
					15
				0
						162

w4	новая	min{w4	пред	, w1	w14} 12		Q2	{x2 , x4} ,
				пред
					12
				0
w5		min{w5		, w1	w15} 10		Q2	{x2 , x4 , x5}.
новая		пред		пред
					10
				0

Таким образом, получаем корректировку очереди Q2 : Q2 {x2 , x4 , x5}. 3. Рассмотрим Q3 Q2 \{x2} {x4 , x5};

запишем последователи вершины x2 : x3 , x4 , x5 ;
корректируем метки вершин x3 , x4 , x5 :
w3	min{w3	, w2		w23} 19		Q3 {x4 , x5 , x3},
новая
	пред		пред
		15		4
w4новая	min{w4пред	, w2пред		w24} 9 12		Q3 {x4 , x5 , x3},
	12	15		6
w5	min{w5	, w2		w25} 10 10 .
новая
	пред		пред
	10	15		2

Таким образом, получаем корректировку очереди Q3 : Q2 {x4 , x5 , x3} .

	4. Рассмотрим Q4 Q3 \{x4} {x5 , x3} ;
запишем последователи вершины x4 : x3 , x5 , x7 ;
корректируем метки вершин x3 , x5 , x7 :
w3	min{w3	, w4	пред	w43} 19	19 ,
новая	пред
				10
	19	9
w5	min{w5	, w4		w45} 10	10 ,
новая
	пред		пред
	10	9		7
w7новая	min{w7пред	, w4пред		w47} 18			Q4 {x5 , x3 , x7} .
		9		9
				163

Таким образом, получаем корректировку очереди Q4 : Q4								{x5 , x3 , x7} .
		5. Рассмотрим Q5 Q4 \{x5} {x3 , x7} ;
запишем последователи вершины x5 : x6 , x7 ;
корректируем метки вершин x6 , x7 :
w6		min{w6		, w5	w56} 5		Q5 {x3 , x7 , x6} ,
	новая
			пред	пред
				10	5
w7		min{w7		, w5	w57} 15 18		Q5 {x7 , x3 , x6}.
	новая
			пред	пред
		18		10	5
Таким образом, получаем корректировку очереди Q5 : Q5								{x7 , x3 , x6}.
		6. Рассмотрим Q6 Q5 \{x7} {x3 , x6};
запишем последователи вершины x7 : нет;
Таким образом, Q6 {x3 , x6} .
		7. Рассмотрим Q7 Q6 \{x3} {x6};
запишем последователи вершины x3 : x5 , x6 , x7 ;
корректируем метки вершин x5 , x6 , x7 :
w5		min{w5		, w3	w35} 10 10 ,
новая
		пред		пред
		10		19	4
w6		min{w6		, w3	w36} 5 5 ,
	новая
			пред	пред
		5		19	2
w7		min{w7		, w3	w37} 15 15 .
	новая
			пред	пред
		15		19	3
Таким образом, получаем корректировку очереди Q7 : Q7								{x6}.
		8. Рассмотрим Q8 Q7 \{x6} ;
					164

запишем последователи вершины x6 : x7 ;

корректируем метку вершины x7 :

w7новая	min{w7пред	, w6пред	w67} 11 15		Q8 {x7}.
	15	5	6

Таким образом, Q8 {x7}.

9. Рассмотрим Q9 Q8 \{x7} ;

запишем последователи вершины x7 : нет;

Таким образом, получаем корректировку очереди Q9 : Q9 .

Согласно алгоритму Беллмана – Мура, процесс корректировки меток окончен, и w7 11 – минимальный вес (x1,x7)-пути графа G.

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

11 w7			w6				w67		,
	п оследняя			временная
								6
					5
5 w6		w5		w56		,
врем
			врем
			10		5
10 w5			w1		w15 .
	время			врем
					10
				0
Следовательно,				11 (w15				w56 ) w67			. Это означает, что искомый
							10		5	6

(x1,x7)-путь веса 11 имеет вид: (x1, x5 , x6 , x7 ) .

Тема 9. Фундаментальные циклы и фундаментальные разрезы графов

165

Задание 9.1. Для неорграфа G найти: а) один из остовов Т;

б) все фундаментальные циклы относительно остова Т; в) матрицу фундаментальных циклов относительно остова Т; г) все фундаментальные разрезы относительно остова Т;

д) матрицу фундаментальных разрезов относительно остова Т.

9.1.1.

9.1.2.

9.1.3.

9.1.4.

9.1.5.

166

9.1.6.

9.1.7.

9.1.8.

9.1.9.

9.1.10.

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

а) Найдем один из остовов графа G. Предварительно введем обозначения для ребер графа G.

167

Согласно определению 21.1, T (V , R ) – остов графа G , если V V и Т является лесом, который образует дерево на каждой связной компоненте графа G. Поскольку граф G содержит 8 вершин (n=8), 11 ребер (m=11) и 1 связную компоненту (k=1), то, ввиду следствия 20.1.1, всякий остов графа G имеет 7 ветвей (n–k =7) и 4 хорды (m–(n–k) =4). В качестве остова Т выберем следующую часть графа G:

T (V , R ) , где V V , R {a11,u1,u2 ,u9 , a8 , a5 , a7}.

Т:

б) Найдем фундаментальные циклы графа G относительно остова Т. Согласно определению 22.1, фундаментальным циклом графа G относительно остова T и хорды u называется цикл C графа G, состоящий из хорды u и тех ветвей остова T, которые соединяют концы хорды u простой цепью. Поэтому граф содержит столько фундаментальных циклов, сколько хорд имеет его остов. Таким образом, граф G имеет 4 фундаментальных цикла:

C1 {u3 ,u1,u2} , C2 {u10,u11,u1,u2 ,u9 ,u8 ,u5}, C3 {u4 ,u2 ,u9},

C4 {u6 ,u7 ,u8}.

в) Найдем матрицу фундаментальных циклов графа G относительно остова Т. Согласно определению 22.2, матрицей фундаментальных

циклов графа G относительно остова T называется матрица размера

m n k m вида:

168

	a		a
	11		1m			1, если u j		Ci
M				,	где aij				, i 1, m n k ,
								C
						0, если u	j		i
am n k 1		am n k m

j 1, m.

Следовательно, матрица фундаментальных циклов графа G относительно остова Т имеет вид:

1		1	1	0	0	0	0	0	0	0	0
	1	1	0	0	1	0	0	1	1	1	1
M	0 1 0 1				0	0	0	0	1	0	0	.
	0	0	0	0	0	1	1	1	0	0	0

г) Найдем фундаментальные разрезы графа G относительно остова Т. Согласно определению 22.6, фундаментальным разрезом графа G относительно остова T и ветви v называется разрез L графа G, состоящий из ветви v, которая является простым разрезом остова T по некоторому разбиению V1 ,V2 , и всех хорд остова T, которые соединяют вершины из V1 с

вершинами из V2. Поэтому граф содержит столько фундаментальных разрезов, сколько ветвей имеет его остов. Таким образом, граф G имеет 7 фундаментальных разрезов:

L1 {u11,u10} , L2 {u1,u10,u3} , L3 {u2 ,u3 ,u10,u4},	L4 {u9 ,u10,u4},
L5 {u8 ,u10,u6} , L6 {u7 ,u6} , L7 {u5 ,u10} .

д) Найдем матрицу фундаментальных разрезов графа G относительно остова Т. Согласно определению 22.7, матрицей фундаментальных разрезов графа G относительно остова T называется матрица N размераn k m вида:

	a		a
	11		1m
N				,
a	n k 1	a
			n k m

		j	i
	1, если u		L
где aij				, i 1, n k , j 1, m.
			Li
	0, если u j

Следовательно, матрица фундаментальных разрезов графа G относительно остова Т имеет вид:

169

0		0	0	0	0	0	0	0	0	1	1
	1	0	1	0	0	0	0	0	0	1	0
	0	1	1	1	0	0	0	0	0	1	0
												.
N 0 0 0 1 0 0 0 0 1 1											0
	0	0	0	0	0	1	0	1	0	1	0
	0	0	0	0	0	1	1	0	0	0	0
	0	0	0	0	1	0	0	0	0	1	0

Тема 10. Нахождение остовов графа минимального и максимального весов

Задание 10.1. Для взвешенного связного неорграфа G, заданного матрицей весов W, с помощью алгоритма Прима найти:

а) остов минимального веса; б) остов максимального веса.

10.1.1.						5	3		6
					4	2		3	7
			4			5	7		1
	W 5		2	5					8
		3			7			3
			3				3		9
		6	7		1	8		9

170