Research On The Full Terminal Reliability Of The Hypernetwork

With the continuous development of human society,an increasing number of complex systems affecting people’s lives and even cognition have appeared in the real world,such as transportation networks,power networks,information networks and so on.Describing these complex systems with graphs leads to complex networks in general sense,which is an important research object of interdisciplinary-network science.The need of real life and the development of science and technology makes researchers realize that the description of complex systems requires new modeling methods.For new communication networks such as Wechat Group and QQ Group,it is more effective to study their characteristics if they are described by hypernetworks with hypergraphs as the underlying topological structures.Because hyperedges in hypergraphs can contain any number of vertices,they can be used to represent group relationships in complex systems without limitation to the relationship between two research individuals represented as nodes.At present,both the research and the application of hypernetworks have attracted people’s wide attention.Complex systems in different fields are the research objects of system theory.In system theory,all-termimal reliability is an important index of evaluating network reliability.The reliability research of general complex networks has obtained abundant research results.In graph theory,an important branch of combinatorial mathematics,network reliability has been studied as an important subject and to some extent,the research results have laid the theoretical foundation for its application in system engineering.With the further development of hypernetworks,it is found that the reliability of hypernetworks is an urgent problem to be solved.In view of research methods of the general complex network reliability and the related theory of hypergraph,this dissertation studies the all-terminal reliability of hypernetwork based on hypergraph under edge failure.The main research contents and results are reflected in the following four aspects:(1)The reliability of hypernetwork based on hypergraphs is systematically proposed and studied.The definition of all-terminal reliability of hypernetworks under edge failure and two basic calculation methods,state enumeration method and factor decomposition method,are given.The factorization method is used to simplify the calculation of the reliability of some hypernetworks.By comparative study of the reliability of hypergraphs and that of ordinary graphs,it is proved by examples that the reliability study of hypergraphs can not be transformed into ordinary graphs for the substitution study.For sparse hypernetworks,a universal algorithm for calculating their reliability is presented.The computational time complexity is polynomial with respect to the corresponding scale of the hypernetwork.After applying the calculated results of reliability to the optimization design of real-world networks,it is found that adjusting the connection way and adding a small number of edges can enhance the reliability of hypernetworks.(2)The properties and counts of generalized hypertrees which is closely related to the reliability of hypernetworks are studied.In this paper,we give the bounds of the edges of a class of generalized hypertrees with special properties,and characterize the structure of generalized hypertrees when the edges are attained.This kind of generalized hypertrees has great application potential in network design and network fault detection.Several types of non-uniform hypergraphs are constructed by graph operation,and the exact analytic expressions of the number of spanning hypertrees with different edges in these hypergraphs are given.(3)The reliability of typical hypergraphs is calculated.The reliability of the complete r-uniform hypergraph,and the Steiner system and it’s generalized ones is studied.A recursive method for calculating the reliability of the complete r-uniform hypergraph is given.The counting problem of spanning subhypergraphs(including spanning hypertrees)of complete r-uniform hypergraph is studied by using the canonical form of reliable polynomials.The generalized Steiner system breaks through the stringent restriction that the number of vertices in the hyperedge is equal.The construction methods of some non-trivial hypergraph classes are given,and the reliability of some small-scale Steiner systems and it’s generalized ones is simulated.(4)The optimal(or worst)hyperernetwork under certain conditions is constructed.This paper describes the characteristics of the optimal hypernetwork under certain conditions.The upper and lower bounds of the reliability of two kinds of hypernetworks are given,and the hypergraphs when the bounds are attained are characterized.