标题：【机器学习｜数学基础】Mathematics for Machine Learning系列之图论（5）：树及其性质

文章目录

• 前言
• 系列文章
• 2.4 数及其性质

• 2.4.1 树的特征

• 定义2.10
• 定理2.4
• 定理2.5
• 定理2.6
• 定理2.7
• 推论2.7.1
• 定义2.11：生成树
• 推论2.7.2

• 2.4.2 生成树的数目

• 边 e的收缩
• 定理2.8：求图的生成树的个数
• 定理2.9：Caylay公式

• 结语

前言

Hello！小伙伴！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，有幸拿过一些国奖、省奖…已保研。目前正在学习C++/Linux/Python
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
机器学习小白阶段
文章仅作为自己的学习笔记 用于知识体系建立以及复习
知其然 知其所以然！

2.4 数及其性质

2.4.1 树的特征

定义2.10

无圈连通图称为树，记为

T中的顶点称为树叶

每个连通片都是树的图称为森林或林

孤立顶点称为平凡树

---

6个顶点的不同构树，共有6颗

定理2.4

是树的充分必要条件是：无环且任何两个顶点之间有唯一的路径

证明：

证必要性：是树无环且任何两个顶点之间有唯一的路径

因为是树

所以明显是无环的且为连通

对于中的任意两个顶点，必定存在一条路径

倘若之间还存在另一条路径

则一定存在一条边在上，但是不在上

或者在上，不在上

但是依然是连通的，设此时连通的路径为

连通说明，去掉边后，之间还是存在路径可以连通

所以

上一篇： 约瑟夫环的循环链表解法和数学公式解法

下一篇： 汉诺塔游戏与递归