Протоколы Internet


Элементы теории графов - часть 4


Граф называется деревом, если он связан и не имеет циклов. Граф является деревом тогда и только тогда, когда каждая пара различных вершин соединяется одной и только одной цепью. Каждое дерево с n вершинами имеет ровно n-1 ребро. Удаление любого ребра в дереве делает его несвязным. По этой причине дерево можно считать минимальным связным графом. Если все вершины графа G принадлежат дереву Т, то считается, что дерево покрывает граф G.

Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Лес из k деревьев, содержащий n вершин имеет в точности n-k ребер.

Пусть G=(v,e) связный граф и FМ E подмножество его ребер. При этом F называется разделяющим подмножеством тогда и только тогда, когда подграф G’=(V, E-F) несвязан. E-F обозначает множество ребер, которое принадлежит Е, но не принадлежит F.

Если узлы графа могут быть соединены несколькими путями, сеть, описываемая таким графом, обладает повышенной надежностью. Рассмотрим задачу выбора оптимального дерева маршрутов, лишенного циклов, в такой сети (см. рис. 10.21.6). Алгоритм используется в схеме “расширяющееся дерево” для локальных сетей со сложной топологией. Алгоритм преобразует многосвязный граф в плоский без замкнутых структур.

Рис. 10.21.6.

В качестве начального выбираем узел 1. Матрица оценки формируется поэтапно (А-E). На этапе А выбирается узел 5, так как к нему ведет ребро с метрикой 1. Здесь становятся доступными ребра, ведущие к узлам 2, 4, 6 и 7. Ребро 1-5 из рассмотрения устраняется. На следующем этапе выбирается узел 7, к нему от узла 5 ведет ребро с метрикой 1. Здесь в рассмотрение включаются ребра 7-4 и 7-8. Следующим выбранным узлом становится 4 и включается в перечень ребро 4-2. Далее рассматривается узел 6 и ребра 6-8 и 6-3.

В результате граф приобретает вид, показанный на рисунке 10.21.7.

Рис. 10.21.7.

Рассмотренный алгоритм сходен с алгоритмом Дикстры, используемым для поиска наилучшего пути во внутреннем протоколе маршрутизации ospf.

Выбранный метод аналитического представления графа достаточно прост, но требует для графа с N узлами N2 ячеек памяти (бит). Впрочем, для неориентированного графа матрица является симметричной и для ее хранения в памяти ЭВМ достаточно N(N-1)/2 ячеек. Это справедливо и для ориентированных графов без петель.

Петлей

называется ребро графа, которое начинается и завершается в одном и том же узле (рис. 10.21.8).

Рис. 10.21.8.

Справедливо следующее утверждение. Узлы i,j соединены путем длиной k тогда и только тогда, когда Ak(i,j)=1.

Надо сказать, что графы являются весьма удобным средством описания и оптимизации алгоритмов вычисления. В качестве примера рассмотрим вычисление квадратного полинома ax2+bx+c по схеме Горнера (рис. 10.21.9).

Рис. 10.21.9. Граф вычисления квадратного полинома по схеме Горнера.




Начало  Назад  Вперед



Книжный магазин