Матрица смежности
Матрица смежности- это двумерный массив размерности N*N.
Для неориентированного графа
A[i,j]=
Для неориентированного графа - это симметричная матрица с нулями на главной диагонали. Сумма цифр в любой строке или столбце равна степени соответствующей вершины.
Ниже представлена матрица смежности графа, изображенного на рисунке 13
Для ориентированных графов
1
,
существует дуга (i,j)
A[i,j]=
0, не существует дуги вида (i,j)
Для ориентированных графов матрица смежности не будет симметрична относительно главной диагонали. Для ориентированных мульти- и псевдографов A[i,j] равно количеству дуг, соединяющих вершину i с вершиной j.
На рисунке 14 изображен ориентированный мульти-псевдограф и его матрица смежности
Матрица инциденций
Матрица инциденций отражает инцидентность вершин и ребер.
Для неориентированных графов
1, вершина с номеромiинцидентна ребру с номеромj,
A[i,j]=
0, вершина с номером iне инцидентна ребру с номеромj.
На рисунке 15 изображен простой граф и его матрица инцидентности.
Для ориентированных графов
1, вершина с номеромiинцидентна ребру с номеромjи является его концом,
A[i,j]= 0, вершина с номеромiне инцидентна ребру с номеромj,
-1 вершина с номером iинцидентна ребру с номеромjи является его началом.
На рисунке 16 изображен орграф и его матрица инцидентности.
-
1
2
3
4
5
6
7
8
1
-1
0
0
0
1
0
1
1
2
1
1
0
0
0
1
0
0
3
0
-1
1
0
0
0
0
-1
4
0
0
-1
1
0
0
-1
0
5
0
0
0
-1
-1
-1
0
0
Перечень ребер
Для хранения перечня ребер используют двумерный массив размерности |Е| х 2, каждая строка которого описывает ребро графа.
Для графа, изображенного на рисунке 15 перечень ребер имеет вид:
-
1
2
3
4
1
2
1
1
2
3
4
5
5
5
4
3
Изоморфизм графов.
Определение. Два графаизоморфны, если существует взаимно однозначное соответствие между их вершинами, обладающее тем свойством, что две вершины соединены ребром в одном графе тогда и только тогда, когда они соединены ребром в другом.
На рисунке 17 изображены изоморфные графы.
Достижимость и связность
Определение. Маршрут – это последовательность ребер (дуг) графа, в которой конец каждого ребра (дуги) совпадает с началом следующего ребра.
Определение. Число ребер маршрута называется егодлиной.
Определение. Цикломназывается замкнутый маршрут.
Например, в графе, изображенном на рисунке 18, вершины v5 и v3соединены маршрутами(е6, е2) длины 2; (е5, е1, е2) длины 3. Маршрут(е5, е1, е2, е3, е4)является циклом.
Определение. Если существует маршрут из вершины графа v в вершину u, то говорят, чтоu достижима из v.