В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 107
Текст из файла (страница 107)
Граф К., называемый полным графом, состоит нз и вершин, каждая пз которых напрямую соединяется ребрами со всеми остальными вершинами графа. Выведите формулу для вычисления количества ребер в графе К.. 2. Рассмотрим графемножеством вершин И=(а, Ь, с,!),е Я и Е=((а, Ь),(а с)) (Ь, с), (Ь, е), (с, е),(с,7), (а. е),(е, Я. а) начертите этот граф; б) найдите все пути от вершины а до вершины Ь; в) чему равна длина кратчайшего пути от вершины а до вершины 7? 466 Глава 14. Теория графов и поиск путей с минимальной стоимостью 14.4.
Задания 469 3. Найдите все связующие деревья для следующего графа: 4. Ребро графа 6 входит во все связующие деревья графа 6. Что можно ск зать об этом ребре? 5, Докажите правильность алгоритма поиска в ширину. То есть покажите, чп) этот алгоритм создает связующее дерево с корнем в вершине Рк 6. Напишите алгоритм поиска в ширину, проверяющий связность графа. 7, В стиле рис. 14.5 проиллюстрируйте выполнение алгоритма поиска в ширину на примере графа, представленного на рис.
14,8. )тв (гв Уч Рис. 14.8. Граф для задания 7 8. Алгоритм Дейкстры для поиска пути с минимальной стоимостью от вершины з может быть выражен в видо показанной ниже программы. В этой программе вначале каждой вершине присваивается временная метка. Когда алтттритм находит окончательный путь к вершине, ей присваивается постоянная метка, равная стоимости пути от вершины к Напишите подобную программу для алгоритма Беллмана — Форда. Подсказка: алгоритм Беллмана-Форда часто называется алгоритмом коррекции меток, в отличие от метода установки меток Дейкстры. Гог и:= 1 Со И бо Ьедтп [[и) нм -: Г)пв1[п]:= Гв1зе; (все вершины вреиенно поиечаются ) ргеб[п]:= 1 епб: [[з] := 0: [1па1[з] :- сгые; (вершина з временно помечается О) гесепг := з; (последняя временно помеченная вершине — зто з) рз(Ь := сгые: (инициализация закончена) ш(П1е Г(пз1[1] = Га1зе бо Ьед! и Гог [и] =1 Со И бо (найти новую иетку) 11 (н[гесеюг, и]< ) йшб (Мб( Г)па1[п)) Впеп 9 10 11 (цикл по всеи еше не поиеченнии вершинзи.
непосредственно следусшии зв вершиной гесепЦ Ьед1п (обновить вреиенные метки) пет)аое1; = [[гесепт] + н[гесепю и]: 11 пен1вЬе1 <[[и] Спел Ьедьз [[п) .= пен1аЬе1: ргеб[п];= гесепс епб (если существует более короткий путь через вершину гесегс, поиетить ворвину п заново. и пометить вершину гесегт как предшествующую вершние п на кратчайшем гути от веошины з) епсд сеяр гог х; = 1 то и бо (найти вершину с наименьшей временной меткой) 1Г (ЧЛ Г1па1[х]) АИ0 Гс(х) < Севд) Спел Ьед1п у:= х: Селр:= [[х] епд; 1Г Севр < гйеп (путь существует) Сйеп Ьед1п Г!па1[у] := сгое: гесепт ; = у епб (врененно понечается вершина у.
следующая блишвйшдя вершина к вершине з) е1ве Ьед1п рвсн := Гз1зе: Гтпв1[С] := Сгые епб епб При обсуждении алгоритма Дейкстры утверждалось, что на каждой итерации к множеству Тдобавляется новая вершина и что путь с наименьшей стоимостью проходит только через вершины, уже принадлежащие множеству Т. Докажите справедливость этого утверждения. Подсказка: начните с начала. Покажите, что первая вершина, добавленная к множеству Т, должна быть связана с вершиной-истт)яником напрямую. Затем покажите, что вторая добавленная к множеству Твершнна должна быть связана напрямую либо с вершиной-источником, либо с вершиной, уже добавленной к множеству Т, и т.
д. Помните, что все стоимости линий являются неотрицательными величинами. При обсуждении алгоритлта Беллмана — Форда утверждалось, что на итерации, при которой й = К, если определяется путь длиной в К + 1 ребер, тогда первые К ребер этого пути образуют путь, уже определенный на предыдущей итерации. Докажите справедливость этого утверждения. На шаге 3 алгоритма Дейкстры значения путей с наименьшей стоимостью обновляются только для вершин, еще не принадлежащих множеству Т. Возможно ли, что может быть найден путь с меньшей стоимостью к вершине, уже принадлежащей множеству Т? Если да, покажите зто на примере.
Если нег, докажите невозможность такого события. 12. С помощью алгоритма Дейкстры создайте путь с минимальной стоимостью ко всем остальным вершинам от вершин со 2-й по 6-ю на рис. 14.2. Оформи те результаты в таблице аналогично табл. 14.2. 13. Повторите задачу 12, используя алгоритм Беллмана — Форда и оформив результаты в таблице аналогично табл. 14.3.
14. Примените алгоритм выбора маршрута Дейкстры к графам, представленным на рис. 14.9. Изображенные на рисунке веса ребер одинаковы в обоих направлениях. Сформируйте таблицу, аналогичную табл. 14.2, и рисунок, аналогичный рис. 14.6. Рио. 14.9. Граф для задании 14 Барбара Вайа (Рут Реноелл). Коеср Нара Сплочена 470 Гнева 14. Теория графов н поиск путей с минимальной стоимостью 15. Повторите задачу 14, используя алгоритм Беллмана — Форда, оформив результаты в таблице, аналогичной табл.
14.3, и в виде рисунка, аналогичною рис. 14.7. 1б. Всегда ли алгоритмы Дейкстры и Беллмана — Форда приводят к одинаковым результатам7 Почему да или почему нет? 17. Как алгоритм Дейкстры, так и алгоритм Беллмана — с11орда находят пути с наименьшей стоимосп ю от одной вершины ко всем остальным вершинам.
Алгоритм Флойда — Уоршзлла (Р[оус[ — ЖагзЬа[]) находит путно наименьшей стоимостью между всеми парами вершин графа. Ввелем обозначения: е Ф вЂ” множество вершин сети; тн(т, у) — стоимость линии от вершины т до вершины), причем тр(1, 1) = О или тр(т, )) =, если две вершины не соединены напрямую; 7.„(т,)) — стоимость пути с минимальной стоимостью от вершины т до вершины) при условии, что путь может проходить только по вершинам 1„2,...,п. Алгоритм состоит из следуюп1их шагов: 1. Инициализация: 1е(т',))=та(т',)) для всех с,у,т'Ф). 2. Для и = О, 1, ..., Ф вЂ” 1 7 ее(О)) = ийп [з'.„(г, )), Ц(г, н + 1) + 7 (и + 1,))] для всех т, ), т Ф ).
Объясните работу етого алгоритма. Используйте метод математической ин лукции для доказательства его работоспособности. Глава 15 Протоколы внутренней маршрутизации Она изучала схему напротив, так как знала, что а определенной точке ей придется пересесть на лруюй поюд. Такой точкой должна была быть станпия Тотепхзы Корт Роуд, пересечение черной линии с красной. Поезд обязательно дос санит ее туда, он и сейчас быстро несет сс туда, а на станина она будет следозать ухазат елям па Сентрал Лайн, потону что там должны быть указатели. Протоколы маршрутизации представляют собой существенную составную часть механизмов обеспечения деятельности объединенных сетей.
В основе работы объединенных сетей лежат маршрутизаторы, переправляющие друг другу 1Р-дейтаграммы по пути от хоста-источника к хосту-приелпшку. Для выполнения своих функций маршрутизатор должен обладать представлением о топологии объединенной сети и способностью выбирать оптимальные маршруты. Назначение протокола маршрутизации заключается в предоставлении необходимой информации. Мы начнем зту главу с обсуждения основных принципов маршрутизации в объединенных сетях, включая вопросы маршрутизации в высокоскоростных сетях.
Затем мы рассмотрим два важных протокола маршрутизации, ИР и ОБРЕ олицетворяющие два разных подхода к сбору информации о маршрутах. 15.1. Принципы маршрутизации в объединенных сетях Маршрутизация представляегсобой один из наиболее сложных и критически важ- ных аспектов разработки объединенных сетей. Этот раздел начинается с обсужде- ния механизма маршрутизации.
Затем мы рассмотрим обшую архитектуру марш- рутизации в объединенных сетях. 4г2 Глава 1б. Протоколы внутренней маршрутизации Функция маршрутизации Маршрутизаторы в объединенной сети выполняют почти ту же самую ф амую функцию, что и узлы комгяутации пакетов в сети с коммутацией пакетов. Так же ггаг жекакузелко гмутации пакетов ответственен за получение и дальнейшую пересылку и ылку пакетов по сети с коммутацией пакетов, маршрутизатор отвечает за получение и и не и пересылку 1Р-дейтаграмм через объединенную сеть. Для этого лгаршрутизаторам объединен ной сети нужно принимать решения о выборе маршрутов, основываясь ваясь на знании топологии и состояния объединенной сети.
Как упоминалось в главе 1ч, решения о выборе маршрутов принимаются на основе некоторого критерия минимальной стоимости. Еслгг этот критер " итерий заключается в минимизации количества ретрансляционных участков, тогда к , тогда каждому ретрансляционному участку (ребру графа) назначается вес, равный единице Чаще каждому ретрансляционному участку в соответствие ставится определенная величина, называемая стоимостью. Стоимость может быть обратно проне ропорциональна пропускной способности линии, прямо пропорциональна текущей нагр щей нагрузке на линию или представлять собой какую-либо комбинацию подобных и ых параметров. При расчете стоимости могут учитываться также такие критерии, как финансовая стоимость использования ретрансляционного участка.
В любом случае, подобного рода стоимостные критерии являются входными данными для алгоритма поиска пути с минимальной стоимостью. Два таких алгоритма описывались в главе 14. Фиксированная маршрутизация В простои конфигурации сети возможно использование фиксированной схемы маршрутизации, в которой для каждой пары узлов определяется постоянный ма- рут.
и маршруты являются фиксированными, поскольку изменяются только при изменении гопологии сети. Таким образом, аначения стоимости линий при прокладке маршрутов не могут основываться на каких-либо динамических перелгенных, таких как объем трафика. Однако для их вычисления могут использовкгься оценки объемов графика между различными парами узлов илн пропускная способность каждой линии, Р ассмотрим конфигурацию, представленную на рис. 15,1 и состоящую из пяти сетей и восьми маршрутизаторов. Каждой выходной линии маршрутизапэра поставлена в соответствие ее стоимость. При фиксированной схеме маршрупгзации у эта стоимость может отражать ожидаемую нагрузку на линию межд данным ма- р шрутизатором и данной сетью.
На рис. 15.2 показан пример реализации схемы фиксированной маршрутизации. Кахсдый маршрутизатор хранит таблицу, в которой есть запись для каждой сети конфигурации. Хранить в таблице записи для каждого возможного хоста-получателя нет необходимскти. Для маршрутизации достаточно хранить сведения о сетях. Когда 1Р-дейтаграмма достигает маршрутизатора, соединенного с сетью получателя, этот маршрутизатор может доставить пентаграмму соответствующему хосту-получателю в этой сети, К счастью, 1Р- -адрес, как правило, состоит из двух частей: номера сети и номера хоста (см. рис.
З.З в главе 3), так что номер сети получателя можно без труда извлечь из 1Р-дейтаграммы. ( 15.1. Принципы маршрутизации в объединенных сетях 473 Хост У Рнс. 1 б.1. КонФигурация мергиругнзагорсе и сетей Таблица маршрутизаторе А Таблице маршрутизатора 0 Сеть Маршрутизатор Сеть МаГгарутизагср Табяида МаРШРУтхзатаРа Е тег и„марш ре н Сеть Маршругнэегср Сеть Маршрутизатор Таблица хоста Х Таблице маршрутизаторе р Сеэь Маршругнэетср Сеть Маршрутизатор Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
