基于改进Wang-代数生成连通图全部树的方法研究

Study on the Method of Spanning Connected Graph All Trees Based on Ameliorative Wang-Algebra

提出了一种求连通图全部树的方法,通过对Wang-代数的改进,在生成连通图的全部树时,无需进行环和运算,从而减少算法的时间复杂度;同时能求得图的全部树,并且能保证同一个树不会重复产生,克服了传统Wang-代数法求连通图的全部树时产生的冗余项问题.算例表明方法的正确性和可行性,可有效地应用于复杂电网络的拓扑分析.

How to count all spanning trees of topologic graph is important in graph theory. A method to generate all spanning trees of graph is presented in the paper, the method need not ring - sum - operation during generating all spanning trees of graph by ameliorating Wang-algebra, accordingly, it can reduce the Lime complexity of algorithm; at the same time, the method can generate all trees of graph and assures that the same tree will not repeated generate, comparing with the Wang-algebra method, the method geL over the question of computing the cancelled terms when generating all trees. The example makes clear that this method is validity anti feasibility, it can be effectively used to topologic analysis of complex electric networks.