Способы задания графов
В табл.3.3 и 3.4 приведены матрицы инцидентности для графов рис.3.1 и 3.2.
Таблица 3.3
|
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
0 |
0 |
Таблица 3.4
|
-1 |
1 |
0 |
0 |
1 |
1 |
|
1 |
-1 |
1 |
0 |
0 |
0 |
|
0 |
0 |
-1 |
1 |
-1 |
-1 |
Можно отметить, что в каждом столбце матрицы инцидентности есть только два элемента отличных от нуля. Кроме того, если в столбце матрицы инцидентности находится только одна 1, а остальные элементы равны нулю, то это означает, что в данной вершине графа есть петля.
Граф можно задать списком дуг в каждой строке которого записывается дуга и две вершины инцидентные этой дуге. В орграфе дуга будет инцидентна вершине, если данная вершина является началом или концом этой дуги. Для неориентированных графов порядок перечисления вершин произволен. Для орграфа вначале записывается вершина являющаяся началом дуги. В табл.3.5 приведен список дуг для орграфа рис.3.2.
Таблица 3.5
|
Дуги |
Вершины |
|
x1 |
v1, v2 |
|
x2 |
v2, v1 |
|
x3 |
v3, v2 |
|
x4 |
v3, v3 |
|
x5 |
v3, v1 |
|
x6 |
v3, v1 |
Из способов задания графов видно, что граф однозначно определяется через множество своих вершин и множество дуг. Поэтому граф часто обозначают так: G(X,V) , где X- множество дуг графа, а V – множество его вершин.
Граф называется конечным, если X и V- конечные множества.
предыдущаяследующая