Введение
1. Методы расчета характеристик связности случайного графа 13
1.1. Определения и обозначения 15
1.1.1. Понятие случайного графа 15
1.2. Характеристики случайных графов 17
1.3. Метод ветвления и его модификация 23
1.4. Использование покрывающих деревьев при точном вычислении надежности графа 31
1.5. Редукция цепей 33
1.6. Расчет коэффициентов полинома связности 35
1.7. Приближенные методы вычисления вероятности связности графа 36
1.8. Выводы 39
2. Оптимизация структур сетей по критерию максимума вероятности связности 41
2.1. Оптимально-связные структуры сетей 41
2.2. Оптимальная достройка кольцевых структур 44
2.3. Оптимальное соединение кольцевых структур 48
2.3.1. Пересечение циклов 48
2.3.2. Соединение двух циклов 49
2.4. Оптимальное циклическое соединение циклов 53
2.5. Выводы 73
3. Программная реализация алгоритмов 75
3.1. Поиск цепи 75
3.2. Перенумерация вершин разрешающей цепи 76
3.2.1. Реализация перенумерации 77
3.3. Реализация расширенной формулы Мура-Шеннона . 79
3.3.1. Варианты результатов стягивания и удаления . 80
3.3.2. Оконечные рассчитываемые варианты графов . 82
3.4. Реализация редукции цепей 84
3.5. Реализация метода Чена-Ли 85
3.6. Реализация расчета коэффициентов полинома связности . 86
3.6.1. Оконечные состояния при расчете полинома связности 86
3.6.2. Ветвление по мультиребру 87
3.6.3. Использование ветвления по цепям 87
3.6.4. Учет "прикрепленных деревьев" 88
3.6.5. Учет "прикрепленных циклов" 88
3.7. Выводы 88
4. Экспериментальное исследование алгоритмов 89
4.1. Формула Мура-Шеннона 89
4.1.1. Классический вариант ветвления по ребрам . 90
4.1.2. Расширенная Формула Мура-Шеннона . 91
4.1.3. Применение последовательно-параллельной редукции 93
4.1.4. Метод Чена-Ли 96
4.2. Расчет и использование полинома связности .:... 97
4.2.1. Зависимость вероятности связности от типа графа 99
4.3. Выводы 105
Заключение 106
Литература 108
