Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

@TOC

前言

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

系列文章

【机器学习｜数学基础】Mathematics for Machine Learning系列之图论（1）：图的基本概念

【机器学习｜数学基础】Mathematics for Machine Learning系列之图论（2）：图的矩阵表示

【机器学习｜数学基础】Mathematics for Machine Learning系列之图论（3）：路径与连通

【机器学习｜数学基础】Mathematics for Machine Learning系列之图论（4）：有向图的连通性

2.4 数及其性质

2.4.1 树的特征

定义2.10

无圈连通图称为树，记为$T$

T中$d(v)=1$的顶点$v$称为树叶

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

孤立顶点称为平凡树

---

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

定理2.4

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

证明：

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

因为$G$是树

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

对于$V(G)$中的任意两个顶点$u,v$，必定存在一条路径$P_1(u,v)$

倘若$u,v$之间还存在另一条路径$P_2(u,v)\quad\{P_2(u,v)\neq P_1(u,v)\}$

则一定存在一条边$e=xy$在$P_1$上，但是不在$P_2$上

或者在$P_2$上，不在$P_1$上

但是$P_1\cup P_2 – e$依然是连通的，设此时连通的路径为$P(x,y)$

$P_1\cup P_2 – e$连通说明，去掉$e$边后，$x,y$之间还是存在路径可以连通

所以$P(x,y)+e$构成一个圈

说明$G$中含有圈，与$G$是树相矛盾

说明$G$中任意两点$u,v$之间只存在唯一的路径

证充分性：$G$无环且任何两个顶点之间有唯一的路径\Rightarrow$$G是树

因为$G$无环且任何两个顶点之间有唯一的路径

所以$G$是连通图

连通图就是图中任意两个顶点之间有路径存在，可以到达

假设$G$中含有一个圈$C$

则对于$C$中任意两个顶点

都存在两条路径连通这两个顶点

与且任何两个顶点之间有唯一的路径相矛盾

假设不成立，说明$G$中无圈

故$G$是树

无圈连通图为树

定理2.5

$G$是树的充分必要条件是：$G$连通且$\epsilon(G)=\nu(G)-1$

证明：

证必要性：$G$是树\Rightarrow$$G连通且$\epsilon(G)=\nu(G)-1$

$G$是树则$G$一定是连通的

下面着重证$\epsilon(G)=\nu(G)-1$

使用数学归纳法进行证明

假设当$v<n$时，$\epsilon(G)=\nu(G)-1$

当$v=1$时，$\epsilon(G)=0$，$\epsilon(G)=\nu(G)-1$成立

当$v=2$时，$\epsilon(G)=1$，$\epsilon(G)=\nu(G)-1$成立

当$v=n$时，在$G$中任意取一条边$e(u,v)\in E(G)$

令$G_0=G-e$

因为在顶点$u,v$之间只存在一条路径

所以$G_0$不连通且$w(G_0)=2$

设$G_0$中的两个连通片分别为$G_1,G_2$

显然有$G_1,G_2$是树，且均无圈，顶点个数均小于$n$

满足$\epsilon(G_1)=\nu(G_1)-1,\epsilon(G_2)=\nu(G_2)-1$

所以$\epsilon(G)=\epsilon(G_1)+\epsilon(G_2)+1=\nu(G_1)-1+\nu(G_2)-1+1=\nu(G)-1$

即

$\epsilon(G)=\nu(G)-1$

证充分性：$G$连通且$\epsilon(G)=\nu(G)-1\Rightarrow G$是树

因为树是无圈连通图，$G$已经是连通图，所以只需要证明其无圈

使用数学归纳法进行证明

假设$v<n$时，$G$连通且$\epsilon(G)=\nu(G)-1\Rightarrow G$无圈成立

当$v=1$时，$\epsilon(G)=\nu(G)-1=1-1=0\Rightarrow G$是无圈

当$v=2$时，$\epsilon(G)=\nu(G)-1=2-1=1\Rightarrow G$是无圈

当$v=n$时，则$G$中至少有一点$u$的次数为1

若$\delta \geq 2$，依据握手定理
$2\varepsilon=\sum d(v)\geq n \cdot \delta\geq 2n$
即$\varepsilon \geq n$
与$\epsilon(G)=\nu(G)-1$相矛盾
所以$G$中至少有一个顶点的次数为1（不可能为0，因为$G$是连通的，最小次数至少为1）

则$G-u$是连通的

$G$是连通的，且$u$的次数是1，所以$G$去掉$u$后的图依然是连通的

可以推导出：$\varepsilon(G – u)=\varepsilon(G) – 1=(\nu(G)-1)-1=\nu(G-u)-1$

因为对于$v<n$时，$G$连通且$\epsilon(G)=\nu(G)-1\Rightarrow G$无圈成立

所以$G-u$是无圈的

进而$G$是无圈的

对一个无圈图，添加一个一次顶点，得到的新图也是一个无圈图

定理2.6

$G$是树的充分必要条件是$G$连通，且对$G$的任一边$e$，$G-e$不连通

证明：

证必要性：$G$是树\Rightarrow$$G连通，且对$G$的任一边$e$，$G-e$不连通

$G$是树，则一定连通

设$e= uv$

因为$u,v$之间只有唯一的一条路径

所以$G-e$不连通，$w(G-e)=2$

证充分性：$G$连通，且对$G$的任一边$e$，$G-e$不连通\Rightarrow$$G是树

已知$G$连通，需要证明$G$是树

只需要再证明$G$中无圈

使用反证法

假设$G$中含有一个圈$C$

若$e$属于圈$C$中的一条边

则$G-e$也是连通的

与已知条件相矛盾

故假设不成立，$G$中无圈

所以$G$是树

定理2.7

（1）$G$是树的充分必要条件是$G$无圈且$\varepsilon(G) = \nu(G) – 1$

（2）$G$是树的充要条件是$G$无圈，对任意$e=uv\notin E(G)(u,v\in V(G))$,$G+e$恰有一个圈

推论2.7.1

每个非平凡树至少有两个一次顶点

证明：

$G$是一个非平凡树

使用反证法

假设一次顶点的个数小于两个

则至少有$v-1$个顶点的次数大于等于2

由握手定理，得

$2\varepsilon=\sum_{v\in V(G)}d(v)>2\cdot(v-1)$

化简，得到

$\varepsilon > v-1$

因为$G$是树，有$\varepsilon = v- 1$

故假设不成立

说明每个非平凡树至少有两个一次顶点

定义2.11：生成树

若$T$是$G$的生成子图，且$T$是树，则称$T$为$G$的生成树

推论2.7.2

$G$连通的充要条件是$G$有生成树

证明：

证必要性：$G$连通\Rightarrow$$G有生成树

设$G$连通，$T$是$G$中边数最少的连通生成子图

图连通，肯定是有生成子图的

若$T$中有圈

则可以去掉圈中任意一边$e$，$T-e$依然连通

但与假设$T$是$G$中边数最少的连通生成子图相矛盾

故$T$中无圈

因为$T$既是$G$的生存子图，且为树（连通且无圈）

所以$T$是$G$的生成树

说明：$G$连通\Rightarrow$$G有生成树

证充分性：$G$有生成树\Rightarrow$$G连通

设$T$是$G$的一个生成树

则$T$一定是连通的

因为$T$是$G$的生成子图且$T$连通

说明$G$一定也是连通的

2.4.2 生成树的数目

边$e$的收缩

图$G$的一边$e$被收缩，是指从$G$中把$e$删除，并将$e$的两端点重合，所得的新图记为$G\cdot e$

定理2.8：求图的生成树的个数

$e$是连通图$G$的非环状边，则图$G$的不同生成树数目$\tau(G)$为

$\tau(G)=\tau(G-e)+ \tau(G\cdot e)$

定理2.9：Caylay公式

$\tau(K_n)=n^{n-2}$

结语

说明：

• 参考于 课本《图论》
• 配合书中概念讲解 结合了自己的一些理解及思考

文章仅作为学习笔记，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正