直径限制最小生成树问题研究

姜娜

(内蒙古大学 数学科学学院，内蒙古 呼和浩特 010021)

摘要：直径限制最小生成树问题是一个经典的网络优化问题。本文对直径限制最小生成树问题进行了综述，介绍了该问题的研究背景、数学模型以及相关的概念，并对问题的求解方法进行了归纳总结。

关键词：直径限制；最小生成树；非完全图；BDMST

收稿日期：*2015-04-27

作者简介：姜娜(1988- )，女， 蒙古族，内蒙古通辽市人，硕士研究生,研究方向：算法分析与设计。

中图分类号：O221.7文献标识码：A

0引言

最小生成树[1](Minimum Spanning Tree 简称MST)是图论、最优化理论、算法分析与设计等诸多领域研究的重要课题，在实际问题中应用广泛，如网络设计、公交车线路设计、排水系统设计等问题；通常情况下，这些问题可转化为最小生成树问题求解。不过，单纯的生成树问题是一个理想状态，在现实应用中，随着信息技术不断提高，大数据量、高传输速度、高清晰度要求现代网络不再是简单地连通，而是要高质量的传递信息，这就要求控制成本的同时网络的连通直径也不能没有限制。为了解决这类问题，便引出了直径限制最小生成树[2](Bounded-Diameter Minimum Spanning Tree,简称BDMST)问题。

直径限制最小生成树问题在资源优化问题中应用广泛，比如网络设计中的网络直径选择，将直接影响着网络的传输速度、网络能耗以及信号传递的快慢等，在路由优化中，直径的限制，也便于设备部署的设计和维护。因此，直径限制最小生成树问题的研究，有着重要的理论和应用价值。……