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

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

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

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

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

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

【机器学习｜数学基础】Mathematics for Machine Learning系列之图论（10）：匹配基本定理

6.1 欧拉图

定义 6.1

设$G=(V, E)$是连通无向图

巡回

经过$G$的每边至少一次闭通路

从起点出发，要求必须回到起点 即终点就是起点

欧拉巡回

经过$G$的每边正好一次都巡回

经过每条边只能为1次 且恰好可以回到起点

欧拉图

存在欧拉巡回的图

欧拉道路

经过$G$的每边正好一次的道路

可以不需要回到起点 只要求经过所有的边且只经过一次

定理 6.1

$G$是非空连通图，则下面命题等价

• $G$是欧拉图
• $G$无齐次顶点
• $G=\bigcup_{i=1}^{d}C_i,\quad G_i$是圈，且$E(G_i)\cap E(G_j)=\phi(i\neq j)$

---

证明：$G$是欧拉图 $\Rightarrow$ $G$无齐次顶点

因为$G$是欧拉图，则必然存在一条欧拉巡回

设$W$是$G$中的欧拉巡回，得到

$\forall V \in V(G)$，$v$一定会在$W$上出现

设$v$出现了$k$次

则$d(v) = 2k$

即$v$是偶数次的

$v$具有任意性，故$G$是欧拉图 $\Rightarrow$ $G$无齐次顶点

当$v$不是起点或终点时，在欧拉巡回$W$中出现一次则度数一定是2 （前、后必定会连接一个顶点）
当$v$是起点或终点时，度数也是2，因为起点和终点在欧拉巡回中是同一个点
综上，对于$W$中任意一个点，出现一次，度数+2

证明：$G$无齐次顶点 $\Rightarrow$ $G=\bigcup_{i=1}^{d}C_i,\quad G_i$是圈，且$E(G_i)\cap E(G_j)=\phi(i\neq j)$

因为$G$无齐次顶点且为非空连通图，可得

$\delta(G)\geq 2$

从而$G$中必有圈$C_1$

令$G_1 = G- E(C_1)$，则$G_1$中仍然没有奇次顶点

因为圈中任意一个顶点都连接两条边，度数为2
去掉圈中一个点的边相当于度数减2
原图$G$中任意一个点的度数都为偶数，再减去2，依然为偶数
故$G_1 = G- E(C_1)$中无奇次顶点

若此时$G_1$中无边，则$G=G_1$，证明完成

若此时$G_1$中还有边，则$G_1$中的每个连通片中必定也是无奇次顶点的

说明$G_1$中连通片也是存在圈的

再去掉$G_1$中的一个圈$C_2$

得到$G_2$

$………..$

经过有限次数的迭代，去除圈

最后一定可以得到一个无边图$G_d$，所以有

$G = \bigcup_{i=1}^{d}C_i$

$C_i$是$G$中的一个圈，且$E(G_i)\cap E(G_j)=\phi \quad(i\neq j,1\leq i,j \leq d)$

可以理解为：$G$是由有限个圈$C_i$构成 且这些圈之间都没有边交集

证明：$G=\bigcup_{i=1}^{d}C_i,\quad G_i$是圈，且$E(G_i)\cap E(G_j)=\phi(i\neq j)$ $\Rightarrow$ $G$是欧拉图

当$d=1$时，$G$是欧拉图

$d=1$，说明$G$由一个圈组成，则必定存在一个欧拉巡回，故为欧拉图

当$d\geq 2$时

设$G$中有两圈$C_1$和$C_2$

因为$G$是连通的，且$E(G_i)\cap E(G_j)=\phi$

所以$C_1$与$C_2$至少有一个公共顶点$v_1$

则可以得到$C_1\cup C_2$是一条闭道路

$C_1\cup C_2$存在一个欧拉巡回
从$v_1$出发，先行遍$C_1$
回到$v_1$，再行遍$C_2$，最后可以回到$v_1$

则$C_1\cup C_2$是一个欧拉图

同理，$C_1\cup C_2\cup …. \cup C_d$都是欧拉图

故 $G=\bigcup_{i=1}^{d}C_i,\quad G_i$是圈，且$E(G_i)\cap E(G_j)=\phi(i\neq j)$ $\Rightarrow$ $G$是欧拉图

推论 6.1

设$G$是非平凡连通图

$G$有欧拉道路的充要条件是$G$最多只有两个奇次顶点

---

证明

证必要性：$G$有欧拉道路 $\Rightarrow$ $G$最多只有两个奇次顶点

设$G$中一条欧拉道路为$P$

$P=v_0e_1v_1e_2v_2….e_xv_x$

在这条道路中，除了起点和终点外，都是偶次顶点

不一定度数都等于2
因为欧拉道路中只是每条边出现了一次，顶点出现的次数可能不止一次

当起点和终点不是同一个点时，起点和终点度数则都是奇数

党起点和终点是同一个点时，起点和终点度数都是偶数

综上：$G$有欧拉道路 $\Rightarrow$ $G$最多只有两个奇次顶点

个人感觉：奇次顶点个数不是0个 就是 2个

证充分性： $G$最多只有两个奇次顶点 \Rightarrow$$G有欧拉道路

若$G$中无奇次顶点

由定理6.1可知道，$G$是欧拉图

则一定有一条欧拉巡回，也就一定有一条欧拉道路

欧拉巡回要求更严格，不仅需要每条边只可以走一次，还需要最后回到起点
而欧拉道路要求相对松一点，不需要最后回到起点，只要求每条边走一次，且走完所有边即可
即有一条欧拉巡回，就一定有一条欧拉道路

若$G$中恰好有两个奇次顶点时，设为$u$和$v$

则$G+e(uv)$无奇次顶点

故$G+e(uv)$中有一条欧拉巡回$C$

$C=ueve_1v_1….e_xu$

于是

$C-e=ve_1v_1….e_xu$

就是$G$中的一条欧拉道路

综上： $G$最多只有两个奇次顶点 \Rightarrow$$G有欧拉道路

结语

说明：

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

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

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