特殊图的生成树的生成与计数

摘要

运用组合论、Feussner公式和Kirchhoff矩阵-树定理等研究了一些特殊图的生成树的生成与计数问题。
　　首先，给出了一种利用基本割集组的余组生成一个图的边收缩图的生成树的生成方法:对一个连通图，任意选取了它的一棵参考生成树T0，并指定它的k条收缩边，求出k条收缩边的基本割集组的余组，再利用基本割集组的余组与参考生成树之间的距离得到了含收缩边的边收缩图的全部互异生成树。
　　其次，介绍了几种特殊图的生成树的生成与计数，依次是旗子图，四边形链，六边行车厢图.给出了它们的生成树的一种新的生成方法—多项式相乘法.接着又给出了它们的生成树数目公式。
　　最后，对梯子图的生成树计数公式运用Feussner递推公式及常系数线性递归给出了一种更简单的证明方法，在此基础上又给出了一种带梯子的完全图的计数公式。

目录

声明

摘要

第一章 引言

1．1 研究背景

1．2 相关记号

1．3 本文的主要工作

第二章 用基本割集组的余组生成边收缩图的生成树

2．1 基本割集组及其余组

2．2 边收缩图的生成树的生成

第三章 链式图的生成树的多项式生成法与组合计数

3．1 旗子图的生成树的生成和计数

3．2 四边形链的生成树的生成和计数

3．3 六边形车厢图的生成树的生成和计数

第四章 带梯子的完全图的生成树的数目

4．1 梯子图Lm的生成树的计数

4．2 带梯子的完全图的生成树的数目

参考文献

致谢

作者简历及发表的学术论文情况