Рассматривается задача расчёта такого показателя надёжности сети, как вероятность связности соответствующего случайного графа. Предполагается, что рёбра сети подвержены отказам, которые происходят независимо друг от друга с заданными вероятностями. Узлы сети полагаются абсолютно надёжными. Приводится общая методика получения формул, выражающих надёжность сети с сечением (вершинным разрезом) через надёжности её подсетей, получаемых при декомпозиции по сечению, а также через надёжности всевозможных вариантов стягивания таких подсетей по разрезающим вершинам. На её основе выводятся такие формулы для сечений из двух, трёх и четырёх вершин. Для двусвязных структур описаны математический аппарат и алгоритм, позволяющие при расчёте их надёжности эффективно учитывать все двухвершинные сечения. Приводятся результаты численных экспериментов, демонстрирующие применимость предлагаемых методов.
Скачать электронную версию публикации
Загружен, раз: 107
- Title Декомпозиция сети по сечениям при расчёте её надёжности
- Headline Декомпозиция сети по сечениям при расчёте её надёжности
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 47
- Date:
- DOI 10.17223/20710410/47/6
Ключевые слова
надёжность сети, случайный граф, вероятность связности, метод факторизации, декомпозиция сети, сечение, разрез, network reliability, random graph, probabilistic connectivity, factoring method, network decomposition, vertex cut, edge cutАвторы
Ссылки
Жуковский М. Е., Райгородский А. М. Случайные графы: модели и предельные характеристики // Успехи математических наук. 2015. Т. 70. № 1(421). С. 35-88
Colbourn Ch. J. The Combinatorics of Network Reliability. N.Y.: Oxford Univ. Press, 1987. 160 p
Valiant L. The complexity of enumeration and reliability problems // SIAM J. Comput. 1979. V. 8. No. 3. P. 410-421
Page L. B. and Perry J. E. A practical implementation of the factoring theorem for network reliability // IEEE Trans. Reliability. 1988. V. 37. No. 3. P. 259-267
Рябинин И. А. Логико-вероятностное исчисление как аппарат исследования надежности и безопасности структурно-сложных систем // Автомат. и телемех. 2003. Т. 7. С. 178-186
Satyanarayana A. and Wood R. K. A linear-time algorithm for computing K-terminal reliability in series-parallel networks // SIAM J. Comput. 1985. V. 18. P. 818-883
Shooman A. M. and Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction // IEEE Proc. Reliability and Maintainability Symp. 1992, Las Vegas, USA. N.Y.: IEEE Press, 1992. P. 441-448
Wood R. K. A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability // Networks. 1985. V. 15. No. 2. P. 173-190
Мочалов В. А. Метод синтеза отказоустойчивой струкутры сенсорной сети при наличии ограничений по размещению узлов сети в разнородном пространстве // T-Comm: Телекоммуникации и транспорт. 2012. Т. 6. № 10. С. 71-75
Rodionov A. S. and Rodionova O. K. Random hypernets in reliability analysis of multilayer networks // Lecture Notes in Electrical Engineering. 2015. V. 343. P. 307-315
Мелентьев В. А. Функция структурной отказоустойчивости и d-ограниченная компонента связности графа вычислительной системы // Прикладная дискретная математика. 2008. Т. 2. № 2. С. 102-106
Levendovszky J., Jereb L., Elek Zs., and Vesztergombi Gy. Adaptive statistical algorithms in network reliability analysis // Performance Evaluation. 2002. V. 48. No. 1-4. P. 225-236
Цициашвили Г. Ш., Осипова М.А., Лосев А. С. Вывод асимптотических констант для вероятности несвязности планарного взвешенного графа // Прикладная дискретная математика. 2014. № 2(24). С. 97-100
Лотоцкий А. Д. Исследование точных методов вычисления структурной надёжности компьютерных сетей // Инновации на основе информационных и коммуникационных технологий. 2014. Т. 1. С. 233-235
Родионов А. С., Родионова О. К. Некоторые методы ускорения расчета надёжности информационных сетей // Тр. 30-й Междунар. конф. «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (IT∙SF'2003), Гурзуф, Украина, 2003. Запорожье: Изд-во Запорож. ун-та, 2003. С. 215-217.
Мигов Д. А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики. 2010. Т. 6. С. 10-17
Chen Y., Li J., and Chen J. A new algorithm for network probabilistic connectivity // Proc. IEEE Military Communications Conf. V. 2. N.Y.: IEEE Press, 1999. P. 920-923
Tittmann P. Partitions and network reliability // Discr. Appl. Math. 1999. V. 95. No. 1-3. P. 445-453
Won J.-M. and Karray F. Cumulative update of all-terminal reliability for faster feasibility decision // IEEE Trans. Reliability. 2010. V. 59. No. 3. P. 551-562
Rodionov A., Migov D., and Rodionov O. Improvements in the efficiency of cumulative updating of all terminal network reliability // IEEE Trans. Reliability. 2012. V. 61. No. 2. P. 460-465
Martinez S. P., Calvino B. O., and Rocco S. C. M. All-terminal reliability evaluation through a Monte Carlo simulation based on an MPI implementation // European Safety and Reliability Conference: Advances in Safety, Reliability and Risk Management (PSAM 2011/ESREL 2012). Helsinki, 2012. P. 1-6
Родионов А. С., Сакерин А. В., Мигов Д. А. Некоторые вопросы параллельной реализации алгоритма полного перебора (на примере задач надёжности сетей) // Вестник Сиб-ГУТИ. 2014. Т. 4. С. 79-84
Hebert P.-R. Sixty years of network reliability // Mathematics in Computer Science. 2018. V. 12. P. 275-293
Попков В. К. Математические модели связности. Ч. 1-3. Новосибирск: Изд-во ИВМиМГ СО РАН, 2000-2002
Wood R. K. Triconnected decomposition for computing K -terminal network reliability // Networks. 1989. V. 19. P. 203-220
Hopcroft J. and Tarjan R. Dividing a graph into triconnected components // SIAM J. Comput. 1973. V. 2. P. 135-158
Мигов Д. А. Использование разрезов случайного графа для вычисления вероятности его связности // Труды конф. молодых ученых ИВМиМГ СО РАН, 2004. Новосибирск: ИВМиМГ СО РАН, 2004. С. 133-130
Мигов Д. А. Расчет вероятности связности сети с применением вершинных разрезов специального вида // Тез. докл. V Всерос. конф. молодых ученых по мат. моделированию и инф. технологиям, 2004. Новосибирск: ИВТ СО РАН, 2004. С. 24-25
Мигов Д. А. Расчет вероятности связности сети с применением продольных разрезов // Труды конф. молодых ученых ИВМиМГ СО РАН, 2006. Новосибирск: ИВМиМГ СО РАН, 2006. С. 144-151
Migov D. A., Rodionova O. K., Rodionov A. S., and Choo H. Network probabilistic connectivity: using node cuts // LNCS. 2006. V. 4097. P. 702-709
Мигов Д. А. Расчёт вероятности связности случайного графа с применением сечений: дис. . . . канд. физ.-мат. наук. Новосибирск: Институт вычислительной математики и математической геофизики, 2008. 96 с
Мигов Д. А. Методы расчета надежности сетей, основанные на использовании сечений // Вычислительные технологии. 2008. Т. 13. С. 425-431
Мигов Д. А. Расчёт надёжности сети с ограничением на диаметр с применением точек сочленения // Автоматика и телемеханика. 2011. Т. 7. С. 69-74
Burgos J. M. and Amoza F. R. Factorization of network reliability with perfect nodes I: Introduction and statements // Discr. Appl. Math. 2016. V. 198. P. 82-90
Burgos J. M. Factorization of network reliability with perfect nodes II: Connectivity matrix // Discr. Appl. Math. 2016. V.198. P. 91-100
Gutwenger C. and Mutzel P. A. A linear time implementation of SPQR-trees // LNCS. 2001. V. 1984. P. 77-90
Tsin Y. H. Decomposing a multigraph into split components // Proc. CATS'12, Melbourne, Australia. 2012. V. 128. P. 3-12
Карпов Д. В. Дерево разрезов и минимальный k-связный граф // Записки научных семинаров ПОМИ. 2014. T. 427. С. 22-40
Halin R. S-functions for graphs // J. Geometry. 1976. V. 8. No. 2. P. 171-186
Декомпозиция сети по сечениям при расчёте её надёжности | Прикладная дискретная математика. 2020. № 47. DOI: 10.17223/20710410/47/6
Скачать полнотекстовую версию
Загружен, раз: 314