【机器学习｜数学基础】Mathematics for Machine Learning系列之图论（8）：割边、割集、割点_图割集

前言

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）：有向图的连通性

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

【机器学习｜数学基础】Mathematics for Machine Learning系列之图论（6）：生成树算法

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

3.2 割边、割集、割点

3.2.1 割边与割集

定理3.4

设$G$是连通图，$e\in E(G)$，则$e$是$G$的割边的充要条件是$e$不含在圈中

---

证明

前提条件是：$G$是连通图，$e\in E(G)$

证必要性：$e是割边\Rightarrow$$e$不含在圈中

因为$e$是$G$的割边，所以$G-e$不连通

若$e$在$G$中的一个圈上，那么$G-e$依然会是连通的，产生矛盾

所以$e$一定是不含在圈中

证充分性：$e$不含在圈中$\Rightarrow$$e是割边$

设$e=uv$不在$G$的任何一个圈上

所以$u,v$之间必定只存在一条路径

若还存在其他一条路径$P(u,v)$，那么$P(u,v)+e$则会构成一个圈，与假设相矛盾

所以$G-e$不连通，故$e$是$G$的割边

推论3.4

设$G$连通，则$G$是树的充要条件是$G$的每条边都是$G$的割边

定理3.5

设$T$是连通图$G$的一颗生成树，$e\notin E(T)$，但$e\in E(G)$，则$T+e$含有唯一圈

---

证明

设$e=xy\notin E(T)$

则$T$中一定存在唯一一条路径$P_{xy}$

$T$是生成树，其中任意两个顶点有且仅有一条路径

所以$P_{xy}+e$便是含在$T+e$中的一个圈

又因为$P_{xy}$在$T$中是唯一的

树中任意两个顶点有且仅有一条路径，具有唯一性

所以圈$P_{xy}+e$也是唯一的

补充知识

设$S\subset V,S\ne \varphi ,S^{{}^{\prime }}=V-S\ne \varphi$

则用$[S,S^{{}^{\prime }}]$表示一个端点在$S$，另一个端点在$S^{{}^{\prime }}$的全体边组成的集合

显然$[S,S^{{}^{\prime }}]$是一个边断集

定义3.3：割集

设$G$连通，若$[S,S^{{}^{\prime }}]$只把$G$断成两个分支，则称$[S,S^{{}^{\prime }}]$为$G$的一个割集

定义3.4

（1）若$H$是$G$的子图，则称$\overline{H}=G-E(H)$为$H$在$G$中的余图

（2）若$G$连通，$T$是$G$的生成子树，则$T$的余图$\overline{(}T)=G-E(T)$称为余树

定理3.6

设$T$是连通图$G$的一棵生成树，对$T$的每条边$e$有：

• 余树$\overline{T}$不含$G$的割集
• $\overline{T}+e$含$G$的唯一割集

第二点的意思是：$\overline{T}+e$中含有$G$的唯一割集 或者 $G$的割集$\in \overline{T}+e$

---

证明：余树$\overline{T}$不含$G$的割集

设$E^{{}^{\prime }}\subseteq E(\overline{T})$，有

$$w(G-E^{{}^{\prime }})\le w(G-E(\overline{T}))$$

又因为

$$w(G-E(\overline{T}))=w(T)=1$$

所以$G-E^{{}^{\prime }}$一定是连通的

故$E^{{}^{\prime }}$不是$G$的割集

简单的理解：无论去掉余树中的多少条边，是不会影响生成树$T$的
所以都不会破坏$G$的连通度，故一定不含有$G$的割集

证明：$\overline{T}+e$含$G$的唯一割集

设$T$是$G$的生成树，那么它的每条边都是割边

故有：$T-e$不连通

用$S$表示$T-e$的一个连通片的顶点集，$\overline{S}=V(G)-S$

所以$B=[S,\overline{S}]$是$G$的一个边断集

且$B$完全含在$\overline{T}+e$中（$B$是$\overline{T}+e$的子集）

假设$B^{{}^{\prime }}$也是$G$的一个割集

那么$B^{{}^{\prime }}$中一个含有边$e$

则$B=B^{{}^{\prime }}$

这里有点绕
首先需要明确的是 割集中每条边所连接的两个端点分布在两个不同的连通片中
在$\overline{T}$所有边中， 符合上面条件：边的两端点分别连接两个连通片$S$和$\overline{S}$ 这些边的是固定且具有唯一性
有$B$和$B^{{}^{\prime }}$一定是需要完全含有这些边
若此时还有一条公共边$e$，那么就可以得出$B=B^{{}^{\prime }}$

所以$\overline{T}+e$含$G$的唯一割集

生成树与割集的对比

余树与割集

• 余树$\overline{T}$不含割集
• $e\in E(T),\overline{T}+e$含唯一割集

生成树与圈

• 生成树$T$不含圈
• $e\in E(\overline{T}),T+e$含唯一圈

3.2.2 割点

定理3.5

设$v$是连通图$G$的一个顶点，则下面命题等价

• $v$是割点
• 存在 V − { v } V-\{v\} V−{v}的一个划分 V − { v } = U ∪ W , U ∩ W = ϕ V-\{v\}=U\cup W,U\cap W=\phi V−{v}=U∪W,U∩W=ϕ,使得$\forall u\in U,\forall w\in E$，$u$到$w$的每条路径都必经过$v$
• 存在与$v$不同的两顶点$u,w$，使得$u$到$w$的每条路径都必经过$v$

推论3.7.1

树$T$的顶点$v$是$T$的割点的充要条件是

证明

前提条件：$T$是树

证必要性：$v$是$T$的割点$\Rightarrow$$d(v)\ge 2$

因为$v$是$T$的割点

所以一定存在不同于$v$的两个顶点$u,v$，其之间的路径经过$v$

在去除割点后的两个连通片中一边取一个顶点就可以满足条件了
而且至少存在两个顶点 可能是多个

故$d(v)\ge 2$

证充分性：$d(v)\ge 2$$\Rightarrow$$v$是$T$的割点

因为$d(v)\ge 2$

对于$v$，一定存在两个顶点$u,w$分别与$v$相邻（与$v$连接）

又因为$T$树，说明顶点$u$到$w$之间路径唯一，且经过$v$

故可得$v$是$T$的割点

推论3.7.2

无环的非平凡连通图至少有两个非割点

证明

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

有$T$中至少有两个一次顶点，它们是$T$的非割点

对$v\in V(G)$，有

$$w(G-v)\le w(T-v)$$

去掉生成树$T$中顶点$v$产生的影响大于去掉$G$中顶点$v$d产生的影响（从连通片的个数考虑）

所以$T$中的这两个非割点也一定是$G$的非割点

故$G$中至少含有两个非割点

结语

说明：

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

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

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