Research Of The Reconstruction Of Graphs Based On Invulnerability Recovery

Network invulnerability refers to the capability of the network to resist external damage,which a research hot topic in graph theory.The reason is that network structures are vulnerable and loads are heavy,the frequency and intensity of external attacks have increased.The research on invulnerability cannot be limited to invulnerability analysis and initial network design.If a network is destroyed after an external attack,it is a problem worth studying to recover it through reconstruction.If the network connectivity performance and connectivity efficiency can be enhanced through reconstruction,it is a significant mode for network optimization and transformation.In the thesis,the concept of network invulnerability and graph reconstruction and its research situation is introduced,and the main contents and results of invulnerability parameters and neighbor invulnerability parameters are summarized,and the invulnerability parameters with the concept of graph reconstruction are combined,the concept of subversion strategy and the S-T reconstruction of graphs are defined,and the concepts of connectivity optimization and scattering number optimization are proposed,the problem of S-T reconstruction of graph based on invulnerability recovery is discussed.The optimal reconstruction of connectivity and the scattering number of several types of basic graphs are given.A class of overlap graph with special structure is constructed,the optimal reconstruction problem of the overlap of two complete graphs based on connectivity optimization is obtained and the optimal reconstruction of the scattering number of three class of join graph with paths and cycles and the windmill graph are focused,and the reconstruction algorithms are given respectively.This thesis proposes and solves some basic problems of the graph reconstruction based on invulnerability recovery,which play a significant basic role for the subsequent in-depth study.