欧拉图与哈密顿图

一、欧拉图

1.1 欧拉图的起源

哥尼斯堡七桥问题：18世纪的哥尼斯堡城有七座桥，问题是能否从某地出发，经过每座桥恰好一次，最后回到出发地。欧拉将此问题抽象为图论问题，开创了图论研究。

1.2 基本定义

欧拉通路：在连通无向图 $G$ 中，通过所有边一次且仅一次的通路称为欧拉通路。

欧拉回路：在连通无向图 $G$ 中，通过所有边一次且仅一次的回路称为欧拉回路。

欧拉图：具有欧拉回路的图称为欧拉图。

半欧拉图：具有欧拉通路但不具有欧拉回路的图称为半欧拉图。

有向图中的欧拉路：在有向图中，经过图中每一边一次且仅一次的一条单向路称为单向欧拉路。

注意：欧拉路不一定经过图中所有的点（可能有孤立点）；欧拉图一定是连通的（否则无法经过所有边）。

1.3 一笔画问题

欧拉图问题就是"一笔画"问题。画的方法：找出起点和终点，先画出一条路，因为是连通图，故可以把与该路相交的回路加入路中，重复此过程，直到这条路包含了所有的边。可见，欧拉路是不唯一的。

1.4 欧拉图的判定定理

无向图的判定

定理1：无向连通图 $G$ 是欧拉图的充要条件是 $G$ 中所有顶点的度数为偶数。

定理2：无向连通图 $G$ 是半欧拉图的充要条件是 $G$ 中恰有两个奇数度顶点。

有向图的判定

定理3：有向连通图 $G$ 是欧拉图的充要条件是 $G$ 中每个顶点的入度等于出度。

定理4：有向连通图 $G$ 是半欧拉图的充要条件是：

• 存在两个顶点，其中一个入度比出度大1，另一个出度比入度大1
• 其余顶点入度等于出度

1.5 判定示例

1.6 欧拉图与半欧拉图的对比

二、哈密顿图

2.1 基本定义

哈密顿回路：在图 $G$ 中，包含所有顶点一次且仅一次的回路称为哈密顿回路。

哈密顿通路：在图 $G$ 中，包含所有顶点一次且仅一次的通路称为哈密顿通路。

哈密顿图：具有哈密顿回路的图称为哈密顿图。

半哈密顿图：具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。

2.2 欧拉图与哈密顿图的区别

注意：哈密顿图一定是连通的；哈密顿路不一定经过图中所有的边。

2.3 哈密顿图的判定条件

必要条件

定理：若图 $G = \langle V, E \rangle$ 是哈密顿图，则结点集 $V$ 的每一个非空子集 $S$ 均有 $W(G - S) \leq |S|$，其中 $W(G - S)$ 是图去掉 $S$ 后的连通分支数。

证明思路：对 $W(G - S)$ 进行归纳证明。

等价的逆否命题：若存在非空子集 $S \subseteq V$ 满足 $W(G - S) > |S|$，则图 $G$ 一定不是哈密顿图。

应用：利用此结论可以证明某些图不是哈密顿图。

例：有割点的图一定不是哈密顿图。因为若 $G$ 连通且有割点 $v$，则 $G - v$ 至少有两个连通分支，即 $W(G - v) > |v| = 1$，不满足哈密顿图的必要条件。

充分条件

定理1：$n$ 个结点的简单图，如果 $G$ 中每一对不相邻结点的度数之和 $\geq n - 1$，则图中存在一条哈密顿通路。

定理2：$n$ 个结点的简单图，如果 $G$ 中每一对不相邻结点的度数之和 $\geq n$，则图中存在一条哈密顿回路。

证明思路：不断地加长已找到的路，直到这条路包含了所有结点。可以通过破圈的方法延长路，为此，要先证明满足该条件的图一定是连通图。

注意：哈密顿图不一定满足此充分条件，因此这不是必要条件。充分条件和必要条件是相互独立的。

标号法

标号法判断哈密顿图：对图中的相邻结点用 A、B 标记，尝试构造哈密顿回路。

2.4 哈密顿图的应用

例题：有7个人（A-G），各掌握不同语言：

• A：英语
• B：英语、汉语
• C：英语、意大利语、俄语
• D：日语、汉语
• E：德语、意大利语
• F：法语、日语、俄语
• G：法语、德语

问：能否将他们沿圆桌安排坐成一圈，使得每个人都能与两旁的人交谈？

解题思路：

1. 将7个人对应为图的7个顶点
2. 如果两人有共同语言，在对应顶点间连边
3. 问题转化为：图中是否存在哈密顿回路

建图：

• A-B（英语）、A-C（英语）
• B-C（英语）、B-D（汉语）
• C-E（意大利语）、C-F（俄语）
• D-F（日语）
• E-G（德语）
• F-G（法语）

求解：找到哈密顿回路 $A \to B \to D \to F \to G \to E \to C \to A$

结论：可以按此顺序安排座位。

三、最短路问题

3.1 Dijkstra标号算法

问题：求带权图中从起点 $u$ 到终点 $v$ 的最短路径。

算法思想：逐步扩展已确定最短路径的顶点集合。

基本概念：

• 永久标号：已确定从起点到该顶点的最短距离
• 临时标号：暂时找到的距离，可能被修改
• 永久标号集 $S$：已获得永久标号的顶点集合

3.2 算法步骤

初始状态：

1. 对起点 $u$ 标号为 0，画圈（永久标号）
2. 对其他所有顶点标号为 $\infty$（临时标号）
3. 永久标号集 $S = \{u\}$

迭代过程（重复以下步骤直到终点 $v$ 获得永久标号）：

1. 标号：对 $S$ 中最新加入的顶点，考察与其相邻的顶点

   • 若从该顶点到相邻顶点的距离 + 该顶点的标号 < 相邻顶点当前标号
   • 则修改相邻顶点的标号为更小的值，并记录来源

2. 画圈：在所有未画圈的标号中，找距离最小的顶点

   • 对该顶点画圈（获得永久标号）
   • 将该顶点加入永久标号集 $S$

3. 终止：当终点 $v$ 获得永久标号时，算法结束

3.3 算法示例

题目：求图中从 $u$ 到 $v$ 的最短路径。

求解过程：

结果：

• 最短路径：$u \to A \to D \to V$（倒推：$V$ 来自 $D$，$D$ 来自 $A$，$A$ 来自 $u$）
• 最短路长：5（终点 $V$ 的标号）

3.4 标号修改规则

修改标号：当发现更短路径时，需要修改顶点的标号：

• 擦除原来的标号
• 写上新的更小距离
• 记录新的来源顶点

不修改条件：如果新计算的距离 ≥ 当前标号，保持原标号不变。

四、解题思路总结

4.1 判断是否为欧拉图

解题思路：

• 是：计算各个结点的度，或直接找出一条欧拉（回）路
• 否：找出度数为奇数的结点

证明欧拉回路存在的方法是构造过程的说明，在论证时要体现 repeat…until 或 while…do 的思路。

4.2 判断是否为哈密顿图

解题思路：

• 是：证明任意一对不相邻结点的度之和 $\geq n$，或直接找出一条哈密顿回路
• 否：找出 $S \subseteq V$，使 $W(G - S) > |S|$ 成立；或用标号法，相邻结点用 A、B 标记

4.3 思考题

问题：若无向图 $G$ 是欧拉图，$G$ 中是否存在割边？

分析：欧拉图中所有顶点度数为偶数。若存在割边 $e = (u, v)$，去掉 $e$ 后图分为两个连通分支，则 $u$ 和 $v$ 在各自分支中的度数都变为奇数。但在每个分支中，奇数度顶点个数必须为偶数（握手定理推论），而每个分支只有一个奇数度顶点（$u$ 或 $v$），矛盾。因此欧拉图中不存在割边。

练习题

练习1：欧拉图判断

题目：判断以下图是否为欧拉图或半欧拉图：

(1) 4个顶点，每个顶点度数为3的无向图

(2) 4个顶点，每个顶点度数为2的无向图（如四边形）

(3) 恰有2个三度顶点、其余顶点度数为偶数的无向连通图

解：

(1) 有4个奇数度顶点，不满足欧拉图条件（需全部偶数度），也不满足半欧拉图条件（需恰有2个奇数度顶点）。既不是欧拉图也不是半欧拉图。

(2) 所有顶点度数为偶数，且图连通。是欧拉图。

(3) 恰有2个奇数度顶点，且图连通。是半欧拉图。

练习2：哈密顿图判断

题目：判断以下命题是否正确：

(1) 有割点的图一定不是哈密顿图

(2) $n$ 个结点的简单图，每一对不相邻结点的度数之和 $\geq n$，则图中存在哈密顿回路

(3) 哈密顿图一定满足"每一对不相邻结点的度数之和 $\geq n$"

解：

(1) 正确。若 $G$ 有割点 $v$，则 $G - v$ 至少有两个连通分支，即 $W(G - v) > 1 = |v|$，不满足哈密顿图的必要条件 $W(G - S) \leq |S|$。

(2) 正确。这是哈密顿图的充分条件。

(3) 错误。充分条件不是必要条件。存在哈密顿图不满足此条件。

练习3：有向图欧拉图

题目：有向连通图 $G$，每个顶点的入度等于出度。$G$ 是否为欧拉图？

解：是。有向连通图是欧拉图的充要条件是每个顶点入度等于出度。可以构造出一条经过所有边恰好一次的回路。

本节小结

• 欧拉图：通过所有边一次且仅一次的回路
• 半欧拉图：通过所有边一次且仅一次的通路
• 有向图单向欧拉路：有向图中经过每边一次且仅一次的单向路
• 一笔画问题：欧拉图问题就是一笔画问题，构造方法是逐步加入回路
• 欧拉图判定：无向图所有顶点度数为偶数；有向图每个顶点入度=出度
• 半欧拉图判定：无向图恰有2个奇数度顶点；有向图恰有2个特殊顶点
• 欧拉图无割边：欧拉图中不存在割边
• 哈密顿图：通过所有顶点一次且仅一次的回路
• 半哈密顿图：通过所有顶点一次且仅一次的通路
• 哈密顿图必要条件：$W(G - S) \leq |S|$，用于证明不是哈密顿图
• 哈密顿图充分条件：度数之和 $\geq n - 1$（哈密顿路），$\geq n$（哈密顿回路）
• 充分条件不是必要条件：哈密顿图不一定满足充分条件
• 标号法：相邻结点用 A、B 标记，辅助判断哈密顿图
• 最短路算法：Dijkstra标号算法，逐步扩展永久标号集

关键术语速查