Оптимизационные методы синтеза графовых структур топологий телекоммуникационных сетей

А.П. Самойленко, О.А. Усенко

ОПТИМИЗАЦИОННЫЕ МЕТОДЫ СИНТЕЗА

ГРАФОВЫХ СТРУКТУР ТОПОЛОГИЙ 

ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное

учреждение высшего профессионального образования

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Инженерно-технологическая академия

А.П. Самойленко, О.А. Усенко

ОПТИМИЗАЦИОННЫЕ МЕТОДЫ СИНТЕЗА

ГРАФОВЫХ СТРУКТУР ТОПОЛОГИЙ 

ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ

Учебное пособие

Таганрог 2016

УДК 519.17: 621.39 (075.8)
ББК 22.176Я73

С 73

Печатается по решению редакционно-издательского

совета Южного Федерального университета

Рецензенты:

доктор 
технических 
наук, 
профессор, 
зав. 
кафедрой 

прикладной 
математики 
и 
информационных 
технологий 

Таганрогского института управления и экономики Карелин В.П.;

доктор технических наук, профессор, профессор кафедры

систем автоматического управления Института 

радиотехнических систем и управления Гайдук А.Р.

Самойленко, А.П.

С173   Оптимизационные методы синтеза графовых структур 

топологий 
телекоммуникационных 
систем
: 
учебное 

пособие
/
Самойленко А.П., Усенко О.А.
; Южный 

Федеральный университет.
– Таганрог
: Издательство

Южного федерального университета, 2016. – 241 с.

ISBN 978-5-9275-2089-3

Изложены основные понятия, определения и терминология 

теории графов, необходимые для анализа и синтеза топологий 
радиотехнических и телекоммуникационных сетей. В пособии 
представлены 
алгоритмы 
оптимизации 
путей 
передачи 

информации 
и 
пропускной 
способности. 
Все 
разделы 

сопровождаются практическими примерами решения задач, а 
также вопросы для самостоятельного решения.

Пособие предназначено для бакалавров, специалистов и 

магистрантов направления 210406 «Сети связи и системы 
коммутации», 210601 «Радиоэлектронные системы и комплексы», а 
также для аспирантов, работающих в области проектирования и 
анализа 
структур 
информационно-вычислительных 

телекоммуникационных систем.

ISBN 978-5-9275-2089-3
УДК 519.17: 621.39 (075.8)
ББК 22.176Я73

© Южный федеральный университет, 2016
© Самойленко А.П., Усенко О.А., 2016

СОДЕРЖАНИЕ

Введение…………………………………………………………………...5
1. Основные понятия и определения………………………………….....9

1.1. Понятие графа……………………………………………………...9
1.2. Способы задания графов…………………………………………25
1.3. Виды и свойства графов…………………………………………38
Задачи для самостоятельного решения……………………………...65

2. Операции над графами………………………………………………..73

2.1. Унарные операции над графами………………………………...73
2.2. Бинарные операции над графами………………………………..79
Задачи для самостоятельного решения……………………………...89

3. Достижимость и связность графов…………………………………..93

3.1. Сильная и слабая связность. Компоненты связности……….....93
3.2. Эйлеровы цепи и циклы………………………………………...104
3.3. Гамильтоновы цепи и циклы…………………………………...114
Задачи для самостоятельного решения…………………………….121

4. Метрические характеристики графов……………………................128

4.1. Понятие расстояния в графе……………………………………128
4.2. Числовые характеристики графов……………………………..136
4.3. Числовые характеристики некоторых графов
специального вида…………………………………………………...154
Задачи для самостоятельного решения…………………………….156

5. Прикладные алгоритмы оптимизации графовых моделей
при оценке эффективности топологий телекоммуникационных
систем…………………………………………………………………...160

5.1. Представление топологий телекоммуникационных
сетей в виде графовых структур……………………………………160
5.2. Алгоритм Дейкстры для нахождения путей
минимального и максимального веса………………………………167
5.3. Метод динамического программирования для
оптимизации путей передачи информации……..…………………178
5.4. Оптимизация путей передачи информации матричным
методом…………………………………………..…………………..185

5.5. Определение экстремальных путей в базисе
квазиминоров………………………………………………………...194
5.6. Определение пропускной способности
телекоммуникационных сетей……………………………………...202
5.7. Проектирование топологий телекоммуникационных
сетей на основе решения задачи Штейнера……………..…………215
Задачи для самостоятельного решения…………………………….221

Заключение……………………………………………………………...227
Библиографический список……………………………………………228

Введение

Какие же цели преследует преподавание дискретной математики 

в техническом вузе? Что Вы должны знать и уметь после изучения 
этой дисциплины, включающей, в том числе, раздел по прикладной 
теории графов? Лейтмотив всего учебного пособия – формирование у 
студента объектно-логического мышления.

Когда студент не знает, как ответить на вопрос преподавателя, 

ему обычно говорят: «Подумайте хорошенько...». При этом, очевидно, 
предполагается, что студент умеет, но просто не хочет подумать и что 
стоит его к этому побудить специальным призывом, но как из 
незнания родится знание? Как показывает наш опыт, многие 
студенты, т.е. бывшие школьники просто не умеют думать и 
рассуждать. И не потому, что они ленивы или чего-то не знают, а 
потому что их не научили думать.

Различают четыре уровня знаний: I – знание-знакомства; II –

знания-копии; III – знания-умения; IV – знания-трансформа-ции 
(творческое созидание).

К сожалению, лекции, лабораторные практикумы обычно 

формируют знания-знакомства и помогают в пересказе этих знаний на 
занятиях или на экзамене. Но такие знания трудно превратить в 
умения 
создавать 
модели 
для 
количественного 
исследования 

проблемно-ориентированных объектов. Поэтому так велико значение 
различных форм практических занятий, значение самостоятельной 
работы обучающихся.

Данное учебное пособие рассчитано на обучение на третьем

уровне, отсюда и некоторые его особенности. Разумеется, у авторов
нет средств заставить Вас прилежно выполнить все задания. Но, 
поверьте, учиться творчески гораздо интереснее, чем методом 
«зубрежки».

Формирование 
правильного 
умения 
требует 
постоянных 

упражнений, поэтому в учебном пособии приведены алгоритмы 
решения задач, что может рассматриваться как специальный тренинг 
на дому. Хорошо известно, что одним из лучших способов усвоения 

разделов 
математики 
является 
решение 
циклов 
задач 
без 

преподавателя. В то же время мы не хотим навязывать предлагаемое 
решение и будем рады, если читатель нашел и альтернативный 
вариант. Нам вообще кажется, что чрезмерно легкое обучение вредно. 
Говорят, что царь Птоломей I спросил у своего учителя математики 
Эвклида: «Нет ли легкого способа изучить геометрию?» И Эвклид 
ответил: «Нет царских путей к геометрии!». Итак, помните, Ваша 
задача заключается в том, чтобы понять приемы и способы решения 
задач в прикладной теории графов.

Теория 
графов 
является 
одним 
из 
разделов 
дискретной 

математики, который исследует свойства конечных или счетных 
множеств с заданными отношениями между их элементами.

Графы 
являются 
неотъемлемым 
исследовательским 

инструментарием при создании математических моделей в самых 
разнообразных областях науки и практики. Они позволяют наглядно 
представить взаимоотношения между событиями или элементами и 
объектами, структуру и свойства сложных систем. Благодаря 
наглядности графовых структур многие алгоритмические задачи 
дискретной математики стремятся сформулировать как задачи на 
графах, например задачи, в которых требуется выяснить какие-либо 
особенности 
устройства 
графа, 
или 
найти 
в 
графе 
часть, 

удовлетворяющую некоторым требованиям, или построить граф с 
заданными свойствами.

Возникнув при решении головоломок и игр, таких, как задача о 

кенигсбергских мостах и игра Гамильтона, теория графов в настоящее 
время является мощным и наглядным средством для исследования и 
решения многих практических задач, возникающих при изучении 
больших и сложных систем различной природы. Действительно, если 
рассматривать современные телекоммуникационные системы и сети 
только в виде совокупности их технических характеристик, то сделать 
выводы 
о 
ее 
эффективности, 
потенциальной 
расширяемости, 

возможностях и средствах оптимизации будет достаточно сложно, а 
иногда просто невозможно для недостаточно подготовленного 

специалиста. Использование же теории графов, когда узлы или 
абоненты представляются в виде вершин, а коммуникации – в виде 
дуг графа, позволяет во многом упростить анализ таких сложных 
систем, а знание специальных характеристик графов, как будет 
показано в учебном пособии, позволяет количественно объективно 
оценивать показатели качества телекоммуникационных систем.

Исторически теория графов возникла как наука о задачах в 

геометрических конфигурациях, состоящих из точек и линий, однако 
в отличие от геометрии, где важны размеры и точное расположение 
элементов изображения, в теории графов основной предмет 
исследования составляет структура, порядок соединения, отношения 
между элементами, блоками и подсистемами. Именно поэтому в 
задачах теории графов не существенно, соединены ли вершины
прямыми линиями или криволинейными дугами, какова длина дуги
или 
ребра, 
а 
также 
другие 
геометрические 
характеристики 

конфигурации. Благодаря определенной абстрактности граф можно 
изображать в разном масштабе, при разных поворотах (и в этом 
случае возникает далеко нетривиальная задача об установлении 
изоморфности двух графов).
Однако графы можно успешно 

использовать и для решения обычных геометрических задач, приняв 
соответствующие ограничения и естественную интерпретацию.

Хорошо известно, что основы теории графов были заложены 

Эйлером при решении задачи о семи кенигсбергских мостах (XVIII
век) [3, 6, 7, 16], суть этой по фактически занимательной задачи 
сводилась к следующему: при прогулке необходимо было обойти семь 
мостов, расположенных так, как это показано на рис. В.1, и вернуться 
к месту, откуда начиналась прогулка. При этом должно выполняться 
существенное ограничение – по каждому мосту можно пройти не 
более одного раза.

Рис. В.1

Решение задачи о кенигсбергских мостах было дано Эйлером.
Современная теория графов даёт исключительно удобный 

аппарат для моделирования структурных свойств различных систем и 
отношений между объектами разной природы. Поэтому она широко 
используется как в самой математике, так и ее приложениях в самых 
разнообразных областях науки, техники и практической деятельности 
[16]. Графы встречаются во многих областях под разными 
названиями: «структуры» в гражданском строительстве, «сети» в 
электротехнике, 
«социограммы» 
в 
социологии 
и 
экономике, 

«молекулярные 
структуры» 
в 
химии, 
«дорожные 
карты», 

электрические или газовые «распределительные сети» и так далее. 
Область применения теории графов может считаться не просто очень 
обширной, 
а 
практически 
повсеместной: 
проектирование,

исследование 
и 
оптимизация 
телекоммуникационных
сетей 
и 

инфокоммуникаций, 
исследование 
потоков 
сигналов, 
анализ 

электрических цепей и печатных схем, задачи календарного 
планирования для минимизации временных затрат, блок-схемы при 
алгоритмировании задач, исследование автоматов, анализ и синтез 
логических цепей, теория информации, методы наилучшего поиска
информации, стратегии инвестиций в экономике, анализ качества
технических средств, исследование движения транспорта и решение 
логистических задач, экономические задачи, доказательство теорем в 
математическом анализе, теория игр и др. Теория графов успешно 
применяется и в таких областях, которые традиционно не считаются 
математизированными и строго формализованными – исследование 

поведения индивидуума, головоломки, тайнопись, генетика, биология 
и многое другое.

Типовыми задачами в теории графов являются [3-9]:
1) задача определения связности;
2) задача укладки;
3) экстремальные задачи;
4) потоки в сетях;
5) матрицы и матроиды;
6) транспортные задачи;
7) задачи о раскраске;
8) задачи о покрывающих множествах;
9) задача коммивояжера;
10) задача о размещении центров и др.
В практике проектирования телекоммуникационных систем 

перечисленные задачи чаще встречаются не по отдельности, а 
комплексно, 
поскольку, 
например, 
распределение 
потоков 

информации влияет на размещение центров обслуживания, что, в 
свою очередь, связано с решением задачи определения кратчайших 
путей и т.д.

Цель 
данного 
учебного 
пособия 
–
дать 
необходимые 

теоретические сведения и практические примеры решения задач на 
графах. Пособие содержит минимум понятий, необходимый для того, 
чтобы можно было начать какую-либо содержательную работу с 
графами или приступить к более глубокому изучению теории графов. 
Подробно разобранные примеры решений формируют практические 
навыки 
работы 
с 
графовыми 
структурами. 
Каждый 
раздел 

сопровождается набором задач для самостоятельного решения, что 
должно способствовать закреплению полученных знаний и навыков, 
выявлению некоторых особых случаев.

1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

1.1. Понятие графа

Для описания строения различных систем, состоящих из 

связанных между собой элементов, часто используют графические 
схемы, изображая элементы точками (кружками, прямоугольниками и 
т.д.), а связи между ними – линиями или стрелками, соединяющими 
элементы
[9]. 
Вершинами 
графа 
могут 
быть 
узлы 
любой 

транспортной,
электрической
или телекоммуникационной сети, 

абоненты, терминальное оборудование или команды операционной 
системы, события в любой сфере человеческой деятельности, а 
рёбрами или дугами –
линии связи в транспортной или в 

электрической сети, в организации работы на компьютере или в 
любой сфере человеческой деятельности. При этом получаются 
диаграммы вроде тех, что показаны на рис. 1.1.

А
В
С

D
E
F

A

B

C
F

E

D

а
б

Рис. 1.1

Приведенные примеры изображения графов, естественно, можно 

дополнить 
другими 
разновидностями, 
при 
этом 
ни 
способ 

изображения вершин, ни форма или длина соединений не имеют 
значения, однако принципиальным является, какие именно пары 
элементов соединены линиями. Например, с этой точки зрения графы, 
приведенные на рис. 1.1,а, б изображают одну и ту же структуру 
связей между элементами A, B, C, D, E, F. Чтобы это было более 
очевидно, опишем эти графы в виде пар вершин, соединенных