Содержание к диссертации
Введение
Глава 1. Анализ существующих методов и алгоритмов построения телекоммуникационных сетей минимальной стоимости 13
1.1 Описание алгоритмов построения сетей минимальной стоимости 13
1.1.1 Алгоритмы построения минимальных остовных деревьев 13
1.1.2 Алгоритмы построения деревьев Штейнера 15
1.1.3 Алгоритмы построения минимальных гамильтоновых контуров 17
1.1.4 Анализ предложенных алгоритмов 20
1.2 Алгоритмы определения маршрута трассы 22
1.2.1 Конструкторская трассировка 22
1.2.2 Строительная трассировка 24
1.2.3 Анализ алгоритмов трассировки 26
1.3 Анализ близких задач 28
Выводы по первой главе 30
Глава 2. Разработка математического аппарата соединения двух точек на взвешенной плоскости 32
2.1 Соединение точек, расположенных в соседних полуплоскостях с различной стоимостью прокладки 34
2.1.1 Решение уравнений третьей степени (метод Кардано) 36
2.1.2 Решение уравнений четвертой степени (метод Феррари)... 37
2.2 Соединение точек, расположенных в полуплоскости с высокой стоимостью прокладки 47
2.3 Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных произвольной кривой 52
2.4 Соединение точек, расположенных в удаленных областях взвешенной плоскости, границами которых являются параллельные прямые 59
2.5 Соединение точек, расположенных в удаленных областях взвешенной плоскости, границами которых являются две непараллельные прямые 62
2.6 Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных тремя прямыми, сходящимися в одной точке 66
2.7 Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных двумя прямыми, сходящимися в одной точке 70
Выводы по второй главе 72
Глава 3. Разработка алгоритмов соединения точек на взвешенной плоскости и объединение п точек в сеть заданной топологии 73
3.1 Разработка алгоритма соединения двух точек на взвешенной плоскости 73
3.1.1 Предварительный этап соединения двух точек на взвешенной плоскости 76
Вариант 1 77
Вариант 2 80
Вариант 3 84
3.1.2 Улучшение пути, соединяющего две точки на взвешенной плоскости 89
3.2 Разработка алгоритма объединения точек на взвешенной плоскости в сеть заданной топологии 95
3.3 Разработка алгоритма построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между
каждой парой узлов на взвешенной плоскости 100
Выводы по третьей главе 109
Глава 4. Экспериментальная проверка работы разработанных алгоритмов 110
4.1 Разработка автоматизированной системы построения сети заданной топологии на взвешенной плоскости 110
4.2 Описание вычислительного эксперимента 113
4.3 Анализ полученных результатов 115
Выводы по четвертой главе 129
Заключение 130
Библиографический список
- Алгоритмы построения минимальных гамильтоновых контуров
- Соединение точек, расположенных в полуплоскости с высокой стоимостью прокладки
- Предварительный этап соединения двух точек на взвешенной плоскости
- Описание вычислительного эксперимента
Введение к работе
В последние годы в Российской Федерации наблюдается развитие рынка информационных и телекоммуникационных услуг. Новые технологии активно внедряются в различные сферы жизни. В связи с этим важной становится проблема передачи данных. Однако существующая на данный момент инфраструктура сетей недостаточно развита, а линии связи (особенно в регионах) не удовлетворяют пользователей ни по качеству, ни по скорости передачи данных, в связи с чем возникает задача проектирования новых и модернизация существующих линий связи. Примером активно развивающихся сетей являются некоммерческие научно-образовательные сети, такие как RUNNet, RBnet, FREEnet, RELARN-IP, RUHEP-Radio-MSU, РОСКОНидр.
Стоимость прокладки линий связи между узлами телекоммуникационной сети, которая складывается из затрат на кабель и стоимости работ по его прокладке, по сравнению с общей стоимостью сети составляет до 70% [38]. Отсюда следует, что снижение затрат на строительство и проектирование линий связи хотя бы на один процент даст экономический эффект в миллионы рублей.
В существующих на данный момент алгоритмах построения сетей минимальной стоимости заданной топологии стоимость затрат на прокладку линий связи между узлами телекоммуникационной сети определяется либо экспертным путем, либо не учитывает неоднородность среды, по которой будет прокладываться трасса: предполагается, что стоимость прокладки единицы длины линии связи по всей территории является постоянной, что не соответствует действительности. Стоимость работ по прокладке сети зависит от выбора трассы прокладки [45,46], например, монтаж линии связи по болотистой местности существенно дороже, чем монтаж вдоль автомобильных трасс. Однако в некоторых случаях дешевле проложить короткий кабель по более «дорогой» местности, чем в обход по более «дешевой». Предварительное определение трасс до начала монтажных работ принесет значительную экономию финансовых средств.
Таким образом, актуальной становится проблема снижения затрат на прокладку линий связи между узлами телекоммуникационной сети с учетом неоднородности стоимости прокладки на разных участках трассы.
Цель работы
В процессе анализа темы диссертационной работы было выявлено, что решение задачи проектированием минимальных по стоимости телекоммуникационных сетей связано с минимизацией затрат на прокладку линий связи телекоммуникационных сетей. Поэтому целями диссертационной работы являются:
1) минимизация затрат на соединение узлов телекоммуникационной сети на взвешенной плоскости;
2) минимизация затрат на объединение узлов телекоммуникационной сети на взвешенной плоскости в сеть заданной топологии.
Основные задачи
В работе поставлены следующие основные задачи:
• исследование существующих способов определения трассы соединения узлов телекоммуникационной сети;
• исследование существующих методов построения минимальных топологий сети;
• разработка математического аппарата для соединения с минимальными затратами двух точек, расположенных в соседних областях взвешенной плоскости;
• определение предварительного направления трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости; • определение минимальной по стоимости трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;
• объединение точек на взвешенной плоскости в минимальную по стоимости сеть заданной топологии.
Методы исследования.
Для решения поставленных задач использован аппарат вычислительной геометрии, теории графов и математического анализа.
Научная новизна.
В диссертационной работе предлагается решение поставленных задач. Научная новизна состоит в следующем:
• сформулирована и решена задача определения минимума стоимости прокладки линии связи между двумя узлами телекоммуникационной сети, расположенными в соседних областях взвешенной плоскости;
• определено необходимое условие минимума стоимости прокладки линии связи между двумя узлами телекоммуникационной сети, расположенными в соседних областях взвешенной плоскости, разделенных произвольной кривой;
• предложены графовые модели для определения направления трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;
• предложен алгоритм определения минимальной по стоимости трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости;
• доказаны метрические свойства минимальной по стоимости трассы, соединяющей две точки, расположенные произвольно на взвешенной плоскости; • предложен алгоритм объединения точек на взвешенной плоскости в минимальную по стоимости сеть заданной топологии без вычисления стоимости прокладки линии связи между каждой парой исходных точек.
Достоверность.
Достоверность основных положений и полученных результатов диссертационной работы подтверждается математическими обоснованиями и доказательствами, результатами работы программы, реализующей предложенные алгоритмы.
Практическая ценность работы
Основным практическим результатом проведенных исследований стала разработка моделей и алгоритмов соединения точек, расположенных произвольно на взвешенной плоскости. Практическое применение разработанных моделей и алгоритмов показало снижение стоимости прокладки линий связи при построении телекоммуникационной сети 25-35%.
Результаты, полученные в диссертационной работе, внедрены и использованы при проектировании трасс линий связи между узлами телекоммуникационной сети в ОАО «Связьэлектромонтаж» (г.Мытищи, Московская обл.), ООО «Ремстроймост» (г. Рязань).
Апробация результатов диссертации
Результаты, полученные в ходе работы над диссертацией, докладывались на VI Международной школе-семинаре аспирантов, магистров и студентов «Современные информационные технологии», Минск, июнь 2003 г.; 9-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 21-23 апреля 2004 г.; 10-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 20-22 апреля 2005 г.; VIII Международной школе-семинаре аспирантов, магистров и студентов «Современные информационные технологии», Минск, июнь 2005 г.; 14-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 6-8 декабря 2005 г.; Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники "Информационно-телекоммуникационные системы", Москва, 14-16 декабря 2005г.; 39-й научно-технической конференции РГРТА, 30 января - 4 февраля 2006 г.; 11-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 19-21 апреля 2006 г.
Публикации
Основные результаты диссертации опубликованы в 11 работах.
Структура и объем диссертации
Диссертация состоит из введения, четырех глав, библиографического списка (90 источников), изложенных на 138 страницах (содержит 6 таблиц, 67 рисунков), и 2 приложений. Общий объем диссертации - 201 страница.
Алгоритмы построения минимальных гамильтоновых контуров
Изучение минимальных сетей Штейнера, т.е. решений знаменитой проблемы Штейнера или одномерной проблемы Плато, представляет собой активно развивающуюся область современной математики, стоящей на стыке дифференциальной и вычислительной геометрии, топологии, комбинаторики и вариационного исчисления [39].
Впервые интерес к подобной задаче возник задолго до Штейнера. В своем простейшем варианте задача была поставлена Ферма, а именно, он предложил найти на плоскости точку S, сумма расстояний от которой до трех фиксированных точек А, В и С наименьшая. Торричелли обнаружил следующее геометрическое решение. Построим на сторонах треугольника ABC правильные треугольники ABC, ВСА и CAB , каждый из которых пересекается с ABC лишь по соответствующей стороне. Опишем окружность вокруг каждого из этих трех правильных треугольников. Тогда эти три окружности пересекутся в одной точке, которая и является решением задачи Ферма. Эта точка часто называется точкой Торричелли. Кавальєри выяснил, что точка Торричелли обладает следующим важным свойством: углы между отрезками, соединяющими вершины треугольника ABC с точкой Торричелли, равны между собой и поэтому равны 120.
Общая задача, охватывающая произвольное количество точек, была предложена в 19 веке математиком Якобом Штейнером. Она носит название «Задача нахождения Евклидового дерева Штейнера», а оптимальные решения этой задачи называются минимальными деревьями Штейнера.
Существует точные и приближенные алгоритмы решения данной задачи.
Самыми первыми алгоритмами для решения общей задачи в графах являются алгоритм Хакими (Hakimi) [76], основанный на переборе всех стягивающих деревьев, и алгоритм динамического программирования Дрейфуса (Dreyfus) и Вагнера (Wagner) [89]. Более современные алгоритмы используют формулировки целочисленного программирования и решают задачу с помощью метода "расширяй и урезай" (brunch and cut) [80]. Еще один точный алгоритм построения на плоскости локально минимальной сети данного топологического типа с данной границей был предложен Мелзаком для случая деревьев [81]. Этот алгоритм за время, экспоненциально зависящее от числа граничных точек, или строил требуемое минимальное дерево, или получал ответ, что такого дерева не существует.
Однако, т.к. задача Штейнера является NP-сложной, время работы данных алгоритмов экспоненциально зависит от числа исходных точек, на которых строится минимальная сеть. Поэтому с увеличением числа граничных точек точные алгоритмы теряют свою эффективность. В связи с этим большое внимание уделяется второму подходу к решению данной проблемы, а именно, к созданию приближенных алгоритмов. К приближенным алгоритмам построения дерева Штейнера относятся алгоритм Вайнера-Зайцева-Лившица [8] и эвристический алгоритм, разработанный Псиолом [41,61].
Топология «дерево» является минимальной связывающей топологией, однако, она, в свою очередь, является и самой ненадежной [55]. Выведение из строя одного узла телекоммуникационной сети или одной линии связи ведет к разрыву сети, т.е. степень связности такой топологии 1.
В связи с этим возникает задача построения более надежной топологии телекоммуникационной сети. На языке теории графов минимальной сетью со степенью связности 2 («кольцо») является гамильтонов контур (рисунок 2.3) [3].
Решение задачи поиска гамильтонова контура минимальной длины на графе сводится к решению задачи о коммивояжере. Задача коммивояжера была поставлена в 1934 году и является одной из знаменитых задач теории комбинаторики [8,31].
Постановка задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,4,3..п и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Соединение точек, расположенных в полуплоскости с высокой стоимостью прокладки
Пусть некоторая часть плоскости U, ограниченная многоугольником, « разбита на области U,, / = 1,и, (У,псУу =0, если i j, и \Ju,=\J, причем эти 1=1 области выпуклые (рисунок 3.2). (0;100) (32; 100) (70; 100) Q21;100) (150; 100) (0;0) (14;0) (84;0) (121;0) (150;0) Рисунок 3.2 Разбиение плоскости на области Утверждение 3.1 (необходимое условие выпуклости областей). Необходимым условием выпуклости областей Ut (/ = 1, и) является аппроксимация границ областей прямыми линиями. Доказательство. Пусть границы между всеми областями Ut и U) заданы некоторыми произвольными функциями ftJ(x) (i,j = \,n). Рассмотрим границу f0(x) между двумя областями U, и С/;( рисунок 3.1) Ui \ Uj fij(x) Рисунок 3.1 Граница fu(x) между областями Ut и Uj Для обеспечения выпуклости области Ut необходимо, чтобы функция d2fy(x) /„(х) была выпуклой со стороны области U,, т.е. ——г— 0. Для обеспечения выпуклости области иj необходимо, чтобы функция fjj{x) d2ftj{x) была выпуклой со стороны области Un т.е. -г — 0. Условием выполнения этих двух утверждений является d2fe(x) =0 (ЗЛ) Найдем функцию ftJ{x), решив дифференциальное уравнение (3.1): W=o =» № - =, = с, =, dx2 J dx2 J dx x = j- j dx = jc.dx = ftj(x) = Cxx + C2 (3.2) где Cj и C2 - константы. Уравнение (3.2) является уравнением прямой. Утверждение 3.1 доказано.
Ограничение на выпуклость областей некритично, так как любую кривую можно аппроксимировать прямыми линиями (для выполнения необходимого условия выпуклости областей), а невыпуклую область, ограниченную отрезками, всегда можно разбить на несколько выпуклых, например, с помощью триангуляции Делоне [48] или какими-либо другими способами (рисунок 3.3).
Исходная плоскость взвешена, т.е. для каждой области U, поставлен в соответствие коэффициент ki 0, определяющий стоимость прокладки единицы длины линии связи внутри данной области. Две соседние области Ut и С/, имеют одно общее ребро Vv. Каждое ребро является границей двух областей. Соответственно любую область U,, / = 1,л можно определить списком ребер Vy, где j = {l,...,n} - номера соседних областей. Каждое ребро Vy можно задать парой точек Ру0і(хуух,уу01) и Pvij2(.xvij2 yvij2)i которые являются вершинами областей U, и U}. Необходимо соединить с минимальными затратами две точки Р,( ,, ,) и Р2(х2,у2), расположенные произвольно на плоскости U (рисунок 3.4). Если соединить точки Pt(х,,ух) и Р2(х2,у2) прямой линией, то с учетом весов областей стоимость пути (рисунок 3.4) составит Ьнеуд =1669.892. (0;100) (32; 100) (70; 100) (121;100) (150; 100) (0;0) (14;0) (84;0) (121;0) (150;0)
Предлагается следующий подход к решению данной задачи: находится предварительный, неоптимальный путь, соединяющий две исходные точки Рх(хх,ух) и Р2(х2,у2), затем этот путь улучшается. В связи с этим решение задачи нахождения минимального по стоимости пути, соединяющего две точки на взвешенной плоскости, предлагается разбить на два этапа:
1) определение списка ребер VtJ, которые пересекает путь (предварительный этап); Л Л Л 2) определение точек Pvij(xvij,yVij) на этих ребрах (этап улучшения)
Предварительный этап соединения двух точек на взвешенной плоскости На данном этапе определяются области U,, через которые ориентировочно будет прокладываться трасса, список ребер Vtji которые будет пересекать путь, и рассчитываются предварительные точки Pvij(xvij,yViJ) на этих ребрах. После проведенных исследований предлагается три графовые модели для решения задачи нахождения предварительного, неоптимального пути, соединяющего две исходные точки Р,(х„я) и Р2(х2,у2) на взвешенной плоскости [5,17,26,53,57,58].
Вариант 1 В данном случае строится неориентированный граф по следующим правилам: 1) каждой области U-, ставится в соответствие вершина графа Qt\ 2) каждому ребру Vv ставится в соответствие ребро графа .., соединяющего вершины Qt и Qj; 3) каждой вершине Qt приписывается вес s, 0, равный коэффициенту kt 0, определяющий стоимость прокладки единицы длины линии связи внутри области U,.
Предварительный этап соединения двух точек на взвешенной плоскости
На данном этапе производится поиск минимальной по стоимости трассы на взвешенной плоскости, путем улучшения неоптимального пути [20,21,33,47].
С математической точки зрения, данная задача формулируется следующим образом. На взвешенной плоскости U, разбитой на области /,., .» i = l,я с коэффициентами kt 0, определяющими стоимость прокладки единицы длины линии связи внутри области, заданы две точки Р,(дг,, ,) и Р2{х2,у2). Эти точки соединены неоптимальным путем, представляющим из себя ломаную кривую с опорными точками Р0(х0,у0),...,Pl(xi,yi) ,..., Рт(хт,ут), где Р,(х„у,) / = 1,«-1 - точки на ребрах Vtj, разделяющих области U, и Uj, т - количество опорных точек ломаной кривой. Вес пути определяется как сумма расстояний между опорными точками ломаной кривой, умноженных на коэффициент kVi 0, соответствующий области и{, по которой проходит данный участок пути т . L = 2Хл/С / - w)2 +( -.У,.,)2 (3.18) Необходимо уточнить координаты точек Р,(х„у,) / = 1,от-1 на ребрах Vv, чтобы вес итогового пути был минимальным. Решать данную задачу предлагается следующим алгоритмом. Шаг 1. Фиксировать координаты всех точек Р,(х„у,) і = 0,т Задать погрешность вычислений є, єтек = 0 . Шаг 2. 1 = 1.
ШагЗ. Уточнить координаты точки Р,(х„у,) соответственно с пп.2.1-6. На данном шаге возможно слияние (рисунок 3.14а) и разделения (рисунок 3.146) точек, при этом возможно изменение списка областей, через которые проходит трасса, полученного на этапе предварительного поиска пути.
В этих случаях необходимо уменьшить (для слияния) или увеличить (для разделения) на единицу значение т = т ± 1 и перенумеровать точки. Шаг 4. Вычислить насколько улучшилась стоимость прокладки пути еул. Если еул єтек, то єтек = єул. Шаг 5. / = / + 1. Шаг 6. Повторять шаги 3-5 пока і т . Шаг7. і-т. Шаг 8. Уточнить координаты точки P,{xt,y,) соответственно с пп.2.1-6 аналогично шагу 3. Шаг 9. Вычислить насколько улучшилась стоимость прокладки пути еул. Если еул єтек, то етек = еуя. Шаг 10. / = /-1. Шаг 11. Повторять шаги 8-10 пока / 0 . Шаг 12. Повторять шаги 2-11 пока етек є (рисунок 3.15). (0;100) (32;100) (70; 100) (121;100) (150;100) (0;0) (14;0) (84;0) (121;0) (150;0) Рисунок 3.15 Улучшенный путь Шаг 13. Вычислить длину пути L (3.18). Для примера, представленного на рисунке 3.15, стоимость пути составляет L = 1074.616. Шаг 14. Сохранить получившийся набор точек Pt(х,,у,) і = 0,т. Шаг 15. Поочередно просматриваются все области ип по которым проходит трасса. Определяется, граничат ли данные области Ut с непомеченными областями U} с меньшим коэффициентом стоимости прокладки единицы длины линии связи k, kj, через которые не проходит трасса. Если такие области существуют, перейти на шаг 16, иначе на шаг 21. Для примера, представленного на рисунке 3.15, такими областями являются области U1 и Ui0.
Шаг 16. В соответствии с п.2.2, в путь добавляются по две новые точки трассы на границе раздела областей U, и С/, (рисунок 3.16), определенной на шаге 14. т = т + 2. Перенумеровать точки.
Улучшенный путь, с учетом перехода в область U 93 Шаг 17. Новая трасса улучшается по шагам 1-12 (рисунок 3.17). Шаг 18. Вычисляется Lnepex (3.18). Для примера, представленного на рисунке 3.17, стоимость пути составляет Lnepex = 1274.399. Шаг 19. Если L Lnepex, то L = Lnepex, иначе восстановить набор точек pi ( / У і) і = 0,т, сохраненный на шаге 14. Шаг 20. Область Uj помечается. Переход на шаг 14. Шаг 21. Трасса определена уточненными точками Р.(Х..УЛ і = 0,т, с длиной пути L. Шаг 22. Конец алгоритма. Распишем более подробно шаг 3 алгоритма. Шаг 3.1. Пусть точка Pt(х„у,) принадлежит ребру V} Для уточнения точки P,(xt,y,) необходимо фиксировать точки /м(хм, ,-_,) и Рм(хм,ум). В соответствии с п.2.1 уточняется положение точки Р{(х,,у,) на ребре Vj. Если точка не выходит за границы ребра (рисунок 3.18а), то переход на шаг 3.5, иначе (рисунок 3.186) переход на шаг 3.2.
Описание вычислительного эксперимента
Для проведения эксперимента был выбран участок карты Рязанской области (рисунок 4.3а). После анализа карта была разбита на области с различной стоимостью прокладки единицы длины линии связи между узлами телекоммуникационной сети, выбраны 14 объектов на карте, которые необходимо соединить в сеть (рисунок 4.36). Проводимый эксперимент состоит из двух частей. В первой части определяется: 1) во сколько раз уменьшается стоимость прокладки между каждой парой точек на взвешенной плоскости; 2) во сколько раз увеличится длина кабеля, необходимого для соединения каждой пары узлов сети; 3) количество итераций, необходимых для уточнения трассы, соединяющей пару точек; 4) средние значения определяемых величин.
В проводимом эксперименте данные, полученные в результате работы предлагаемых алгоритмов, сравниваются с результатами соединения точек напрямую.
Во второй части проводимого эксперимента определяется: 1) сокращение стоимости прокладки линий связи между узлами телекоммуникационной сети заданной топологии; 2) увеличение расхода кабеля, необходимого для построения сети заданной топологии; 3) количество итераций, необходимых для построения сети заданной топологии, при использовании алгоритма построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости; 4) число трасс, рассчитываемых в алгоритме построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости.
Iter - количество итераций, необходимых для построения сети заданной топологии, при использовании алгоритма построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости;
Ntr - число трасс, рассчитываемых в алгоритме построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости.
При использовании алгоритма построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости для топологии «дерево» рассчитано 47,2% всех возможных трасс, для топологии «звезда» - 60,4%. Графики числа трасс, рассчитываемых на каждой итерации алгоритма построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости, представлены на рисунке 4.5.
Алгоритм построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости для топологии «кольцо» не применялся.
Результаты работы программы при построении топологий «дерево», «звезда» и «кольцо» представлены на рисунках 4.8-4.10.
Из рассмотренного примера следует, что использование алгоритма определения минимальной по стоимости трассы между узлами телекоммуникационной сети приводит к уменьшению стоимости прокладки линий связи и незначительному увеличению длин самих линий связи, а применение алгоритма построения телекоммуникационной сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости сокращает число рассчитываемых трасс в 2 раза.
