Содержание к диссертации
Введение
Глава 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
- Показатели надежности и общие подходы к их расчёту
- Формула для EDP-полинома графа, представляющего собой два несвязных блока
- Сравнение оптимального добавления ребра но критериям EDP и вероятности связности
- Замечания о программной реализации подсчета коэффициентов обычного полинома надежности
Введение к работе
Анализ на надежность - важная часть проектирования и модернизации инфокоммупикационных сетей. Существует много критериев надежности сетей. Обычно выбор критерия надежности осуществляется исходя из особенностей конкретной сети и ее назначения. Связность сети, максимальная пропускная способность, время восстановления работоспособности и многие другие характеристики сети могут быть выбраны в качестве показателей надежности. Например, в случае передачи аудио и видео сообщений, биржевых сводок, 1Р-телефонии наиболее критичным оказывается время задержки доставки сообщений. Для сетей мониторинга в опасных производствах, например, в шахтах, важно, чтобы информация на обрабатывающий компьютер поступала от всех датчиков, поэтому необходима максимальная вероятность связности сети. Для сетей абонентского доступа важно максимизировать вероятность установления соединения между произвольно выбранными абонентами и т.д. Для многих систем передачи данных, используемых в военных или финансовых нуждах, в сфере гражданской обороны и для ликвидации чрезвычайных ситуаций, в обслуживании ракетно-космических войск и т.д. требуется повышенная надежность. Это оправдано тем, что нарушения работы такой системы могут повлечь большой экономический ущерб или даже гибель людей. Поэтому требуется исследовать различные критерии сетевой надежности, способы расчета соответствующих показателей и разрабатывать инструментарии для оптимального проектирования инфокоммуникационных сетей согласно выбранному критерию надежности. Эти инструментарии должны включать в себя как программные комплексы для быстрого расчета функционалов надежности, так и каталоги уже проверенных на оптимальность решений для различных сетевых топологий.
Исследованиями различных критериев надежности инфокоммуникационных сетей занимались и занимаются многие ученые. Из отечественных исследователей следует, прежде всего, отметить Артамонова Г.Т., Вишневского В.М., Дудника Б.Я., Егунова М.М., Епихина В.В., Кауля C.B., Кель- манса А.К., Литвака В.И., Ломоносова М.В., Майнагатлева С.М., Нече- пуренко М.И., Мухопада Ю.Ф, Полесского В.П., Попкова В.К, Родионова A.C., Скоробогатова В.А., Толчана А.Я, Харкевича А.Д. Среди зарубежных исследователей это Ball M.О., Colbourn C.J., Koide Т., Moore E.F., Page L.B., Palmer C.R., Perry J.E., Provan J.С., Satyanarayana A., Shannon C.E., Shooman A.M., Van Slyke R., Wood R.K.
Данная диссертационная работа посвящена исследованию такого критерия надежности сети, как минимум числа несвязных пар узлов. Этот критерий может использоваться как критерий надежности в сетях связи, некоторые элементы которых могут выходить из строя в результате естественных причин (изнашивание оборудования, воздействие погодных условий, стихийные бедствия) или намеренного разрушения. Он, очевидно, довольно хорошо отражает последствия для сети после выхода из строя ее элементов: чем больше несвязных пар узлов появилось, тем значительней разрушение сети. Таким образом, используя этот критерий, можно искать критические точки (узлы и линии связи) сети, выход из строя которых влечет за собой значительное ухудшение функционирования сети. Такой показатель надежности, как число несвязных пар узлов сети характеризует качество связи с точки зрения абонента, т.к. показывает его степень уверенности в соединении с другим произвольным абонентом.
Если элементы сети выходят из строя с некоторой вероятностью, то становится возможным оценивать математическое ожидание числа несвязных пар узлов сети (EDP, от англ. Expectation of the number of disconnected pairs of nodes). Далее критерий минимума математического ожидания числа несвязных пар вершин будем называть критерием минимума EDP или просто EDP-критерием. Задача точного расчета математического ожидания числа несвязных пар узлов сети довольно нова. В то время, как этот критерий надежности сетей давно известен [12, 32, 36, 50], ранее этот показатель вычислялся только приближенными методами, в основном методом
Монте-Карло [12], в связи с NP-трудностью задачи [52]. Использование приближенных методов обуславливалось, прежде всего, тем, что вычислительные мощности имеющейся техники не позволяли вычислять точные значения функционалов надежности для реальных сетей связи. В настоящее время произошло значительное увеличение возможностей вычислительной техники и поэтому стало возможным использовать точные методы вычисления для сетей реальных размерностей (десятки узлов). Точные методы расчета этого функционала надежности необходимы также для проверки качества приближенных методов расчета. Одни из первых работ о точном вычислении математического ожидания числа несвязных пар узлов - это работы Родионова A.C. и Родионовой O.K. [52, 54, 55]. Программное обеспечение по приближённой оптимизации методом Монте-Карло структур сетей связи с использованием EDP-критерия разработано М.М. Егуновым и используется в ГОУ ВПО СибГУТИ [12].
В диссертационной работе рассматривается выбор оптимальных сетевых топологий согласно критерию минимума математического ожидания числа несвязных пар узлов, в случае, когда узлы сети (пользовательские терминалы, маршрутизаторы и другое сетевое оборудование) абсолютно надежны, а линии связи равно ненадежны и выходят из строя независимо друг от друга с вероятностью р. Такая постановка задачи моделирует ситуацию проектирования новой сети, в случае, если надежность узлов сети предполагается много большей, чем надежность ее линий связи, а линии связи однотипны и находятся в одинаковых условиях. В этом случае EDP- функционал представляет собой полином. Целью данной диссертационной работы является разработка и программная реализация алгоритмов для расчета коэффициентов EDP-полиномов и создание библиотеки программ на основе этих алгоритмов. Также в работе рассматриваются некоторые задачи выбора оптимальной сетевой топологии по критерию минимума EDP, в частности задача об оптимальном добавлении элемента (новой линии связи) в некоторые распространенные сетевые топологии и оптимальном соединении топологий, а также оптимальном размещении особого узла. Приводятся программные алгоритмы для точного расчета EDP-полиномов, в том числе в случае наличия ограничений на диаметр сети. Обсуждается выбор оптимальных сетевых топологий, основываясь на полученных полиномах, приведены результаты численных экспериментов, подтверждающих полученные теоретические результаты. Показано отличие оптимизации по критерию EDP от оптимизации по известному критерию максимума вероятности связности.
Диссертация состоит из введения, трех глав, заключения и списка литературы.
Показатели надежности и общие подходы к их расчёту
Первый способ вычисления EDP - это полный перебор реализаций случайного графа: т Сгт N(G) = У(1 (1.1) i=0 j=1 где Gij - j-ый вариант удаления из графа G ровно г рёбер (осуществляется с вероятностью рг( 1 — р)т г ), N (G{j) - число несвязных пар вершин в Gij. По сути, эта формула представляет собой подсчет математического ожидания в дискретном случае по определению, как сумма значений случайной величины, помноженных на вероятности случайной величины принять такие значения [2]. Очевидно, что в нашем предположении о равенстве надежностей всех ребер N(G) имеет вид полинома от р. Второй способ подсчета EDP функционала - это полный перебор всех пар вершин: 71 — 1 П N(G) =ЕЕ (1.2) г=0 j=i+1 1.3.2. Широко известный метод ветвления (метод факторизации), описан, например, в [46]. В сущности, этот метод заключается в применении формулы полной вероятности при использовании в качестве альтернатив гипотезы о присутствии очередного ребра eZJ- и гипотезы о его отсутствии: N(G) = pi\r(G (ву)) + (1 - P)N(G\{eij}), (1.3) где G {eij) - граф, стянутый по ребру е -, имеющему вероятность срабатывания р, в нем вес объединенной вершины v равен W( + Wj, а G\{eij} - граф, получаемый из С7 удалением ребра е . Таким образом, если надежность каждого ребра одинакова и равна р, то функционал N(0) имеет вид полинома от р. (1.4)
Поясним понятие стягивания вершин: это отождествление двух вершин У{ и при котором ребро е , соединяющее эти вершины, убирается из графа, вместо двух вершин г г- и г - в графе появляется объединенная вершина т; - и все ребра, инцидентные вершинам У{ и г - становятся инцидентными этой вершине. Схема метода ветвления приведена на рисунке 1.1 G Рис. 1.1. Схема метода ветвления Приведем также формулу метода ветвления для расчета вероятности связности графа С?: R{G) = рД((Г(еу)) + (1 - р)Д(С\{еу}) где (G (eij)) - граф, стянутый по ребру ег-у, в нем вершины Vi и vj отождествляются в одну, но суммирования весов не происходит, т.к. само понятие веса вершины для критерия вероятности связности не определено. Граф G\{eij} - это граф, получаемый из G с помощью удаления ребра ег-у.
Как видно, сама рекурсивная формула метода ветвления для критериев EDP и вероятности связности одна и та же, разница же состоит в том, что при подсчете EDP стягивание вершин влечет за собой изменение веса стянутой вершины.
Заметим, что метод ветвления (1.3) также представляет собой полный перебор всех реализаций случайного графа, но можно значительно сокращать дерево ветвления, например, если графы одинаковой структуры встречаются в нем несколько раз, применяя формулы сокращения расчетов из [52, 54, 55] и т.д. Различные методы ускорения расчетов, основанных на методе ветвления для вероятности связности случайных графов обсуждаются в [27, 28, 29].
Замечание: В этой главе кратность ребер предполагалась равной 1. Формулы легко могут быть обобщены на случай мультиребер: вместо р для мультиребра кратности к используется вероятность чрисутствия хотя бы одного из составляющих рёбер 1 — (1 — р)к.
Как уже упоминалось, в случае, когда надежность всех ребер одинакова и равна р, ЕБР-функционал принимает вид полинома от р. Такие полиномы называются полиномами надежности. Эти полиномы представляют собой инвариант случайного графа и используются, например, для решения задачи изоморфизма графов [36, 40, 41]. Возможно различное представление ЕБР-полинома с различным смыслом его коэффициентов. В дайной работе используются следующие два представления ЕБР-полиномов. тп м(с) = 2М1-рУрт-\ (1-5) г=0 где А{ имеет смысл суммарного количества числа несвязных пар вершин по всем возможным удалениям ровно г ребер из исходного графа. Также используется классическое представление полиномов: т 2 = 0 В этом случае коэффициенты В{ нельзя интерпретировать содержательно, но это представление иногда бывает более удобно для теоретических выкладок.
Формула для EDP-полинома графа, представляющего собой два несвязных блока
Пусть G(n + 1, п) - звезда, все веса вершин в которой равны w. Очевидно, что существует только два возможных способа добавления ребра в граф с такой топологией - дублирование уже существующего ребра или соединение новым ребром двух вершин на лучах звезды.
Теорема 2.1. Пусть G\(n + 1, п 4-1) - звезда с п + 1 вершиной и одним мулътиребром, и граф С?2(п+1, п+1)) получен из простой звезды соединением новым ребром двух вершин на лучах звезды. Веса всех вершин графов Gi и G2 одинаковы и равны w. Тогда, если п 5, то N{G 1) — N(G2) 0. Если п Ъ, то граф G\ более надежен по критерию EDP, чем граф G2, при р G (0, ц), о, граф G2 более надежен при р 1).
Доказательство. Пронумеруем вершины звезды Ох так, чтобы центральная вершина имела номер 0, а вершина, соединенная с центральной мультиребром имела номер п. Также пронумеруем вершины графа таким образом, чтобы центральная имела номер 0, а вершины на лучах звезды, соединенные добавленным ребром, имели номера п—1 и п. Применим метод ветвления (1.3) к добавленному ребру в звездах и С2. Тогда, с вероятностью 1 —р мы получим исходную звезду С и с вероятностью р из и С?2 мы получим графы 1 и 2 соответственно. 61 это звезда с п вершинами, центральная вершина имеет вес 2ги. 2 это звезда с п вершинами, вершина номер п—1 имеет вес 2ни и соединена с центральной вершиной мультиребром. Ясно, что N((31) - А/"( 32) = N(81) - Л (52).
Надежность мультиребра в Б2 равна, очевидно, р\ = 1 -(1 —р)2 = 2р—р2. ЩБг) = ]Г 22(1 - р) + Е - Л = (2-6) г=1 г=1 3=1+1 = 2(п - 1) (1 -р)+ (" 1}2(П 2) г(1 - Р2), п—2 п—3 п—2 г=1 1=1 3=1+1 п-2 г=1 = (п - 2)ад2(1 - р) + 2(1 - р)2уз2 + (п-2)(п-3) 2 _ + 2(я _ 2)ад2(1 _ + Очевидно, 1 — 2р2 + р3 = (1 — р)(1 + р — р2), следовательно Щ31)-Щ32) = т2{1-р)[2(п - 1)+(п - 2)(1+р)-(п - 2)- (2.8) 2(1-р)-2(п-2)(1+р-р2)]- = ад2(1 - р)р[{2п - 4)р - (п - 4)]. Проанализируем многочлен /(р) = (2п — 4)р — (п — 4). Ясно, что /(р) = О когда = Если п 5, то на интервале (0,1) корня у многочлена /(р) нет. Если же п 5, то существует корень ргоог 6 (0,1). Если р (0,Ргоо) и тг 5, то /(р) О, если р (рГ004,1) и п 5, то /(р) 0. Значит, если п 5, то N(81) — N(82) 0 для всех р (0,1). Если п 5, то N(81) - N(82) 0 для всех р в интервале (0,ргоо4) и //(51) - О для всехр в интервале (ргоог, 0). 2.2.2. Добавление ребра к цепи Рис. 2.2. Графы с 6 вершинами и 6 ребрами Были посчитаны полиномы надежности графов на рис. 2.2 (веса всех вершин были положены равными 1). Полиномы надежности этих графов приведены ниже в табл. 2.1: Таблица 2.1. Коэффициенты ЕБР-полиномст графов на Рис.2.2 Граф Коэффициенты полинома Gi 0 0 105 210 189 84 15 G2 0 5 95 205 188 84 15 Gz 0 13 101 204 188 84 15 G4 0 22 115 210 188 84 15 G5 0 30 130 221 191 84 15 Из этой таблицы легко видеть, что только граф G5 однозначно хуже по критерию EDP, чем все остальные графы, т.к. коэффициенты его полинома надежности мажорируют коэффициенты всех других полиномов. Полином надежности графа G\ пересекается со всеми остальными полиномами (кроме полинома графа G$), следовательно, как и для случая графа- звезды, нужно искать промежутки оптимальности для различных способов добавления ребра в цепь. Следует также заметить, что в этом примере отражен лишь такой способ добавления ребра в цепь, как соединение крайней вершины цепи с другой вершиной цепи, что не охватывает все способы добавления ребра, а именно, соединение новым ребром двух не крайних вершин цепи. Пока что аналитически разрешить задачу оптимального добавления ребра в цепь по критерию ЕБР не удалось и это остается целью дальнейших исследований. Сложность этой задачи может быть продемонстрирована следующим примером.
Пусть графы (к + 1,к + 1) и 02(к + I, к + I) представляют собой циклы длины к и к + 1, соединенные с цепями длины / и / — 1 соответственно, веса всех вершин в графах равны ги. Найдем 7У(Сп.) — N(02). Для этого применим метод ветвления (1.3) к ребрам е1 и е2 как на рис. (2.3). Таким образом, N(1) - АТ{в2) = N(01) N(01). Очевидно, что граф представляет собой два несвязных между собой блока: цикла длины к и цепи длины 1 — 1. Граф 0 2 представляет собой цепь длины к + I — 1. Применим формулу (1.18) и формулы (1.20) и (1.22) для ЕБР-полиномов цепи и цикла, и вычислим N(0]) — N(0%):
Сравнение оптимального добавления ребра но критериям EDP и вероятности связности
Теорема 2.5. Пусть граф G(n, п) имеет топологию цикл с присоединенной вершиной, пусть и в нем есть особая вершина, вес которой равен w , а вес всех остальных вершин графа одинаков и равен w w . Тогда по критерию EDP расположение этой вершины в точке присоединения висячей оптимально.
Доказательство. Действительно, лемма 2.5 показывает, что расположение в точке присоединения висячей вершины наибольшего веса лучше по критерию EDP, чем расположение этой вершины в висячей. С другой стороны, в лемме 2.7 доказано, что расположение в точке присоединения висячей дает более надежную структуру, чем расположение в цикле на расстоянии 1 от этой точки. Если же применить к графам, у которых вершина с весом w находится на цикле, формулу для висячей вершины (1.13), так же, как в лемме 2.7, то, по следствию 2.2 из леммы 2.6, получаем, что расположение вершины весом w на расстоянии 1 от точки присоединения висячей является самым оптимальным из всех расположений этой вершины па цикле (не в точке присоединения висячей).
Особая вершина в графе-восьмерке
Лемма 2.8. Пусть G - граф-восьмерка, состоящий из двух циклов Gk и Gi длины к и I соответственно, соединенных в точке сочленения vz. Пусть все вершины графа G имеют одинаковый вес w, за исключением одной особой вершины vx,vx ф vz, имеющей вес wx w. Тогда чем блиоюе вершина vx к точке сочленения vz, тем надежней граф G по критерию EDP.
Доказательство. Пусть для определенности особая вершина vx находится в цикле Gk- Рассмотрим два графа, Gs и Gs+1, в графе Gs вершина vx находится на расстоянии s, 1 s _fj, а в Gs+i на расстоянии s + 1. Будем применять метод ветвления к ребру, смежному с точкой сочленения vz в цикле Gi. Для определенности можно всегда выбирать ребро, смежное с vz против часовой стрелки. По стягиванию t мы всегда будем получать две структуры, G f и Gf+1, в которых циклы изначальной длины I будут одинаковыми и будут уменьшаться до петли. Итоговые графы G /"1 и G +i представляют собой два цикла длины к. В графе Gвершины I наибольшего веса v z и vx находятся ближе друг к другу, чем в графе Gs +1 . Следовательно, по лемме 2.6 граф С? /-1 более надежен по критерию EDP, i—i чем граф Gs +i .
Рассмотрим графы Gg,b и Gg+j, получающиеся на каждом этапе метода ветвления при выполнении гипотезы разрыва очередного ребра. Эти графы представляют собой циклы длины к с присоединенной цепью одинаковой длины. Применяя теорему 2.8 легко видеть, что на каждом шаге ветвления N(0/) - Л С ) - N(01) -ЩФ+г), где графы и представляют собой циклы с двумя особыми вершинами у\ и ух, находящимися на расстоянии в в графе С? и на расстоянии з + 1 в графе Таким образом, снова применяя лемму 2.6, очевидно, что на каждом этапе ветвления граф С? более надежен по критерию ЕБР, чем граф Значит, граф более надежен по критерию БЭР, чем граф
Лемма 2.9. Пусть - граф-восьмерка, состоящий из двух циклов и длииы к и I соответственно, соединенных в точке сочленения уг. Пусть все вершины графа С имеют одинаковый вес ио, за исключением одной особой вершины ух, имеющей вес и)х ш, смежной с вершиной уг. Пусть (Яг - граф-восьмерка, состоящий из двух циклов и О/ длины к и I соответственно, соединенных в точке сочленения уг. Пусть все вершины графа имеют одинаковый вес ш, за исключением одной особой вершины уг, имеющей вес иох ш. Тогда N(0) — 0; т.е. граф С? менее надежен по критерию ЕВР, чем граф
Доказательство. Пусть для определенности вершина наибольшего веса ух находится в цикле Обозначим в графе вершину, расположенную на том же месте, что и вершина ух в графе тоже как ух. Применим метод ветвления для графов Сх и к ребру, соединяющему вершины УХ и уг. По стягиванию мы получаем одинаковые структуры, т.е. не влияющие на разность ЕОР-функционалов. Рассмотрим структуры С? и образовавшиеся при выполнении гипотезы о разрыве выбранного ребра. Они одинаковы, за исключением того, что вершина наибольшего веса тх в графе находится на свободном конце цепи, а в графе она является точкой сочленения между цепью и циклом длины I.
Применим формулу для ЕБР-функционала (1.2). Очевидно, ЕБР-функ- ционал различается для графов и С? только для тех слагаемых, которые не содержат вершины у2 и ух. Разобьем эти отличные слагаемые на две группы - попарные суммы для цикла и для цепи. Пронумеруем вершины в циклах от VI до Ук+1-2 (здесь не пронумерована вершина уг), а вершины в цепях от v\ до Vk-i (здесь не пронумерована вершина г; ).
Замечания о программной реализации подсчета коэффициентов обычного полинома надежности
Для подсчета полиномов надежности был создан специальный класс Polinom языка С++, состоящий из массива переменной длины (на основе типа std::vector). Для него были определены операции сложения, вычитания и умножения, создано несколько конструкторов класса. Как можно видеть, применение формул (1.14,1.15) для ветвления по цепи длины 2 не позволяет использовать только класс Polinom, т.к. эти формулы подразумевают наличие деления полинома на полипом (полиномиальной дроби). Заметим, что в итоге, после выполнения всех вычислений, числитель и знаменатель такой дроби обязательно сократятся [55]. Но мы не можем определить заранее в какой именно момент произойдет сокращение, т.к. веса вершин в процессе вычисления сами имеют вид полийомиальных дробей. Таким образом, был создан класс Drob языка С++, имеющий в себе в качестве членов экземпляр класса Polinom и 4 целых положительных числа. Такая реализация была выбрана, т.к. очевидно, что в формулах (1.14,1.15) для ветвления по цепи длины 2 в знаменателе может возникнуть только два вида полиномов: р+1 и —р2+р+1. Таким образом, умножение и деление на эти полиномы осуществляется в виде увеличения соответствующего члена класса. Для класса Drob были определены операции сложения, вычитания, умножения, сокращения, а также было создано несколько конструкторов класса.
Для хранения случайных графов был создан специальный класс Graph языка С++. В качестве членов класса в нем имеются переменной длины массивы целых чисел для хранения имеющихся в графе вернтин и ребер, каждое ребро задается парой вершин, а также массив экземпляров класса Drob для хранения весов вершин. В начале работы программы для заполнения исходного графа используется специальный метод класса Graph для чтения из файла.
Подсчет полинома надежности осуществляется рекурсивной функцией Count, являющейся методом класса Graph и возвращающей тип Drob.
При поступлении очередного графа в функцию Count сначала выполняются проверки на окончание ветвления. Если в экземпляре класса Graph, от которого запущена функция Count, не более одной вершины, то Count возвращает 0 несвязных пар. Если осталось две вершины, то Count считает число несвязных пар по формуле (1.10). Если осталось три вершины, то число несвязных пар такого графа считается по формзше (1.11) для трехвершинного графа. Если количество вершин, оставшихся в графе, более трех, то запускается проверка на наличие висячих вершин. Висячей считается вершина, смежная ровно одной другой вершине. Изолированной вершины быть не может, т.к. любой несвязный граф, возникающий в процессе ветвления, разделяется на два графа, которые обрабатываются по формуле (1.12) для моста. Если висячая вершина обнаружена, то применяется формула (1.13) для висячей вершины и запускается метод Count для вновь созданного графа, в котором изменился вес одной вершины и убрано одно ребро. Заметим, что в этом случае далее рассматривается только половина дерева ветвления, в которой ребро соединяющее висячую вершину с остальной частью графа абсолютно надежно, тл:. мы значительно сокращаем подсчет.
Если висячих вершин не найдено, то производится проверка на наличие в графе цепи длины 2. Под цепью понимается наличие вершины, смежной ровно двумя другим вершинам. Если в графе найдена цепь, то производятся преобразования графа по формуле (1.14) или (1.15), и запускается метод Count для вновь созданных графов. В этом случае из графа убираются два ребра-кандидата на ветвление и дерево ветвления также значительно уменьшается. Коэффициент вероятности несвязности ast вершин цепи vs и vt в графе G\{e.sx, ext, est} из формул (1.14,1.15) считается с помощью метода Count2 по формуле метода ветвления (1.4), возвращающего экземпляр класса Polinom. Необходимости считать полином вероятности несвязности в алгебре класса Drob нет, т.к. веса вершин при расчете вероятности связности не учитываются. В методе Count2 поступивший для расчета граф xt, est} сначала преобразовывается для расчета двутерминальной надежности, в частности, из него удаляются все висячие вершины, кроме vs и Vt, если они оказались висячими.
Если цепи в графе также не обнаружено, то выбирается очередное ребро, выполняется проверка, оставляет ли удаление этого ребра граф связным, и если да - то применяется обычный метод ветвления. Если после удаления этого ребра граф становится несвязным - то применяется формула (1.12) для удаления ребра-моста. Проверка на связность графа реализована обычным алгоритмом поиска очередной смежной вершины "в глубину"[1, 16]. Обычный метод ветвления реализован через формирование методами класса Graph UdalenieCon (метод для удаления ребра из графа, возвращает экземпляр класса Graph) и Styagivanie (метод для стягивания ребра в графе, возвращает экземпляр класса Graph) двух новых графов по формуле метода ветвления (1.3). В случае моста используется метод DoubleGraph класса граф, возвращающий экземпляр структуры, каждое из двух полей которой представляет собой экземпляр класса Graph.
После прохождения всего дерева ветвления и расчета EDP-полинома исходного графа возвращаемое значение имеет тип Drob. Выполняется его упрощение и приведение к классическому виду полинома.
Для расчетов была выбрана классическая алгебра полиномов, т.е. полином надежности графа сначала считается в виде (1.6), а затем легко пересчитывается в более удобный для анализа вид (1.5). Сначала представлялось заманчивым реализовать алгебру полиномов в виде (1.5), т.к. в программе присутствуют многочисленные умножения на полиномы вида (1 — р)к, которые реализовывались бы в такой алгебре простым сдвигом на к нулей вправо. Но после анализа такой алгебры полиномов стало понятно, что ее реализация сопряжена со значительными трудностями и невозможно предсказать заранее, будет ли выйгрыш по времени вычислений. Действительно, например, сложение полиномов такой алгебры требует намного более значительных вычислительных ресурсов, чем сложение полиномов в обычной алгебре.
