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

На правах рукописи

Гадяцкая Ольга Александровна

ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКОГО ОЖИДАНИЯ ЧИСЛА НЕСВЯЗНЫХ ПАР ВЕРШИН СЛУЧАЙНОГО ГРАФА И ЕГО ПРИМЕНЕНИЕ В ВЫБОРЕ ОПТИМАЛЬНЫХ СТРУКТУР СЕТЕЙ

05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск - 2008

□03450691

003450691

Работа выполнена в Новосибирском Государственном Университете.

Научный руководитель:

доктор технических наук Родионов Алексей Сергеевич

Официальные оппоненты: доктор физико-математических наук,

профессор Попков Владимир Константинович

кандидат технических наук, доцент Егунов Михаил Михайлович

Ведущая организация:

Институт математики СО РАН (г. Новосибирск)

Защита состоится 11 ноября 2008 г. в 15 часов на заседании диссертационного совета Д 003.061.02 при Институте Вычислительной Математики и Математической Геофизики СО РАН по адресу: 630090, Новосибирск, проспект Ак. Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Института Вычислительной Математики и Математической Геофизики СО РАН.

Автореферат разослан 10 октября 2008 г.

Ученый секретарь диссертационного совета д.ф.-м.н.

С.Б. Сорокин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. При проектировании и модернизации ин-фокоммуникационных сетей возникает важная задача оценки их надежности (способности функционировать). Так как инфокоммуникаци-онные сети применяются во всех сферах человеческой деятельности, то необходимо исследовать различные модели сетей и критерии надежности, реализованные на этих моделях, разрабатывать методы для точного и приближенного вычисления соответствующих функционалов, давать точные рекомендации по проектированию и модернизации сетей связи, опираясь на выбранные показатели надежности. Число несвязных пар узлов является известным показателем надежности для сетей, элементы которых могут выходить из строя в результате естественных причин или намеренного разрушающего воздействия. Если элементы сети выходят из строя с некоторой вероятностью, то можно вычислять математическое ожидание числа несвязных пар узлов (EDP, от англ. Expectation of the number of disconnected pairs of nodes). Традиционно этот показатель используется, когда в качестве модели сети связи выбран случайный граф. Ранее, в связи с NP-трудностью задачи вычисления EDP, использовались, в основном, приближенные методы расчета математического ожидания числа несвязных пар вершин случайного графа. Но с развитием вычислительных мощностей стало возможным вычислять точное значение EDP для графов, состоящих из 10-100 узлов (что соответствует, например, размерности средней локальной сети), а, с другой стороны, для определения качества приближенных методов требуется проверять их точными расчетами. Поэтому важно исследовать методы ускорения точного расчета математического ожидания числа несвязных пар вершин случайного графа и создавать программные комплексы, способные рассчитывать значение EDP для сетей реальных размерностей.

Исследование методов вычисления математического ожидания числа несвязных пар вершин и ускорения расчетов требуются и для того, чтобы решать задачи оптимального (согласно выбранному критерию надежности) проектирования и модернизации сетей. На практике распространены ситуации, когда необходимо наилучшим образом соединить уже существующие сети, подключить новых абонентов к уже существующей сети или разместить в ней особый узел. Получение теоретических результатов в этой области для такого показателя надежности, как EDP, является актуальной и до сих пор мало исследованной задачей.

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

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

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

• исследование оптимального по критерию минимума EDP размещения особой вершины в таких распространенных сетевых топологиях,как цепь(шина), звезда, цикл с висячей вершиной, граф-восьмерка (два цикла с общей вершиной);

• исследование оптимального по критерию минимума EDP добавления ребра в цепь, цикл, звезду;

• исследование оптимального по критерию минимума EDP присоединения сети распространенной топологии (цепи, звезды и графа-восьмерки) к некоторой сети;

• получение формул полиномов надежности для распространенных сетевых топологий в случае наличия ограничения на диаметр;

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

• исследование существующих методов ускорения расчетов EDP-функционала;

• проведение численных экспериментов на разработанной программной библиотеке.

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

Научная новизна работы состоит в следующем:

• впервые решена задача точного расчета коэффициентов EDP-no-линома в общем случае, в том числе в случае наличия ограничений на диаметр графа;

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

Практическая ценность работы заключается в создании программных алгоритмов для точного расчета EDP-полиномов и их реализация в виде программной библиотеки на языке С++, в том числе с случае наличия ограничения на диаметр сети. Обоснованные в работе теоретические результаты, алгоритмы и программная библиотека могут быть использованы в практике анализа надежности сетей связи.

Основные положения, выносимые на защиту:

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

2. теоремы об оптимальности по критерию минимума числа несвязных пар вершин случайного графа (СГ) для определённых топологий СГ и способов их соединения;

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

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

Апробация работы. Основные научные результаты диссертации докладывались и обсуждались на семинаре "Моделирование инфоком-муникационных систем" под руководством д.ф.-м.н. В.К. Попкова, на 9-ой и 10-ой Международных конференциях "Проблемы функционирования информационных сетей" (Новосибирск, август 2006г. и август 2008г.), на 3-ей Азиатской международной школе-семинаре по проблемам оптимизации сложных систем (Чолпон-Ата, Киргизия, июнь-июль 2007г.), на The 2008 International Conference on Computational Science and Its Applications (Перуджа, Италия, июнь-июль 2008гю), на 13-ой Конференции молодых ученых ИВМиМГ СО РАН (Новосибирск, апрель 2008г. Работа отмечена дипломом второй степени).

Также результаты диссертации были представлены и обсуждались на 9-ой Всероссийской конференции с участием иностранных ученых "Современные методы математического моделирования природных и антропогенных катастроф "(Барнаул, сентябрь 2008г.), на 45-ой и 46-ой Международных научных студенческих конференциях "Студент и научно-технический прогресс" (Новосибирск, апрель 2007г. и апрель 2008г.), на 8-ой Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Новосибирск, ноябрь 2007г.) и на Конференции-конкурсе работ студентов, аспирантов и молодых ученых "Технологии Microsoft "в теории и практике программирования (Новосибирск, март 2008).

Основные научные результаты диссертации опубликованы в 10 работах, список которых приведен в конце автореферата, среди них одна работа в журнале из списка ведущих научных изданий, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы. Диссертация изложена на 96 страницах, включает библиографический список из 64 наименований работ, 24 рисунка и 9 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

G(n, т) — (V, Е) - неориентированный граф с множеством вершин V и

множеством ребер Е. n=\V\ - число вершин графа. т = \Е\ - число ребер графа. ь\ - вершина графа G под номером г. etJ - ребро между вершинами гч и vy р - вероятность присутствия произвольного ребра. N(G) - математическое ожидание числа несвязных пар вершин, EDP. Nq(G) - математическое ожидание числа несвязных пар вершин графа

G в случае наличия ограничения на диаметр графа. R(G) - вероятность связности графа G.

Определим расстояние 1Ч между вершинами к, и и, в цепи обычным образом, как число рёбер в пути между этими вершинами. В случае цикла под расстоянием 1г] между вершинами v, и vj будем понимать число ребер в пути от вершины v( до вершины vj против часовой стрелки.

EDP-полином для цепи. Если граф G(n, тг — 1) представляет собой простую цепь, то, пронумеровав вершины цепи слева направо, получим

тг — 1 гг

(1)

¿=1 j=i+J

EDP-полином для звезды. Если S(n+ 1,п) - граф с одной центральной вершиной, смежной п остальным вершинам. Занумеруем вершины, пусть центральная имеет номер 0, а все остальные вершины номера с 1 до п. Тогда

п п— 1 п

N(S) = £( 1 - p)wow, + (1 - P2)WIWJ. (2)

г = 1 г=1 J=i+1

EDP-полином для цикла. Если G(n,n) - граф циклической структуры, то

п —1 п

ад^Е Е(i-p'")(I-P,'>.«'J. (з)

г=1 j=i+l

В главе рассмотрено получение полиномов надежности для наиболее распространенных сетевых топологий в случае наличия ограничения на диаметр, обозначим его D. Сразу заметим, что если D < 1, то, очевидно, все пары вершин становятся несвязными и EDP любого графа G(n, т)

п—1 п

с весами вершин WT{G) в этом случае равно ^ 2 wiw] ■

i=i j=i+i

Полином надежности для звезды в случае наличия ограничения на диаметр. Очевидно, что в случае D>2 полином надежности для звезды S{n+1, п) совпадает с полиномом надежности EDP без ограничения на диаметр (2). Если D = 1, то все вершины на лучах звезды становятся несвязными друг с другом. В этом случае

п п—1 п

Np(S{n+ 1,п)) = У](1 -p)w0wj + WiWj. (4)

t=i ¿=1 j=t+i

Полином надежности для цепи в случае наличия ограничения на диаметр. Если ограничение на диаметр D > п — 1, то полином надежности для цепи Ch(n,n — 1) совпадает с полиномом надежности для цепи в случае отсутствия ограничения на диаметр (1). Рассмотрим случай 0 < D < п - 1:

n—D j+D

ND(Ch(n,n-1)) = Y, I E (5)

j=i >=j+i

n n—1 n

i=j + D+1 j=n-D+lt=j+l

Полином надежности для цикла в случае наличия ограничения на диаметр. Если С(п,п) - цикл, то для всех D > п Nd(C) совпадает с формулой для полинома надежности цикла в случае отсутствия ограничения на диаметр (3). Рассмотрим случай 0 < D < п. Возможны следующие случаи: 0 < D < [f J, < D < п и D =

Если 0 < D < J, то каждая пара вершин может быть связана не более чем одним путем, либо несвязна.

п D

ND(C(n,n)) = ]![>,(X>(.+J),w»0 -?'•■<•+»""'»)+ (6) 1=1 } = \ тгп(г+п — 1 —D,n)

]=i+D

Если [JJ < D < n, то каждая пара вершин может быть связана одним или двумя путями в цикле.

n i+n-D-1

ND{C(n,n)) = £>,( Е (1-Р1—н+ (7)

t-1

mm(t+D,n)

£ (1 -pl"){l

Осталось рассмотреть случай D = [f J • Если длина цикла п - четное число, то Nd{C) в этом случае совпадает с формулой (7), иначе Nd(C) совпадает с (6).

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

Лемма 1 Если две цепи Gi(n, п —I) u Gj(n, п— 1) имеют п— 1 вершину веса w и одну (особую) вершину vx веса wx > и>, и в цепи G\ вершина vx расположена ближе к центру цепи, нем в цепи G2, то N(G\) < iV(G'2).

Оптимальное добавление ребра в звезду, цепь и цикл

Лемма 2 Пусть G(n,n — 1) - цепь, веса всех вершин в которой равны IV. Тогда по критерию EDP более надежной будет структура после замыкания цепи G е цикл, чем после дублирования уже существующего ребра.

Теорема 1 Пусть Gi(n + 1,п + 1) - звезда с п + 1 вершиной и одним мультиребром, и граф G-i{n+ l,n+ 1)) получен из простой звезды соединением новым ребром двух вершин на лучах звезды. Веса всех вершин графов G\ и G2 одинаковы и равны w. Тогда, если п < 5, то N(G 1) — N(G2) > 0. Если п > 5, то граф Gi более надежен по критерию EDP, чем граф G2, прир € (0, 2^1144), а граф G2 более надежен при Р 6(^,1)-

Доказательство теоремы опирается формулу EDP-полинома для звезды (2) н вычисление корня полинома разности N(G 1) — N(G2)-

Теорема 2 Если G - цикл длины п, и вес каждой вершины в нем равен w, то при добавлении хорды в цикл оптимальной будет та структура, у которой концы хорды наиболее отдалены друг от друга. Т.е. концы хорды в оптимальной структуре находятся на расстоянии k = [n/2J.

Доказательство этой теоремы опирается на доказательство того факта, что цикл длины 2х с хордой, которая делит его на части длины х + к и х — к более надежен по критерию EDP, чем цикл с хордой, делящей его на части длины х+к + 1нх—к — I, это утверждение доказывается полным разбором дерева ветвления (разбором случаев). Аналогично доказывается подобный факт для цикла нечетной длины.

Оптимальное, расположение особых вершин отличного веса

Теорема 3 Пусть имеется цепь G{n,n — 1), в которой одна (особая) вершина имеет вес w*, а все остальные вершины имеют вес w < w*. Тогда наиболее надежно по критерию EDP расположение такой особой вершины в центре цепи.

Теорема 4 Пусть имеется звезда G(n 4- 1, п), в которой есть одна (особая) вершина с весом w*, а все остальные п > 1 вершин имеют вес w < ги*. В этом случае для любого р EDP-полипом звезды, у которой особая вершина расположена в центре, меньше EDP-полинома звезды, у которой она расположена на луче (является висячей).

Теорема 5 Пусть сеть имеет топологию "цикл длины п с присоединенной вершиной", пусть в такой сети есть особая вершина, которой приписан вес w*, а вес всех остальных вершин в сети одинаков и равен w < w*. Тогда по критерию EDP расположение этой вершины в точке присоединения висячей оптимально.

Доказательство теоремы основано на серии лемм, ниже приведена одна из них.

Лемма 3 Пусть имеются два цикла длины п > 1, в которых есть две вершины веса w\ и w^, а все остальные вершины имеют вес w < wi, wi-Пусть в первом цикле С\ вершины весом ui\ и ш2 находятся на расстоянии к > 1, а в цикле Сг эти вершины находятся на расстоянии k+ 1 < [tj J . Тогда цикл С\ более является более надежным по критерию EDP чем цикл Сц, т.е. N(C\) - N(C?) < 0.

Теорема 6 Оптимально по критерию EDP расположение особой вершины наибольшего веса в точке сочленения графа-восьмерки. Здесь предполагается, что веса всех остальных вершин графа-восьмерки одинаковы.

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

Оптимальное по критерию EDP присоединение структур Задачи оптимального соединения двух сетей встречаются довольно часто. В данной работе под присоединением графа G к графу F понимается граф Н = F U G, в котором некоторая вершина vq из G и заранее выбранная вершина vp из F отождествлены в одну вершину ьц. Таким образом, оптимальное присоединение графа G к графу F сводится к поиску такой оптимальной для соединения вершины vq в графе G, что присоединение этой вершины к заранее выбранной вершине vp в графе F дает наименьшее математическое ожидание числа несвязных пар вершин в графе Я. Веса всех вершин в графах G, F, Н предполагаются равными w.

Теорема 7 Если G(n,n — 1) - звезда, а F(k,m) - произвольный граф с выбранной вершиной vp, то оптимальная для соединения вершина vq - это центр звезды.

Теорема 8 Пусть имеется цепь Gh(n, п—1) и граф G(k, т). Тогда чем ближе выбранная для соединения вершина цепи Ch к центру цепи, тем более надежна полученная после соединения графов сетевая топология Н.

Теорема 9 Если G - граф-восьмерка, состоящая из циклов Gk и Gi, длины к и I соответственно, соединенных в вершине vz (считаем вершину vz частью цикла длины к для определенности); F - произвольный случайный граф из п вершин, в которол1 есть выбранная вершина vp, с которой надо соединить граф G, то среди всех возможных соединений графов F и G оптимально по критерию EDP соединение вершины vy с вершиной vz. Здесь предполагается, что веса всех вершин графов F, G и Н одинаковы и равны и>.

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

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

Рис. 1: Графы после добавления ребра в звезду

экспериментов, подтверждающих теоретические результаты из второй главы. Например, для тестирования результатов об оптимальном по критерию EDP добавления ребра в звезду с помощью разработанной программной библиотеки были посчитаны EDP-полиномы графов G i и G2, изображенных на рис. 1. Веса всех вершин в начале расчетов были положены равными 1.

N(Gi) = 48р8(1 — р)+399рт(1 — р)2+1410р6(1 — р)3+

2781р5(1 - р)4+3360р4(1 - р)5+2553р3(1 - р)6+ 1194р2(1 - р)7+315р(1 - р)8+36(1 - р)9, N{G2) = 56р8(1 - р)+435р7(1 - р)2+1470р6(1 - р)3+

2821р5(1 - р)4+3360р4(1 — р)5+2541р3(1 — р)6+ 1190р2(1 - р)7+315р(1 - р)8+36(1 - р)э.

Корень разности полиномов N(G\) и /V((?2) был посчитан в программе Maple 11 и равен На промежутке ре (0, |) граф G2 более надежен по критерию EDP, и на промежутке р 6 1) граф G\ более надежен по критерию EDP. Эти результаты в точности совпадают с полученными теоретически с помощью теоремы 1 об оптимальном по критерию EDP добавлении ребра в звезду.

Для проверки теоретических результатов об оптимальном по критерию EDP добавлении ребра в цикл были посчитаны EDP-полиномы графов Gi - G5, изображенных на рис. 2 и представляющих собой циклы длины 10 с разным расположением хорды. Веса всех вершин были положены равными 1.

Рис. 2: Циклы с разным расположением хорды

Л^СО = З00р9(1-р)2+2775р8(1-р)3+8420р7(1~р)4+

14640р6(1-р)5+16620р5(1-р)6+12860р4(1-р)7+ 6786р3 (1 -р)8+2351р2 (1 -р)9+484р(1 -р) 10+45( 1 -р)11, ЛГ(С2) = З25р9(1-р)2+2855р8(1-р)3+8525р7(1-р)4+

14704рб(1-р)5+16635р5(1-р)6+12860р4(1-р)7+ 6786р3(1-р)8+2351р2(1-р)9+484р(1-р)10+45(1-р)11, ЛГ(Сз) = 398р9(1-р)2+3082р®(1-р)3+8823р7(1-р)4+

14903р6 (1 —р)5+16703р5 (1—р)6+12870р4 (1—р)7+ 6786р3(1-р)8+2351р2(1-р)9+484р(1-р)10+45(1-р)п, М(С4) = 513р9(1-р)2+3417р8(1-р)3+9264р7(1-р)4+

15246р6(1-р)5+16872р5(1-р)6+12918р4(1-р)7+ 6792р3(1-р)8+2351р2(1-р)9+484р(1-р)10+45(1-р)и, Ы{в5) = 660р9(1-р)2+3795р8(1-р)3+9768р7(1-р)4+

15708р6 (1 —р)5+17160р5 (1 —р)6+13035р4 (1—р) 7+ 6820р3 (1 —р)8+2354р2 (1 —р)9+484р(1 —р) 10+45( 1-р)11.

Из этих соотношений очевидно, что полином 1) мажорируется всеми остальными полиномами и чем дальше концы хорды друг от друга, тем более надежна получаемая структура по критерию ЕБР, что согласуется с теоремой 2.

Даны примеры по применению точно расчитанных с помощью программной библиотеки EDP-полиномов для выбора оптимальной по критерию EDP сетевой топологии в зависимости от значения надежности ребрар. Например, были рассмотрены два графа Gi(10,17) и 10,17), изображенные на рис.3.

С помощью программной библиотеки для подсчета коэффициентов полиномов надежности, были получены следующие полиномы:

N{G 0 = 18р16(1-р)+305р15(1-р)2+2411р14(1-р)3+

11950р13(1-р)4+41942р12(1-р)5+И0959рп(1-р)6+ 228747р10(1-р)7+372645р9(1-р)8+479339/(1-р)9+ 480185р7(1-р)10+367664р6(1-р)и+211619р5(1-р)12+ 90062p4 (1 —р)13+27605р3 (1 —р)14 +5792р2 (1 —р)15 + 748р(1-р)16+45(1-р)17, N(G2) = 39р15(1-р)2+677р14(1-р)3+5377р13(1-р)4+

26069p12 (1—р)5+86762рп(1—р)6+210214р1О(1—р)7+ 380438рэ(1-р)8+515498р8(1-р)9+518639р7(1-р)1о+ 389367р6(1-р)п+219022р5(1-р)12+91615р4(1-р)13+ 27792р3(1-р)14+5802р2(1-р)15+ 748р(1-р)16+45(1-р)17.

Полиномы надежности графов G\ и G2 пересекаются на отрезке (0,1) в точке р* « 0.5312978 (точка пересечения была получена с помощью программы Maple 11). Граф G\ более надежен по критерию EDP на отрезке р 6 (0, р*). Граф С2 более надежен по критерию EDP

ре(рМ).

Рис. 3: Графы с 10 вершинами и 17 ребрами

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

• исследованы для некоторых классов случайных графов такие задачи структурной оптимизации по критерию EDP, как расположение вершины особого веса, добавление ребра и присоединение графов;

• получены формулы полиномов надежности графов топологии звезда, цепь и цикл в случае наличия ограничения на диаметр;

• разработаны программные алгоритмы для точного расчета коэффициентов EDP-полиномов случайных графов, в том числе в случае наличия ограничения на диаметр;

• на основе этих алгоритмов созданна программная библиотека для расчета EDP-полиномов;

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

Список работ по теме диссертации

Статьи в реферируемых изданиях и журналах, рекомендованных ВАК

[1] Гадяцкая O.A. Применение EDP-полиномов при выборе оптимальных структур. // Вестник НГУ (Серия: математика, механика, информатика), т. 8, выпуск 1, 2008г. С. 3-14.

[2] GadyatskayaO., Rodionov A., RodionovaO. Using EDP-polynomials for network structure optimization. // Proceedings of The 2008 International Conference on Computational Science and Its Applications, Lecture Notes in Computer Science, vol. 5073, Springer, 2008. P. 1061-1077.

[3] Гадяцкая O.A. Оптимизация структуры сети по критерию минимума математического ожидания числа несвязных пар узлов // Электронный журнал "Исследовано в России", т. 15, 2008г., С. 195-202.

Доклады на международных и всероссийских конференциях

[4] Гадяцкая O.A., Родионов A.C. Исследование некоторых показателей связности случайных графов // Труды IX Международной конференции "Проблемы функционирования информационных сетей"ИВМиМГ СО РАН, Новосибирск, 2006г., С. 87-89.

[5] Гадяцкая. O.A. Некоторые вопросы вычисления полиномов связности случайных графов // Материалы XLV Международной научной студенческой конференции "Студент и научно-технический прогресс" (секция "математика"), НГУ, Новосибирск, 2007г. С. 155-156.

[6] Гадяцкая O.A. О некоторых оптимальных по критерию EDP системах сетевой структуры // VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. Тезисы докладов. Новосибирск, 2007г., С. 89.

[7] Гадяцкая O.A. О некоторых сетевых топологиях, оптимальных по критерию минимума числа несвязных пар узлов // Материалы XLVI Международной научной студенческой конференции "Студент и научно-технический прогресс" (секция "математика"), НГУ, Новосибирск, 2008г. С. 183.

[8] Гадяцкая O.A. Оптимальное соединение случайных графов по критерию минимума математического ожидания числа несвязных пар вершин. //Материалы X Международной конференции "Проблемы функционирования информационных сетей", ИВМиМГ СО РАН, Новосибирск, 2008. С. 28-31.

[9] Родионов A.C., Гадяцкая O.A. Применение и расчет EDP-полинома случайного графа // Труды ИВМиМГ СО РАН (Материалы Третьей азиатской международной школы-семинара "Проблемы оптимизации сложных систем"), Новосибирск, 2007г. С. 93-107.

Прочие издания

[10] Гадяцкая O.A. Оптимизация структуры сети по критерию минимума математического ожидания числа несвязных пар узлов // Технологии Microsoft в теории и практике программирования. Конференция-конкурс работ студентов, аспирантов и молодых ученых. Материалы конференции. Новосибирск, 2008г. С. 109-110.

Подписано в печать 9.10.2008 Бумага 60x84 1/16 Объём 1 п. л. Тираж 100 экз. Заказ № 462 Отпечатано, ЗАО "РИЦ "Прайс-курьер"", Новосибирск, 630128, ул. Кутателадзе, 4г, оф. 311, Тел. (383) 330-72-02.

Введение

Глава 1. Критерий математического ожидания числа несвязных пар узлов. Постановка задачи и предварительные сведения

1.1. Моделирование сетей связи и исследование их нг.дежностей

1.1.1. Показатели надежности и общие подходы к их расчёту

1.1.2. Оптимизация структур сетей по критериям надёжности

1.1.3. Критерий максимума вероятности связности.

1.1.4. Критерий вероятности передачи потока заданной величины

1.1.5. Критерий EDP.

1.2. Основные определения и формулы.

1.3. Способы вычисления EDP-функционала.

1.3.1. Методы полного перебора

1.3.2. Метод ветвления.

1.4. Полиномы надежности.

1.5. Полиномы надежности для вероятности связности.

1.6. Формулы для расчета EDP.

1.6.1. EDP-полином двухвершинного графа.

1.6.2. EDP-полином трехвершинного графа.

1.6.3. Формула для моста.

1.6.4. Удаление висячей вершины.

1.6.5. Ветвление по цепи длины 2.

1.6.6. Формула для EDP-полинома графа в случае наличия в нем точки сочленения.

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

1.7. Предварительные утверждения.

1.8. Пример различия результатов оптимизации по критериям вероятности связности и EDP.

1.9. Формулы полиномов надежности для распространенных сетевых топологий

1.9.1. Полином надежности для цепи

1.9.2. EDP-полином для звезды.

1.9.3. EDP-полином для цикла.

1.10. Полиномы надежности известных графов в случае наличия ограничения на диаметр.

1.10.1. Полином надежности для звезды в случае наличия ограничения на диаметр.

1.10.2. Полином надежности для цепи в случае наличия ограничения на диаметр.

1.10.3. Полином надежности для цикла в случае наличия ограничения на диаметр.

1.11. Результаты и выводы к Главе

Глава 2. ТЕОРЕТИЧЕСКАЯ ОПТИМИЗАЦИЯ СЕТЕВЫХ

ТОПОЛОГИЙ ПО КРИТЕРИЮ EDP

2.1. Вспомогательные утверждения.

2.2. Добавление ребра в распространенные сетевые топологии

2.2.1. Добавление ребра в звезду.

2.2.2. Добавление ребра к цепи.

2.2.3. Добавление ребра в цикл.

2.2.4. Сравнение оптимального добавления ребра но критериям EDP и вероятности связности.

2.3. Оптимальное расположение особых вершин отличного веса

2.3.1. Цепь с особой вершиной.

2.3.2. Звезда с одной особой вершиной.

2.3.3. Особая вершина в топологии цикл с присоединенной вершиной

2.3.4. Особая вершина в графе-восьмерке.

2.4. Оптимальное по критерию EDP присоединение структур

2.4.1. Присоединение звезды

2.4.2. Присоединение цепи.

2.4.3. Присоединение графа-восьмерки

2.4.4. Сравнение результатов оптимального присоединения графов по критерию EDP с результатами оптимального присоединения этих графов по критерию максимума вероятности связности.

2.4.5. Оптимальное соединение циклов.

2.5. Результаты и выводы к Главе 2.

Глава 3. ПРОГРАММНЫЕ АЛГОРИТМЫ И ИХ РЕАЛИЗАЦИЯ

3.1. Реализация подсчета коэффициентов обычного полинома надежности

3.1.1. Замечания о программной реализации подсчета коэффициентов обычного полинома надежности.

3.2. Особенности программной реализации подсчета коэффициентов полинома надежности графа в условиях наличия ограничения на диаметр.

3.3. Числениые эксперименты.

3.3.1. Ускорение расчетов в случае обычного подсчета коэффициентов полиномов надежности.

3.3.2. Тестирование теоретических результатов из главы

3.3.3. Оптимизация сетевых топологий по критерию EDP с помощью точного расчета полиномов надежности.

3.4. Результаты и выводы к Главе 3.

Анализ на надежность - важная часть проектирования и модернизации инфокоммупикационных сетей. Существует много критериев надежности сетей. Обычно выбор критерия надежности осуществляется исходя из особенностей конкретной сети и ее назначения. Связность сети, максимальная пропускная способность, время восстановления работоспособности и многие другие характеристики сети могут быть выбраны в качестве показателей надежности. Например, в случае передачи аудио и видео сообщений, биржевых сводок, 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 от оптимизации по известному критерию максимума вероятности связности.

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

Основные результаты работы, выносимые на защиту:

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

2. Теоремы об оптимальности по критерию минимума математического ожидания числа несвязных пар вершин случайного графа (СГ) для определённых топологий СГ и способов их соединения.

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

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

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

Заключение

В работе рассмотрен точный расчет полиномов надежности такой характеристики случайных графов, как математическое ожидание числа несвязных пар. Исследованы для некоторых классов случайных графов такие задачи выбора оптимальных топологий по критерию ЕОР, как расположение особого веса, добавление ребра и присоединение графов. Получены формулы полиномов надежности звезды, цепи и цикла в случае наличия ограничения на диаметр. Разработаны программные алгоритмы для точного расчета коэффициентов ЕБР-полиномов случайных графов, в том числе в случае наличия ограничения на диаметр. На основе этих алгоритмов создана программная библиотека для расчета ЕБР-полиномов. В работе также представлены результаты численных экспериментов, в том числе подтверждающие основные теоретические результаты из главы 2.

1. Ахо A.B., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы // М.: Мир, 2001.

2. Боровков A.A. Теория вероятностей. 2-е изд., перераб. и доп. // М.: Наука., 1986. 431 с.

3. Гадяцкая O.A. Применение EDP-полиномов при выборе оптимальных структур. //Вестник НГУ, Серия: Математика, механика, информатика. Т.8. Выпуск 1, Новосибирск, 2008г. С.3-14.

4. Гадяцкая O.A. Оптимальное соединение случайных графов по критерию минимума математического ожидания числа несвязных пар вершин. // Материалы X Международной конференции "Проблемы функционирования информационных сетей", Новосибирск, 2008 г., С. 28-31.

5. Гадяцкая O.A., Родионов A.C. Исследование некоторых показателей связности случайных графов //IX Международная конференция "Проблемы функционирования информационных сетей"ИВМ и МГ, Новосибирск, 2006 г., С. 87-89.

6. Гадяцкая O.A. О некоторых оптимальных по критерию EDP системах сетевой структуры // VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. Тезисы докладов. Новосибирск, 2007г. С.89.

7. Дудник Б.Я., Овчаренко В.Ф., Орлов В.К. и др.; Под ред. Б.Я. Дудника. Надежность и живучесть систем связи // М.: Радио и связь, 1984. 216 с.

8. Егунов M. М. Анализ и синтез систем связи с учётом структурной надёжности // 3-й Евразийский форум международная научно-практическая конференция "Связьпром 2006", Екатеринбург: Ростелеком. С. 161-163.

9. Кауль С.Б. Оценка вероятности связности случайного графа // Эффективность и структурная надёжность информационных систем (СМ-7), Новосибирск, 1982. С. 3-6.

10. Кельманс А.К. Некоторые вопросы надёжности сетей // Автоматика и телемеханика, Т. 26, 1965, С. 567-574.

11. Краковская О. С., Толчан А. Я. Оценки вероятности связности графа сети связи // Информационные сети и коммутация, М.: Наука, 1968. С. 138-141.

12. Кристофидес Н. Теория графов: Алгоритмический подход; Пер. с англ. Э.В. Верш-кова, И.В. Коновальцева; Под ред. Г.П. Гаврилова // М.: Мир, 1978. 432 с.

13. Литвак Е.И. О вероятности связности графа // Изв. АН СССР. Техн. Кибернетика № 5, 1975. С. 161-165.

14. Ломоносов М.В., Полесский В.П. Верхняя граница надежности информационных сетей // Проблемы передачи информации, Т. 7, вып. 4, 1971. С. 78-81.

15. Ломоносов М.В., Полесский В.П. Нижняя оценка надежность сетей // Проблемы передачи информации, Т. 8, вып. 2, 1972. С. 567-574.

16. Ломоносов М.В., Полесский В.П. О максимуме вероятности связности // Проблемы передачи информации, Т. 8, вып. 1, 1972. С. 68-73.

17. Мигов Д.А. Выбор разрешающего ребра в методе ветвления и применение сечений для расчета надежности сетей// Мат. X межд. конф. "Проблемы функционирования информационных сетей". Новосибирск: Изд. ИВМиМГ СО РАН, 2008. С. 73-75.

18. Козлов Б.А., Ушаков И.А. Справочник по расчету надежности аппаратуры радиоэлектроники и автоматики // М.: Советское радио, 1975.

19. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях // Наука. Сиб. отд-ние, Новосибирск, 1990, 515с.

20. Попков В. К. Математические модели связности. 2-е изд., перераб. и доп. // Новосибирск: Изд. ИВМиМГ СО РАН, 2006.

21. Родионова O.K. Исследование и разработка методов анализа и синтеза оптимально-связных информационных сетей: Дис. . канд. гехн. наук: 05.13.18. // Новосибирск, 2003.

22. Родионов А.С., Гадяцкая О.А. Применение и расчет EDP-полинома случайного графа // Труды ИВМ и МГ СО РАН (Материалы Третьей азиатской международной школы-семинара "Проблемы оптимизации сложных систем"), Новосибирск, 2007 г. С. 93-107.

23. Родионов А.С., Родионова O.K. О точном вычислении вероятности связности графа // Тр. Междунар. конф. "Вычислительные технологии и математические модели в науке, технике и образовании", Т. 5 Алма-Ата, Казахстан, 2002. С. 140-147.

24. Родионов А.С., Родионова O.K. Некоторые методы ускорения расчета надежности информационных сетей // Мат. 30 Междунар. конф. "Информационные технологии в науке, образовании, телекоммуникации и бизнесе", Гурзуф, Украина, 2003. С. 215-217.

25. Степанов В.Е. О вероятности связности случайного графа Gm(t) // Теория вероятностей и её применения, Т. 15, вып. 1, 1970. С. 56-68.

26. Aggarwal К.К., Chopra Y.C., Bajwa J.S. Topological layout of links for optimizing the overall reliability in a computer communication system / / Microelectonics and Reliability, Vol. 22, 1982. P. 347—351.

27. Bail M.O., Colbourn C.J. and Provan J.S. Network reliability, Handbook of Opérations Research // Network Models, Elsevier North-Holland, 1995, P. 673-762.

28. Buzacott J.A., Chang S.K. Cut set intersection and node partition // IEEE Trans. Reliab. R-33, 1984. P. 385-389.

29. Carlier J., Lucet C. A decomposition algorithm for network reliability evaluation // Discrete Applied Mathematics, Vol. 65, №1-3, 1996. P. 141-156.

30. Colbourn C.J. The Combinatorics of Network Reliability // Oxford University Press, New York, 1987.

31. Colbourn C.J. Some open problems on reliability polynomials // Congr. Numer. 93, 1993. P. 187-202.

32. Erdes P, Renyi A. On Random Graphs I // Publicationes Mathematicae Debrecen 5 (1959), P. 290—297.

33. Jan R.H., Hwang F.J., Chen S.T. , Topological optimization of a communication networksubject to a reliability constraint// IEEE Trans. Reliab. Vol. 42,1993. P. 63—70.

34. Kelmans A. K. Crossing properties of graph reliability functions // Journal of Graph Theory, Vol. 35, Iss. 3, 2000. P. 206-221.

35. Kelmans A. K. On graphs with randomly deleted edges // Acta Math Acad Sci Hung,Vol. 37, Issues 1-3,1981. P. 259-267.

36. Kelmans A. K. Multiple crossings of network reliability functions // RUTCOR Research Report, Rutgers University, 1994. P. 43-94.

37. Koide T., Shinmori S., Ishii H., Topological optimization with a network reliability constraint // Discrete Applied Mathematics, Vol. 115, Issues 1-3, 2001. P. 135-149.

38. Krivoulets V.G., Polesskii V.P. What is the Theory of Bounds for Network Reliability?// Inf. Processes (ISSN: 1819-5822) Vol. 1 n. 2, 2001. P. 199-203.

39. Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer-Verlag Lecture Notes in Computer Science, Vol. 4097, 2006. P. 702-709.

40. Moore E.F., Shannon C.E. Reliable Circuits Using Less Reliable Relays //J. Franclin Inst., Vol. 262, n. 4b, 1956. P. 191-208.

41. Nahman J. Fuzzy logic based network reliability evaluation // Microelectronics and Reliability. Vol. 37, Iss. 8, 1997. P. 1161-1164.

42. Page L.B., Perry J.E. Reliability polynomials and link importance in networks // IEEE Transactions on Reliability, Vol. 43 Iss. 1, 1994 P. 51-58.

43. Reittu H., Norros I. Random graph models of communication network topologies // ICCS-07, Boston, USA, 2007. The paper can be found via http: //arxiv.org/abs/0712.1690

44. Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Optimal Structures // The 2004 International Conference on Computational Science and Its Applications, Springer, Lecture Notes in Computer Science, Vol. 3047, 2004, P. 431440.

45. Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Exact Calculation with Use of Chains // ICCSA-2004, Springer Lecture Notes in Computer Sciences. Vol. 3046. P. 315-324.

46. Rodionov A., Rodionova O. Network Probabilistic Connectivity: Expectation of a Number of Disconnected Pairs of Nodes // HPCC 2006, Springer, Lecture Notes in Computer Science, Vol. 4208, Springer 2006, P. 101-109.

47. Rodionov A.S., Choo H. On Generating Random Network Structures: Connected Graphs // Proc. Intern. Conf. On Information Netwotking ICOIN, Vol. 3, 2004. P. 11451152.

48. Satyanarayana A., Chang M.K. Network reliability and the factoring theorem // Networks Vol. 13, 1983. P. 107-120.

49. Satyanarayana A., Wood R.K. A linear-time algorithm for computing /¿ terminal reliability in series-parallel networks // SIAM. J. Comput., Vol. 14, 1985. P. 818-883.

50. Shooman A.M. Algorithms for Network Reliability and Connection Availability Analysis // Electro/95 Int. Professional Program Proc.,1995. P. 309 333

51. Shooman A.M., Kershenbaum A. Exact graph-reduction algorithms for network reliability analysis // GLOBECOM '91. Countdown to the New Millennium. Featuring a Mini-Theme on: Personal Communications Services, Vol. 2, 1991. P. 1412-1420.

52. Shooman A.M., Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction // Reliability and Maintainability Symposium, Proceedings, 1992. P. 441-448.

53. Shooman A.M. Algorithms for network reliability and connection availability analysis // Electro-95 International. Professional Program Proceedings, 1995. P. 309-333.

54. Van Slyke R, Frank H. Network Reliability Analysis. Pt. 1 // Networks, Vol. 1, Iss. 3,1972. P. 279-290.

55. Wood R.K. Triconnected Decomposition for Computing ii-Terminal Network Reliability // Networks, Vol. 19, 1989. P. 203-220.