几种图的生成树的数目.pdfVIP

20 09 年 10 月第 5 期 　　　几种 图的生成树的数 目 85 几种图的生成树的数 目 严坤妹 ( ) 福建商业高等专科学校基础部 , 福建 福州 3500 12 　　 [摘 　要 ] 连通图 G的生成树是它的极小连通生成子图 。对给定 图 G来说 , 如何精确求解出图的全部生成树 的数 目, 是图论中一个重要的问题 ; 对于特殊的图类已经有着各种各样的计算方法 , 文章利用图的 K irchho ff矩阵研 究了一些图类的生成树的数 目, 并给出了相应的生成树数的计算公式 。 [关键词 ] 对偶图 ; 生成树 ; 生成子图 ; 计数 ; 矩阵树定理 [中图分类号 ] O 15716　　　　文献标识码 : A 　　　　文章编号 : 1008 - 494 0 (2 009) 0 5 - 00 85 - 04 　　一 个无 圈的连通 图称为一棵树 。一 个连通 图 G 分隔 。 的生成树是指顶点与 G相 同 、边集是 G 的边集子 集 1　三个 引理 的含边数最少 的连通子 图 。任意一个连通 图 G至 少 我们先 介 绍有 关定 义 和 约定 记号 : 设 v , v , 1 2 有一棵生成树 , 当 G 的生 成树不唯一时 , 计算生 成 ⋯, v 和 e , e , ⋯, e 分别表示 图 G的顶点和边 , n 1 2 m 树 的棵数具有重要 的理 论意义和实际意义 。我们 知 则图 G的邻接矩阵是指 A ( G) = [ ij ] , 其 中 ij是 道 , 对于顶点数为 n 的完全图 k 中的生成树 的数 目 , ( ) n 连接 v 和 v 的边的数 目。G的度矩阵是指 D G = i j 可 由 C yley 公式 给 出简 单精确 公式 。一般 情况下 , d i g (d ( v ) , d ( v ) , ⋯d ( v ) ) , (由 G的所有