用选边法求最优树

The Optimal Tree Determined by the Method of Election Edges

设图G=(V,E)是一个有限的无向连通图,这里V表示图G的顶点集,E表示图G的边集。每条边e_i∈E,还有一定的长度l_i,称l_i为边e_i的权。这种每条边标有权的连通图称为赋权连通图。如果图T是一个不包含有回路的连通图,则称图T是一棵树。如果图T是图G的一个生成子图,而且T又是一棵树。则称T是图G的一棵生成树。一棵生成树T的权W(T)是指图T中各条边权的总和,其中具有最小权的生成树称为最优树。赋权连通图的最优树往往是图论中具有较广泛地实际应用价值的。例如在若干城市之间修公路,铺铁路,或架通信线路等,都需要求出城市之间的最短连通线路,使修建成本降到最低。这种求出若干城市之间最短连通线路就是一个求出赋权连通图最优树的问题。

This paper gives an optimal tree determined by the method of election edges. It is the method that has line of wonderful thought and simple understanding. The method of election edges can determine an optimal tree of an arbitrarily degree-constrained connected weighted graph.