第 10 讲 · 欧拉路与哈密顿路

欧拉问题要求每条边恰好走一次，哈密顿问题要求每个顶点恰好访问一次。这一点决定了两类问题的难度和判据完全不同。

无向欧拉图只看连通性和奇度点

连通无向图存在欧拉回路，当且仅当每个顶点度数都是偶数。直觉是每次进入一个顶点都要用另一条未用边离开，边在顶点处成对消耗。

存在从 $u$ 到 $v$ 的非闭合欧拉路，当且仅当图连通，且恰有两个奇度顶点 $u,v$。其余顶点为偶度。可以在 $u,v$ 间补一条边，把问题化成欧拉回路，再删除补边。

构造欧拉回路时，从任一顶点沿未用边前进。偶度保证不会在别处提前卡住；得到闭合链后，若还有未用边，就从回路上与剩余边关联的顶点出发构造另一条回路并拼接。这就是 Hierholzer 式的回路合并思想。

有向欧拉图比较入度和出度

在有向强连通图中：

• 有欧拉回路，当且仅当每点 $d^+(v)=d^-(v)$；
• 有从 $s$ 到 $t$ 的欧拉路时，$s$ 的出度比入度多 1，$t$ 的入度比出度多 1，其他点相等。

实际判定时还必须检查所有有边的部分在方向或底图意义下连成一个整体；度数平衡而图分成两块，仍无法一笔走完。

de Bruijn 序列把字符串变成欧拉边

要让每个长度为 $n$ 的二进制串在一个循环序列中恰好出现一次，可以把长度 $n-1$ 的串作为顶点，把每个长度 $n$ 的串作为一条边：前 $n-1$ 位是起点，后 $n-1$ 位是终点。

于是“每个长度 $n$ 串恰好出现一次”变成“每条边恰好走一次”。各顶点入度等于出度，且图连通，因此欧拉回路给出 de Bruijn 序列。选对“串放在顶点还是边上”会把困难的哈密顿问题转成容易判定的欧拉问题。

哈密顿图没有简单的通用充要条件

哈密顿路经过每个顶点恰好一次；哈密顿圈还要回到起点。穷举顶点排列需要阶乘级搜索，一般判定问题比欧拉图困难得多。

课件给出几类条件：

• 必要条件：若 $G$ 有哈密顿圈，则删去任意非空真顶点集 $S$ 后，连通分支数不超过 $|S|$；
• 哈密顿路的充分条件：$n$ 阶无向图中每对顶点度数和至少为 $n-1$；
• Ore 型充分条件：每对不相邻顶点度数和至少为 $n$，则存在哈密顿圈；
• 有向完全图必有哈密顿通路。

充分条件不满足，不能推出没有哈密顿圈；必要条件满足，也不能推出一定存在。彼得森图就是提醒：它有很多哈密顿路，却没有哈密顿圈。

建模时先问资源是边还是点

七桥、一笔画和邮递路线主要关心边，因此用欧拉模型；课程排期、圆桌座位等要求每个对象出现一次，因此用哈密顿模型。把现实约束翻成“相邻代表允许还是冲突”后，再决定要找路径、圈，还是补图中的路径。