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

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

作　　者：霍玉洪[1] 万禧[2] 李晓毅[3] 

机构地区：[1]淮南师范学院数学与计算科学系,安徽淮南232038 [2]安徽理工大学土木建筑学院,安徽淮南232001 [3]沈阳师范大学数学与系统科学学院,辽宁沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2010年第2期148-150,共3页Journal of Shenyang Normal University:Natural Science Edition

基　　金：安徽省教育厅高等学校科学研究项目(KJ2009B269Z)

摘　　要：首先给出了生成子图的定义,生成子图与生成树、含圈的生成子图的关系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.

关 键 词：生成树 构造 计数 生成子图 

分 类 号：O157.5[理学—数学]