带有边集限制的最均匀支撑树问题

Minimal Balanced Degree Spanning Tree with edge set Restricted Problem

本文在无向网络中 ,建立了带有边集限制的最均匀支撑树问题的网络模型 .文中首先解决最均匀支撑树问题 ,并给出求无向网络中最均匀支撑树的多项式时间算法 ;然后 ,给出了求无向网络中带有边集限制的最小树多项式时间算法 ;最后 ,在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题 .

In this paper,we construct the network model of the minimal balanced degree spanning tree with edge set restricted problem in the undirected network.We give a polynomial time algorithm to solve the minimal balanced degree problem.Then we give a polynomial time algorithm to solve the minimal weight spanning tree with edge set restricted problem.At last we solve the minimal balanced degree spanning tree with edge set restricted problem based on the two solved problems.