求解区域网络问题的近似算法

An approximation algorithm about regional networks problem

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

Supposo that there is a graph , and containing a sub - graph which is a forest in G, some connected branches in the forest are named Regionals. Regional networks problem is to find the shortest connection to connect the forest to be a tree along pre - existing networks. In the text, we change the problem to the Steiner tree problem in graph, and give out an approximation algorithm and proved the algorithm complexity of this problem. In the last, we show the algorithm accuracy with an example.