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

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

Тема 1. Способы задания графов

Задание 1.1. Для графа G записать: а) матрицу смежности AG;

б) матрицу инцидентности BG; в) матрицу Кирхгофа KG;

г) список дуг; д) структуру смежности:

1.1.1.

1.1.2.

1.1.3.

111

1.1.4.

1.1.5.

1.1.6.

112

1.1.7.

1.1.8.

1.1.9.

1.1.10.

113

Решение задания 1.1.1.
а) Найдем матрицу смежности AG					графа				G (V , R) . Поскольку
граф G содержит 5 вершин, то, согласно							определению 4.1, матрица
AG aij является матрицей 5-го порядка, в которой
					i	j	) R
	1, если (a , a
aij									.
	0, если (ai , a j ) R
Таким образом, матрица смежности AG имеет вид:
			a1	a2 a3			a4	a5
	a1	0		1	1		0	0
	a2		0	0	0		0	0
									.
A	a		0	1	1		1	1
G	3
	a4	0		0	0		0	0
	a5		1	1	0		0	0

б) Найдем матрицу инцидентности BG графа G (V , R) . Поскольку
граф G содержит 5 вершин и 8 ребер, то, согласно определению 4.3, мат-
рица BG	bij является матрицей размера 5 8, в которой
		1, если реброu j				исходит из вершины ai ;
bij		1, если реброu j заходит в вершину ai
									и не является петлей;
		0, в противном случае.
Таким образом, матрица инцидентности BG имеет вид:
				u1		u2	u3 u4 u5 u6		u7	u8
			a1	1 1				0 0 0 0	1	0
			a2		0	1		1 0 0 0	0	1 .
		B a			0 0			1 1 1 1	1	0
		G	3					0 0 1 0
			a4	0		0			0	0
								0 0 0 1
			a5		1	0			0	1
								114

в) Найдем матрицу Кирхгофа KG графа G (V , R) . Согласно опре-

делению 4.5, матрица KG

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

рой

1,

если вершины ai

и a j

смежны

k

ij

0,

если вершины a и a

j

не смежны .

i

если i j

deg ai ,

Таким образом, матрица Кирхгофа KG имеет вид:

a1

a2

a3

a4

a5

a1

3

1

1 0

1

a2

1

3 1 0

1 .

K

a

1

1

6 1

1

G

3

1

a4

0

0

1

0

1

1

1 0

a5

3

в) Найдем список дуг графа

G (V , R) . Напомним, что если

ui (am

, an ) – i-е ребро графа G, то

i

i

m (m ,m ,...,m

R

)

1

2

список дуг графа G .

(n1 ,

n

n2 ,..., n

R

)

Так как

R a5 , a1 , a1, a2 , a3 , a2 , a3 , a3 , a3 , a4 , a3 , a5 , a1, a3 , a5 , a2 ,

то

m (5,1, 3, 3,3,3,1,5)
					список дуг графа G .
	n	(1,2,2,3,4,5,3,2)

г) Найдем структуру смежности графа G (V , R) . Напомним, что данный способ задания графа заключается в записи для каждой вершины графа списка всех ее последователей. Таким образом, структура смежности графа G имеет вид:

115

вершины – последователи a1 a2 , a3 ;

a2 нет ;

a3 a2 , a3 , a4 , a5 ; a4 нет ;

a5 a1, a2 .

Задание 1.2. Изобразить граф G, заданный матрицей смежности AG.

1.2.1.		1		0	1	1	1		1.2.6.		0		1	1	1	0
			0	1	0	1	0					1	0	0	0	0
	A		1	1	1	1	0			A		0	1	0	1	0
	G									G
		0 0			0	0	0				0 0 0 1					1
			0	1	0	1	1					1	1	1	1	0
1.2.2.		1		0	1	0	1		1.2.7.		0		0	1	0	0
			0	0	1	1	0					1	0	1	0	0
	A		0	1	0	0	0			A		0	0	0	0	1
	G									G
		1 1			1	0	0				0 1 0 1					0
			0	0	0	1	0					0	0	0	0	1
1.2.3.		0		1	0	0	0		1.2.8.		1		0	1	0	1
			1	1	1	0	0					1	0	0	1	1
	A		0	1	0	1	0			A		0	1	0	1	0
	G									G
		1 1			0	0	1				1 0 0 1					0
			0	0	1	1	0					0	0	0	0	0

116

	1.2.4.		0		1	1	1	0				1.2.9.						0		0	1	0	1
				1 0		0 1		0											0	1	1	1	0
		A		0 0		0 0		1								A			0	1	0 1		0
		G														G
			1 1 0 0					1										0 1 0 1					0
				0 0		1	0	1											0	0	1	1	0
	1.2.5.		0		0	1	1	0										1		1	0	0	1
				1	0	1	1	1				1.2.10.							0	0	1	0	0
		A		1 1 1			0	1								A			1 1		1	0	0
		G														G
			0 0 0 0					0										0 1 0 1					1
				0 0		1	0	0											0	0	1	0	0
	Решение задания 1.2.1.
Изобразим граф G, заданный следующей матрицей смежности:
									1			0	1	1		1
										0		1	0	1		0
							A			1		1	1	1		0	.
							G
									0			0	0	0		0
										0		1	0	1		1

Поскольку AG aij – матрица 5-го порядка, то, ввиду определения 4.1, граф G имеет 5 вершин a1, a2 , a3 , a4 , a5 , причем aij 1 тогда и только тогда, когда граф G имеет ребро ai , a j . Таким образом, граф G

имеет вид: G

117

Задание 1.3. Изобразить граф G, заданный матрицей инцидентности

BG.

1.3.1.			1	0	1	0	0	0	0
			1	1	0 1 0 1				0
	BG
			0	0	0	1	1	1	0
			0	1	0	0	1	0	1
1.3.2.			1	0	0	0	1	1	0
			0	0	1	1	0	1	0
	B		1 0		1 0		0	0 0
	G
			0	1	0	1	0	0	0
			0	0	0	0	1	0	1
1.3.3.			1	1	0	1	0
			0	0	0	0	1
	B		1	1	1	0	0
	G
			0	0	0	0	1
			0	0	0	1	0
1.3.4.			1	0	0	0	1
			1	1	0	0	0
	B		0	1	0	1 0
	G
			0	0	1	0	0
			0	0	1 1		0
1.3.5.			1	0	0	0	1	0	0
			0	1	0	1	0	1	0
	BG		0 0 0 1				1 1 1
			0	1	1	0	0	0	1
						118

1.3.6.		1		0	1	0	0
			0	0	1	0	1
	B		0	1	0	0	0
	G
		1		1	0	1	0
			0	0	0	1	1
1.3.7.		1		0	1	0	1
			1	0	0	0	0
	B		0	0 0		1	1
	G
		0		0	1	0	0
			0	1	0	1	0
1.3.8.		1		1	1	0	0		0	0
			0	0	0	1	0		1	0
	B		1 0		0	0	0		1	0
	G
		0		1	0	1	1		0	0
			0	0	1	0	0		0	1
1.3.9.		0		1	1	0	1
			0	1	0	1	0
	B		1	0	0	0	1
	G
		0		0	1	0	0
			1	0	0	1	0
1.3.10.		1		1	1	0	0
			0	0	1	0	0
	B		0	1	0	1	1
	G
		1		0	0	1	0
			0	0	0	0	0

119

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

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

	1		0	1	0	0	0	0
		1	1	0	1	0	1	0
BG									.
		0	0	0	1	1	1	0
		0	1	0	0	1	0	1

Поскольку	BG	bij – матрица размера 4 7 , то, ввиду определе-
ния 4.3, граф	G	имеет	4	вершины a1, a2 , a3 , a4	и 7 ребер
u1,u2 ,u3 ,u4 ,u5 ,u6 ,u7 , причем bij				1 тогда и только тогда, когда ребро
u j исходит из вершины ai ,			bij 1 тогда и только тогда,		когда ребро u j
заходит в вершину ai		и не является петлей. Таким образом, граф G имеет
вид:

G

120