组合图中生成树的计数

Counting spanning trees in composite graphs

经典理论矩阵树定理用于图中生成树的计数并不实用,但利用Chebyshev多项式的性质作为工具,结合Kel’mans和Chelnokov的结果,可以给出较简单的方法对很多图中的生成树进行精确计数.通过给出一些组合图中生成树的计数进一步体现了该技术在其中所起的作用.

The classical Matrix Tree Theorem is infeasible for counting spanning trees in graphs. By employing the properties of Chebyshev polynomials and combining Kel＇mans and Chelnokov＇s result, it is possible to give a simpler method for accurately counting the spanning trees in many graphs. By means of presenting counting spanning trees in some composite graphs, the function of this technique in it is further embodied.