论文摘要
我们生活在一个网络社会中。从某种意义上说,现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物质分派网路等各种网络所组成的复杂的网络系统。网络优化就是研究如何有效的计划、管理和控制这个网络系统。使之发挥最大的社会效益和经济效益。其中,度约束最小生成树问题是网络优化中一个常见的问题。现实世界中,有着许多这样的例子。例如:电路设计、管道铺设、计算机网络、通信系统等等。如何求解网络的度约束最小生成树问题已成为一个好的研究课题。本文的主要工作概述如下:在第二章,我们对单点度约束最小生成树问题进行了研究。首先给出了单点最大度约束最小树算法并分析了该算法的复杂度,该算法的复杂度为Ο（ n2）。为了便于在计算机上操作,我们给出了相应的权矩阵法。其次,经过分析我们发现:在网络G （V , E , G ）的所有生成树中,顶点v0的最小度刚好等于网络G （V , E , G ）关于v0的分裂数,在此基础上提出了单点最小度约束最小树算法,该算法的复杂度为Ο（ n2）。在以上两个算法的基础上,我们推导得出了网络单点度约束最小树存在的充要条件,最后给出了单点度约束最小树算法,对已有的Glove-Klingman算法进行了改进,大量仿真实验表明改进后的算法是非常有效的。在第三章,主要研究了度约束最小生成树问题,针对度约束最小树问题我们给出了一种新的快速近似算法,实验结果表明算法的性能良好。在此基础上,我们又提出了解决旅行商问题的两步法,大量的仿真实验表明这一算法取得了良好的效果。