The Critical Node Problem Based On Combination Of The Connectivity Index?degrees And Connected Branch Property

In this paper,we consider the critical node problem in an undirected graph,in which some nodes are deleted from a given undirected graph G to make the minimum connectivity of the resid-ual graph in some sense.Critical node problem has important applications in epidemic prevention network,communication network,transportation network and other fields.By analyzing the ad-vantages and disadvantages of previous research work,we put forward two new models,in which the connectivity index,the degree and the properties of connected components are considered to make the minimum connectivity in residual graph.In chapter 1,we firstly introduce the background and significance of critical node problem,and then present some research work on critical node problem based on the analysis of social network and system science.We list some main models on the critical node problem.Lastly,the preliminary knowledge of graph theory and dynamic programming algorithm are put forward.In chapter two,we analyzed the different models of critical node problem and found their deficiency in the balance description of the residual graph.It is possible that there exist multiple isolated nodes and a larger connected component after deleting some nodes,which results in the unbalanced distribution of the residual graph.Hence,we present two new models to minimize the sum of connectivity indexes and degrees satisfying the constraint condition on the properties of the connected components.They are "critical node problem by minimizing the sum of connectivity indexes and degrees with constraint on the size of the connectivity components" and "critical node problem by minimizing the sum of connectivity indexes and degrees with constraint on the size and the number of the connectivity components".Chapter 3 and chapter 4 are similar in the structures,and the main consideration is the solution of two new models in the case of tree with unit node weight.We firstly give a dynamic programming algorithm to solve each new model and analyze their time complexities.However,the time complexity of this dynamic programming algorithm is not polynomial time.Therefore,we improved the concrete implementation methods of the algorithm.A new data structure has been designed to form a continuous dynamic programming process-the left s-subtree Ti1:s of node i.We transform Ti1:s to the combination of left s-1-subtree Ti1:s-1 and subtree Tis.The objective function value of Ti1:s can be calculated by combining the solutions of these two subtrees.So the dynamic programming algorithm can be improved to done in polynomial time.Lastly,we also write MAT LAB programs to run the algorithm,and carry out a lot of numerical experiments.According to the experimental results,the efficiency of the algorithm is satisfactory.In chapter 5,we make a summary of the paper and propose some further research work in the future.