Researches On Reliability Indexes Of 2-Separable And 3-Separable Networks

Since the 21st century,with the rapid development of information technology represented by the Internet,human society has entered a complex network era.Common complex networks include communication networks,transportation networks,social networks,etc.These networks are closely related to human production and life,but they may not work properly due to either natural factors affecting nodes or edges or deliberated attacks.Therefore,under natural conditions,how to construct a network structure with the strongest or stronger communication ability is worthy of studying,and the results have important theoretical significance and practical application value.Given a network,assuming that the nodes are normally and the edges fail with equal and independent probabilities,the probability that all nodes in the network can be connected(communication)is a polynomial of the edge failure probability,which is known as the reliability polynomial of the network.In a network,as the coefficient sequence of the reliable polynomial is the sequence of the number of spanning connected subgraphs by the network,these coefficients will be important parameters for constructing a network structure with strong connectivity.The spanning connected subgraphs with the least number of edges are spanning trees,followed by the spanning connected unicyclic subgraphs and the spanning connected bicyclic subgraphs.In 1993,Colbourn proposed the question whether it can effectively calculate the number of spanning connected unicyclic(bicyclic)subgraphs a graph.Up to now,there are rich achievements on the number of spanning tree,but few results on the number of spanning connected unicyclic(bicyclic)subgraphs.Therefore,this thesis mainly focuses on the counting methods of spanning connected unicyclic subgraphs,spanning connected bicyclic subgraphs,and spanning trees of 2-separable and 3-separable networks.The main research work and results are as follows:(1)The counting problem of spanning connected unicyclic subgraphs in 2-separable networks is studied.A counting method of spanning connected unicyclic subgraphs in 2-separable networks is proposed,and applied to self-similar networks and pseudofractal scale-free networks,a linear algorithm is proposed to compute the number of spanning connected unicyclic subgraphs respectively.In addition,the entropy of spanning connected unicyclic subgraphs is defined,and the entropy of spanning connected unicyclic subgraphs in self-similar networks and pseudo-fractal scale-free networks is calculated.It is found that the entropy of spanning connected unicyclic subgraphs in these two kinds of networks is equal to the entropy of their spanning trees.(2)The counting problem of spanning connected bicyclic subgraphs in 2-separable networks is studied.A counting method for spanning connected bicyclic subgraphs in 2-separable networks is proposed.The method is applied to fractal scale-free networks and a linear algorithm is proposed to compute the number of spanning connected bicyclic subgraphs.In addition,the entropy of spanning connected bicyclic subgraphs is defined,and it is found that the entropy of spanning connected bicyclic subgraphs in fractal scale-free networks is equal to the entropy of spanning connected unicyclic subgraphs and the entropy of spanning trees.(3)The counting problem of spanning trees and spanning connected unicyclic subgraphs in 3-separable networks is studied.A counting method for spanning trees and spanning connected unicyclic subgraphs in 3-separable networks is proposed.The expressions for calculating the number of spanning trees and spanning connected unicyclic subgraphs in a class of 3-tree networks are obtained.The recursive relation for calculating the number of spanning connected unicyclic subgraphs in Apollonian networks is given.