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

			0		1	1	1
				1	0	1	1
	AG								.
				0	0	1	0
				0	0	0	0

Решение:

Замечание 4.2. Число единиц в i-й строке матрицы AG равно числу

ребер, исходящих из i-й вершины. Между множеством всех графов n-го порядка и множеством всех матриц n-го порядка, состоящих из элементов 0 и 1, существует взаимно однозначное соответствие с точностью до изоморфизма.

Определение 4.3. Пусть G (V , R, f ) – ориентированный мульти-

граф,		V {a1 , a2 ,..., am }, R {u1 ,u2 ,...,un } . Матрицей инцидентности
мультиграфа G называется матрица BG размера m n вида
							b	b ...	b
							11	12	1n
						BG	b21	b22 ...	b2n , где
							... ... ...		...
								bm2 ...
							bm1		bmn
			1, если реброu j			исходит из вершины ai ;
		1, если реброu j				заходит в вершину ai
bij									и не является петлей;
			0, в противном случае.
i 1, m,			j 1, n .
								21

Определение 4.4. Матрицей инцидентности произвольного мультиграфа G называется матрица инцидентности соответствующего ему ориентированного мультиграфа Gор.

Пример 4.3. Составим матрицу инцидентности следующего мультиграфа G:

Решение:
	1		1	0	0	0	0
BG		1	1	1	1	1	1
		0	0	1	1	1	0
									.

Пример 4.4. Изобразим мультиграф G, имеющий следующую матрицу инцидентности

	1		0	1	0	1	0	0
		0	1	0	1	1	0	1
B		1 0		0	0	0	0	0
G
	0		1	0	0	0	1	0
		0	0	0	1	0	1	0
										.

Решение:

22

Определение 4.5. Пусть G (V , R)			–	граф,		V {a1 , a2 ,..., an } .
Матрицей Кирхгофа графа G называется матрица KG						n-го порядка вида
	k	k	...	k
	11	12		1n
KG	... ...		...	...	,
		kn2	...
	kn1			knn

где
						1,	если вершины ai		и a j	смежны,
				kij		0,	если вершины ai		и a j	не смежны,
								если i j,
						deg ai ,
i 1, n,			j 1, n .

Пример 4.5. Найдем матрицу Кирхгофа следующего графа G:

Решение:

23

	2		1	1	0
KG		1	3	1	1
		1	1	4	0
		0	1	0	1
							.

Пример 4.6. Граф G задан матрицей Кирхгофа KG . Изобразим G графически.

	3		1	1	1
KG		1	2	0	1 .
		1	0	1	0
		1	1	0	4

Решение:

4. Задание ориентированного графа с помощью списка дуг.

Пусть G (V , R) –

ориентированный граф, ui

(am

, an ) – i-е

i

i

)

m (m , m ,..., m

R

ребро графа G. Тогда

1

2

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

n

(n1,

n2 ,..., n

R

)

Пример 4.7. Зададим граф из примера 4.4 с помощью списка дуг. Решение:

m(1,2,1,5,1,4,2) ,

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

24

Пример 4.8. Изобразим граф 5-го порядка, заданный с помощью списка дуг m (1,2,2,1) , n (4,3,1,3) .

Решение:

5. Задание ориентированного графа с помощью структуры смежности. Если u (a,b) , то вершина b называется последователем верши-

ны a. Данный способ заключается в записи для каждой вершины списка ее последователей.

Пример 4.9. Зададим граф из примера 4.8 с помощью структуры смежности.

Решение:

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

a2 a1 , a3 ; a3 a1 ;

a4 нет; a5 нет.

Пример 4.10. Изобразим граф, имеющий следующую структуру смежности:

25

вершины – последователи

aa,b, c ;

bb, d ;

ca, e ;

de ;

ec, d, e .

Решение:

Представление графов в памяти ЭВМ

Известны различные способы представления графов в памяти компьютера, отличающиеся друг от друга объемом занимаемой памяти и скоростью выполнения операций над графами. Выбор наилучшего представления определяется требованиями конкретной задачи. Наиболее используемыми представлениями графов в памяти ЭВМ являются следующие:

представление матрицей смежности;

представление матрицей инцидентности;

представление структурой смежности;

представление списком дуг.

26

§ 5. Операции над графами

Содержание параграфа

бинарные операции над графами: пересечение, объединение, кольцевая сумма, соединение, произведение, композиция;

унарные операции над графами: удаление и добавление вершин и ребер, введение вершины в ребро, отождествление вершин, расщепление вершины, дополнение графа;

определение n-мерного куба.

Бинарные операции над графами

К основным бинарным операциям над графами относят следую-

щие:

1)пересечение графов,

2)объединение графов,

3)кольцевая сумма графов,

4)соединение графов,

5)произведение графов,

6)композиция графов.

Определение 5.1. Пусть		G1 (V1 , R1 )	и	G2 (V2 , R2 ) –	графы,
V1 V2	. Пересечением	графов G1	и	G2 называется	граф
G (V1	V2 , R1 R2 ) и обозначается: G G1		G2 .

Пример 5.1.

27

Определение 5.2.

1. Пусть G1 (V1 , R1 ) и G2 (V2 , R2 ) – графы. Объединением графов G1 и G2 называется граф G (V1 V2 , R1 R2 ) и обозначается:

GG1 G2 .

2.Объединение графов G1 (V1 , R1 ) и G2 (V2 , R2 ) называется дизъ-

юнктивным, если V1 V2 , и обозначается: G G1 G2 .

Пример 5.2.

Определение 5.3.		Пусть	G1 (V1 , R1 )		и G2 (V2 , R2 ) –	графы.
Кольцевой суммой		графов	G1	и	G2 называется	граф
G (V1 V2 , R1 R2 ) ,	где R1 R2 (R1			\ R2 ) (R2 \ R1 ) и обозначает-
ся: G G1 G2 .

Пример 5.3.

Определение 5.4. Пусть G1 (V1 , R1 )		и G2 (V2 , R2 ) – графы. Со-
единением	графов G1 и G2 называется	граф G (V1 V2 , R) , где
R R1 R2	{(a,b) | (a V1,b V2 ) или (a V2 ,b V1 ),a b} и обозна-

чается: G G1 G2 .

28

Пример 5.4.

Определение 5.5. Пусть	G1 (V1 , R1 ) и G2	(V2 , R2 ) – графы.
Произведением графов G1 и	G2 называется граф	G (V1 V2 , R) , где
R {((a1 ,b1 ),(a2 ,b2 )) | (a1 a2	и (b1 ,b2 ) R2 )	или (b1 b2 и
(a1 , a2 ) R1 )} и обозначается:	G G1 G2 .

Пример 5.5.

Определение 5.6. Пусть G1 (V1 , R1 )		и	G2 (V2 , R2 ) –	графы.
Композицией графов G1 и G2	называется	граф G (V1 V2 , R) , где
R {((a1 ,b1 ),(a2 ,b2 )) | (a1 , a2 ) R1	или ( a1 a2		и (b1 ,b2 ) R2 )}	и обо-
значается: G G1[G2 ] .

Пример 5.6.

29

Замечание 5.1. Граф G1 G2 получается из графа G1 G2			добавле-
нием всех	ребер ((a1,b1 ),(a2 ,b2 )) ,	удовлетворяющих	условию
(a1, a2 ) R1	(в примере 5.6 данные ребра	отмечены пунктирной линией).

Унарные операции над графами

Косновным унарным операциям над графами относят следующие:

1)операция удаления ребра,

2)операция добавления ребра,

3)операция удаления вершины,

4)операция добавления вершины,

5)операция введения вершины в ребро (операция подразделения ребра),

6)операция отождествления вершин,

7)операция расщепления вершины (стягивание ребра),

8)дополнение графа.

Определение 5.7. Пусть G (V , R) – граф и u (a,b) R . Говорят, что граф G1 получен из графа G с помощью операции удаления ребра u (или удалением ребра u), если G1 (V , R \{u}) , и обозначается:

G1 G u.

Пример 5.7.

30