Vertex decomposition to calculate the network probabilistic connectivity

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$\times$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.