A Research Of Graph Reconstruction Based On Weighted Connectivity Optimization

In recent decades,there has been a great deal of interest in the study of network resilience and the design of reliable networks.When a network design is completed,its invulnerability can be analyzed by invulnerability parameters.For a network destructor,the network is expected to be destroyed at a minimum cost,while for the network designer,reconstruction needs to be considered to maximize its recovery.A network is essentially a weighted graph,and reconstruction can restore some functions to the network.Therefore,the reconstruction of the weighted graph has important theoretical significance and application value.In this thesis,the concepts of network invulnerability and weighted graph reconstruction are outlined by us,and summarize the work and research results on invulnerability parameters and neighborhood invulnerability parameters.In addition,we combine the invulnerability parameter and the weighted graph reconstruction,define the（S,T）subversion strategy of weighted graph and the concept of graph reconstruction in the sense of weighted connectivity,construct the weightedgraph with maximum or minimum weighted connectivity by studying the reconstruction methods based on weighted connectivity optimization for some typical graph classes,such as weighted tree,weighted circle,weighted wheel graph,etc.And the related algorithms are designed.Finally,The relationship between the size of the weighted connectivity of the same order weighted path,weighed comet graph and weighted star graph for a given weight set isK^w（P _n^R,w）≤K^w（C _a^R,_b,w）≤K^w（S₁,_m^R,w）.In this thesis,some problems of graph reconstruction based on weighted connectivity optimization are presented and solved,revealing the relationship between weighted paths,weighted comet graphs,weighted star graphs and the relationship between weighted connectivity and the magnitude of weights,weighted methods and graph structure.