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

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

РОДИОНОВА Ольга Константиновна

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ АНАЛИЗА И СИНТЕЗА ОПТИМАЛЬНО-СВЯЗНЫХ ИНФОРМАЦИОННЫХ СЕТЕЙ

.13.18 - математическое моделирование, численные методы и

Автореферат

диссертации на соискание ученой степени кандидата технических наук

комплексы программ

Новосибирск, 2003

Работа выполнена в Институте вычислительной математики и математической геофизики СО РАН.

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

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

Научный консультант: д.ф.-м.н., профессор

Нечепуренко Михаил Иванович. Официальные оппоненты: д.ф.-м.н.

Полесский Валерий Петрович, к.ф.-м.н.

Мельников Леонид Сергеевич.

Ведущая организация: Новосибирский государственный

университет телекоммуникаций и информатики, г. Новосибирск.

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

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

Автореферат разослан 19 сентября 2003 года.

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

С.Б. Сорокин

Общая характеристика работы

ть\9

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

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

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

Научная новизна работы. В диссертации получены следующие новые результаты:

1. Исследованы структуры однородных по степеням вершин и кратностям ребер мультиграфов.

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

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

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

"" •' ША

Публикации. По материалам, представленным в диссертации, опубликовано: 4 доклада в материалах всесоюзных и международных конференций, 1 статья в сборнике ИБМиМГ СО РАН, 1 препринт ВЦ СО РАН, 1 глава в монографии В.К. Попкова "Математические модели связности", т. 2, 2002 г. Имеются также научные отчеты по темам и тезисы Всесоюзных и международных совещаний, семинаров и конференций и зарегистрированные в ГОСФАП программы. Список наиболее важных публикаций приведен в конце автореферата.

В работах, выполненных по теме диссертации в соавторстве с М.И. Нечепуренко и С.М. Майнагашевым, автору принадлежат реализация алгоритмов и часть выводов. В работах, выполненных в соавторстве с A.C. Родионовым и A.A. Герцевой, последним принадлежит программная реализация алгоритмов и участие в постановке численных экспериментов и обсуждении результатов. Автор выраг жает благодарность дипломнику НГУ Мурзину Михаилу Юрьевичу за реализацию Windows-версии программ разработанных алгоритмов точного расчета вероятности связности случайного графа.

Апробация работы. Результаты докладывались на многих всесоюзных и международных конференциях. Среди них:

• 1 и 2 Всесоюзные конференции "Методы и программы решения оптимизационных задач на графах и сетях", Новосибирск и Ташкент, 1982 и 1984;

• Международный симпозиум по проблемам модульных систем и сетей ICSNET'2001, Москва, 2001.

• Международная научно-практическая конференция ИНФОРА-ДИО'2000, 21-26 августа 2000 г., Омск.

• II Всесибирский конгресс женщин математиков, 15-18 января 2002 г., Красноярск.

• Международная конференция "Вычислительные технологии и математические модели в науке, технике и образовании", Алма-Ата, Казахстан, 18-20 сентября 2002 г.

• XXX Международная конференция "Информационные технологии в науке, образовании, телекоммуникации и бизнесе", Украина, Гурзуф, 19-28 мая 2003 г.

Объем и структура диссертации. Диссертация содержит 117 страниц машинописного текста, 35 рисунков и 7 таблиц и состоит из введения, четырех глав, заключения и списка литературы из 86 наименований.

Содержание работы

► Во введении рассматривается история вопроса. Отмечается важ-

ность исследований, указан вклад в решение этой задачи Г.Т. Арта-t монова, В.М. Вишневского, В.В. Епихина, С.Б. Кауля, А.К. Кельман-

са, В.И.Литвака, М.В.Ломоносова, М.И.Нечепуренко, В.П.Полесского, В.А. Скоробогатова, А.Я. Толчана, А.Д. Харкевича, Э.Мура [Е. Moor], К.Шеннона [К. Shennon], Р.Ван Слайка [R.Van Slyke], А. Шумана [A. Shooman].

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

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

Глава 1 содержит формальное описание задач и обзор применяемых методов.

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

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

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

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

Далее рассматриваются различные характеристики связности случайных графов. Отмечается, что многие характеристики, такие как число остовных деревьев или число разрезов, позволяют получать достаточно близкие к оптимуму структуры сетей и при этом их вычисление гораздо менее трудоемко. Собственные результаты автора по этому вопросу опубликованы в [3-5, 10, 12].

В качестве основного метода точного вычисления вероятности связности всех узлов сети (вершин графа) рассматривается метод ветвления (Мура-Шеннона). Предлагается модификация метода, позволяющая осуществлять ветвление по простым цепям (при их наличии в графе), что позволяет существенно снизить число рекурсий (порядка в раз, где Nc - число цепей, найденных за время

расчета, а 1С - средняя длина найденной цепи). Модификация метода основана на следующих доказанных теоремах.

Теорема 1.1. Пусть граф G содержит простую цепь из к ребер ei, в2, ■.., е* с вероятностями присутствияPi,P2, ■ - ■ ,Pk и соединяющую вершины sut. Тогда вероятность связности графа G равна

к

R(G) = (pi+p.t-PiPH)l[pj-R(G,(e1,e2,...,ek)) +

j=2

к

- Pi) IIpj- • -R(ö\{ei, e2,..., e*}) +

¿=2

к

(1 -P1-PH+ PlPH) Д Pi ■ R(G\{e 1, e2,..., ek, e,t}), (1) t=2

где G*(ei,e2,...,ek) - граф, получаемый из G последовательным стягиванием по ребрам ei, е2,..., ек, <?\{е1; ег,..., e,t} ~ граф, получаемый из G удалением цепи этих ребер с вершинами (кроме оконечных), a p,i - вероятность того, что существует ребро, непосредственно соединяющее оконечные вершимы разрешающей цепи.

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

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

Теорема 1.2. Пусть граф G содержит простую цепь из к ребер ei, е2,..., ел с вероятностями присутствияpi,p2, ■ ■ ■ ,Pk « соединяющую вершины sut. Тогда вероятность связности графа G равна k

R(G) = p1Y[pj-R(G'(e1,e2,...,ek)) + i=i

к

2> - Pi) ПPi ■ е2,..., е»>), (2)

i=1 jjn

при отсутствии ребра est и

R(G) =

к к Ы + P,t ~ PlPét) П Pi + P't Si1 ~ Pi) 1Ь

j=2 i=2 jqti

R(G*(ei,e2,...,ek) +

к к (i -pi-ри + i1 -л«) Si1 -pôJIPJ

j=2

R{G\{ei,e2,... ,ek,e,t}), при его наличии.

i=2

iiti

(3)

Эти результаты опубликованы автором в [8-11, 13]. Затем рассматривается авторская модификация еще одного существующего метода, на этот раз метода последовательно-параллельной редукции, предложенного A.M. Шуманом [A.M. Shooman]. Доказана теорема, позволяющая вместо ранее предложенной редукции пары последовательных ребер редуцировать цепь произвольной длины.

Теорема 1.3. Пусть граф Gi(n,m) содержит простую цепь из к ребер ei, е2,... ,ек с вероятностями присутствия pi,p2,... ,рк. Тогда надежность графа Gi (n, т) равна

k , к , R(Gx{n,m))= ДрЛ r^2pi-1-k+l)R(G2(n-k+l,m-k+l)), >=i ^ ¡=1 '

где граф Ог(п — к + 1,т — к + 1) получен из (?1(п,т) заменой этой цепи ребром с вероятностью присутствия

Р=~к-±-• (5)

1=1

Этот метод позволяет еще более сократить среднее время вычислений, так как ветвление начинается только после завершения редукций по всем цепям, что позволяет начать ветвление с графа меньшей размерности и, следовательно, на более ранних шагах доходить до рассчитываемых графов. Результаты автора по этому вопросу опубликованы в [14].

Обсуждается метод, основанный на использовании разрушения выделенного покрывающего дерева и предложенный Ченом и Ли [Y. Chen, J. Li]. Показана относительная неэффективность этого метода для графов уже средней размерности.

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

т—п+1

R(p)=pm+ £ а{(1-рУрт-\ (6)

i=l

что соответствует разложению по связным суграфам с заданным числом ребер.

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

максимума вероятности связности. На основании полученных полиномов для некоторых однородных по степеням вершин и кратностям ребер структур показывается, что в общем случае для равнонадеж-ных ребер различной надежности ребра могут соответствовать различные оптимальные структуры графа. Результаты автора по расчету коэффициентов полинома связности опубликованы в [4-6].

Глава включает также краткий обзор приближенных методов расчета вероятности связности графа. Автор реализовала эти методы (как и метод Мура-Шеннона и расчет коэффициентов полинома связности) в ППП ГРАФ-ЕС [1-5, 7].

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

Глава 2 посвящена задаче построения оптимально-связных структур сетей. Основное внимание уделяется оптимально-связным циклическим структурам, т.е. структурам, содержащим явно выраженные циклы.

Дается определение оптимально-связной структуры сети. Задача рассматривается применительно к случаю равнонадежных ребер. Приводятся общие требования, которым заведомо должна удовлетворять такая сеть. Прежде всего это требования однородности по степеням вершин, кратностям ребер и длинам цепей. Показано, что различной надежности одного ребра могут соответствовать различные оптимально-связные структуры графа. По этим результатам автором опубликованы работы [2, 4, 6].

Рассматривается вопрос оптимального добавления ребер к циклическим графам с целью повышения их вероятности связности. Доказаны оптимальные варианты добавления одного и двух ребер к циклу, сформулирована гипотеза об оптимальном варианте добавления до [п/2] ребер к циклу длины п.

Далее исследуется задача оптимального соединения циклов. Рассматриваются два варианта: пересечение двух циклов в двух вершинах и соединение их произвольным количеством ребер I < тт{п1, пг}. Для пересечения циклов доказана оптимальность такого выбора общих вершин, при котором циклы делятся на равные (с точностью до единицы) части.

Особо рассмотрен такой интересный случай, как "циклическое соединение циклов". Как и в предыдущем случае доказана оптимальность разбиения соединяемых циклов на цепи равной (с точностью до единицы) длины. Доказана

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

и ее усиленная формулировка

Теорема 2.3. При соединении двумя ребрами произвольного графа (7 и циклического графа С, в котором все ребра равнонадежны, при заданном выборе пары вершин графа (7, оптимальным способом выбора вершин соединения в С является любая пара вершин, которые делят цикл на цепи, длина которых отличается не более чем на единицу,

а также

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

и ее усиление

Теорема 2.5. При соединении четырьмя ребрами произвольного графа (7 и циклического графа С, в котором все ребра равнонадежны, при заданном выборе четырех вершин графа (7, оптимальным способом выбора вершин соединения в С является любая четверка вершин, которые делят цикл на цепи, длина которых отличается не более чем на единицу.

Теорема 2.6. При соединении четырьмя ребрами произвольного графа <3 и циклического графа С, в котором все ребра равнонадежны, при заданном выборе четырех вершин графа <7, оптимальным

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

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

Результаты автора, изложенные в главе, были опубликованы в [9-12].

Глава 3 посвящена программной реализации алгоритмов расчета вероятности связности графа, изложенных в главе 1.

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

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

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

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

Результаты автора по главе 3 опубликованы в [5-7, 13].

Глава 4 содержит результаты численных экспериментов и их обсуждение.

Прежде всего проведено сравнение методов Мура-Шеннона (классический и модифицированный варианты), последовательно-параллельной редукции и Чена-Ли. Экспериментально показано преимущество предложенных автором модификаций. Программы, реализующие эти модификации позволяют за разумное время рассчитывать графы с десятками вершин и ребер, что соответствует реальным задачам расчета характеристик локальных информационно-вычислительных сетей. Результаты сведены в таблицы. Ниже в качестве примера приводятся две из них, показывающие зависимость времени. счета от числа ребер при заданном количестве вершин и наоборот. Равенство значений для разреженных графов (число ребер не намного превосходит число вершин) объясняется тем, что собственно время расчета пренебрежимо мало и регистрировалось фактически только время генерации случайного графа и вывода результатов. В таблицах использованы следующие сокращения': МШ - метод Мура-Шеннона (вариант А, В, Е, Р), РМШ - расширенный метод Мура-Шеннона и ППР - метод Мура-Шеннона с последовательно-параллельной редукцией.

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

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

Результаты расчетов для 30 случайных 20-вершинных графов

Результаты расчетов для 30 случайных 30-реберных графов

Число ребер Время счета, с Число вершин Время счета, с

МШ РМШ ППР МШ РМШ ППР

19-22 0.11 0.11 0.11 15 239.09 28.02 18.57

23 0.17 0.22 0.16 16 150.11 27.25 14.33

24 0.17 0.28 0.11 17 126.44 18.85 7.86

25 0.22 0.72 0.22 18 69.92 11.53 5.00

26 0.49 0.88 0.27 19 31.03 9.73 3.46

27 1.10 1.54 0.38 20 17.08 6.65 1.64

28 3.46 2.58 0.66 21 3.84 2.96 0.82

29 5.21 3.18 0.88 22 3.41 2.15 0.77

30 25.01 6.65 1.64 23 1.16 1.27 0.50

31 30.10 8.63 3.24 24 0.44 1.04 0.33

32 47.29 10.88 4.06 25 0.27 0.66 0.22

33 267.00 37.08 8.23 26 0.22 0.39 0.22

34 337.02 54.82 12.83 27 0.22 0.27 0.22

35 967.23 107.77 23.21 28-31 0.22 0.22 0.16

Так, на рис. 1 показаны наименее надежный (один из вариантов)

Соответствующие полиномы надежности имеют вид

(р) = РЫ + 6р13(1 -р) + 15р12(1 - Р)2 + 16рп(1 ~ р)3, (7) дм (р) = Ри + 14р13(1 -р) + 81р12(1 - р)2 + 200рп(1 - р)3,

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

Рис. 2. Графики полиномов надежности графов с рис. 1 I

На графике, представленном на рис. 3, показан рост средней надежности графа с ростом числа его ребер при фиксированном числе вершин (в примере число вершин равно 16, а надежность ребра - 0.95). Для каждого значения числа ребер среднее рассчитывалось по 30 случайным графам.

16 18 17 18 19 20 21 22 23 24 26 2в 27 2А 26 30 31 32 33 т

Рис. 3. Средняя зависимость надежности 16-вершинного графа от числа его ребер

На этом же графике отмечены значения максимальных надежно-стей для графов <7(16,16), <7(16,17), <7(16,18), (7(16,20), <7(16,24) и 0(16,28) (0.7876, 0.9034, 0.9471, 0.9760, 0.9977 и 0.9989 соответственно) для той же надежности ребра. Очевидная разница значений также подтверждает тезис о необходимости проведения оптимизации.

Результаты по главе опубликованы автором в [13, 14].

В Заключении сформулированы следующие основные положения, выносимые автором на защиту:

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

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

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

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

5. Разработаны программы расчета вероятности связности случайного графа и расчета коэффициентов полинома связности, применимые к моделям сетей практически интересной размерности (до десятков элементов).

Основные публикации по теме диссертации

[1] Бежаева Б.Б.,..., Родионова O.K. и др. Пакет прикладных программ "Анализ и синтез сетевых моделей сложных систем". П007484, 1983. Государственный фонд алгоритмов и программ СССР. Алгоритмы и программы. Информационный бюллетень № 5162. ВНТИЦ ГКНТ. -М., 1984. - С. 49-50.

[2] Нечепуренко М.И., Майнагашев С.М., Родионова O.K. Структурная оптимизация графов с равно надежными ребрами // Труды XXI-

II Обл. научн.-техн. конф. НТО РЭС им. А.С.Попова. - Новосибирск, 1980. - С. 114-115.

[3] Родионова O.K. Число остовов //В препринте Л.Н.Постниковой. ППП ГРАФ/2. Генерация графов. - Новосибирск, 1980. - (Препринт / АН СССР. Сиб. отд-ние; ВЦ 266). - П. 5, 6.3. - С. 21-24.

[4] Родионова O.K. ППП ГРАФ/3. Связность мультиграфов с ненадежными ребрами (Атлас, процедуры). - Новосибирск, 1982. - 32 с. -(Препринт/ АН СССР. Сиб. отд-ние. ВЦ; 356).

[5] Родионова O.K. Комплекс программ ППП ГРАФ анализа связности ненадежных мультиграфов // Вычислительная техника и системный анализ. - Новосибирск, 1982. - С. 17-19.

[6] Родионова O.K. Процедуры построения оптимально-связных мультиграфов в ППП ГРАФ-ЕС // Методы и программы решения оптимизационных задач на графах и сетях. - Новосибирск, 1982. - Ч. I. -С. 171-172.

[7] Родионова O.K. Тексты программ "Связность" // Алгоритмы и программы решения задач на графах и сетях / Под ред. М.И. Нечепуреюсо. - Новосибирск: Наука, 1990. - С. 514.

[8] Родионов A.C., Родионова O.K. К вопросу практического использования формулы Мура-Шеннона для расчета вероятности связности локальных сетей // Тр. 2 Между нар. науч.-практ. конф. "Информационные технологии и радиосети", ИНФОРАДИО-2000. - Омск, 2000. - С. 67-69.

[9] Родионова O.K., Герцева A.A. О построении оптимально-связных графов // Мат. междунар. симп. по проблемам информатики, модульных систем и сетей ICS-NET'2001. - М., 2001. - С. 200-204.

[10] Родионова O.K. Связность случайных графов // В кн.: Попков В.К. Математические модели связности. Ч. И. Гиперграфы и гиперсети. -Новосибирск, 2001. Гл. 7. - С. 98-122.

[11] Родионова O.K. Некоторые вопросы расчета и оптимизации сетей с ненадежными ребрами //II Всесибирский конгресс женщин математиков, 15-18 января 2002. - Красноярск, 2002. - С. 176-178.

[12] Родионова O.K. О случайных графах с ненадежными ребрами и оптимизации их структуры // Труды ИВМиМГ СО РАН. Сер. Информатика - 2002. - Вып. 4. - С. 138-144.

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

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

РОДИОНОВА Ольга Константиновна

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ АНАЛИЗА И СИНТЕЗА ОПТИМАЛЬНО-СВЯЗНЫХ ИНФОРМАЦИОННЫХ СЕТЕЙ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Лицензия ИД № 02202 от 30 нюня 2000 г. Подписано в печать 17.09.2003 г.

Формат бумаги 60 х 841/1в Объем 0,9 п. л. 1,0 уч.-жэд. л. Тираж 70 экз. Заказ № 67

ООО "Омега Принт", Новосибирск-90, пр. Лаврентьева, б

i

РНБ Русский фонд

2005-4 16593

0 9 ürií 2003

Введение

1. Методы расчета характеристик связности случайного графа

1.1. Определения и обозначения

1.1.1. Понятие случайного графа.

1.2. Характеристики случайных графов.

1.3. Метод ветвления и его модификация.

1.4. Использование покрывающих деревьев при точном вычислении надежности графа.

1.5. Редукция цепей. 1.6. Расчет коэффициентов полинома связности.

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

1.8. Выводы.

2. Оптимизация структур сетей по критерию максимума вероятности связности

2.1. Оптимально-связные структуры сетей.

2.2. Оптимальная достройка кольцевых структур.

2.3. Оптимальное соединение кольцевых структур. 2.3.1. Пересечение циклов.

2.3.2. Соединение двух циклов.

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

2.5. Выводы.

3. Программная реализация алгоритмов

3.1. Поиск цепи.

3.2. Перенумерация вершин разрешающей цепи. 3.2.1. Реализация перенумерации.

3.3. Реализация расширенной формулы Мура-Шеннона

3.3.1. Варианты результатов стягивания и удаления

3.3.2. Оконечные рассчитываемые варианты графов

3.4. Реализация редукции цепей.

3.5. Реализация метода Чена-Ли.

3.6. Реализация расчета коэффициентов полинома связности

3.6.1. Оконечные состояния при расчете полинома связности

3.6.2. Ветвление по мультиребру.

3.6.3. Использование ветвления по цепям.

3.6.4. Учет "прикрепленных деревьев".

3.6.5. Учет "прикрепленных циклов".

3.7. Выводы.

4. Экспериментальное исследование алгоритмов

4.1. Формула Мура-Шеннона.

4.1.1. Классический вариант ветвления по ребрам

4.1.2. Расширенная Формула Мура-Шеннона

4.1.3. Применение последовательно-параллельной редукции

4.1.4. Метод Чена-Ли.

4.2. Расчет и использование полинома связности 97 4.2.1. Зависимость вероятности связности от типа графа

4.3. Выводы.

Задачи структурной оптимизации информационно-вычислительных сетей с точки зрения надежности и живучести, равно как задача расчета этих характеристик, являются одними из основных при проектировании подобных сетей [3, 6-8, 12, 23, 24, 28, 29, 38, 50, 56, 59-62, 68, 69, 72, 73, 75, 79, 80, 82]. Одним из важнейших показателей надежности работы сетей связи является их связность.

Существует много характеристик связности, что делает задачу не однозначной: реальным целям проектирования соответствуют различные целевые функции и ограничения [23]. В классической теории графов под связностью понимают либо реберную, либо вершинную связность.

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

Одной из наиболее распространенных характеристик связности сети является вероятность связности заданного подмножества вершин vi,.,vk, то есть вероятность того, что в конкретный момент времени между каждой парой этих вершин существует хотя бы один путь при заданных вероятностях присутствия ребер (эту вероятность для краткости часто называют надежностью ребра, в данном исследовании также используется этот термин). Существует два крайних варианта: к = 2 и к — п, где п — число вершин сети. Некоторые авторы (см., например, [51]) рассматривают в качестве основного показателя среднюю вероятность существования хотя бы одного пути по всем парам ребер. При рассмотрении сетей с равнонадежными каналами многие выводы, особенно при сравнении надежности различных структур, можно сделать с помощью так называемого полинома надежности или полинома связности, который показывает зависимость вероятности связности сети (графа) от надежности одного канала (ребра). Мы будем придерживаться термина "полином связности". На наш взгляд, он более точно соответствует смыслу.

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

Вопросом вычисления или оценки вероятности связности сетей занимались и занимаются многие исследователи как в России, так и за рубежом. Прежде всего надо упомянуть Артамонова Г.Т., Вишневского В.М., Епихина В.В., Кауля С.Б., Кельманса А.К., Литвака В.И., Ломоносова М.В., Нечепуренко М.И., Полесского В.П., Скоробогато-ва В.А., Толчана А.Я., Харкевича А.Д., Мура Э. [Moor Е.], Шеннона К. [Shennon К.], Ван Слайка P. [Van Slyke R.], Шумана A. [Shooman А.].

В данном исследовании в качестве модели сети рассматривается случайный граф.

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

1. Приближенные методы: а) метод Монте-Карло; б) методы, основанные на рассмотрении остовов; в) методы, основанные на рассмотрении разрезов.

2. Точные методы: а) методы ветвления, основанные на последовательном рассмотрении состояния ребер; б) методы, основанные на алгебре событий (комбинаторные); в) методы последовательной редукции, основанные на эквивалентных преобразованиях графа (методы последовательно-параллельной редукции).

Часто эти методы возможно комбинировать.

Необходимость разработки комбинированных алгоритмов вызвана по крайней мере следующими причинами [8]:

1. Крупномасштабные сети передачи данных обычно проектируются поэтапно, причем размерность сети на первых этапах невелика, что позволяет получать точное решение задачи топологической оптимизации с помощью комбинаторных алгоритмов. В то же время известные приближенные алгоритмы [12] не позволяют находить точное решение даже для сетей небольшой размерности. При этом лучшие эвристические алгоритмы по данным разработчиков дают погрешность до 10%.

2. Наличие точного решения позволяет оценить качество известных и вновь разрабатываемых.эвристических алгоритмов.

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

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

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

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

При рассмотрении оптимальных структур в качестве частного случая рассматриваются циклические (кольцевые) структуры, характерные для современных оптоволоконных сетей, построенных с использованием технологии SONET. Переход от классических SO NET-архитектур к ячеистым также дает иерархические структуры, которые возможно оптимизировать предлагаемыми методами.

Изложение материала организовано следующим образом:

4.3. Выводы

В главе экспериментально проверены предложенные методы расчета вероятности связности графа с ненадежными ребрами и коэффициентов I полинома связности. Основные выводы заключаются в следующем:

1) метод ветвления по цепям существенно снижает число рекурсий по сравнению с ветвлением по ребрам. Эффект ускорения тем выше, чем меньше средняя степень вершины графа;

2) метод последовательно-параллельной редукции с непосредственной редукцией цепей длины более 2 показал себя наиболее эффективным;

3) экспериментально подтверждена важность проверки возможности раннего завершения рекурсий по получению непосредственно вычисляемых графов (деревьев и циклов) и оптимального построения формул вычисления надежности графов малой размерности;

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

5) экспериментально подтверждена возможность точного расчета вероятности связности графов сетей практически интересной размерности - до десятков вершин и ребер.

Заключение

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

На защиту выносятся следующие положения.

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

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

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

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

5. Разработаны программы расчета вероятности связности случайного графа и расчета коэффициентов полинома связности, применимые к моделям сетей практически интересной размерности (до десятков элементов).

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

1. Автоматизация в проектировании. - М.: Мир, 1972. - С. 9-18.

2. Алгоритмы и программы решения задач на графах и сетях / под ред. М.И. Нечепуренко. Новосибирск: Наука, 1990. - 514 с.

3. Артамонов Г.Т., Морозов A.M. Метод построения квазирегулярных сетей связи с максимальной надежностью // Информационные сети и их структура. М., 1976. - С. 17-24.

4. Бежаева Е.Б., ., Родионова O.K. и др. Проблемно-ориентированный пакет прикладных программ "Анализ и синтез систем сетевой структуры". (ППП ГРАФ-ЕС). (Оперативно-информационный материал) ВЦ СО АН СССР. Новосибирск, 1984. 21 с.

5. Белоцерковский Д.Л., Вишневскмий В.М. Новый алгоритм генерации остовных подграфов для оптимизации топологии сетей передачи данных // Автоматика и телемеханика. 1997. — № 1. — С.108-120.

6. Вишневский В.М., Федотов Е.В. Диалоговая система топологического прооектирования сети связи ЭВМ // Вычислительные сети коммутации пакетов. / Ин-т электроники и вычислительной техники. Рига: ИЭВТ, 1983. - С. 25-99.

7. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. - 506 с.

8. Епихин В.В. Об одной задаче размещения ребра в графе // Системы распределения информации. М.: Наука, 1972. - С. 42-44.

9. Епихин В.В. Оценка числа деревьев графа // Методы теории телетрафика в системах распределения информации. — М.: Наука, 1975. С. 157-163.

10. Епихин В.В., Харкевич А.Д. К вопросу о построении оптимальных графов // Методы теории телетрафика в системах распределения информации. М.: Наука, 1975. - С. 146-157.

11. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. Киев: Техника, 1986. - 168 с.

12. Кауль С.Б. Вычисление одного класса характеристик случайного графа // Математические и имитационные модели сложных систем (СМ-6). Новосибирск, 1981. - С. 49-54.

13. Кауль С.Б., Попков В.К., Майнагашев С.М. Оптимальные структуры случайных графов // Алгоритмические основы обработки структурной информации. Новосибирск, 1981. — Вып. 85. — С. 35-47.

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

15. Кельманс А.К. Некоторые вопросы анализа надежности сетей // • Автомат, и телемех. 1965. - Т. XXVI, № 3. - С. 567-574.

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

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

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

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

20. Майнагашев С.М., Нечепуренко М.И. Об однородности оптимально-связных мультиграфов // Системное моделирование-5. — Новосибирск, 1979. С. 19-24.

21. Мур Э., Шеннон К. Надежные схемы из ненадежных реле // Кибернетический сб. М.: Иностр. лит., 1960. — Вып. 1. - С. 109— 148.

22. Надежность и живучесть систем связи под ред. Б.Я. Дудника. — М.: Радио и связь, 1984. 216 с.

23. Назаров А.Н. Модели и методы расчета структурно-сетевых параметров сетей ATM. М.: Горячая линия-Телеком, 2002. - 256 с.

24. Нечепуренко М.И. Случайные мультиграфы с равнонадежными ребрами // Системный анализ и исследование операций. — Новосибирск, 1979. С. 84-93.

25. Нечепуренко М.И. Уточнение оценок одной характеристики связности мультиграфа // Моделирование на вычислительных системах. Новосибирск, 1982. - С. 87-92.

26. Нечепуренко М.И., Майнагашев С.М., Родионова O.K. Структурная оптимизация графов с равно надежными ребрами // Труды XXIII Обл. н.-т.конф. НТО РЭС им. А.С.Попова, Новосибирск, 1980. -С. 114-115.

27. Полесский В.П. Структурная надежность однородных вероятностных сетей связи // Управление сетями связи и синтез управляющих устройств. М.: Наука, 1969. - С. 16-20.

28. Полесский В.П. Об одном способе построения структурно-надежной сети связи // Дискретные автоматы и сети связи. — М.: Наука, 1970. С. 3- 18.

29. Попков В.К. О решении некоторых задач на сверхбольших графах // Моделирование на вычислительных системах (СМ-5). — Новосибирск, 1982. С. 93-106.

30. Попков В.К. Математические модели связности. Ч. 1—3. — Новосибирск: Изд. СО РАН, 2000-2002.

31. Родионова O.K. Число остовов //В препринте Л.Н.Постниковой "ППП ГРАФ/2. Генерация графов", Препринт №266. Разделы 5,6.3. С. 21-24. ВЦ СО АН СССР, Новосибирск, 1980.I

32. Родионова O.K. ППП ГРАФ/3. Связность мультиграфов с ненадежными ребрами (Атлас, процедуры). — Новосибирск, 1982. 32 с. - (Препринт/ АН СССР. Сиб. отд-ние. ВЦ; 356).

33. Родионова O.K. Комплекс программ ППП ГРАФ анализа связности ненадежных мультиграфов // Вычислительная техника и системный анализ, Новосибирск, 1982. — С. 17-19.

34. Родионова O.K. Процедуры построения оптимально-связных мультиграфов в ППП ГРАФ-ЕС // Методы и программы решения оптимизационных задач на графах и сетях, Новосибирск, 1982. -Ч. I. С. 171-172.

35. Родионов А.С., Постникова JI.H., Родионова O.K. Комплекс процедур генерации случайных графов ППП ГРАФ-ЕС // Тез. докл. конф. ВНТО им. А.С.Попова "Вычислительная техника и системный анализ". Новосибирск, 1982. - С. 13-15.

36. Родионова O.K. Тексты программ "Связность" // Алгоритмы и программы решения задач на графах и сетях/ Под ред. Нечепу-ренко М.И. Новосибирск: Наука, 1990. - С. 514.

37. Родионова O.K., Герцева А.А. О построении оптимально-связных графов // Мат. междунар. симп. по проблемам информатики, модульных систем и сетей ICS-NET'2001. М., 2001. - С. 200-204.

38. Родионова O.K. Связность случайных графов //В кн.: Попков В.К. Математичес. модели связности. 4.II. Гиперграфы и гиперсети. Новосибирск, 2001. Гл. 7. - С. 98-122.

39. Родионова O.K. Некоторые вопросы расчета и оптимизации сетей с ненадежными ребрами //II Всесибирский конгресс женщин математиков, 15-18 января 2002. Красноярск, 2002. - С. 176-178.

40. Родионова O.K. О случайных графах с ненадежными ребрами и оптимизации их структуры // Труды ИВМиМГ СО РАН. Сер. Информатика 2002. - Вып. 4. - С. 138-144.

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

42. Сешу С., Рид М.Б. Линейные графы и электрические цепи. М.: Высшая школа, 1971.

43. Скоробогатов В.А. Анализ связности неографов // Автоматизация проектирования. Вычислительные системы. Новосибирск, 1975.- Вып. 64. С. 11-25.

44. Степанов В.Е. Комбинаторная алгебра и случайные графы // Теория вероятностей и ее применения. — 1969. Т. XIV, вып. 3.- С. 393-420.

45. Степанов В.Е. О вероятности случайного графа Gm{t) // Теория вероятностей и ее применения. 1970. — Т. XV, вып. 1. - С. 56-68.

46. Толчан А.Я. О связности сети // Проблемы передачи информации.- 1964. Вып. 17. - С. 3-7.

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

48. B. Berkowitz. Analysis of fracture network connectivity using percolation theory // International Journal of Rock Mechanics and Mining Sciences. 1996. - Vol. 33, Iss. 5. - P. 208A.

49. F. Boesch, F. Harary, C. Suffel and R. Tindell. The neighborhood inclusion structure of a graph // Mathematical and Computer Modelling.- 1993. Vol. 17, Iss. 11. - P. 25-28.

50. Cancela H., Urquhart M.E. Adapting RVR simulation techniques for residual connectedness network reliability models // Computers, IEEE Transactions. 2002. - Vol. 51, Iss. 4. - P. 439-443.

51. J. Carlier and С. Lucet. A decomposition algorithm for network reliability evaluation // Discrete Applied Mathematics. 1996. -Vol. 65, Iss. 1-3. - P. 141-156.

52. J. Carlier, Li Yu and J.-L. Lutton. Reliability evaluation of large telecommunication networks // Discrete Applied Mathematics. 1997. - Vol. 76, Iss. 1-3. - P. 61-80.

53. Y. Chen, J. Li, J. Chen. A new algorithm for network probabilistic connectivity // Military Communications Conference Proceedings, 1999, MILCOM 1999. IEEE. 1999. - Vol. 2. - P. 920-923.

54. Chen Jingcheng, Yu Erkeng, Zhang Xuesong, Wang Feng. Distribution network modeling and connectivity analysis // Power System Technology, 1998. Proceedings. POWERCON'98. 1998 International Conference 1998. Vol. 1. - P. 293-296.

55. Coyle Т., Arno R.G., Male P.S. GO-branch reliability methodology applied to gold book standard network // Industrial and Commerical Power Systems Technical Conference, 2002. 2002 IEEE. P. 73-81.

56. Coyle Т., Arno R.G., Hale P.S. Application of the minimal cut set reliability analysis methodology to the gold book standard network // Industrial and Commerical Power Systems Technical Conference, 2002. 2002 IEEE. P. 82-93.

57. Dotson W., Norwood F., Taylor, C. Reliability polynomial for a ring network // IEEE Transactions on Communications. 1993. - Vol. 41, Iss. 6. - P. 825-827.

58. H. A. Eiselt, Michel Gendreau and Gilbert Laporte. Optimal location of facilities on a network with an unreliable node or link // Information Processing Letters. 1996. - Vol. 58, Iss. 2. - P. 71-74.

59. Erdos P., Reyi. A. On random graphs // Publ. Math. (Debrecen). -1959. Vol. 6. - P. 290-297.

60. N. Fard and Tae-Han Lee. Spanning tree approach in all-terminal network reliability expansion // Computer Communications. 2001. - Vol. 24, Iss. 13. - P. 1348-1353.

61. Feige Uriel. A fast randomized LOGSPASE algorithm for graph connectivity // Theoretical Computer Science. -1996. № 169. - P. 147160.

62. Gilbert E.N. Random graphs // Ann. Math. Statist. Vol. 30, N°. 4. -P. 1141-1144.

63. Henzinger M.R., Rao S., Gabow H.N. Computing vertex connectivity:new bounds from old techniques // Foundations of Computer Science,1996. Proceedings., 37th Annual Symposium on, 1996. - P. 462-471.f

64. John Lee. Reliability models of a class of self-healing rings // Microelectronics and Reliability. 1997. - Vol. 37, Iss. 8. - P. 1179-1183.

65. M.L. Kansal, Arun Kumar, P.B. Sharma. Reliability analysis of water distribution systems under uncertainty // Reliability Engineering & System Safety. 1995. - Vol. 50, Iss. 1. - P. 51-59.

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

67. Chat Srivaree-ratana, Abdullah Konak and Alice E. Smith. Estimation of all-terminal network reliability using an artificial neural network // Computers & Operations Research. 2002. - Vol. 29, Iss. 7. - P. 849868.

68. Koval D.O., Xinlie Zhang, Propst J. Spreadsheet reliability model applied to gold book standard network // Industrial and Commerical Power Systems Technical Conference, 2002. 2002 IEEE. P. 66-72.

69. Chae Young Lee, Нее Kwun Cho Multicast routing considering reliability and network load in wireless ad-hoc network // Vehicular Technology Conference, 2001. VTC 2001 Spring. Vol.3, IEEE VTS 53rd. -P. 2203-2207.

70. J. Levendovszky, L. Jereb, Zs. Elek and Gy.Vesztergombi. Adaptive statistical algorithms in network reliability analysis // Performance Evaluation. 2002. - Vol. 48, Iss. 1-4. - P. 225-236.

71. Baoding Liu, K. Iwamura. Topological Optimization Models for Communication Network with Multiple Reliability Goals // Computers & Mathematics with Applications. 2000. - Vol. 39, Iss. 7-8. - P. 59-69.

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

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

74. Shaio J. A family of algorithms for network reliability problems // Communications, 2002. ICC 2002. IEEE International Conference. -2002. Vol. 4. - P. 2167-2173.

75. Shao Fang-Ming and Zhao Lian-Chang. Optimal design improving a communication network reliability // Microelectronics and Reliability.- 1997. Vol. 37, Iss. 4. - P. 591-595.

76. Fang-Ming Shao and Lian-Chang Zhao. Topological Optimization of Computer Network Expansion with Reliability Constraint, Computers к Mathematics with Applications. 1998. - Vol. 35, Iss. 11. - P. 17-26.

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

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

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

80. P. Tittmann. Partitions and network reliability // Discrete Applied Mathematics. 1999. - Vol. 95, Iss. 1-3. - P. 445-453.

81. Wang Wenyi and Zhang Hongfen. The methods of reduction in network reliability computing // Microelectronics and Reliability. 1997. -Vol. 37, Iss. 3. - P. 461-465.