几类图的支撑树的个数  

The Number of Spanning Tree in Several Classes of Graths

作　　者：左光纪[1] 

机构地区：[1]青海民族学院数学系,西宁810007

出　　处：《数学的实践与认识》2008年第12期107-112,共6页Mathematics in Practice and Theory

基　　金：教育部科学技术研究重点项目(205169)

摘　　要：推广了计算图的支撑树个数的递归公式,解释了组合计数原理的用法.用组合技巧和常系数线性递归序列的解法,对n步梯、n-棱柱、Mobius n-棱柱及有关图,找到了计算它们的支撑树的个数的若干公式.In this article, we generalize the recurrent formula for computing number of spanning tree of graph, and explan the use of combinatorial count principle. By combinatorial technic and solution of liner recurrent sequence with constant coefficient, some formula for calculus number of spanning tree of n-lader Ln, n-prism Pn, Mobius n-prism Xn and related graphs have been found.

关 键 词：连通图 支撑树 边的收缩 递推关系 

分 类 号：O157.5[理学—数学] O175.12[理学—基础数学]