论文部分内容阅读
区域网络是给定一个无向图G=（V,E）,在图G中,存在一个子图是森林,森林中的若干个不相交的树称为若干个区域。该问题的目标是把该森林子图即若干个区域连结成一棵树,且使增加的边的权和最小。把该问题归结为图的Steiner tree问题,给出了求解该问题的一个近似算法,并证明其复杂性,最后用实例说明算法的准确性。