Алгоритмы расчета надежности сети на основе декомпозиционного подхода
Автор: Коробов А.В., Мигов Д.А.
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая и системная информатика
Статья в выпуске: 4 (61), 2023 года.
Бесплатный доступ
В статье рассматривается задача точного расчета структурной надежности сети с ненадежными ребрами и абсолютно надежными вершинами. В качестве показателя надежности используется вероятность связности соответствующего случайного графа. Точный расчет данного показателя - NP-трудная задача, что делает его затруднительным для сетей реальной размерности. Предлагаются модификации метода факторизации, использующегося для точного расчета, основанные на декомпозиции сети по вершинному разрезу (сечению, сепаратору), образованному двумя вершинами. Для более эффективного использования декомпозиции учитывается структурная схожесть получающихся при декомпозиции подграфов - собственно подграфов, и графов, получающихся из них склейкой разрезающих вершин. Разработано три алгоритма, в среднем ускоряющих процесс вычисления вероятности связности произвольного графа. Для сравнения предложенных алгоритмов с методом факторизации и методом факторизации с предварительной декомпозицией приводятся результаты численных экспериментов.
Надежность сети, случайный граф, вероятность связности, метод факторизации, декомпозиция сети, сечение, сепаратор
Короткий адрес: https://sciup.org/143182818
IDR: 143182818 | DOI: 10.24412/2073-0667-2023-4-17-28
Список литературы Алгоритмы расчета надежности сети на основе декомпозиционного подхода
- Colbourn Ch. J. The combinatorics of network reliability. N. Y: Oxford Univ. press. 1987. P. 160.
- Hebert Perez-Roses. Sixty Years of Network Reliability // Mathematics in Computer Science. 2018. V. 12. P. 275-293.
- Yeh W.C. Novel Binary-Addition Tree Algorithm (BAT) for Binary-State Network Reliability Problem // Reliability Engineering and System Safety. 2020. 208: 107448.
- Valiant L. The complexity of enumeration and reliability problems. // SIAM Journal on Computing. 1979. V. 8. N 3. P. 410-421.
- Page L.B., Perry J.E. A Practical Implementation of the Factoring Theorem for Network Reliability // IEEE transactions on reliability. 1988. V. 37, N 3. P. 259-267.
- Rodionova О. K., Rodionov A. S., Choo H. Network Probabilistic Connectivity: Exact Calculation with Use of Chains // ICCSA-2004, Springer Lecture Notes in Computer Sciences. 2004. Vol. 3046. P. 315-324.
- Мигов Д. А., Нестеров C.H., Родионов А. С. Методы ускорения расчета надежности сетей с ограничением на диаметр // Вестник СибГУТИ. № 1, 2014, С. 49-56.
- Wood R. К. Triconnected decomposition for computing К-terminal network reliability // Networks. 1989. V. 19. P. 203-220.
- Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer Lecture Notes in Computer Sciences. 2006. V. 4097. P. 702-709.
- Burgos J. M., Amoza F. R. Factorization of network reliability with perfect nodes I: Introduction and statements // Discrete Applied Mathematics. 2016. V. 198. P. 82-90.
- Д. Мигов. Декомпозиция сети по сечениям при расчете ее надежности // Прикладная дискретная математика. 2020. № .47. С. 62-86.
- Мур Э., Шеннон К. Надежные схемы из ненадежных реле // Кибернетически сб. М.: Иностр. лит. 1960. Вып. 1. С. 109-148.
- Мигов Д. А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики. № 6, 2010, С. 10-17.
- Rodionov A., Migov D. Obtaining and Using Cumulative Bounds of Network Reliability // Chapter no 5 in: System Reliability. Edt. by Constantin Volosencu. ISBN 978-953-51-3705-4. Publisher: InTech. Rijeka, Croatia. 2017. P. 93-112.
