Введение
Глава 1. Критерий математического ожидания числа несвязных пар узлов. Постановка задачи и предварительные сведения 11
1.1. Моделирование сетей связи и исследование их нг.дежностей . 11
1.1.1. Показатели надежности и общие подходы к их расчёту . 11
1.1.2. Оптимизация структур сетей по критериям надёжности . 12
1.1.3. Критерий максимума вероятности связности 13
1.1.4. Критерий вероятности передачи потока заданной величины13
1.1.5. Критерий EDP 13
1.2. Основные определения и формулы 14
1.3. Способы вычисления EDP-функционала 16
1.3.1. Методы полного перебора 16
1.3.2. Метод ветвления 16
1.4. Полиномы надежности 18
1.5. Полиномы надежности для вероятности связности 19
1.6. Формулы для расчета EDP 19
1.6.1. EDP-полином двухвершинного графа 19
1.6.2. EDP-полином трехвершинного графа 20
1.6.3. Формула для моста 20
1.6.4. Удаление висячей вершины 20
1.6.5. Ветвление по цепи длины 2 21
1.6.6. Формула для EDP-полинома графа в случае наличия в нем точки сочленения 22
1.6.7. Формула для EDP-полинома графа, представляющего собой два несвязных блока 22
1.7. Предварительные утверждения 22
1.8. Пример различия результатов оптимизации по критериям вероятности связности и EDP 24
1.9. Формулы полиномов надежности для распространенных сетевых топологий 26
1.9.1. Полином надежности для цепи 26
1.9.2. EDP-полином для звезды 26
1.9.3. EDP-полином для цикла 26
1.10. Полиномы надежности известных графов в случае наличия ограничения на диаметр 26
1.10.1. Полином надежности для звезды в случае наличия ограничения на диаметр 27
1.10.2. Полином надежности для цепи в случае наличия ограничения на диаметр 27
1.10.3. Полином надежности для цикла в случае наличия ограничения на диаметр 28
1.11. Результаты и выводы к Главе 1 29
Глава 2. Теоретическая оптимизация сетевых топологий по критерию EDP 30
2.1. Вспомогательные утверждения 30
2.2. Добавление ребра в распространенные сетевые топологии . 32
2.2.1. Добавление ребра в звезду 32
2.2.2. Добавление ребра к цепи 34
2.2.3. Добавление ребра в цикл 37
2.2.4. Сравнение оптимального добавления ребра но критериям EDP и вероятности связности 41
2.3. Оптимальное расположение особых вершин отличного веса . 42
2.3.1. Цепь с особой вершиной 42
2.3.2. Звезда с одной особой вершиной 42
2.3.3.
2.3.4. Особая вершина в графе-восьмерке 53
2.4. Оптимальное по критерию EDP присоединение структур 56
2.4.1. Присоединение звезды 56
2.4.2. Присоединение цепи 58
2.4.3. Присоединение графа-восьмерки 61
2.4.4. Сравнение результатов оптимального присоединения графов по критерию EDP с результатами оптимального присоединения этих графов по критерию максимума вероятности связности 63
2.4.5. Оптимальное соединение циклов 63
2.5. Результаты и выводы к Главе 2 65
Глава 3. Программные алгоритмы и их реализация 66
3.1. Реализация подсчета коэффициентов обычного полинома надежности 67
3.1.1. Замечания о программной реализации подсчета коэффициентов обычного полинома надежности 68
3.2. Особенности программной реализации подсчета коэффициентов полинома надежности графа в условиях наличия ограничения на диаметр 71
3.3. Числениые эксперименты 73
3.3.1. Ускорение расчетов в случае обычного подсчета коэффициентов полиномов надежности 73
3.3.2. Тестирование теоретических результатов из главы 2 75
3.3.3. Оптимизация сетевых топологий по критерию EDP с помощью точного расчета полиномов надежности 85
3.4. Результаты и выводы к Главе 3 88
Заключение 89
Литература 91
