计算机 · 算法
欧拉与哈密顿路径/回路
Euler & Hamilton Paths/Circuits
约 16 分钟 · v151
欧拉与哈密顿路径
cs-algo/euler-hamilton-paths · COMP2521
0 / 5
1 什么是"一笔画"：欧拉路径
欧拉路径是把每条边恰好走一次的路线（"一笔画"）；哈密顿路径是把每个顶点恰好访问一次的路线。走回到起点就分别叫欧拉回路、哈密顿回路。
欧拉就是小时候玩的「一笔画」：笔不离纸、每条线只描一遍，能不能画完？——这有个超简单的判据（看奇数度顶点的个数）。哈密顿像「环游所有城市各一次」（旅行商）：听起来类似，却没有简单判据、是出了名的难题（NP-难）。一字之差，难度天壤之别——这正是本页要讲清的反差。
2 数奇数度顶点，判断能不能一笔画
欧拉路径有个一眼判据：在连通图里，数一下奇数度（连着奇数条边）的顶点个数。点 ▶ 看：先逐个算度数、标出奇点，再给出判定，最后把欧拉路径一笔画出来。
欧拉判定器 + 一笔画
图（红虚环=奇数度顶点，绿边=已一笔画过，橙=当前）
欧拉判据（图连通时）
点 ▶ 开始：先数每个顶点的度数。
一笔画路径
判定通过后在这里逐步画出
提示
点 ▶ 演示：逐个顶点算度数 → 数出奇点个数 → 给出判定 → 从一个奇点出发，把每条边恰好走一次。
?
奇数度顶点个数
0
已走过的边 / 共 5
3 欧拉 vs 哈密顿：看着像，难度天壤之别
每张卡片先一句大白话。重点：欧拉的判据、哈密顿的"没有判据"、以及两者千万别混。
① 欧拉看「边」，哈密顿看「点」
一句话：欧拉=每条边走一次（一笔画），哈密顿=每个顶点到一次（环游）。一字之差，对象完全不同。
"路径"是不要求回到起点，"回路"要求回到起点。所以有四个词：欧拉路径 / 欧拉回路 / 哈密顿路径 / 哈密顿回路。
② 欧拉的一眼判据
一句话：连通图里，看奇数度顶点的个数：0 个→有欧拉回路；2 个→有欧拉路径；其它→没有。
直觉：除起点终点外，每"进入"一个顶点就得"离开"，进出成对，所以中间点必须偶数度。0 个奇点能首尾相接成回路；2 个奇点只能从一个奇点走到另一个（路径）。
奇点数 0 → 欧拉回路
奇点数 2 → 欧拉路径 （奇点↔奇点）
其它(4,6…) → 都没有
③ 哈密顿：没有简单判据
一句话：判断哈密顿路径/回路是否存在，是 NP-难问题——没有像欧拉那样数一下就行的捷径。
最坏情况只能近似枚举，规模一大就算不动（这也是为什么旅行商问题出名地难）。所以考试常考"会不会判反"——别给哈密顿套欧拉的度数判据。
④ 别把两者搞混
一句话："一笔画"=欧拉，"环游所有城市"=哈密顿。题目问的是边还是点，决定了用哪套思路。
看到"每条路只走一次/一笔画/七桥问题"→欧拉，数奇点。看到"每个城市去一次/不重复访问所有点"→哈密顿，老老实实搜索，没有捷径。
4 四个最常见的混淆（点一下看对错）
下面 4 个是这块最常翻车的坑——混淆边/点、给哈密顿套度数判据、记错欧拉判据、忘了连通前提。点击卡片看" 错误 → 正确"。
① 欧拉/哈密顿混为一谈
把"走遍点"当成"走遍边"
② 给哈密顿套度数判据
以为数奇点也能判哈密顿 → 错
③ 记错欧拉判据
以为"全偶才有欧拉路径" → 漏了2奇点的情况
④ 忘了连通前提
图不连通，度数判据再漂亮也白搭
// 点击上方任一卡片，查看错误推导与正确结论
$ 分析中...
（等待运行...）
5 自测
这 5 题正对套路：欧拉 vs 哈密顿、欧拉判据、本图判定、哈密顿的难度、"一笔画"对应谁。最后到练习系统亲手数奇点、做判定。
去做例题：欧拉 · 数奇数度顶点
去做例题