Протоколы Internet


           

О E, необходимо пронумеровать узлы


Для описания графа с помощью матрицы смежности 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-однородным.



Рис. 10.21.5.

Конечная последовательность ребер графа e1, e2,…,en называется маршрутом длины n. Маршрут называется замкнутым, если вершины начала и конца маршрута совпадают. Если ребра, образующие маршрут различны, то такой маршрут называется цепью.


Содержание  Назад  Вперед





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий