本文主要研究限制顶点度的最小K-树问题,该问题是限制顶点度的最小支撑树和最小K-树问题的推广。限制顶点度的最小K-树问题具体描述如下:给定一个图G=(V,E;ω,K),|V|=n +1,ω:E→R+,K∈Z0+,及一个G中由s个顶点构成的集合S={vi1,vi2,...,vis},对于每个顶点vik∈S,有一对正整数aik,bik(aik≤bik),要寻找一棵K-树T,满足aik≤dT(vik)≤bik,目标是使得K-树T的权重之和达到最小,即ω(T)= min{Σe∈T’ ω(e)|T’是G的一棵K-树,aik≤dT’(vik)≤bik,(?)vik∈S}。本论文得到如下两个结果:(1)当S为非独立集时,本论文证明了限制顶点度的最小K-树问题是NP-完备的;(2)当S为独立集时,本论文设计了一个多项式时间算法DCMKT求解该问题,该算法的时间复杂度为O(n4)。在算法后面并用MATLAB语言编写程序实现了该算法。