Телекоммуникационные технологии
Конечная последовательность ребер графа e1,
Рис. 10.21.5.
Конечная последовательность ребер графа e1, e2,…,en называется маршрутом длины n. Маршрут называется замкнутым, если вершины начала и конца маршрута совпадают. Если ребра, образующие маршрут различны, то такой маршрут называется цепью.
Граф называется деревом, если он связан и не имеет циклов. Граф является деревом тогда и только тогда, когда каждая пара различных вершин соединяется одной и только одной цепью. Каждое дерево с 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.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий