图论（7）生成树及其计数

目录

（一）、生成树的概念与性质

1.生成树的概念

2.生成树的性质

（二）、生成树的计数

1.凯莱递推计数法

2.关联矩阵计数法

3.矩阵树定理

例题：

（三）、回路系统简介

例题：

习题：

定义1：图G的一个生成子图T如果是树，称它为G的一棵生成树。若T为森林，称它为G的一个生成森林。

     首先回忆一下生成子图的概念，如果一个子图包含原图的所有顶点，则称该子图为原图的生成子图。

G中生成树的边称为树枝，G中非生成树的边称为弦。

定理1：每个连通图至少包含一棵生成树。

      利用破圈法，可以求出连通图的生成树，以及任意图的生成森林。1棵树也是特殊的森林哦。需要注意的是，连通图的生成树一般是不唯一的哦。

      我们已知树的边数为顶点数减一，所以推论也说明了树是同一顶点数条件下边数最少的图。

边被收缩定义：收缩一个边，即把这个边删掉，把这个边的两个端点合为一个点

凯莱定理：图G的生成树的个数，等于图G减去一条边的子图的生成树个数

                  加上图G收缩该边得到的子图的生成树个数。

例题：

结论：凯莱公式计算量很大，而且只能指出生成树的棵数，不能指出具体的每颗生成树长什么样

略过吧。网课没讲PPT里有，

方阵C的主对角线元素是对应顶点的度，其它元素是邻接矩阵中对应位置元素的负数。

生成树的棵树是方阵C的任意一个余子式的值。也就是说方阵C的任意一个代数余子式都相等咯。

1.矩阵树定理求生成树棵树

连枝也被称为弦

对于一个（n,m）图G，它有m条边，它的生成树T有n-1条边，所以G关于T的树枝有n-1条，

所以G关于T的弦有m-(n-1)条，每一条弦，都能产生一个基本圈，所以有m-n+1个基本圈，即基本

回路，构成了G对应于T的基本回路组Cf.

注意：图G对应于它的每一棵生成树T都有一个基本回路组。

注意：由基本回路作为基构成的向量空间。

先找到一颗生成树，根据该树找到基本回路组，然后用该基本回路组，通过环和运算来找到所有的回路。

基本回路找到所有回路的方法是环合运算，即并减交运算，先用两个基本回路并减交，再用三个，......，直到用上所有基本回路

两种证明方法上方已经写出