On The Mixed Reliability Of Networks With Both Vertex And Edge Failures

With the rapid development of science and technology,a variety of complex networks appear in human society,affect and change the way people live and work.However,vertices and edges in the network may fail due to various factors,which may cause the entire network to fail to work normally,or even cause heavy losses.Therefore,the study of network reliability has certain actual significance and value.In real network,vertex failure,edge failure or both vertex and edge failures may occur.There are many research results on network reliability in the case of vertex failure or edge failure.But there are relatively few research results in the case of vertex and edge failures.In order to realize the theoretical integrity,it is very necessary to study the mixed reliability of networks with vertex and edge failures.The research of network reliability can be roughly divided into two parts:Reliability analysis and design.Generally,network reliability analysis and design are studied in the following aspects:The existence of a mixed reliable uniformly optimal network in a network family with a given number of vertices and edges;Construction of a mixed reliable optimal network;Measurement of the mixed reliability of networks.In order to solve the above problems,we study the mixed reliable uniform optimality and local optimality of networks,and calculate the number of subtrees and the mixed reliability of the 3-cactus network under the assumptions that vertices fail with equal probability and edges fail with equal probability and the failures of vertices and edges are independent of each other.The main research contents and results of this thesis are as follows:(1)The mixed reliable local optimality and uniform optimality of networks with both vertex and edge failures are studied.The criteria of the mixed reliable local optimality of networks are given when the vertex failure probability and the edge failure probability approach 0 or 1,respectively.It is proved that there are mixed reliable uni#12(n(n-1))/2-1 edges,respectively.But there is no a mixed reliable uniformly optimal network in other network families.The problem on the existence of mixed reliable uniformly optimal networks with both vertex and edge failures is solved.(2)The mixed reliable local optimal networks in sparse network families are studied.The criterion of the mixed reliable local optimality of networks is further studied when both vertex failure probability and edge failure probability are sufficient.The mixed reliable local optimal networks in sparse network families with n vertices and n,n+1,n+2 edges are characterized,respectively.(3)The enumeration of subtrees of 3-cactus networks is studied.The number of subtrees is an important parameter to measure the mixed reliability of networks.A linear algorithm for calculating the number of subtrees in 3-cactus networks is proposed.The upper and lower bounds of the number of subtrees of these networks are determined,and the extremal graphs are characterized.Moreover,the lower bound of the number of subtrees of 3-cactus networks with maximum degree is given,and the extremal graph is characterized.In addition,linear algorithms are proposed to calculate the number of subtrees in Koch networks and hierarchical networks,respectively.(4)The calculation of the mixed reliability of 3-cactus networks is studied.The mixed reliability of networks is a key parameter to measure its reliability in both vertex and edge failures cases.A linear algorithm is proposed to calculate the mixed reliability of 3-cactus networks.The upper and lower bounds of the mixed reliability of 3-cactus networks are determined,and the extremal graphs are characterized.In addition,linear algorithms for calculating the mixed reliability of Koch networks and hierarchical networks are proposed,respectively.