目录
（一）、生成树的概念与性质
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都有一个基本回路组。
注意：由基本回路作为基构成的向量空间。
先找到一颗生成树，根据该树找到基本回路组，然后用该基本回路组，通过环和运算来找到所有的回路。
基本回路找到所有回路的方法是环合运算，即并减交运算，先用两个基本回路并减交，再用三个，......，直到用上所有基本回路
两种证明方法上方已经写出
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/4714.html