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

3.2.9.		а)	удалить ребро (1,4);
		б)	добавить ребро (3,1);
		в)	удалить вершину 1;
		г)	добавить вершину 5;
		д)	ввести вершину 6 в ребро (2,3);
		е)	отождествить вершины 3, 4;
		ж) расщепить вершину 2 по разбие-
			нию V ={1,4}, V ={3} множества
			{1,3,4};
		з) найти G .
3.2.10.		а)	удалить ребро (2,4);
		б)	добавить ребро (1,2);
		в)	удалить вершину 4;
		г)	добавить вершину 5;
		д)	ввести вершину 6 в ребро (3,2);
		е)	отождествить вершины 1, 2;
		ж) расщепить вершину 3 по разбие-
			нию V ={1,4}, V ={2} множества
			{1,2,4};
		з)	найти G .

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

Используя определения 5.7-5.14, выполним унарные операции над графом G1:

а) Удалим из графа G1 ребро (1,2):

б) Добавим в граф G1 ребро (1,4):

131

в) Удалим из графа G1 вершину 4:

г) Добавим в граф G1 вершину 5:

д) Введем вершину 6 в ребро (3,4):

е) Отождествим вершины 1 и 4 в графе G1:

ж) Расщепим вершину 1 по разбиению V={2}, V ={3,4} множества

{2,3,4}:

132

з) Найдем G1 :

Тема 4. Гомоморфизм графов

Задание 4.1. Построить гомоморфизм графа G в граф G1:

G

G1

4.1.1.

4.1.2.

133

4.1.3.

4.1.4.

4.1.5.

4.1.6.

4.1.7.

134

4.1.8.

4.1.9.

4.1.10.

Решение задания 4.1.1. Рассмотрим графы G и G1:

G=(V,R) G1=(V1,R1)

Построим отображение φ: V V1, удовлетворяющее определению 6.1, т.е. удовлетворяющее условию a, b V:

(a, b) R ( (a) , (b) ) R1.

Зададим отображение φ: V V1 по правилу:

(1) c , (2) c , (3) a , (4) a , (5) b . 135

Тогда для каждого ребра (a,b) графа G найдется соответствующее ему ребро ( (a) , (b) ) в графе G1:

[1,4] R ( (1) , (4) ) =(c, a) R1, [1,5] R ( (1) , (5) ) =(c, b) R1, [2,3] R ( (2) , (3) ) =(c, a) R1, [2,5] R ( (2) , (5) ) =(c, b) R1, [3,5] R ( (3) , (5) ) =(a, b) R1, [4,5] R ( (4) , (5) ) =(a, b) R1.

Следовательно, φ – гомоморфизм G в G1.

Тема 5. Нахождение маршрутов графа заданной длины

Задание 5.1. Для графа G из задания 1.1 найти матрицу маршрутов длины 3 и выписать все маршруты длины 3 .

Решение задания 5.1.1. Рассмотрим граф G из задания 1.1.1:

136

Согласно определению 7.8, матрицей маршрутов длины k графа G назы-

вается матрица				Ak , где			A			– матрица смежности графа G.
				G				G
Запишем матрицу смежности графа G (см. решение задания 1.1.1 а)):
										0		1	1		0		0
											0	0	0		0		0
							A				0	1	1		1		1		.
								G
										0		0	0		0		0
											1	1	0		0		0
Тогда
		0 1		1 0 0 0 1 1									0	0			0 1 1 0 0
			0 0	0 0 0				0 0 0					0	0			0 0 0 0 0
A	3		0 1	1 1 1				0 1			1		1	1			0 1 1 1 1
G
		0 0		0 0 0 0 0 0									0	0			0 0 0 0 0
			1 1	0 0 0				1 1			0		0	0			1 1 0 0 0
		0 1		1 1 1 0 1 1									0	0			1 2 1 1				1
			0 0	0 0 0				0 0			0		0	0				0 0 0 0			0
			1 2	1 1 1				0 1			1		1	1				1		3 2 1 1		.
		0 0		0 0 0 0 0 0									0	0			0 0 0 0				0
			0 1	1 0 0				1 1			0		0	0				0 1 1 1			1
Следовательно, матрица маршрутов длины 3 графа G имеет вид:
										1		2	1		1		1
											0	0	0		0		0
						A3					1 3		2		1 1				.
								G
										0		0	0		0		0
											0	1	1		1		1

137

Найдем в графе G все маршруты длины 3. Для этого воспользуемся

k	c	...	c
	11			1n
теоремой 7.1. Согласно теореме 7.1, если AG	=					, то эле-
		...
	cn1		cnn
мент cij равен числу (ai,aj)-маршрутов длины k графа G,			i=1, n ,			j=1, n .
Таким образом, получаем:

с11=1 в графе G существует один (a1,a1)-маршрут длины 3: (a1,a3,a5,a1);

с12=2 в графе G существует два (a1,a2)-маршрута длины 3: (a1,a3,a3,a2), (a1,a3,a5,a2);

с13=1 в графе G существует один (a1,a3)-маршрут длины 3: (a1,a3,a3,a3);

с14=1 в графе G существует один (a1,a4)-маршрут длины 3: (a1,a3,a3,a4);

с31=1 в графе G существует один (a3,a1)-маршрут длины 3: (a3,a3,a5,a1);

с32=1 в графе G существует три (a3,a2)-маршрут длины 3: (a3,a3,a3,a2),

(a3,a3,a5,a2), (a3,a5,a1,a2);

с33=2 в графе G существует два (a3,a3)-маршрут длины 3: (a3,a3,a5,a1); (a3,a5,a1,a3);

с34=1 в графе G существует один (a3,a4)-маршрут длины 3: (a3,a3,a3,a4);

с35=1 в графе G существует один (a3,a5)-маршрут длины 3: (a3,a3,a3,a5);

с52=1 в графе G существует один (a5,a2)-маршрут длины 3: (a5,a1,a3,a2);

с53=1 в графе G существует один (a5,a3)-маршрут длины 3: (a5,a1,a3,a3);

с54=1 в графе G существует один (a5,a4)-маршрут длины 3: (a5,a1,a3,a4);

с55=1 в графе G существует один (a5,a5)-маршрут длины 3: (a5,a1,a3,a5). Следовательно, мы получили все маршруты графа G длины 3.

138

Тема 6. Сильные компоненты графа

Задание 6.1. Для графа G из задания 1.1 найти: а) матрицу достижимости, б) матрицу контрдостижимости,

в) матрицу сильных компонент, г) все сильные компоненты.

Решение задания 6.1.1. Рассмотрим граф G из задания 1.1.1:

а) Найдем матрицу достижимости графа G. Так как граф G имеет 5 вершин, то, согласно определению 8.2, матрица достижимости C cij

графа G является матрицей 5-го порядка, причем

		i		j
	1, если из вершины a достижима вершина a				,
cij
			не достижима вершина a j .
	0, если из вершины ai

Напомним, что, ввиду определения 8.1, вершина b является достижимой из вершины a, если в G существует a, b -маршрут. Следовательно, матрица достижимости С графа G имеет вид:

139

1		1	1	1	1
	0	1	0	0	0
C	1	1	1	1	1	.
0		0	0	1	0
	1	1	1	1	1

б) Найдем матрицу контрдостижимости графа G. Согласно замечанию 8.3, матрица контрдостижимости D dij графа G получается в ре-

зультате транспонирования матрицы достижимости графа G, т.е. D tC . Таким образом, матрица контрдостижимости D графа G имеет вид:

1	0	1	0	1
1	1	1	0	1
D 1	0	1	0	1 .
1	0	1	1	1
1	0	1	0	1

в) Найдем матрицу сильных компонент графа G. Согласно замечанию 9.2, матрицей сильных компонент графа G называется матрица S, построенная в теореме 8.2:

S C D sij , где sij cij dij ,

C cij , D dij – матрицы достижимости и контрдостижимости графа

G соответственно. Следовательно,
1 1 1 1					1		1 0 1 0 1		1		0	1	0	1
	0	1	0	0	0		1 1 1 0 1			0	1	0	0	0
S C D	1	1	1	1	1		1 0 1 0 1			1	0	1	0	1	.
0		0	0	1	0		1 0 1 1 1		0		0	0	1	0
	1	1	1	1	1		1 0 1 0 1			1	0	1	0	1

Таким образом,

140