五面体平图中的生成树的构造与计数

Constructing and Enumerating the Spanning Trees of G(p,q)

首先给出了生成子图的定义,生成子图与生成树、含圈的生成子图的关系S(G)=C(G)+T(G);其次对于任意连通图,以p=4,q=6的完全图K4为例给出了生成子图个数的计算公式,同样以p=4,q=6完全图K4为例给出了生成树的构造定理和计数定理,提出了图S(G)生成树的计数方法和构造方法;最后,介绍了五面体平图生成子图个数的计算和各生成子图的构造,并验证了所给公式的正确性,从而解决了任意平图G(p,q)生成树的构造问题。

This study introduces first the definition of the spanning subgraph,and the relationship between constructing and enumerating the spanning trees： S（G）=C（G）＋T（G）;then about any connected graph,take p=4,q=6 as a full graph and take K4 as an example,to give out a computational formula of the number of subgraph;at the same time we give a constructive theorem and counting theorem, the method of graph of counting formula and construction way of G（p,q） as constructing and enumerating the spanning trees;at last we introduce the methods of enumerating and constructing the spanning trees of graph G（p,q）,show the rightness of all the formula,and a method of how to solve the question of construction method of any graph G（p,q） to enumerating the spanning trees.