Телекоммуникационные технологии


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



В результате граф приобретает вид, показанный на рисунке 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. Граф вычисления квадратного полинома по схеме Горнера.


Previous:

   UP:

    Next:




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



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