Способы задания графов
Граф с кратными дугами и без петель называется мультиграфом. Граф на рис.3.1 является мультиграфом. Ориентированный мультиграф соответственно имеет параллельные дуги, но не имеет петель.
Любой граф или орграф можно задать матрицей смежности.
|
у которой элемент aij
= k, если вершина i и
j соединены k дугами,
иначе aij = 0.
В табл.3.1 и 3.2 приведены матрицы смежности графа рис.3.1 и орграфа рис.3.2 соответственно.
Таблица 3.1
|
0 |
2 |
1 |
0 |
|
|
2 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0
Таблица 3.2
|
0 |
1 |
0 |
||
|
1 |
0 |
0 |
||
|
1 |
1 |
Можно заметить, что для неорграфа (неориентированного графа) матрица смежности симметрична. Если в графе (орграфе) нет петель, то в матрице смежности по главной диагонали стоят нулевые элементы.
Граф (орграф) можно задать матрицей инцидентности.
Определение. Матрицей
инцидентности графа, имеющего n вершин
и m дуг, называется матрица B
у которой элемент bij =
1, если вершина vi инцидентна
дуге xj, т.е. соединена дугой xj с другой вершиной
графа. Иначе bij = 0.
Для орграфа элемент матрицы инцидентности bij = - 1, если из вершины vi выходит дуга xj, и bij = 1, если в вершину vi заходит дуга xj. Элемент bij = 0, если вершина vi не инцидентна дуге xj. Элемент bij = ±, где ±- число петель в вершине vj.
предыдущаяследующая