Исследование и разработка методов анализа и синтеза оптимально-связных информационных сетей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Родионова, Ольга Константиновна

• Родионова, Ольга Константиновна
• кандидат технических наук
• 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. Разработаны программы расчета вероятности связности случайного графа и расчета коэффициентов полинома связности, применимые к моделям сетей практически интересной размерности (до десятков элементов).

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

Список литературы диссертационного исследования кандидат технических наук Родионова, Ольга Константиновна, 2003 год

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.