摘要:最小生成树问题是一个经典的网络优化问题，而直径约束最小生成树问题是最小生成树问题的一种变形．出于实际应用的需要，本文在直径约束最小生成树问题的基础上，提出了度、直径约束最小生成树问题，建立了该问题的数学规划模型，并证明了该问题是一个NP-完全的难解问题，且给出了度、直径约束最小生成树问题的启发式求解算法，其时间复杂性为O(m2n)．分析和实例实验表明，该算法有良好的效果．
关键词：最小生成树问题；启发式算法；度约束；直径约束
目录
摘要
Abstract
第一章-引言-1
第二章 相关知识介绍-3
2.1 最小生成树-3
2.2 度约束最小生成树-3
2.2.1问题描述和模型-3
2.2.2 度约束最小生成树的快速算法-3
2.3 直径约束最小生成树-4
2.3.1 问题描述和模型-4
2.3.2 直径限制最小生成树问题的OTTC算法-4
第三章 DCBDMST问题描述和模型-6
第四章-DCBDMST问题的计算复杂性分析-7
第五章 启发式算法-9
第六章 数值试验-11
第七章-结语-13
参考文献-14
致谢-15
