中文摘要：

研究内部节点受限的最小生成树问题：给定一个赋权无向完全图G=(V,E)，假定w:E→R+为边集E的权重函数且满足三角不等式，给定点集V的一个子集R(R.V)，目标是寻找图G的一个满足R中的点皆为内部顶点的权重最小的生成树。由于该问题是NP-困难的，提出了一个伪多项式时间最优算法，设计了一个近似比为2的多项式时间近似算法，并且给出例子以说明该近似比是紧的。

英文摘要：

The minimum internal nodes constrained spanning tree problem is considered.Give a metric graph G=(V,E)with a cost function w:E→R+and one subset R of V(R?V),the minimum internal nodes constrained spanning tree problem asks for a minimum weight spanning tree such that every vertex in R is not a leaf.As the problem is NP-hard,a Pseudo-polynomial time optimal algorithm is first provided,then a simple polynomial time approximation algorithm with a performance ratio of2is designed and an instance is constructed to show the ratio is tight.