第一部分 --- 无向树
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.我们可以发现通过两种方法得到的连通图的生成树是不一样的，也就是说一个连通图的生成树是不唯一的
文章来源地址https://www.toymoban.com/news/detail-495621.html
上面这个算法的原理：
1.一个连通图中必定有至少一个生成树，这个生成树是连通图的生成子图（点集和原图的点集一样，边集是原图边集的子集） --- 也就是说，从图中的任意一个结点出发，以这个结点原有的边为基础连接与它邻接的点，然后再通过这些邻接的点继续连接与它们邻接的点 --- 最终我们一定能够得到一个符合要求的生成树（已经被连接过的点就打上标记，避免重复连接形成回路）
这种算法就称为广度优先搜索算法
文章来源：https://www.toymoban.com/news/detail-495621.html
第三部分 --- 最小生成树
1.第三步中选边有两个要求：
一.要选择当前没被选的边中的最小权重边（可以选多个）
二.我们选择的边不能够与已经被选中的边构成回路
上面这个算法每一次选边都需要进行一次回路判断，算法复杂度高，所以我们一般选择下面这个算法来寻找最小生成树
普里姆算法
到了这里，关于离散数学 --- 树 --- 无向树，生成树与最小生成树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[云原生] 二进制安装K8S一部分](https://imgs.yssmx.com/Uploads/2024/02/835642-1.png)
