返回：0100 离散数学课程总目录 · 上一章：0106 图的基本概念、通路回路与连通性 · 下一章：0108 树

1、资料来源与学习目标

本章对应北大离散数学刘田老师“集合论与图论”第七章。Auto_Tutor 中整理到的资料包括：

资料 内容
7.1 欧拉图 欧拉通路、欧拉回路、欧拉图、半欧拉图、有向欧拉图、Fleury 算法、逐步插入回路算法
7.2 哈密顿图 哈密顿通路、哈密顿回路、哈密顿图、必要条件、Ore 条件、Dirac 条件、竞赛图
007 习题与答案 习题 8.4、8.7、8.13，重点考察任意行遍点、哈密顿必要条件和半哈密顿充分条件

本章的核心目标：区分欧拉与哈密顿。欧拉关注“每条边恰好走一次”，判定容易；哈密顿关注“每个顶点恰好经过一次”，判定困难，更多依赖必要条件和充分条件。

2、颜色标注

颜色 含义
粉色 必背、必会证明、后续章节反复使用
蓝色 核心术语和定义
橙色 易错点、边界条件
绿色 理解提示和后续连接

3、章节主线

模块 本章要会什么 后续连接
欧拉图 会用度数判定欧拉图、半欧拉图 一笔画、边遍历
有向欧拉图 会用入度/出度判定 有向网络遍历
Fleury 算法 知道“除非别无选择，否则不走桥” 构造欧拉回路
哈密顿图 会区分哈密顿通路、回路、半哈密顿图 旅行、路径覆盖
必要条件 会用 p(G-V1) 反证非哈密顿 习题 8.7
充分条件 会用 Ore、Dirac 条件判定哈密顿 图存在性证明
竞赛图 知道竞赛图一定半哈密顿，强连通竞赛图哈密顿 有向图应用

4、欧拉图

4.1 基本定义

欧拉通路：

1
经过图中所有边的简单通路。

半欧拉图：

1
有欧拉通路的图。

欧拉回路：

1
经过图中所有边的简单回路。

欧拉图：

1
有欧拉回路的图。

欧拉问题看的是边：每条边恰好走一次；顶点可以重复经过。

4.2 无向欧拉图的充要条件

定理 8.1：设 G 是无向连通图，则以下三件事等价：

1
2
3
(1) G 是欧拉图。
(2) G 中所有顶点都是偶数度。
(3) G 是若干个边不交的圈的并。

证明思路：

方向 思路
(1)⇒(2) 欧拉回路每进入一个顶点，就必须再离开，贡献成对出现
(2)⇒(3) 在偶度连通图中找圈，删去圈边后各点仍为偶度；对每个连通分支重复
(3)⇒(1) 有公共点但边不交的回路可以在交点处拼接

“连通 + 全偶度”是无向欧拉图最核心的判定。若忽略连通性，两个互不相交的圈每个点也是偶度，但整体没有一条欧拉回路能走完所有边。

4.3 无向半欧拉图的充要条件

定理 8.2：设 G 是无向连通图，则：

1
G 是半欧拉图 ⇔ G 中恰有 2 个奇度顶点。

更完整地说：

情况 结论
奇度顶点 0 个 有欧拉回路，是欧拉图
奇度顶点 2 个 有欧拉通路，是半欧拉图；欧拉通路从一个奇度点出发，到另一个奇度点结束
奇度顶点超过 2 个 不是半欧拉图

一笔画口诀：没有奇点就能“回到起点”；两个奇点就能“从一个奇点画到另一个奇点”。

4.4 有向欧拉图的充要条件

定理 8.3：设 G 是有向连通图，则：

1
2
3
G 是欧拉图
⇔ ∀v∈V(G), d^+(v)=d^-(v)
⇔ G 是若干个边不交有向圈的并。

这里的“连通”通常按底图连通理解，同时入度出度相等保证每次进入顶点后都能离开。

4.5 有向半欧拉图的充要条件

有向图存在欧拉通路但不一定回到起点时，度数条件为：

1
2
3
有一个顶点 s 满足 d^+(s)=d^-(s)+1；
有一个顶点 t 满足 d^-(t)=d^+(t)+1；
其余顶点满足 d^+(v)=d^-(v)。

此时欧拉通路从 s 出发，到 t 结束。

课件抽取文字里“有向半欧拉图的充分必要条件”一页把“有向连通图”误抽成了“无向连通图”。这里按有向图结论整理。

5、求欧拉回路的算法

5.1 Fleury 算法

Fleury 算法也叫避桥法：

1
2
3
4
5
从任意一点开始；
沿着没有走过的边向前走；
在每个顶点，优先选择剩下图中的非桥边；
除非只有唯一一条边，否则不要走桥；
直到得到欧拉回路或宣布失败。

定理 8.5：

1
设 G 是无向欧拉图，则 Fleury 算法终止时得到的简单通路是欧拉回路。

迭代形式：

1
2
3
4
5
6
P_0:=v
设 P_i=v_0 e_1 v_1 e_2 ... e_i v_i 已经行遍
令 G_i=G-{e_1,e_2,...,e_i}
选择与 v_i 关联的下一条边 e_{i+1}
除非别无选择，否则 e_{i+1} 不是 G_i 中的桥
若 G_i 仍有边，则继续；否则停止

Fleury 的直觉是：桥一旦走掉，就可能把剩余未走边隔在另一边，所以尽量晚走桥。

5.2 逐步插入回路算法

思路：

1
2
3
4
5
先找一个简单回路；
再在已有回路上找一个仍有未用边的顶点；
从该顶点出发找新的简单回路；
把新回路插入旧回路；
重复直到所有边都被用完。

这个算法正好对应“欧拉图 = 若干个边不交圈的并”的证明。

6、哈密顿图

6.1 基本定义

哈密顿通路：

1
经过图中所有顶点的初级通路。

半哈密顿图：

1
有哈密顿通路的图。

哈密顿回路：

1
经过图中所有顶点的初级回路。

哈密顿图：

1
有哈密顿回路的图。

哈密顿问题看的是顶点：每个顶点恰好经过一次；不要求经过所有边。

欧拉与哈密顿对比：

项目 欧拉 哈密顿
核心对象 边 顶点
通路要求 经过所有边 经过所有顶点
顶点是否可重复 可以 不可以
边是否可遗漏 不可以 可以
判定难度 有漂亮充要条件 一般很难

6.2 哈密顿图的必要条件

定理 8.6：设 G=<V,E> 是无向哈密顿图，则对 V 的任意非空真子集 V_1 有：

1
p(G-V_1) ≤ |V_1|

证明直觉：

1
2
3
哈密顿回路 C 是 G 的生成子图。
从一个圈里删掉 |V_1| 个顶点，最多把圈切成 |V_1| 段。
G 的边只会让连通分支更少，不会更多。

所以：

1
p(G-V_1) ≤ p(C-V_1) ≤ |V_1|

这个定理常用于反证：只要找到某个 V_1，使 p(G-V_1)>|V_1|，就能说明 G 不是哈密顿图。

6.3 半哈密顿图的必要条件

定理 8.7：设 G=<V,E> 是无向半哈密顿图，则对 V 的任意非空真子集 V_1 有：

1
p(G-V_1) ≤ |V_1|+1

直觉：哈密顿通路是一条“线”，删掉 k 个顶点，最多切成 k+1 段。

6.4 必要条件不是充分条件

Petersen 图满足：

1
∀V_1≠∅, p(G-V_1)≤|V_1|

但 Petersen 图不是哈密顿图，只是半哈密顿图。

因此：

1
p(G-V_1)≤|V_1|

只是哈密顿图的必要条件，不是充分条件。

7、哈密顿图的充分条件

7.1 半哈密顿图的 Ore 型条件

定理：设 G 是 n≥2 阶无向简单图，若对 G 中任意不相邻顶点 u,v 都有：

1
d(u)+d(v)≥n-1

则 G 是半哈密顿图。

证明主线：

  1. 由度数条件推出 G 连通。
  2. 取一条极大路径 Γ=v_0v_1...v_k。
  3. 若路径没有包含所有顶点，则用度数条件找到交叉连接，把极大路径变成一个圈。
  4. 连通性保证圈外还有顶点可以接进来，得到更长路径，矛盾。
  5. 因此极大路径已经包含所有顶点，是哈密顿通路。

7.2 Ore 定理

推论 1：设 G 是 n≥3 阶无向简单图，若对任意不相邻顶点 u,v 都有：

1
d(u)+d(v)≥n

则 G 是哈密顿图。

这通常称为 Ore 定理。

7.3 Dirac 定理

推论 2：设 G 是 n≥3 阶无向简单图，若对任意顶点 u 都有：

1
d(u)≥n/2

则 G 是哈密顿图。

因为任意不相邻顶点 u,v 都满足：

1
d(u)+d(v)≥n/2+n/2=n

所以由 Ore 定理得到哈密顿图。

Dirac 是更容易检查的条件；Ore 更强、更灵活。二者都是充分条件，不是必要条件。

7.4 加边定理

定理 8.8：设 u,v 是 n 阶无向简单图 G 中两个不相邻顶点，且：

1
d(u)+d(v)≥n

则：

1
G 是哈密顿图 ⇔ G+(u,v) 是哈密顿图。

含义：

1
在度数和足够大的不相邻顶点之间加边，不改变“是否哈密顿”。

这是闭包思想的基础。

8、有向图与竞赛图

8.1 竞赛图一定半哈密顿

定理 8.9：

1
设 D 是 n≥2 阶竞赛图，则 D 是半哈密顿图。

证明可用插入法：

1
2
3
4
先对较小竞赛图取一条哈密顿通路；
加入新顶点 v；
沿通路寻找第一个满足 v→v_i 或 v_i→v 的位置；
把 v 插入合适位置，仍得到一条经过所有顶点的有向通路。

推论：

1
若 n 阶有向图 D 含 n 阶竞赛图作为子图，则 D 是半哈密顿图。

8.2 强连通竞赛图是哈密顿图

定理 8.10：

1
强连通的竞赛图是哈密顿图。

证明主线：

  1. 强连通竞赛图中存在长度为 3 的有向圈。
  2. 若已有长度为 k 的有向圈 C，且 k<n，则可把圈外某个顶点插入 C，得到长度为 k+1 的有向圈。
  3. 不断插入，直到得到长度为 n 的有向圈，即哈密顿回路。

关键插入情形：

1
2
3
若存在 v∉C 以及相邻位置 v_{i-1},v_i，
使 v_{i-1}→v 且 v→v_i，
则可把 v 插入这条边之间。

若没有这种直接插入位置，课件把圈外顶点分成：

1
2
V_1={v∈V(D-C) | 对所有 u∈V(C), u→v}
V_2={v∈V(D-C) | 对所有 u∈V(C), v→u}

强连通性保证存在 s∈V_1、t∈V_2 且 s→t，于是仍可把 s,t 接入圈，扩成更长圈。

推论：

1
若 n 阶有向图 D 含 n 阶强连通竞赛图作为子图，则 D 是哈密顿图。

8.3 完全图中的边不重哈密顿回路

定理 8.11：

1
2
完全图 K_{2k+1} 中同时有 k 条边不重的哈密顿回路，
并且这些哈密顿回路覆盖 K_{2k+1} 的所有边。

推论：

1
2
完全图 K_{2k} 中同时有 k-1 条边不重的哈密顿回路；
除此之外，剩下 k 条彼此不相邻的边。

这部分可理解为完全图的边分解：奇阶完全图可以完全分解成若干条哈密顿回路；偶阶完全图会剩下一组完美匹配。

9、习题与答案

习题 8.4：任意行遍点的判定

题目：设 G 为欧拉图，v0∈V(G)。若从 v0 开始行遍，无论行遍到哪个顶点，只要未经过的边就可以行遍，最后行遍所有边回到 v0，即得 G 中一条欧拉回路，则称 v0 是可以任意行遍的。证明：

1
v0 是可以任意行遍的 ⇔ G-v0 无圈。

证明 ⇒：反证。若 G-v0 含圈，设该圈为 C'，则 v0 不在 C' 上。令：

1
G'=G-E(C')

删除一个圈上的所有边不会改变各顶点度数的奇偶性，因此 G' 中仍无奇度顶点。

若 G' 连通，则 G' 仍是欧拉图。因为 v0 可以任意行遍，可以先从 v0 出发行遍 G' 中所有边，并回到 v0。但此时 C' 上的边还没有行遍，且 v0 不在 C' 上，无法再从 v0 接入 C'，矛盾。

若 G' 不连通，设连通分支为：

1
G_1,G_2,...,G_k, k≥2

且 v0∈G_1。可以先行遍 G_1 中的欧拉回路并回到 v0，但由于不连通，无法行遍其他分支以及 C' 中的边，也与“可以任意行遍”矛盾。

所以 G-v0 无圈。

证明 ⇐：由定理 8.1，欧拉图 G 可以分解为若干个边不重的圈的并：

1
G=C_1∪C_2∪...∪C_k

因为 G-v0 无圈，所以 G 中每个圈都必须经过 v0。从 v0 出发时，随意走完某个经过 v0 的圈都会回到 v0；再继续走另一个经过 v0 的圈。反复进行，直到所有圈都走完，就得到一条从 v0 出发又回到 v0 的欧拉回路。

因此 v0 是可以任意行遍的。

习题 8.7：两个图都不是哈密顿图

题目：证明原题图中的两个图 (a)、(b) 都不是哈密顿图。

证明思路：使用哈密顿图必要条件：

1
2
若 G 是哈密顿图，则对任意非空真子集 V1，
p(G-V1)≤|V1|。

对图 (a)，按原图标号取：

1
V1={a,b,c,d,e}

由图可见：

1
p(G-V1)=7>|V1|=5

违反定理 8.6，因此图 (a) 不是哈密顿图。

对图 (b)，按原图标号取：

1
V1={a,b,c,d,e,f}

由图可见：

1
p(G-V1)=7>|V1|=6

也违反定理 8.6，因此图 (b) 不是哈密顿图。

习题 8.13：认识关系中的排队问题

题目：今有 n 个人，已知他们中任何二人合起来认识其余的 n-2 人。证明：当 n≥3 时，这 n 个人能排成一列，使得中间任何人都认识两旁的人。

证明：构造无向简单图：

1
2
3
G=<V,E>
V={v | v 为 n 人之一}
E={(u,v) | u≠v 且 u 与 v 相互认识}

题目要证明的排队方式，等价于证明 G 中存在哈密顿通路。

任取两个不同顶点 v_i,v_j。

若 v_i 与 v_j 认识，则二人合起来认识其余 n-2 人，而且二人彼此也认识，所以：

1
d(v_i)+d(v_j) ≥ (n-2)+2 = n

若 v_i 与 v_j 不认识，则对任意第三人 v_k：

  1. 由 v_i 与 v_k 合起来认识其余人，必须认识 v_j；但 v_i 不认识 v_j，所以 v_k 认识 v_j。
  2. 同理由 v_j 与 v_k 合起来认识其余人，可得 v_k 认识 v_i。

因此除了 v_i,v_j 彼此不认识外，他们都认识其余 n-2 个人：

1
d(v_i)+d(v_j) ≥ 2(n-2)

当 n≥3 时：

1
2(n-2)≥n-1

所以任意不相邻顶点都满足：

1
d(u)+d(v)≥n-1

由半哈密顿图充分条件，G 中存在哈密顿通路。于是这 n 个人能排成一列，使得中间任何人都认识两旁的人。

补充：当 n≥4 时：

1
2(n-2)≥n

由 Ore 定理还可得到 G 是哈密顿图，即这些人甚至可以围成一圈，使每个人都认识两旁的人。

10、复盘清单

  1. 欧拉通路经过所有边；哈密顿通路经过所有顶点。
  2. 无向欧拉图判定：连通且所有顶点偶度。
  3. 无向半欧拉图判定：连通且恰有两个奇度顶点。
  4. 有向欧拉图判定：连通且每点入度等于出度。
  5. 有向半欧拉图判定：一个起点出度比入度多 1，一个终点入度比出度多 1，其余点入度等于出度。
  6. Fleury 算法：除非别无选择，否则不走桥。
  7. 哈密顿图必要条件：p(G-V1)≤|V1|。
  8. 半哈密顿图必要条件：p(G-V1)≤|V1|+1。
  9. 半哈密顿充分条件：不相邻点度数和至少 n-1。
  10. Ore 定理：不相邻点度数和至少 n，则哈密顿。
  11. Dirac 定理：每个顶点度数至少 n/2，则哈密顿。
  12. 竞赛图一定半哈密顿；强连通竞赛图一定哈密顿。

11、下一步

第八章进入树。复习第七章时，先把“欧拉看边、哈密顿看点”这条分界线记牢，再分别记住欧拉的充要条件和哈密顿的必要/充分条件。