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

Задание 1.4. Изобразить граф G, заданный матрицей Кирхгофа KG.

1.4.1.		2		1	1	0	0		1.4.6.		1		0	1 0		0
			1 1		0	0	0					0	3	0	1	0
	K		1	0	3	1	1			K		1	0	4	1	0
	G									G
		0		0	1 4		1				0		1	1 5		1
			0	0	1	1	2					0	0	0	1	1
1.4.2.		2		1	0	0	1		1.4.7.		3		0	1	1	1
			1			1
				4	0		0					0	2 0		0	0
	K		0	0	2	1	1			K		1	0 3 1			1
	G									G
		0		1	1 4		0				1		0 1 3			1
			1		1							1	0 1		1
				0		0	2									5
1.4.3.		2		1	0	0	1		1.4.8.		2		1	0	0	1
			1	2	0	1	0					1	2	1 0		0
	K		0	0	1	1	0			K		0	1	3	1	1
	G									G
		0		1	1 2		0				0		0	1 3		0
			1 0		0	0	3					1	0	1 0		4
1.4.4.		5		1	1	1	0		1.4.9.		3		1	0	0	0
			1	3	1	1	0					1	3	0	1	1
	K		1	1 2 0			0			K		0	0	2	1	1
	G									G
		1		1	0	3	1				0		1	1 4		0
			0	0	0	1	3					0	1	1 0		2
1.4.5.		2		0	1	1	0		1.4.10.		3		0	1 1		1
			0	5	1	1	1					0	1	1 0		0
	K		1	1 2 0			0			K		1	1 4 0			0
	G									G
		1		1 0		2	0				1		0	0	2	1
			0	1 0		0	1					1	0	0	1	2
									121

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

Изобразим граф G, заданный следующей матрицей Кирхгофа:

							2	1	1	0	0
							1
								1	0	0	0
			K				1	0	3	1	.
											1
				G
							0	0	1	4	1
									1	1
							0	0			2
Поскольку		KG kij			– матрица 5-го порядка, то, ввиду определе-
ния 4.5, граф		G	имеет				5	вершин		a1, a2 , a3 , a4 , a5 , причем
aii deg ai , i 1,5, и при i j							справедливо			aij	1 тогда и только то-
гда, когда вершины ai			и a j		являются смежными. Таким образом, граф G
имеет вид:

Задание 1.5. Изобразить граф G 5-го порядка, заданный списком дуг.

1.5.1.					1.5.6.
		m (1,2,3, 4,5,1)				m (1,2,3, 4,5,1)
				(2,4,3,5,1,4)					(2,4,3,5,1,4)
		n				n
1.5.2.					1.5.7.
		m (1,2,3, 4,5,1)				m (1,2,3, 4,5,1)
				(2,4,3,5,1,4)					(2,4,3,5,1,4)
		n				n
					122

1.5.3.					1.5.8.
		m (1,2,3, 4,5,1)				m (1,2,3, 4,5,1)
				(2,4,3,5,1,4)					(2,4,3,5,1,4)
		n				n
1.5.4.					1.5.9.
		m (1,2,3, 4,5,1)				m (1,2,3, 4,5,1)
				(2,4,3,5,1,4)					(2,4,3,5,1,4)
		n				n
1.5.5.					1.5.10.
		m (1,2,3, 4,5,1)				m (1,2,3, 4,5,1)
				(2,4,3,5,1,4)					(2,4,3,5,1,4)
		n				n

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

Изобразим граф G 5-го порядка, заданный следующим списком дуг:

m (1,2, 3, 4,5,1) . n (2,4,3,5,1,4)

Напомним, что список дуг графа G=(V,R) имеет вид

m (m1 , m2		,..., m		R		)	,

n (n1 , n2 ,..., n R )

		) ui
где (am	, an		– i-е ребро графа G. Поскольку векторы m и n имеют 6
i	i
координат,		то	граф G имеет 6 ребер u1 (a1, a2 ) ,		u1 (a2 , a4 ) ,
u1 (a3 , a3 ), u1 (a4 , a5 ) , u1 (a5 , a1 ) , u1 (a1, a4 ) .

G

123

Тема 2. Части и подграфы графа

Задание 2.1. Для графа G из задания 1.1 найти (записать аналитически) один подграф и одну часть, не являющуюся подграфом графа G.

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

Рассмотрим граф G (V , R) из задания 1.1.1:

1) Найдем один из подграфов графа G. Согласно определению 1.18, G1 (V1 , R1 ) – подграф графа G, если V1 V и R1 R V12 .

Пусть V1 a1, a2 , a5 . Тогда R1 R V12 u1,u2 ,u7 . Таким образом, G1 (V1 , R1 ) , где V1 a1, a2 , a5 , R1 u1,u2 , u7 , – подграф графа G.

2) Найдем одну из частей графа G, не являющуюся подграфом графа G. Ввиду определений 1.17 и 1.18, G2 (V2 , R2 ) – часть графа G, не

являющаяся подграфом графа G, если V2 V и R2 R V22 .

Пусть V2 a2 , a3 , a5 . Тогда R V22 u3 ,u4 ,u6 ,u7 . Тогда в качестве части графа G, не являющейся его подграфом, можно выбрать, например, G2 (V2 , R2 ) , где V2 a2 , a3 , a5 , R1 u1,u2 , u7 .

124

Тема 3. Операции над графами

Задание 3.1. Для графов G1 и G2 найти (записать аналитически): а) пересечение G1 G2 ;

б) объединение G1 G2 ;

в) кольцевую сумму G1 G2 ; г) соединение G1 G2 ;

д) произведение G1 G2 ; е) композицию G1 G2 .

G1

G2

3.1.1.

3.1.2.

3.1.3.

125

3.1.4.

3.1.5.

3.1.6.

3.1.7.

3.1.8.

3.1.9.

126

3.1.10.

Решение задания 3.1.1.
Опишем графы G1 и G2 аналитически:
G1 (V1 , R1 ) , где		V1 1, 2, 3, 4 , R1			(1,2), (3,4),[2,4],[1,3], (2,2) ;
G2 (V2 , R2 ) , где		V2 1, 2, 3 , R2			(1,2),[2,3], (1,3), (1,1) .
а) Найдем пересечение графов G1 и G2. Согласно определению 5.1,
G1 G2	(V , R) ,		где	V V1 V2 ,		R R1 R2 .	Таким	образом,
G1 G2	(V , R) ,		где V 1, 2, 3 ,		R (1,2), (1,3) .
б) Найдем объединение графов G1 и G2. Согласно определению 5.2,
G1 G2	(V , R) ,		где	V V1 V2 ,		R R1 R2 .	Таким	образом,
G1 G2	(V , R) ,		где V 1, 2, 3, 4 ,

R (1,2),(3,4),[2,4],[1,3],[2,3],(2,2),(1,1) .

в) Найдем кольцевую сумму графов G1 и G2. Согласно определе-

нию	5.3,	G1 G2 (V , R) ,	где	V V1 V2 ,
R R1 R2	(R1	\ R2 ) (R2 \ R1) . Таким	образом,	G1 G2 (V , R) ,
где V 1, 2, 3, 4 , R (3,4),[2,4],(3,1),[2,3],(2,2),(1,1) .
г) Найдем соединение графов G1 и G2. Согласно определению 5.4,
G1 G2 (V , R) ,		где V V1 V2 , R R1	R2 {(a,b) | (a V1,b V2 )
		127

или (a V2	,b V1 ),a b}. Таким образом,	G1 G2 (V , R) , где
V 1, 2, 3, 4	, R [1,2],[3,4],[2,4],[1,3],[2,3],[1,4],(2,2),(1,1) .

д) Найдем произведение графов G1 и G2. Согласно определению

5.5, G1	G2	(V , R) , где	V V1 V2 , R {((a1 ,b1 ),(a2 ,b2 )) | (a1 a2 и
(b1 ,b2 ) R2 )		или (b1 b2		и (a1 , a2 ) R1 )}. Таким образом,
G1 G2	(V , R) , где

V{ (1,1), (1,2), (1,3), (2,1),(2,2), (2,3), (3,1),(3,2),(3,3), (4,1), (4,2),(4,3)} ,

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

R { (x1, x1 ), (x1, x2 ), (x1, x3 ), [x2 , x3 ], (x4 , x4 ), (x4 , x5 ), (x4 , x6 ),[x5 , x6 ], (x7 , x7 ), (x7 , x8 ), (x7 , x9 ),[x8 , x9 ],

(x10, x10 ), (x10, x11), (x10, x12 ),[x11, x12 ]; (x1, x4 ), (x1, x7 ), (x4 , x10 ),[x7 , x10 ],

(x2 , x5 ), (x2 , x8 ), (x5 , x5 ), (x5 , x11),[x8 , x11],

(x3 , x6 ), (x3 , x9 ), (x6 , x6 ), (x6 , x12 ),[x9 , x12 ] } A.

е) Найдем композицию графов G1 и G2. Согласно определению 5.6,

G1[G2 ] (V , R) , где V V1 V2 , R {((a1 ,b1 ),(a2 ,b2 )) | (a1 , a2 ) R1 или ( a1 a2 и (b1 ,b2 ) R2 )}, т.е. R A {((a1,b1),(a2 ,b2 )) | (a1, a2 ) R1}.

Таким образом, G1 G2 (V , R) , где

V{ (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3)} ,

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12

R A { (x1, x5 ), (x1, x6 ), (x2 , x4 ), (x2 , x6 ), (x1, x8 ), (x1, x9 ),(x2 , x9 ), [x2 , x7 ], [x4 , x11],[x4 , x12 ],[x5 , x10 ],[x5 , x12 ], [x6 , x10 ],[x6 , x11],(x7 , x11), (x7 , x12 ), (x8 , x10 ),(x8 , x12 ),(x9 , x10 ),(x9 , x11), (x3 , x4 ), (x3 , x5 ),(x5 , x4 ), (x6 , x4 ),[x2 , x9 ], [x3 , x8 ],[x3 , x9 ] }.

128

Задание 3.2. Выполнить следующие унарные операции над графом G1 (результат изобразить графически):

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

129

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