Для представления графа может использоваться
Для представления графа может использоваться Булева функция S(x,y), для которой S(i,j)=1 тогда и только тогда, когда (i,j)О E. S(i,j) обозначает ребро графа, соединяющее узлы i и j. Одной из возможностей реализации s является использование матрицы смежности А графа g. А - двухмерная матрица.
Для описания графа с помощью матрицы смежности A(i,j), где (i,j)О E, необходимо пронумеровать узлы графа. Элементы матрицы могут принимать значения 0 или 1. Так как представленный на рисунке граф не имеет ребер исходящих и завершающихся в одном и том же узле (нет петель), диагональные элементы матрицы равны нулю. Единицы присутствуют в позициях, которые соответствуют парам узлов, соединенных ребрами, например, 1-3, 1-4 или 5-2 и 5-3. Число ребер, исходящих из вершины (петля учитывается дважды), называется
степенью вершины d(v). В конечном графе число вершин с нечетной степенью всегда четно.
Другой способ представления графа обеспечивает функция, которая выдает списки узлов, с которыми данный узел связан непосредственно. Для графа, отображенного на рис. 10.21.4, такое описание можно представить в виде структуры (таблица 10.21.1). В колонке s представлены номера узлов, далее в строке таблицы следует список соседних узлов. По этой причине число колонок в каждой из строк различно.

Рис. 10.21.4
Таблица 10.21.1.
S |
Список "соседних" узлов |
1 |
2 |
5 |
6 |
|
2 |
1 |
3 |
|
|
3 |
2 |
4 |
5 |
|
4 |
3 |
|
|
|
5 |
1 |
3 |
6 |
7 |
6 |
1 |
5 |
7 |
|
7 |
5 |
6 |
|
|
Нули и единицы в матрице смежности могут быть заменены целыми числами, характеризующими путь из точки i в точку j (например, метрика маршрута телекоммуникационной сети). Такая матрица называется
матрицей оценки. Граф называется
обыкновенным, если он не содержит петель и параллельных ребер.
Граф называется
полным, если любые две вершины являются смежными.
Если для всех вершин d(v) = k, то граф называется
однородным графом степени k или k-однородным. Граф на рис. 10.21.5 является полным и 3-однородным.
Содержание Назад Вперед