Пусть 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) и G2(V2, X2) называются изоморфными, если существует биекция f: V1→V2, такая, что выполнено:
При этом f называется изоморфизмом графов G1 и G2. Изоморфизм графа G на себя называется автоморфизмом.
Примеры решения типовых задач
Пример 1. Задать матрицами инцидентности и смежности, а также списком ребер графы G1, G3см. рис. 8.
Матрицы инцидентности графов G1 и G3 приведены в табл. 1. В матрице инцидентности в каждом столбце только два элемента, отличных от 0 (или один, если ребро – петля). Список ребер является более компактным описанием графа. Матрицы смежности графов G1, G3 даны в табл. 2.
G1
a
b
c
d
e
f
g
G3
a
b
c
d
e
f
g
-1
-1
-1
-1
-1
-1
Табл. 1
G1
G3
Табл. 2
Пример 2. На рис.9 изображен сетевой граф (сетевая модель) выполнения комплекса операций (работ) некоторой программы. В нем стрелки обозначают операции, вершины - события, характеризующие окончание одних работ и начало других. Направленность стрелок отражает последовательность наступления этих событий.Задать сетевой граф различными способами.
Рис. 9
Табл. 3
(1,2)
(1,3)
(2,4)
(2,5)
(3,4)
(4,6)
5,6)
-1
-1
-1
-1
-1
-1
-1
Табл. 4
Изображенная сетевая модель представляет собой ориентированный граф, который может быть полностью задан различными способами:
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 - граф, представленный на рис. 10, а;
5) G5 - граф на рис. 10, б;
6) G6 - граф на рис. 10, в;
7) G7 - граф на рис. 10, г;
3. Представленные на рис.11 графы задать матрицами смежности. Определить, изоморфны ли эти графы.
4. Показать, что 2 графа на рис. 12 изоморфны.
5. Дан граф. Написать для него матрицы смежности и инцидентности.
6. Задать граф, состоящий из 8 ребер и 9 вершин, графически, списком ребер и вершин, а также с помощью матриц смежности и инцидентности.
7. Даны матрица смежности и инцидентности. Построить по ним граф.
Матрица смежности
a
b
c
d
a
b
c
d
Матрица инцидентности
u
v
w
x
a
b
c
d
8. Написать для данного графа матрицы смежности и инцидентности, задать его списком ребер и вершин.
9. Проверить изоморфизм графов
1)
2)
3)
10. Докажите, что полные (пустые) графы изоморфны тогда и только тогда, когда они имеют одинаковое количество вершин.
11. Найдите все попарно неизоморфные графы пятого порядка (без изолированных вершин).
12. Какой многогранник двойственен тетраэдру? Какой додекаэдру (двенадцатиграннику, рёбра которого являются правильными пятиугольниками)?
Двудольные графы.
Граф G называется стягиваемым к графу H, если H получается из G в результате некоторой последовательности стягивания ребер.
Граф называется двудольным графом, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям. Если при этом любые две вершины, принадлежащие разным частям долям смежные, то граф называется полным двудольным.
Рис. 10 (а, б, в, г)
Рис. 11 (а, б, в)
Рис. 12
