「这是我参与2022首次更文挑战的第31天，活动详情查看：2022首次更文挑战」。

@TOC

前言

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

系列文章

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

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

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

2.2 有向图的连通性

定义2.5

在有向图$D=(V,A,\psi)$中：

（1）设$\psi(a_i)=(v_{i-1},v_i)$，序列$v_0a_1v_1a_2v_2,…,a_kv_k$称为从$v_0$到$v_k$的有向通路

（2）弧不重复但顶点可以重复的有向通路称为有向道路

（3）顶点不重复的有向通路称为有向路径

（4）起点和终点重合的有向路径称为有向圈

（5）起点和终点重合的有向通路称为有向回路

---

有向通路：顶点可以重复、边也可以重复，只要求从一点到另一点即可
有向道路：$v_1e_1v_2e_2v_3e_3v_2e_4v_4$（顶点$v_2$重复，但没有边重复）
有向路径只要是顶点不重复即可：例如$v_1e_1v_2e_3v_3$
有向圈是在有向路径的基础上要求起点和终点为同一点，其实圈中依然没有重复的顶点

定义2.6

在有向图中：

（1）若存在从顶点$u$到$v$的有向通路，则称顶点$u$可到达$v$

（2）若改变某些弧的方向，能从顶点$u$到达$v$，则称顶点$u$与$v$是连接的，并称$u$与$v$之间存在一条半通路

定义2.7

在有向图$D$中，对任意两个顶点$v_i,v_j:$

（1）若$v_i$和$v_j$可以互相到达，则称D为强连通图

（2）若$v_i$可到达$v_j$，或$v_j$可到达$v_i$，则称$D$为单向连通图

（3）若$v_i$与$v_j$是连接的，则称$D$是弱连通图

（4）不满足以上条件的图称为不连通图

---

强连通图

弱连通图：$e$可以到达$a$，但$a$不能到达$e$，$a$和$e$没有相互到达，但满足其中一个顶点可以到达另一个顶点

相对于强连通图，要求更低
只需要任意两个顶点其中的一个顶点可以到达另一个顶点，不需要相互到达

弱连通图：在不看方向的情况下，任意的两个顶点之间可以到达

不连通图：

显然

• 强连通图必定也是单向连通图、弱连通图
• 单向连通图必定也是弱连通图

定义2.8

在有向图$D$中：

（1）通过所有顶点的有向回路，称为$D$的完备回路

（2）通过所有顶点的有向通路，称为$D$的完备通路

（3）通过所有顶点的半通路，称为$D$的完备半通路

定理2.2

一个有向图$D$是强连通的，当且仅当它有一条完备回路

---

证明

证必要性：有向图D是强连通的$\Rightarrow$图D有一条完备回路

假设图D有n个顶点：$v_1,v_2,…,v_n$

因为D是强连通的

所以$v_1$到$v_2$之间必然存在一条有向通路，设为$W_1$

同理

$v_2$到$v_3$之间必然存在一条有向通路，$W_2$

….

$v_{n-1}$到$v_n$之间必然存在一条有向通路，$W_{n-1}$

$v_n$到$v_1$之间必然存在一条有向通路，$W_n$

那么$W_1W_2,…,W_n$就可以表示：从顶点$v_1$到$v_n$，最后又回到$v_1$的一条通路，经过了D的所有顶点，且起点和终点重合，说明是一条完备回路

综上：有向图D是强连通的可以说明图D有一条完备回路

证充分性：有向图D有一条完备回路 $\Rightarrow$ 图D是强连通的

因为图D有一条完备回路，设为c

$c=v_1v_2….v_iv_{i+1}…v_jv_{j+1}…v_tv_1\quad( t\leq n)$

所以D中任意两个顶点$v_i,v_j$一定是在完备回路c中

从顶点$v_i$到$v_j$有通路：$v_iv_{i+1}…v_j$

从顶点$v_j$到$v_i$有通路：$v_jv_{j+1}…v_tv_1v_2…v_i$

故，对于任意两个顶点$v_i,v_j$，是可以互相到达的

说明图D是强连通的

推论2.2.1

一个有向图是单向连通的，当且仅当它有一条完备通路

推论2.2.2

一个有向图是弱连通的，当且仅当它有一条完备半通路

定义2.9

在有向图D中，最大的强连通子图$D_1$称为D的强连通片或强连通分图

所谓最大的强连通子图$D_1$，是指$D_1$是强连通的子图，且D不再包含$D_1$的强连通子图

定理2.3

有向图D的每一个顶点必在一个且仅在一个强分图中

推理2.3

有向图的各强分图无公共顶点也无公共边

结语

说明：

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

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

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