Degree-constrained Minimum Spanning Tree Algorithms

We live in a network society. In a sense, modern society is a computer information network, telephone communications network, transport network, energy and material distribution network and other network components of the complex network system. Network Optimization is the study of how effective planning, management and control of the network system. Make it to maximize the social and economic benefits. The degree-constrained minimum spanning tree problem is a common network optimization problem In the real world, have many examples of this. Such as: circuit design, pipeline laying, computer networks, communications systems, and so on. How to solve the constraint network minimum spanning tree problem has become a good research topic.The main work summarized as follows:In chapter two, we have a single point of the constrained minimum spanning tree problem was studied. First, we proposed the largest single point of minimum spanning tree algorithm and analysis of the complexity of the algorithm. Complexity of the algorithm is 2Ο( n). In order to facilitate the operation on the computer, we are given the right of the corresponding matrix method. Secondly, we found that through analysis: all the spanning tree in the network, the smallest degree of v0 on exactly equivalent to the number of its split. On the basis , we proposed the smallest single point of minimum spanning tree algorithm . Complexity of the algorithm is 2Ο( n). In the above algorithm on the basis of two, we deduced the sufficient and necessary conditions of k-gree-constraint minimum spanning tree exist, and give a single point of k-degree-constraint minimum spanning tree algorithm. The Glove-Klingman algorithm has been improved, a large number simulation experiments show that the improved algorithm is very effective.In chapter three, our main constraint on the degree-constraint minimum spanning tree problem,view of the binding problem, we give a new fast algorithm similar to the poblem. Experimental results show that the algorithm performance. On this basis, we proposed a two-step solution of the traveling salesman problem, a large number of simulation experiments show that the algorithm has produced good results.