石磊，冯祖针，杨建强

(红河学院数学学院，云南蒙自661100)

度、直径约束最小生成树问题及其算法

石磊，冯祖针，杨建强

(红河学院数学学院，云南蒙自661100)

提出了度、直径约束最小生成树问题，证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法，其时间复杂性为O(mn).分析和实例实验表明，该算法有良好的效果.

最小生成树;启发式算法;度约束;直径约束

最小生成树(minimum spanning tree，MST)［1］问题是网络中的一个经典问题，被广泛应用于网络优化问题中.MST问题中2个变形问题度约束最小生成树(degree-constrained minimum spanning tree，DCMST)［2-3］问题和直径约束最小生成树(bounded diameter minimum spanning tree，BDMST)［4-5］问题受到普遍的重视和研究.文献［6］证明了DCMST问题和当直径约束值Δ∈［4，n-1)的BDMST问题为NP -完全问题.

DCMST问题和BDMST问题都有着很强的应用背景，如网络通信、资源优化、预测决策等.在某些领域求最小生成树时，其数学模型中节点同时受到度约束和直径约束，如覆盖多播路由［7］.现有研究并未考虑节点需同时满足度约束和直径约束的最小生成树问题，而此问题有一定的应用价值.因此本文提出度、直径约束最小生成树(degree-constrained，radius-constrained minimum spanning tree，DCBDMST)问题，它是一个NP-完全问题，即不存在多项式求解算法，同时给出了DCBDMST问题的启发式求解算法.

1 问题描述和模型

给定无向网络G=(V，E，D，W)，任意节点vi∈V，且|V|=n;任意边e=(vi，vj)∈E，且|E|=m.对∀vi∈V对应一个度约束值dmax(vi)∈N，称为度约束，D={dmax(vi)|vi∈V}.对∀(vi，vj)∈E对应一个非负权值w(vi，vj)，称为长度或代价，W={w(vi，vj) |(vi，vj)∈E}.

定义1［4］给定树T=(¯V，¯E)，树中2个节点的最大距离(所含边的数目)称为树T的直径，简记diam(T).

定义2度、直径约束最小生成树(DCBDMST)问题可以描……