Матрицы смежности и инцидентности. Изоморфизм.

Пусть D=(V,X) ориентированный граф, V={v1,...,vn}, X={x1,...,xm}.

Матрица смежности ориентированного графа D − квадратная матрица

A(D)=[aij] порядка n, где

Матрица инцидентности − матрица B(D)=[bij] порядка nm, где

Матрицей смежности неориентированного графа G=(V,X) называется квадратная симметричная матрица A(G)=[aij] порядка n, где

Матрица инцидентности графа G называется матрица B(G)=[bij] порядка nm, где

Графы G1(V1, X1) и G(V2, X2) называются изоморфными, если существует биекция f: V1→V2, такая, что выполнено:

При этом f называется изоморфизмом графов G1 и G2. Изоморфизм графа G на себя называется автоморфизмом.

Примеры решения типовых задач

Табл. 1

Табл. 2

Пример 1. Задать матрицами инцидентности и смежнос­ти, а также списком ребер графы G1, G3 см. рис. 8.

Матрицы инцидентности графов G1 и G3 приведены в табл. 1. В матрице инцидентности в каждом столбце толь­ко два элемента, отличных от 0 (или один, если ребро – петля). Список ребер является более компактным описанием графа. Матрицы смежности гра­фов G1, G3 даны в табл. 2

Табл. 3 Табл. 4

Пример 2. На рис.9 изображен сетевой граф (сетевая модель) выполнения комплекса операций (работ) некоторой программы. В нем стрелки обозначают операции, вершины - события, характеризу­ющие окончание од­них работ и начало других. Направлен­ность стрелок отража­ет последователь­ность наступления этих событий.

Задать сетевой граф различными способами:

Рис. 9

Изображенная сетевая модель представляет собой ори­ентированный граф, который может быть полностью задан различными способами:

1) графически (см. рис. 9);

2) с помощью задания двух множеств: V={1,2,3,4,5,6} и E={(1,2),(1,3),(2,4),(2,5),(3,4),(4,6),(5,6)};

3) матрицей инцидентности (см. табл. 3). Особенностью сетевой модели является то, что из начального события 1 стрелки только выходят, а в конечное 6 - только входят. Поэтому в первой строке матрицы инцидентности имеются единицы только со знаком "минус", а в последней - только со знаком "плюс";

4) матрицей смежности см. табл. 4. По причине, ука­занной в п. 3, в последней строке матрицы смежности про­ставлены только нули;

5) списком ребер сетевой граф задается очевидным обра­зом, поскольку ребра графа обозначены через свои конце­вые вершины. В таком случае в столбце "вершины" списка будут повторяться номера вершин, указанных в столбце "реб­ра", причем в той последовательности, в какой в данном слу­чае стрелки-ребра обозначены.

Упражнения

Рис. 10 (а, б, в, г)

Рис. 11 (а, б, в) Рис. 12

1. Задать графы G1-G5, изображенные на рис.6, матри­цами инцидентности и смежности, а также списком ребер.

2. Задать различными способами графы G1-G7, опреде­ленные ниже. Проверить справедливость правил переходов от одного способа задания гра­фа к другому:

1. G1 - тетраэдр;

2. G2 - тетраэдр с петлями во всех вершинах;

3. G3 - кy6;

4. G4 - граф, представленный на рис. 1.10, а;

5. G5-граф на рис. 1.10, б;

6. G6 -граф на рис. 1.10, в;

7. G7 - граф на рис. 1.10, г;

3. Представленные на рис.11 графы задать матрицами смежности. Определить, изоморфны ли эти графы.

4. Показать, что 2 графа на рис. 12 изоморфны.

5. Дан граф. Написать для него матрицы смежности и инцидентности.

6. Задать граф, состоящий из 8 ребер и 9 вершин, графически, списком ребер и вершин, а также с помощью матриц смежности и инцидентности.

7. Даны матрица смежности и инцидентности. Построить по ним граф.

Матрица смежности Матрица инцидентности

	a	b	c	d
a	0	1	1	0
b	1	0	1	0
c	1	1	0	1
d	0	0	1	0

	u	v	w	x
a	1	0	0	0
b	1	1	1	0
c	0	1	0	1
d	0	0	1	1

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

9. Проверить изоморфизм графов.

1)

2)

3)

10. Докажите, что полные (пустые) графы изоморфны тогда и только тогда, когда они имеют одинаковое количество вершин.

11. Найдите все попарно неизоморфные графы пятого порядка.

12. Какой многогранник двойственен тетраэдру? Какой додекаэдру? (двенадцатиграннику, рёбра которого являются правильными пятиугольниками)?