АЛГОРИТМЫ РАСЧЕТА НАДЕЖНОСТИ СЕТИ НА ОСНОВЕ ДЕКОМПОЗИЦИОННОГО ПОДХОДА

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

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

Работа выполнена в рамках проекта № 0251-2021-0005 ПФИ ИВМиМГ СО РАН

Список литературы

1.           Colbourn Ch. J. The combinatorics of network reliability. N.Y: Oxford Univ, press. 1987. P. 160.

2.           Hebert Perez-Roses. Sixty Years of Network Reliability // Mathematics in Computer Science. 2018. V. 12. P. 275-293.

3.           Yeh W. C. Novel Binary-Addition Tree Algorithm (BAT) for Binary-State Network Reliability Problem // Reliability Engineering and System Safety. 2020. 208: 107448.

4.           Valiant L. The complexity of enumeration and reliability problems. // SIAM Journal on Computing. 1979. V. 8. N 3. P. 410-421.

5.           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.

6.           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.

7.           Мигов Д. А., Нестеров С. H., Родионов А. С. Методы ускорения расчета надежности сетей с ограничением на диаметр // Вестник СибГУТИ. № 1, 2014, С. 49-56.

8.           Wood R. К. Triconnected decomposition for computing К-terminal network reliability // Networks. 1989. V. 19. P. 203-220.

9.           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.

10.         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.

11.         Д. Мигов. Декомпозиция сети по сечениям при расчете ее надежности // Прикладная дискретная математика. 2020. № .47. С. 62-86.

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

13.         Migov D. A. Formuly dlya bystrogo rascheta veroyatnosti svyaznosti podmnozhestva vershin v grafah nebol’shoj razmernosti // Problemy informatiki, 2010. N 6. P. 10-17.

14.         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.