赋权有向图最小生成树的表上作业法

Table Operations Method for Minimum Spanning Tree Problem in Weighted Digraph

每一赋权有向图可用一个赋权表来表示。本文在借助于赋权表而不是赋权有向图本身讨论圈和生成树的基础上，给出了一种求解赋权有向图最小生成树的新方法——表上作业法，证明了方法的最优性。该方法简单易行，借助于计算机Ｓｐｒｅａｄｓｈｅｅｔ软件，如ＭｉｃｒｏｓｏｆｔＥｘｃｅｌ，可很方便地进行大规模复杂问题的求解。

Each diagraph with weights can be represented by a table called weighted table.Based on the discussion of cycles and spanning trees by the weighted table rather than by the digraph itself a new method to solve the minimum spanning tree problem,called table operations method(TOM),is proposed.The optimality of TOM method is proved.By means of spreadsheet softwares,such as Microsoft Excel,TOM can be used very conveniently to solve the large scale complex minimum spanning tree problems.