求解度约束最小生成树问题的新算法  

New algorithm for solving degree constrained minimum spanning tree problem

作　　者：孙小军[1] 刘三阳[2] 王志强 

机构地区：[1]宝鸡文理学院数学系,陕西宝鸡721013 [2]西安电子科技大学理学院,西安710071 [3]总装备部驻天水地区军事代表室,陕西宝鸡721006

出　　处：《计算机工程与应用》2010年第36期40-42,47,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60674108;No.60574075);宝鸡文理学院院级科研项目(No.ZK0931)~~

摘　　要：针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。Regarding the characteristics of degree-constrained minimum spanning tree problem in network design and combi-natorial optimization,a new algorithm for the the k-degree minimum spanning tree on a designated point is presented on the base of the k minimum spanning tree’s algorithm.This new algorithm is supposed to change the minimum spanning tree in the optimal and operable way,and gradually make the degree of the designated point to be closer to the i-degree minimum spanning tree and finally reach the k-degree minimum spanning tree in network G.The correctness of this algorithm is proved by the given specific steps.Finallyt,he simulation and a practical transportation example turn out that the new algo-rithm is effective in the degree constrained minimum spanning tree problem.

关 键 词：度 度约束 最小生成树 第k最小生成树 最小k度生成树 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]