В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 103
Текст из файла (страница 103)
В главе 15 исследуются два 1 иОРР, наиболее важных протокола внутренней маршрутизации: й Р и 3 + Глава 16. Протоколы внешней маршрутизации и групповая рассылка. В то время как маршрутиза шрутизаторы внутри одной автономной системы, пользующиеся протоколом внутренней. ней маршрутизации, должны обмениваться подробной информациеи о топологии с логии сети и состоянии графика в автономной системе, протоколы внешней маршрутизации, используемые между автономными систелшмп, в основном мен ва обмениваются меньшими объемами данных об общих ш ах ме сетями и автономными системами.
В главе 16 исследуются два п отокола внешней маршрутизации: ВОР и 1ОКР, — р , — а также ассматриваются вопросы групповой рассылки и применения протоколов маршрутизации при групповой рассылке. 14.1. Элементарные понятия теории графов 453 Глава 14 Теория графов и поиск путей с минимальной стоимостью Карта лондонской подземки, развспзснная но всех вагонах, была своего рсла молелью, произведением искусства. Она представляла сеть подземных туннелей в виде геометрической сетки.
Линии мет1ю, конечно, н о,нсрасполагаются друг к другу под прямыми углами. как улицы Манхэттена Оннтакже не расходятся пслострымнугламн н пе образуют прямоугояьцнков. Барбора Войн (Руи Венделя). Колер поря Соланона Компьютерные сети, как правило, представляются в виде г фо е графов, при этом коммутаторы и маршрутизаторы сетей являются узлами графа, а линии связи представляют собой ребра графа. Ряд понятий из теории графов оказывшотся полезными при разработке сетей и алгоритмов маршрутизации. Эта глава начинается со знака со знакомства с некоторыми элементарными концепциями из тео ии афов. Зат р граг1 в.
Затем мы рассмотрим два алгоритма поиска кратчайшего пути и протоколы марнтрутизации в обьединенных сет Вп а ях. протоколах маршрутизации, обсуждающихся в главах 15 и 16, для выбора маршрутов используются алгоритмы, описываемые в данной главе. Однако для понимания работы этих протоколов маршрутизации исчерпывающее знание алгоритмов поиска кратчайшего пути не требуется, Соответственно, при первом знакомстве с книгой читатель мажет просто просмотреть эту главу или вообще ее пропустить. 14.1. Элементарные понятия теории графов р ф '(, Е) остоит из объектов двух типов: вершин (уегг!сез), или узлов(пас!ез), и ребер (ес16ен), или связей (1из!сз), при атолл каждое ребро графа определяется как неупорядоченная пара вершин.
Таким образам, ребра ()гь 1*з) представляет собой то >ке самое, что и ребро (1гх, г'1). При изображении графов вершины представляются точками нли кружками, а ребра — линиями, соединяющими вершины, Например, на рис. 14,1, а множество вершин 1' — это ( Уь 1гз, Уз, 1гь Уз, $га), а множество ребер Š— зто 1((гь 1гз), (1гь 1гз) (1'ь )га), ((гт, 1з), (Рг, 1га), (Ъзь 1~а) (Уз 1гз), (11з, Ре), (1гь 1'з), (1гэ, )гэ)1. Вершины з иг из множества вершин 1г назывшотсн сллелсньглги (аг))асеп1), если ребро (т, у) принадлежит множеству ребер Е При этолт ребро (т,у) называется инцидентным (!пса!епс) вершинам т иу. тг! тга тгз те Чь ге 0 1 1 1 0 0 1 О 1 1 О 0 1 1 0 1 1 1 1 1 1 0 1 0 0 0 1 1 О 1 О 0 1 0 1 О Рис.
14.1. Граф с матрицвй смвжности Величина графа характеризуется количеством вершин!)г1 называемым порядком (огс)ег) графа С, а число ребер 1Е) называется размером (мхе) графа С. Время работы алпзритма, обрабатывающего граф, зависит, главным образом, от этих двух параметров. У представленного на рисунке зрафа ! $~! = 6, а 1Е! = 1О. Граф также часто представляется в вила магприцы сиежнасгпгг (ас))асепсу тпагпх). Вершины нумеруются произвольным образом от 1 до!1 "1 Затем матртща смежности А = (ал) размерности!)г! х 1Ц определяется следующим образом: ~1, если (г, 7)н Е, '(6 в протипном случае. На рис. 14.1, б приведен пример лгатрицы смежности.
Обратите внимание нато, что эта матрица является симметричной относительно диагонали, проходящей от левого верхнего до правого нижнего угла. Это объясняется тем, что ребра графа определены как неупорядоченные пары. Два ребра, инцидентные одной и той же паре вершин, называются нараътельными (раш11е1).
Ребро, инцидентнае всего одной вершине, называется петлей (1оор). Граф, в котором отсутствуют петли и параллельные ребра, называется нростылг графом (знпр1е ясар)т). Пухнем (рагЬ) от вершины г до вершины! называется такая последовательность вершин и ребер, начинающаяся с верппшы г и заканчивающаяся вершиной у, в которой каждое ребро является ннцидентным двум вершинам, соседним с ннм в втой последовательности. Путь называется просты,н (зппр!е рат)з), если в последовательности кюкдое ребро и каждая вершина присутствуют только однажды.
В простом графе путь может быть определен как последователыюсть вершин, в которой каждая вершина является смежной с предыдугцей и следуюп1ей вершинами в последовательности и ни одна из веригин нс повторяется. 464 Глава 14. Теория графов и поиск путей с минимальной стоимостью 14,1. Элементарные понятия теоРии графов 465 Ниже перечислены пути от вергпины У, до вершины Уб (см. рис. 14.1); К, )г, Уз, У У» Уб~ У1, Уг, Уз Уз 16 21 Уг И! 16 1'» Уъ $'4, 1'з, 1'ь 1'ь' 11, 12, 14 1» 16 Гь Уъ Уг, Уб, Уь Уб' Уг Уз! Уб 1 5 1 б Уь Уз, 1'б, Уа Уб 12! 15 15 16 Уг, 14, Уг 1'з, Кь' 1!» Уб, 1'з, 1!5 Уб Уг, 1о Уз К.' 1 ь 14, Уз Уб.
Из этих 14 путей путь 1» Иь 1 б является самым коротким, так как он состоит всего из двух ребер. В общем случае рассгиояние (с)15(апсе) между двумя всршинамн равно минимальному количеству ребер во всех путях, соединя кгщнх эти верпшны. Циквон (сус1е), или замкнутым маршрутом, называют путь, начинающийся н заканчивающийся в одной и той же вершине. Например, У» Уз, Уб, 141 представляет собой цикл графа, показанного на рнс. 14.1. Наконец, граф называется свлэнваи (соппес1ес1 ягарЬ), если существует путь между двумя любыми его вершинами.
Ориентированный граф и взвешенный граф Орпеягви)гованггьш цгсгф (с(!ясар)г) С(У, Е) состоит из множества вершин Ун множества ребер Е, при этом каждое ребро определяется как упорядоченная пара вершин. Вершины ориентированных графов также обозначаются точками нли кружками, а ребра — стрелками, соединяк!щимн вершины, Как правило, в ориентированных графах допускается наличие параллельных ребер при условии, что параллельные ребра ориентированы в противоположном направлении. Такие ориентированные графы хорошо подходят для представления компьютерных сетей, в которых каждое ребро обозначает поток данных в одном направлении между узламн сети.
Для описания ориентированного графа также может использоваться матрица смежности, но в данном случае эта матрица уже не будет симметричной, если только каждая пара смежных вершин не соединена парой параллельных бер. ре звешенным гуга40олг (узе)я)ггес1 ягар!1) н гкгвегленнылг ориентнггованнььи гра1210 и (гуегй)пес1 с(1йгар)г) называется такой граф, в котором каждому ребру поставлено в соответствие некоторое число. Пример взвешенного ориентированного графа показан на рис. 14.2, 41.
Матрица смежности А = (ау) определяется для такого графа следукнцим образом (14.2, б): ' Эготв Этот взвешенный арвевгиравзв1в,1Й граф часто исаальзуегсл для иллкктрваии злгоритиав иаршрутиззвии. Впервые ав был оаубликоввв в 12001. /ге„, если (г, г)н Е, '1 0 в противном случае. Здесь кгз представляет собой вес, поставленный в соответствие ребру (г, !), Ьб Уг Уз Рио.
14.2. Взвешенный ориентированный граф с мвтрицей смежности Во взвешенном графе (обычном илн ориентированном) длиной (1епф)г) пути называется сумма весов всех ребер пути. В табл. 14.1 показаны длины путей между вершинами У! и Уб в графе, представленном на рис. 14.2, а также соответствующие этим путям расстояния. Обратите внимание на то, что путь с кратчайшим расстоянием, то есть с минимальным количеством ребер (Гь Гв 14), не совпадает с кратчайшим путем, то есть с путем с наименьшим весом (Га Уб, Уз, 1'6). Таблица 14.1. Расстояния н длины путей от К до 14 в графе на рис. 14.2 Путь Раоотоеиие Длина 10 10 Ч! У2 Уз К 1'6 Уб У!. 14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
