摘要:最小生成树问题是一个经典的网络优化问题，而直径约束最小生成树问题是最小生成树问题的一种变形．出于实际应用的需要，本文在直径约束最小生成树问题的基础上，提出了度、直径约束最小生成树问题，建立了该问题的数学规划模型，并证明了该问题是一个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