ДМ Практикум

Применим описанный выше алгоритм:

T1 , w(T1) = 1

T2 , w(T2 ) = 2

T3 , w(T3 ) = 3

T4 , w(T4 ) = 4

T5 , w(T5 ) = 6

T6 , w(T6 ) = 8

T7 , w(T7 ) = 11

Кратчайший остов найден, его вес равен 11.

71

V * := V * {v*} .

Кратчайшие пути

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

Пусть G(V , E) - связный н-граф, v и u - две его несовпадающие верши- ны. Длина кратчайшего маршрута, соединяющего вершины v и u называется (взвешенным) расстоянием между вершинами v и u . Если G - ненагруженный, то считаем вес каждого его ребра равным 1.

Алгоритм Дейкстры позволяет найти кратчайшие пути от заданной вер- шины до остальных вершин графа. Алгоритм применим как для связных н- графов, так и для сильно связных орграфов, и является модифицированным по- иском в ширину, в котором для определения «уровня» вершины учитывается вес ребер.

Пусть G(V , E) - нагруженный сильно связный орграф с n вершинами, за-

данный матрицей весов W (G) , причем все веса дуг неотрицательны:

	w(vi ,v j ), (vi ,v j ) E,
w	=	∞, (v ,v	) E, , i, j =1,..., n .
ij		i j

	0, i = j

Будем искать кратчайшие пути из начальной вершины u во все осталь- ные вершины графа. Каждой вершине припишем метку (d (v), p(v)) , где d (v) - длина кратчайшего на данном шаге пути из u в v , а p(v) - предыдущая верши- на на этом пути (эта метка необходима, чтобы восстановить маршрут). На каж- дом шаге будем формировать множество V * - множество вершин, кратчайшие пути до которых уже найдены, и выбирать «ведущую» вершину v* .

1) На начальном этапе полагаем: V * := {u}; v* := u ;

d (u) := 0 , p(u) := 0 ; для всех остальных вершин: d (v) := ∞ , p(v) := 0 .

2) Для всех вершин v V \V * , смежных с v* :

d (v) := min{d (v), d (v* ) + w(v* ,v)} .

Если эта метка изменилась, то меняем и другую метку: p(v) := v* .

Добавляем вершину v* в множество V * :

3)Выбираем новую ведущую вершину v , такую, что v V \V * и d (v) мини- мальна, v* := v .

4)Повторяем шаги 2) и 3) до тех пор, пока в множество V * не попадут все вершины.

72

Пример 8.3. Найти кратчайшие пути из вершины v1 во все остальные вершины орграфа, заданного матрицей весов:

0∞10

∞

W (G) = ∞

∞∞∞

2	∞	3	∞	∞	∞	∞
0	∞	5	∞	∞	∞	∞
7	0	2	∞	3	∞	∞
∞	∞	0	1	5	∞	∞
∞	7	∞	0	10	∞	5	.
∞	∞	∞	∞	0	1	2
∞	∞	∞	1	∞	0	∞
∞	∞	∞	∞	∞	7	0

Применим алгоритм Дейкстры. Результат применения алгоритма приве- дем в таблице:

v*, d (v *), p (v *)

d (v1 )

d (v2 )

d (v3 )

d (v4 )

d (v5 )

d (v6 )

d (v7 )

d (v8 )

v1,0,

–

2

∞

3

∞

∞

∞

∞

v2 , 2,1

–

–

∞

3

∞

∞

∞

∞

v4 ,3,1

–

–

∞

–

4

8

∞

∞

v5 , 4,4

–

–

11

–

–

8

∞

9

v6 ,8,4

–

–

11

–

–

–

9

9

v7 ,9,6

–

–

11

–

–

–

–

9

v8 ,9,5

–

–

11

–

–

–

–

–

v3 ,11,5

–

–

–

–

–

–

–

–

Итак, кратчайшие пути из v1 в остальные вершины:

l(v1, v2 ) : v1 , v2

(длина пути 2);

l(v1, v3 ) : v1 , v4

, v5 , v3 (длина пути 11);

l(v1, v4 ) : v1 , v4 (длина пути 3);

l(v1, v5 ) : v1

, v4

, v5

(длина пути 4);

l(v1, v6 ) : v1

, v4

, v6

(длина пути 8);

l(v1, v7 ) : v1

, v4

, v6

, v7 (длина пути 9);

l(v1, v8 ) : v1

, v4

, v5

, v8 (длина пути 9).

73

Раскраски графов

Пусть G(V , E) - н-граф без петель. Раскраской (вершин) графа G называ- ется функция, которая каждой его вершине ставит в соответствие некоторое на- туральное число (цвет) таким образом, что смежные вершины имеют различные цвета. Хроматическим числом χ (G) графа G называется минимальное число цветов, требующихся для раскраски графа. Имеет место неравенство: χ (G) ≤ deg(G) +1, где deg(G) - наибольшая из степеней вершин графа G .

Независимым множеством вершин называется множество попарно не- смежных вершин графа. Независимое множество вершин графа называется максимальным, если оно не является собственным подмножеством другого не- зависимого множества вершин того же графа.

Алгоритм последовательной раскраски:

Для каждой вершины vi графа G определяем множество допустимых цветов S(vi ) , i =1,..., n . Например, на начальном этапе для всех вершин можно определить S(vi ) = {1, 2,..., n} , n - число вершин графа G .

1)Выбираем произвольную неокрашенную вершину v графа G и приписыва- ем ей минимальный допустимый для нее цвет s , s S (v) .

2)Цвет s удаляем из множеств допустимых цветов вершин, смежных с v .

3)Повторяем действия до тех пор, пока все вершины графа не будут окрашены.

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

Алгоритм точной раскраски:

1)Среди вершин графа G выделяем максимальное независимое множество вершин и окрашиваем их цветом 1. Удалив окрашенные вершины. получим граф G1 .

2)Пусть на предыдущем шаге построен граф Gk . Выбираем в нем некоторое максимальное независимое множество вершин и окрашиваем их в цвет k +1 . Удалив окрашенные вершины, получим граф Gk +1 .

3)Повторяем действия до тех пор, пока все вершины не будут окрашены.

Пример 8.4. Построить раскраску графа, заданного матрицей смежности:

		0	1	0	0	0	0	1	1
		1	0	1	0	0	0	1	1
		0	1	0	1	1	1	1	0
A(G) =	0 0 1 0 1 1 0 0 .
		0	0	1	1	0	1	0	0
		0 0 1 1 1 0 1 0
	1		1	1	0	0	1	0	1
	1 1 0 0 0 0 1 0

74

Для наглядности сделаем чертеж:

deg(G) = 5 , следовательно, χ (G) ≤ 6 и для любой вершины v графа G(V , E) можно определить множество допустимых цветов S(v) = {1, 2,3,4,5,6}. Будем строить раскраску как функцию ϕ :V →{1, 2,3, 4,5,6}.

а) Построим точную раскраску:

C1 = {v1,v3} ϕ(v1 ) = ϕ(v3 ) = 1 ;				C2 = {v2 ,v4} ϕ(v2 ) = ϕ(v4 ) = 2 ;
C3 = {v5 , v7 } ϕ(v5 ) = ϕ(v7 ) = 3 ;				C4 = {v6 ,v8} ϕ(v6 ) = ϕ(v8 ) = 4 .
б) Применим алгоритм последовательной раскраски:
шаг 0) S(v1 ) = {1, 2,3, 4,5,6};				S(v2 ) = {1,2,3, 4,5,6};		S(v3 ) = {1, 2,3, 4,5,6};
	S(v4 ) = {1,2,3, 4,5,6};			S(v5 ) = {1, 2,3, 4,5,6};		S(v6 ) = {1,2,3, 4,5,6};
	S(v7 ) = {1,2,3, 4,5,6};			S(v8 ) = {1, 2,3,4,5,6}.
шаг 1)	ϕ(v1 ) = 1 ;	S(v2 ) = {2,3, 4,5,6};			S(v3 ) = {1, 2,3, 4,5,6};
	S(v4 ) = {1,2,3, 4,5,6};			S(v5 ) = {1, 2,3, 4,5,6};		S(v6 ) = {1,2,3, 4,5,6};
	S(v7 ) = {2,3, 4,5,6};			S(v8 ) = {2,3,4,5,6}.
шаг 2)	ϕ(v2 ) = 2	S(v3 ) = {1,3, 4,5,6};			S(v4 ) = {1,2,3, 4,5,6};
	S(v5 ) = {1, 2,3, 4,5,6};			S(v6 ) = {1,2,3, 4,5,6};		S(v7 ) = {3,4,5,6};
	S(v8 ) = {3,4,5,6}.
шаг 3)	ϕ(v3 ) = 1 ;	S(v4 ) = {2,3, 4,5,6};			S(v5 ) = {2,3, 4,5,6};
	S(v6 ) = {2,3, 4,5,6};			S(v7 ) = {3,4,5,6}; S(v8 ) = {3,4,5,6}.
шаг 4)	ϕ(v4 ) = 2 ;		S(v5 ) = {3, 4,5,6} ;		S(v6 ) = {3,4,5,6}; S(v7 ) = {3,4,5,6};
	S(v8 ) = {3,4,5,6}.
шаг 5)	ϕ(v5 ) = 3	S(v6 ) = {4,5,6}; S(v7 ) = {3,4,5,6}; S(v8 ) = {3,4,5,6}.
шаг 6)	ϕ(v6 ) = 4	S(v7 ) = {3,5,6}; S(v8 ) = {3,4,5,6}.
шаг 7)	ϕ(v7 ) = 3	S(v8 ) = {4,5,6}.
шаг 8)	ϕ(v8 ) = 4 .

Получили раскраску, совпадающую с точной:

ϕ(v1 ) = 1 ; ϕ(v2 ) = 2 ; ϕ(v3 ) = 1 ; ϕ(v4 ) = 2 ;

75

ϕ(v5 ) = 3 ; ϕ(v6 ) = 4 ϕ(v7 ) = 3 ; ϕ(v8 ) = 4 .

Для данного графа последовательная раскраска оказалась минимальной.

А) Контрольные вопросы

8.1Дайте определение обхода графа. В чем состоят «поиск в глубину» и «по- иск в ширину»?

8.2Сформулируйте и докажите критерий а) существования эйлерова цикла в н-графе;

б) существования эйлеровой цепи в н-графе,

в) эйлерова цикла в орграфе.

8.3Можно ли нарисовать, не отрывая карандаш от бумаги и не проходя по отрезкам линий дважды фигуры, приведенные на рисунке 8.1?

а) сабли Магомета		б)		в)
	Рисунок 8.1.

8.4Нарисуйте орграф, заданный матрицей весов:

∞		2	∞	5
	∞ ∞ 3			∞
W (G) =					.
	2	∞	∞	10
	∞	∞	1	∞

8.5Опишите алгоритм нахождения кратчайшего остова в нагруженном графе.

8.6Опишите алгоритм нахождения кратчайших путей от заданной вершины графа до остальных.

76

8.7Дайте определения (вершинной) раскраски графа, хроматического числа графа. Опишите алгоритмы раскраски графа.

8.8Найдите, чему равно хроматическое число графа G , если:

а) G - полный граф;

б) G - дерево.

Б) Задачи и упражнения

8.9В н-графе, заданном матрицей смежности, проведите поиск в глубину и поиск в ширину из вершины v1 :

		0	1	0	0	0	0	1	1					0	0	1	1	0	0	1	1
		1	0	1	0	1	0	1	1					0	0	1	0	1	0	1	1
		0	1	0	0	0	0	0	0					1	1	0	1	0	0	1	0
		0	0	0	0	1	1	0	0					1	0	1	0	0	0	0	1
а) A(G ) =											;	б) A(G ) =										.
1		0	1	0	1	0	1	0	1			2		0	1	0	0	0	0	0	0
							0 1
	0 0 0 1 1								0				0 0 0 0 0 0 0 0
	1		1 0 0 0 1					0 1					1		1	1	0 0 0 0 1
	1		1	0 0 1			0 1		0				1		1	0 1		0 0 1			0

8.10В орграфе, заданном матрицей смежности, проведите поиск в глубину и поиск в ширину из вершины v3 :

	0	0	0	0	0	0	0	1			0	0	1	1	0	0	0	0
	1	0	0	0	0	0	0	1			1	0	1	0	0	0	0	0
	0	1	0	0	0	0	1	0			0	0	0	1	1	1	0	0
	0	0	0	0	0	1	1	0			0	1	0	0	0	1	0	0
а) A(G ) =									;	б) A(G ) =									.
1	0	0	0	0	0	0	1	0		2	0	0	0	0	0	0	1	1
															0 0 1
0 0 0 0 1 0 1 0										0 0 0 1								0
0 0 0 0 0 0 0 0										0 0 0 0 0 0 0 0
0 0 1 1 0 0 1								0		0 0 0 0 0 1							1	0

8.11В н-графе, заданном матрицей смежности, найдите эйлеров цикл (цепь), если он (она) существует:

77

		0 1 1					0 0 0 0													0 1 1 0 0 0 0
		1 0 1					0 0 0 1													1 0 1 0 0 0 0
		1 1 0 1 0 0 1																		1 1 0 0 0 0 0
а) A(G ) =		0		0	1		0		1		0		0 ;				б) A(G ) =			0 0 0 0 1 0 1 ;
1													1				2
		0		0	0 1				0		1									0 0 0 1 0 0 1
				0	0 0				1		0
	0												1					0 0 0 0 1 0 1
	0			1	1		0		1		1		0					0 0 0 0 1 1 0
			2	1		0		0		0		1	0	0					0 1 1				0	0	1	0	1
			1	0		0		0		0		1	0	0					1		0	0 0 0 1				0 0
			0	0		2		1		0		0	1	0					1		0	0 1 0 0 1 1
			0	0		1		2		2		0	0	1					0 0 1				2	1	0	0	1
в) A(G ) =																;	г) A(G ) =											.
3			0	0		0		2		0		1	1	0			4		0 0 0 1 0 1							1 0
																					1
	1 1 0 0 1 0 0 1																	1				0 0 1 0 0 1
	0 0 1 0 1 0 0 0																	0 0 1					0	1	0	0	0
	0 0 0 1 0 1 0 2																	1			0	1	1	0	1	0	0

8.12В орграфе, заданном матрицей смежности, найдите эйлеров цикл, если он существует:

		1		0 0 1 0 0 1								1		1	0	0	0	1	1	0
												0 0 2 0 0 1 0 0
		0		1	1	1	0	1	0				0	0	1	2	1	0	0	0
		0		1 0 0 0 1 0
													1 0 0 1 1 0 0 0
	а) A(G ) =	1		0 0 1 0 0 1 ;								б) A(G ) =									;
	1											2	0 1 0 0 0 1 0 0
		0		1 0 0 0 1 0
												0 1 1 0 0 0 0 1
	0			1	0	0	1	1	1			0 0 0 0 0 0 0 1
	1 0 1 0 1 0 1
												2 0 0 0 0 0 0 1
			1	0	0	1	0	0	1
			0 1 1 1 0 1 0
	0			1	0	0	0	1	0
	в) A(G ) = 1 0 0 1 0 0 1 .
	3
			1	1	0	0	1	1	0
				1	0	0	1	1
	0								1
	1 0 1 0 1 0 1

8.13 Найдите кратчайший остов графа G , заданного матрицей весов:

78

	∞ 3		1 ∞ 5			1 ∞			∞ 4		1	∞ 4 1			∞
	3	∞ 2		3	∞ 3		∞		4	∞ 2		1	∞ ∞		∞
	1	2	∞ 1		2 ∞ 2				1	2	∞ ∞ 1			∞ 3
а) W (G1 ) =	∞ 3		1	∞ 1		2	∞ ; б) W (G2 ) =		∞ 1		∞ ∞ 2			3	∞ .
	5	∞ 2		1	∞ 1		5		4	∞ 1		2	∞ 2		6
		3	∞ 2		1					∞ ∞ 3			2	∞
1						∞ 2		1							1
∞ ∞ 2				∞ 5		2	∞	∞ ∞ 3				∞ 6		1	∞

8.14В графе, заданном матрицей смежности, найдите расстояния от первой вершины до остальных:

	0	1	0	0	0	1	0	1			1	1	0	0	0	1	1	1
	1	0	0	0	0	1	0	0			0	0	1	0	0	1	0	0
	0	0	0	1	0	0	0	0			0	0	1	1	0	0	0	0
	0	0	1	0	1	0	0	1			1	0	0	1	1	0	0	0
а) A(G ) =									; б) A(G2 ) =										.
1	0	0	0	1	0	1	1	0			0	1	0	0	0	1	1	0
		1 0 0 1											1
1						0 0 1				0 1				0 0 0 0 1
0 0 0 0 1						0 0 0				0 0 0 0 0 0 0 1
1		0 0 1			0 1		0 0			1		0 0 0 0 0 0 1

8.15В графе, заданном матрицей весов, найдите кратчайшие пути из второй вершины в остальные:

	0	3	1	∞	1		1	∞
	3	0 3 ∞ 1 ∞ 5
	1	3	0	∞ ∞			1	3
а) W (G ) =	∞ ∞ ∞ 0 1 ∞ 1 ;
1			∞
	1	1		1	0		1	2
		∞	1	∞	1		0
1								1
∞ 5 3 1 2 1 0
	0	∞ ∞ ∞			1		∞ 1
	∞ 0 6 8 3 ∞ 2
	∞ 6		0	3	1		∞ 3
в) W (G ) =	∞ 8 3 0				1	∞ 4 ;
3
	1	3	1	1	0		1	1
	∞ ∞ ∞ ∞				1		0
								1
1 2 3 4					1	1 0

	0	2	6	4 ∞ ∞ ∞
	4 0 ∞			1	∞ 4 1
	1	1	0	1	1	1	1
б) W (G ) =	∞ ∞ ∞ 0				∞	3 2 ;
2	∞		∞ ∞
		1			0	3	4
		∞ ∞		3	∞	0
3							1
∞ ∞ 2 1					∞ 2 0
	0	∞	2	∞ ∞ ∞			1
	∞ 0 6 5				7 2 1
	∞	2	0	∞	1	∞	2
г) W (G ) =	2 ∞ 1 0 ∞ ∞ ∞ .
4	∞ ∞			∞		∞
			1		0		1
	∞ ∞ ∞ ∞ ∞					0
							3

1 1 1 ∞ ∞ 5 0

8.16 Используя алгоритмы точного раскрашивания и последовательного рас- крашивания, задайте раскраску вершин графа, заданного матрицей смежности:

79

		0 1		1	0	0 0		1	1				0	0	1	1	1	1	1	1
		1	0	1	0	1	0	1	1				0	0	1	0	1	0	1	1
	1		1	0	0	0 1		0 0				1 1			0 1		0 0 1 0
а) A(G ) = 0 0 0 0 1							1	0	0		; б) A(G ) = 1 0 1					0	1	0	0	1 .
1	0 1 0 1					0 1		0 1			2	1		1	0 1		0 0 0 0
		0 0		1	1	1	0	1	0				1	0	0 0		0	0	1	1
		1	1	0	0	0 1		0	1				1	1	1	0	0	1	0	1
	1		1	0	0	1	0	1	0			1		1	0 1		0 1		1	0

8.17Структура сети сотовой связи представлена на рисунке 8.2. радиус зон покрытия базовых станций равен 1 км, координационное расстояние – 4 км. Определите, какие станции будут оказывать взаимные влияния друг на друга, постройте граф сети и распределите частоты таким образом, чтобы станции не создавали помех друг другу.

Рисунок 8.2

В) Тестовые задания (укажите единственный верный ответ)

8.18Эйлеровым называется цикл…

а) содержащий все ребра графа ровно один раз;

б) содержащий все вершины графа ровно один раз;

в) имеющий минимальную длину;

г) содержащий только вершины степени 2.

8.19Матрица смежности н-графа, содержащего эйлеров цикл, может иметь вид…

80