离散数学 --- 树 --- 无向树，生成树与最小生成树

第一部分 --- 无向树

1.图为连通图的时候才能成为树

2.图为非连通图，但是每个其每个连通分支都是树的时候这个图称为森林

3.单独的树也能够称为森林，因为一个无向图为树时，它的连通分支就是它自己，此时它满足森林的定义：“每个连通分支都是树的无向图”

（简单来说就是满足树的定义的无向图也满足森林的定义，所以树可以是森林）

 

1.使用循环论证可以让我们的证明结果变为环状，而蕴涵关系又具有传递性，此时环上的任意一个结果都能够根据传递性推出环上的其它结果，从而完成我们的证明了

2.连通图只有一个连通分支，那就是连通图本身

 

 

 

---

第二部分 --- 生成树

1.某个图的生成子图：子图的点集和原图的点集一样，但是边集是原图的边集的子集

 

1.如果一个图非连通图的话，它的边集中的边必定缺少某两个结点之间的边

而这个非连通图的生成子图也必定不可能有原图就已经缺少的边，所以生成子图是非连通图

（生成子图的点集和原图一样，边集是原图的边集的子集）

而图是树的前提是图是连通图，所以非连通图的生成子图必不是连通图，连通图的生成子图可能是连通图

 1.为什么是直到删除的边的总数等于 m - n +1呢？

首先生成树是连通图的生成子图，也就是说生成树的点集合原图的点集一样，也就是说生成树中的点合原图中的点一样多。又因为生成树是树，所以它的边 m‘ = n - 1

又因为我们不停的删边后得到的图是生成树，也就是说删完边后剩下的边的总数等于 n - 1

又根据公式 ： 总边 - 删去的变数 = 剩下的变数

可得 删去的边数 = m - n + 1

2.避圈法的步骤：1.将结点放到对应位置上；2.任选两个结点连接一条边；3.根据不形成回路规则不断选边直到边数 = 结点数 - 1为止

3.我们可以发现通过两种方法得到的连通图的生成树是不一样的，也就是说一个连通图的生成树是不唯一的

 

上面这个算法的原理：

1.一个连通图中必定有至少一个生成树，这个生成树是连通图的生成子图（点集和原图的点集一样，边集是原图边集的子集） --- 也就是说，从图中的任意一个结点出发，以这个结点原有的边为基础连接与它邻接的点，然后再通过这些邻接的点继续连接与它们邻接的点 --- 最终我们一定能够得到一个符合要求的生成树（已经被连接过的点就打上标记，避免重复连接形成回路）

这种算法就称为广度优先搜索算法

 

---

第三部分 --- 最小生成树

 

1.第三步中选边有两个要求：

一.要选择当前没被选的边中的最小权重边（可以选多个）

二.我们选择的边不能够与已经被选中的边构成回路

上面这个算法每一次选边都需要进行一次回路判断，算法复杂度高，所以我们一般选择下面这个算法来寻找最小生成树

普里姆算法