前言

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）：生成树算法

3.1 连通度

定义3.1 ：点断集

（1）设 $G$ 连通， $V^{‘}\subset V(G),G[V-V^{‘}]$ 不连通，则称 $V^{‘}$ 为 $G$ 的点断集

去掉 $G$ 的一些顶点后， $G$ 不再连通，则这些点为 $G$ 的一个点断集

（2）最小点断集中顶点的个数称为 $G$ 的连通度，记为 $K(G)$

若 $G$ 无点断集，则规定 $K(G)=v(G)-1$
若 $G$ 不连通，则 $K(G) = 0$
若 $G$ 平凡，则 $K(G) = 0$

由一个顶点组成的点断集称为割点

（3）若 $k \leq K(G)$ ，称 $G$ 为 $k-$ 连通图

上面这句话的意思可以理解为：若 $K(G)=3$ ，则可以称 $G$ 为3-连通图、2-连通图、1-连通图

为使 $G$ 称为不连通图或平凡图，至少需要删除 $k$ 个顶点，则 $k$ 为 $G$ 的连通度

定义3.2

（1）设 $G$ 连通， $E^{‘}\subseteq E(G),G-E^{‘}$ （从 $G$ 中删除 $E^{‘}$ 中的边）不连通，则称 $E^{‘}$ 是 $G$ 的边断集

删除 $G$ 中的一些边后，使得 $G$ 不再连通，则这些边组成 $G$ 的边断集

（2）最小边断集所含的边数称为 $G$ 的边连通度，记为 $K^{‘}(G)$

当 $|E^{‘}|=1$ 时，称 $E^{‘}$ 中的边 $e$ 为割边
若 $G$ 是平凡图，则 $K^{‘}(G)=0$
若 $G$ 是不连通图，则 $K^{‘}(G)=0$

割边：去掉 $G$ 中的一条边后， $G$ 不再连通，这条边被称为割边

（3）若 $k \leq K^{‘}(G)$ ，称 $G$ 为 $k-$ 边连通图

定理3.1

$K(G) \leq K^{‘}(G)\leq \delta$

证明：

设 $d(v)=\delta$ ，则去掉与 $v$ 相连的 $\delta$ 条边后

$G$ 不连通，有

$K^{‘}(G) \leq \delta$

当去掉 $\delta$ 条边后， $G$ 一定是不连通的

但是对于去掉小于 $\delta$ 条边后， $G$ 也可能是不连通的（比如去掉1条边 $G$ 就不连通了）

所以 $K^{‘}(G) \leq \delta$

证 $K(G)\leq K^{‘}(G)$ 稍微有点复杂，这里使用数学归纳法

当 $K^{‘}(G)=0$ 时说明 $G$ 为连通图或平凡图 $\Rightarrow K(G) = 0$

当 $K^{‘}(G)=1$ 时，说明 $G$ 存在割边，则一定存在割点 $\Rightarrow K(G) = 1$

设 $e=(u,v)$ 为 $G$ 的割边
则去掉 $u或v$ 的同时，一定会去掉割边 $e$ ，可以得到一个不连通图
所以 $G$ 存在割边，则一定存在割点

假设 $K^{‘}=k$ 时， $K(G) \leq K^{‘}(G)$ 成立

那么我们就需要证明当 $K^{‘}=k+1$ 时， $K(G) \leq K^{‘}(G)$ 成立

令 $K^{‘}(H)=k+1\geq 2$ ， $E$ 是 $H$ 的一个边断集，且 $|E|=k+1$

假设 $e=uv\in E$ ，则

$K^{‘}(H-e)=(k+1) – 1= k$

因为 $e$ 是最小边断集中的一条边
当 $e$ 不存在时
那么最小边断集的数量会减1

所以 $H-e$ 中，必定存在一个顶点集 $S$ ，使得 $[H-e] – S$ 不连通或平凡，且 $|S|\leq k$

因为 $K^{‘}(H-e)=k$
说明 $H-e$ 中最少去掉 $k$ 条边后， $H-e$ 不连通
若这 $k$ 条边所连接的顶点无重合
则至少需要去掉 $k$ 个顶点才会同时去掉这 $k$ 条边，说明 $|S|=k$
若这 $k$ 条边所连接的顶点有重合（即存在一个顶点连接不止这 $k$ 条边中的一条边）
所以去掉边断集中 $k$ 条边所需要去掉的顶点数是小于 $k$ 的，说明 $|S|<k$
综上， $|S|\leq k$