Orosz nyelvű Tudományos Szakcikk (Folyóiratcikk)

- SJR Scopus - Applied Mathematics: Q3

Azonosítók

- MTMT: 31444304
- DOI: 10.17223/20710410/47/6
- WoS: 000520869800009
- Scopus: 85086000665

Szakterületek:

We consider the problem of calculating such an indicator of network reliability as
the random graph probabilistic connectivity. It is assumed that the edges of the network
are subject to failures that occur independently of each other with given probabilities.
Network nodes are assumed to be absolutely reliable. The possibility of using network
decomposition via vertex cuts for the network reliability calculation is investigated.
By cut we mean a set of network elements, the removal of which makes the network disconnected.
The history of the development of such methods is given, and the place of our results
is indicated among them. The results related to the case of two nodes cuts are presented
in detail, including the results of the author and R. K. Wood (1985). Next, we consider
the cuts of arbitrary power. The results in this area were obtained by the author
(2004-2008) and J. M. Burgos (2016). Also, certain results using cuts were obtained
by the author for the cumulative bounds updating of the random graph probabilistic
connectivity (2012) and for the diameter constrained reliability calculation (2011-2012).
Author results include the general method, which gives the formulas expressing the
reliability of a network with a vertex cut through the reliabilities of its subnets
obtained by cut decomposition, as well as through reliabilities of the subnets, contracted
by all possible variants over cut vertices. On its basis, we derive such formulas
for cuts of two, three, and four vertices. Some of the results of the author were
previously published; some results are published for the first time, including the
correct formula for four vertices cut and the valid proof of the solvability of a
system of linear equations, which guarantees the existence of the above mentioned
formulas. The results of numerical experiments showing the applicability of the proposed
methods are given. For example, using the 3 cut formula the reliability calculation
of the 3 x 16 grid shows an acceleration of about 120 times compared with the factoring
method. For biconnected structures, a mathematical apparatus and an algorithm are
given that make it possible to effectively take into account all two-vertex sections
when calculating their reliability. Without such an approach we should use above mentioned
cut formulas recursively, for graphs obtained by cut decomposition and for these graphs
contracted by all possible variants over cut vertices. This inevitably leads to recalculation
of reliability for certain graphs. Using the proposed algorithm allows to avoid such
recalculation and additionally speeds up the reliability calculation for suitable
network structures.

2021-05-13 10:23