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

• Мигов, Денис Александрович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Мигов, Денис Александрович

Введение

Глава 1. Существующие методы расчета вероятности связности случайного графа и возможности их ускорения

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

1.2. Методы редукции.

1.3. Учет точек сочленения и мостов.

1.4. Метод ветвления (Мура-Шеннона).

1.5. Вероятность связности графов малой размерности.

1.5.1. Вероятность связности 4-х вершинного графа.

1.5.2. Вероятность связности 5-и вершинного rpacba.

1.6. Вероятность связности подмножества вершин в графах малой размерности.

1.6.1. Формула вероятности связности подмножества вершин в графе произвольной размерности.

1.6.2. Вероятность связности подмножества вершин в 4-х вершинном графе.

1.7. Прочие методы.

1.8. Выводы.

Глава 2. Использование сечений в расчете вероятности связности случайного графа 34 2.1. Расчет с использованием двухвершинных сечений.

2.1.1. Формула вероятности связности графа с двухвершинным сечением.

2.1.2. Случай недвусвязного графа.

2.1.3. Расчет вероятности связности графа с использованием формулы (2.1).

2.1.4. Обобщение на произвольное количество компонент, получаемых при удалении сечения.

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

2.2.1. Циклические графы.

2.2.2. Продольные графы.

2.3. Расчет с использованием сечений произвольной мощности

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

2.3.2. Вероятности отделений.

2.3.3. Формула для вероятности связности с использованием сечения

2.3.4. Случай двухвершинного сечения

2.3.5. Случай трехвершинного сечения.

2.3.6. Случай четырехвершинного сечения.

2.4. Выводы.

Глава 3. Использование сечений в расчете вероятности связности подмножества вершин случайного графа ТО

3.1. Использование двухвершинных сечений для расчета вероятности двухвершинной связности.

3.1.1. Случай разделения графа двухвершинным сечением на два подграфа

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

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

3.3. Выводы.

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

4.1. Алгоритмы с использованием формул для графов малой размерности

4.2. Алгоритмы с использованием двухвершинных сечений

4.2.1. Формулировка алгоритмов.

4.2.2. Результаты численных экспериментов

4.3. Алгоритмы с использованием трехвершинных сечений.

4.4. Алгоритмы с использованием четырехвершинных сечений

4.5. Выводы.

Введение диссертации (часть автореферата) на тему «Расчет вероятности связности случайного графа с применением сечений»

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

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

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

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

Данная задача является NP-трудной [35, 47], поэтому ранее на практике использовали различные приближенные методы, тогда как точные методы представляли в большей степени академический интерес. Однако развитие вычислительной техники привело к возрождению интереса к использованию этих методов на практике, так как появилась возможность за разумное время рассчитывать надежность сетей малой и средней размерности (десятки узлов). С другой стороны, проверка приближенных методов на точность их работы также вызывает необходимость дальнейшего исследования точных методов.

Вопросом вычисления или оценки различных характеристик связности подмножества узлов сетей различной природы на моделях случайных графов (особенно в частных случаях, когда это подмножество состоит из двух или из всех узлов) занимались и занимаются многие исследователи как в России, так и за рубежом. Из отечественных прежде всего надо упомянуть Артамонова Г.Т., Вишневского В.М., Егунова М.М., Епи-хина В.В., Кауля С.Б., Кельманса А.К., Литвака В.И., Ломоносова М.В., Майнагашева С.М., Нечепуренко М.И., Полесского В.П., Попкова В.К, Родионова А.С., Родионову O.K., Скоробогатова В.А., Толчана А.Я, Хар-кевича А.Д. Из зарубежных исследователей это Colbourn C.J., Moor Е., Satyanarayana A., Shennon К., Shooman A.M., Van Slyke R., Wood R.K.

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Мигов, Денис Александрович

4.5. Выводы

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

1) Полученные в первой главе формулы для графов малой размерности существенно ускрояют процесс расчета вероятности связности графа произвольной размерности методом ветвления. Так, на полных графах использование формулы (1.8) дает ускорение приблизительно в три раза по сравнению с использованием ранее известной формулы для 4-х вершинного графа из [27], и приблизительно в пять раз по сравнению с методом ветвления до 2-х вершинных графов.

2) Полученные во второй и в третьей главах формулы для вероятности связности графа с сечением из двух, трех и четырех вершин существенно сокращают время вычислений для графов, в которых такое сечение имеется. Так, решетка 4 х 11 обсчитывается предложенным методом за 1,5 секунды, а методом ветвления (усиленным всеми возможными способами) — за 22,5 минуты. При этом, если подобное сечение отсутствует, время работы предложенного метода незначительно больше времени работы алгоритма ветвления.

Заключение

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Мигов, Денис Александрович, 2008 год

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

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

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

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

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

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

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

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

9. Мигов Д.А. Использование разрезов случайного графа для вычисления вероятности его связности// Труды конф. молодых ученых ИВМиМГ СО РАН. — Новосибирск: ИВМиМГ СО РАН, 2004. С. 133-140.

10. Мигов Д.А. Вероятность связности 5-и вершинного графа// Мат. Межд. семинара "Выч. методы и решение оптимизационных задач"(Кыргызская респ., Бишкек).

11. Новосибирск, 2004. — С. 113-116.

12. Мигов Д.А. Расчет вероятности связности .ЙГ-полюсной сети с применением двухвершинных разрезов// Труды конф. молодых ученых ИВМиМГ СО РАН. — Новосибирск: ИВМиМГ СО РАН, 2005. С. 95-101.

13. Мигов Д.А. Расчет вероятности связности сети с применением продольных разрезов// Труды конф. молодых ученых ИВМиМГ СО РАН. — Новосибирск: ИВМиМГ СО РАН, 2006. — С. 144-151.

14. Мигов Д.А. Методы ускорения расчета надежности Л'-полюсной сети, основанные на рассмотрении вершинных разрезов// Мат. IX межд. конф. "Проблемы функционирования информационных сетей". — Новосибирск: ИВМиМГ СО РАН, 2006. — С. 205-209.

15. Мигов Д.А. Использование вершинных разрезов для точного вычисления вероятности связности сети// Труды межд. конф. "Вычислительные и информационные технологии в науке, технике и образовании". — Казахстан, Павлодар: ПГУ, 2006. С. 51-56.

16. Мигов Д.А. Вычисление вероятности связности подмножества узлов сети с использованием двухвершинных разрезов// Мат. 2-ой Азиатской межд. школы-семинара "Проблемы оптимизации сложных систем". — Новосибирск: ИВМиМГ СО РАН, 2006. С. 134-138.

17. Мигов Д.А. Стратегия выбора разрешающего ребра в методе ветвления и применение сечений при вычислении вероятности связности графа// Мат. 4-ой Азиатской межд. школы-семинара "Проблемы оптимизации сложных систем"(респ. Алтай), 2008. В печати.

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

19. Мур Э., Шеннон К. Надежные схемы из ненадежных реле // Кибернетический сб.

20. М.: Иностр. лит., 1960. — Вып. 1. — С. 109-148.

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

22. Родионов А.С., Родионова O.K., Мигов Д.А., Мурзин М.Ю. Использование метода ветвления для точного расчёта вероятности связности случайного графа// Математика и безопас-ность информационных технологий. — М.: МГУ MIIHMO. 2005. С. — 333-341.

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

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

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

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

27. Baoding, Liu К. Topological Optimization Models for Communication Network- with Multiple Reliability Goals // Computers and Mathematics with Applications. — 2000. Volume 39, Issues 7-8. P 59-69.

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

29. Birnbaum Z.W., Esary J.D. Modules of coherent binary systems // SIAM J. Appl. Math. 1965. Vol. 13. P. 444-462.

30. Cancela H., Petingi L. Reliability of communication networks with delay constraints: computational complexity and complete topologies // IJMMS. — 2004. Vol 29. P. 15511562.

31. Chat Srivaree-ratana, Abdullah Konak and Alice E. Smith. Estimation of all-terminal network reliability using an artificial neural network // Computers and Operations Research, Volume 29, Issue 7, June 2002, p. 849-868

32. Charles J. Colbourn. The Combinatorics of Network Reliability. — Oxford University Press, New York, 1987.

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

34. Fang-Ming Shao, Lian-Chang Zhao. Topological Optimization of Computer Network Expansion with Reliability Constraint // Computers and Mathematics with Applications. — 1998. Volume 35, Issue 11. P. 17-26

35. Fard N., Tae-Han Lee Spanning tree approach in all-terminal network reliability expansion // Computer Communications. — 2001. Volume 24, Issue 13. P. 1348-1353.

36. Jacques Carlier, Corinne Lucet. A decomposition algorithm for network reliability evaluation // Discrete Applied Mathematics. — March 1996. Vol. 65, no. 1-3. P. 141156.

37. Jacques Carlier, Li Yu and Jean-luc Lutton // Reliability evaluation of large telecommunication networks. Discrete Applied Mathematics. — 1997. Volume 76, Issues 1-3. P. 61-80.

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

39. Kansal M.L., Arun Kumar P.B. Reliability analysis of water distribution systems under uncertainty // Reliability Engineering and System Safety. — 1995. Volume 50, Issue 1. P. 51-59

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

41. Lehman A. Wye-delta transformation in probabilistic // J. SIAM, 1963. V. 11. P. 713825.

42. J. Levendovszky, L. Jereb, Zs. Elek and Gy. Vesztergombi. Adaptive statistical algorithms in network reliability analysis // Performance Evaluation, Volume 48, Issues 1-4, May 2002, p. 225-236.

43. Yubin Chen, Jiandong Li, Jiamo Chen. A new algorithm for network probabilistic connectivity // Military Communications Conference Proceedings, 1999. Vol. 2. P. 920923.

44. Li Ying. Analysis method of survivability of probabilistic Networks// Military Comm. Technology Magazine. Vol. 48, 1993.

45. Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer-Verlag LNCS, Vol. 4097, 2006.— P. 702-709.

46. Nahman J. Fuzzy logic based network reliability evaluation // Microelectronics and Reliability. — 1997. Volume 37, Issue 8. P. 1161-1164.

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

48. Rosenthal A. Computing the realiability of comlex networks // SIAM J. Appl. Math. 1977. Vol 32. P. 133-152.

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

50. Shaio J. A family of algorithms for network reliability problems // Communications — 2002. Vol 4. P. 2167 -2173.

51. Shao Fang-Ming and Zhao Lian-Chang. Optimal design improving a communication network reliability // Microelectronics and Reliability. — 1977. Vol. 37, Issue 4. P. 591595.

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

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

54. 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. — 1991. Vol 2. — P. 1412 -1420.

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

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

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

58. Wood R.K. Triconnected Decomposition for Computing K-Terminal Network Reliability // Networks. 1989. Vol. 19. P. 203-220.883.