离散数学里有两张图，一个叫 Euler 图，一个叫 Hamilton 图，名字长得像亲兄弟，脾气却完全不同。Euler 图解决的是“能不能一笔画完”，Hamilton 图关心的是“能不能一圈走完所有顶点”。很多初学者把它们混在一起记，做题时拿 Euler 的条件去判 Hamilton，一错就错一大片。这篇文章把这两个概念从头到尾掰开揉碎，从定义、判定条件、经典应用再到做题时的常见误判，一次性讲清楚。
如果你是正在学离散数学的大学生、准备期末考试或者考研的考生，又或者只是想搞明白一笔画问题背后数学原理的爱好者，这篇内容都适用。我不会从定义抄到定理就完事，而是用“为什么这样判定”“这个定理想表达什么直觉”的方式来拆解，让你真正理解，而不是死记硬背。
1. 从哥尼斯堡七桥到 Euler 定理：一笔画问题的数学化
1.1 七桥问题为什么震撼了当时的数学家
Euler 图的诞生要从一个城市布局说起。在东普鲁士的普雷格尔河畔有一座老城，河中间有两座小岛，七座桥把两座岛和河两岸连接起来。当地居民流传着一个有趣的谜题：能不能从某个地点出发，不重复地走过全部七座桥，最后回到出发点？
这个问题听起来像民间的智力游戏，但当时没人能给出严谨回答。直到大数学家欧拉在 1736 年解决了它，他用一种非常高明的方式处理：把“过桥”这个动作抽象成“在图中走边”。
欧拉把每一块陆地抽象成一个点，把每座桥抽象成连接两个点的一条边。于是“不重复地走完所有桥”就变成了“不重复地经过图中每一条边”。这个抽象过程实在太关键了，它把现实世界的走街串巷变成了数学里的图论问题，图论这个学科也由此正式诞生。
1.2 从一个点出发为什么必须考虑“进出次数”
要理解欧拉的判定思路，我们先想一个简单问题：假设你从某个点出发，最后还要回到这个点，途中每经过一个点一次，就要用掉一条进边和一条出边。也就是说，除起点外的每个点，被进入的次数必须等于离开的次数。
如果你不想回到起点，起点只要多出一条边走出去，终点多出一条边走进来，而中间经过的每个点仍然要求进出次数相等。
这里的“进出次数”就是数学里的度。一个点有多少条边和它相连，它的度就是多少。由此可以推出一条核心结论：如果一个图存在从某点出发又回到该点的欧拉回路，那么图中每个顶点的度都必须是偶数。
这不是巧合，而是必然。想象一下你正在某个非起点处，你从一条边走进来，就必须从另一条边走出去，否则就卡住了。所以这个点连接的边数一定是成对的，也就是偶数。起点也一样，出发用一条，回来用一条，最后也是偶数。这个“进出配对”的逻辑是理解整个 Euler 定理的基础。
1.3 充要条件的完整表述与自证的直觉闭环
欧拉最终给出的定理是这样的：
- 一个连通图存在欧拉回路，当且仅当所有顶点的度都是偶数。
- 一个连通图存在欧拉路径（不必回到起点），当且仅当恰有两个奇度顶点，这两个点就是起点和终点。
这两条并不是猜测，而是经过严格证明的充要条件。充分性的关键在于：如果所有顶点度数都是偶数，图必然是若干个边不相交的圈拼起来的，而连通性又能保证这些圈可以串联成一条完整回路。这个证明过程本身就是一个很好的思维训练，它展示了一个看似不可能一步到位的构造性问题，如何通过“局部圈逐步合并”来完成。
理解 Euler 图的判定后，你会发现它其实是整个图论里“性质最好”的一类图：判定算法简单、构造算法清晰、计算复杂度低。这也解释了为什么我们在实际应用中特别喜欢用到 Euler 路径。
2. Euler 图的应用实操：从判定到一笔画的完整流程
2.1 一个物流巡检问题的建模过程
Euler 图在现实生活中最常见的应用场景就是路径规划，比如邮递员送信、洒水车洒水、巡逻路线设计。我试过一个冷链仓储的巡检路径项目：仓库有若干个冷库门，巡检员要从值班室出发，走遍每一条需要检查的通道，最后回到值班室。通道不重复走，路径要尽量短。
这个问题的关键就是每条通道恰好走一次，建模下来就是求一个有欧拉回路的方案。先用图的方式把通道交点当作顶点、通道当作边，然后统计每个点的度，发现有两个奇度顶点。这就说明原图不存在欧拉回路，硬要每条通道只走一次还回到起点是做不到的。
解决方案有两种思路：要么改成欧拉路径，允许从某个冷库门进入后从另一个门出来，还能保证每条通道走一次；要么在两条奇度顶点之间加一条虚拟通道，把它变成欧拉回路。第二种做法在实际工程里非常常见，相当于允许额外重复某段路程，换取闭环路径。
2.2 判定流程的标准化操作步骤
在实际工程中，我一般按下面这几步来处理一笔画问题：
- 把现实场景抽象成无向图，顶点和边的定义要明确。
- 统计每个顶点的度数，判断图的连通性。
- 根据奇度顶点数量分类处理：
- 0 个奇度顶点：存在欧拉回路。
- 2 个奇度顶点：存在欧拉路径，起点为任一奇度顶点，终点为另一个。
- 超过 2 个奇度顶点：不存在一笔画路径，需要考虑增加重复边。
- 若需要构造具体路径，就用 Fleury 算法或者 Hierholzer 算法。
第一步和第二步经常被跳过，但恰恰是最容易出错的地方。很多同学在考试时看见图就直接断言“能一笔画”，忘了先判断图是否连通。不连通的图即使每个点度数都是偶数，也不能一笔画完——图断成两块，你怎么走也走不到另一块去。
2.3 路径构造算法的选择逻辑
如果只需要判断是否存在，统计奇度顶点就够了。但如果你需要真的把路径走一遍，就得用路径构造算法。这里有两套常用方案：
Fleury 算法的思路是“优先走非桥边”，也就是能不走割边就不走割边，因为一旦走过一座桥，另一头就回不来了。这个算法直观、容易理解，但每次选边前都要判断桥边，效率相对较低。
Hierholzer 算法则是递归地找回路再拼接，时间复杂度可以做到线性级别，比 Fleury 更快。它的执行逻辑是先随便找一个回路，然后把回路上的每个点当作新起点继续扩展，最后把回路串起来。工程实现上我会优先选择 Hierholzer，考试计算题则看题目要求，不少教材喜欢考 Fleury 的选择过程，因为可以考察“为什么不能走那条边”的理解。
我写过一个 Python 脚本用来快速判断任意无向图能否一笔画：
from collections import defaultdict def can_draw_euler_path(n, edges): # n 为顶点数，edges 为边列表 [(u, v), ...] graph = defaultdict(list) degree = [0] * n for u, v in edges: graph[u].append(v) graph[v].append(u) degree[u] += 1 degree[v] += 1 # 检查连通性（忽略孤立点） visited = [False] * n stack = [] start = -1 for i in range(n): if degree[i] > 0: start = i break if start == -1: return False stack.append(start) visited[start] = True while stack: node = stack.pop() for neigh in graph[node]: if not visited[neigh]: visited[neigh] = True stack.append(neigh) for i in range(n): if degree[i] > 0 and not visited[i]: return False odd_count = sum(1 for d in degree if d % 2 == 1) if odd_count == 0 or odd_count == 2: return True return False print(can_draw_euler_path(4, [(0,1),(1,2),(2,3)]))这段代码把连通性检查和奇度顶点统计一次完成。实际修改路线方案时，我只要把通道数据导入这个函数，马上就能知道方案可不可行。
3. Hamilton 图的“无解”本质：为什么没有一个简单判别法
3.1 从旅行商问题开始理解 Hamilton 回路
Hamilton 图的背景故事完全不同，它源自爱尔兰数学家哈密顿在 1857 年左右提出的一种游戏：在一个正十二面体的顶点上，能不能找到一条回路，恰好经过每个顶点一次并回到起点？
这个问题的目标对象从“边”转移到了“顶点”。Hamilton 回路是经过每个顶点恰好一次的回路，Hamilton 路径是经过每个顶点恰好一次的路径。如果一个图存在 Hamilton 回路，就称为 Hamilton 图。
这里要注意一个细节：Hamilton 回路并不要求经过每一条边，这和 Euler 回路是根本性的差异。一条 Hamilton 回路通常只用到图中很少一部分边，剩下的边完全不管。正是这个差异，导致 Hamilton 问题比 Euler 问题难了不止一个量级。
跟它绑定最深的经典难题就是旅行商问题：有若干个城市，已知任意两个城市之间的距离，求一条经过每个城市恰好一次且总路程最短的回路。这个问题的可行解空间是 n 个顶点的全排列数，n 稍微大一点，穷举就彻底爆炸。
3.2 为什么 Hamilton 判定长期悬而未决
很多同学初学到这里会很不适应：Euler 图判定一句话就完了，Hamilton 图怎么讲了半天也只是“必要条件”“充分条件”，没有一个“当且仅当”的漂亮定理？
根本原因在于 Hamilton 回路对全局结构的约束太强。一条回路要覆盖所有顶点，意味着每个顶点周围如何连接、各条边之间如何配合，都必须同时满足。这种全局约束不像度数那样可以局部统计，它涉及到排列组合级别的复杂度，所以很难用一个简单条件刻画。
直觉类比一下：Euler 问题好比在一堆通道里规划一条“每条路都走一次”的巡逻路线，只要每个路口的路数量是偶数，一定能闭环；Hamilton 问题则像在若干嘉宾中安排一个“每个人只见一次”的圆桌顺序，顺序是否可行取决于所有嘉宾之间的亲密关系，这些关系彼此牵连，牵一发而动全身。关系足够多时大概率有解，但具体到某一张图，没有任何简单规则能保证一定成功。
这正是 Hamilton 问题在计算复杂度理论中成为 NP 完全问题经典代表的原因。现阶段最直观的判定方式仍然是不断尝试所有顶点的排列，也就是回溯搜索。这也是为什么我们做题时会发现，Hamilton 图相关的题目往往给的是“可判定”的特例，而不是通用的“一眼看穿”的技巧。
3.3 常用的充分条件：Dirac 定理和 Ore 定理的直觉
虽然还没有一个简单的充要条件，但数学家们找到了很多充分条件，其中最常考的是 Dirac 定理和 Ore 定理。
Dirac 定理说的是：如果有 n 个顶点，且每个顶点的度数都不小于 n/2，那么这个图一定是 Hamilton 图。
这个条件看起来很强，直觉也很好理解：每个人的关系都足够多，整个网络的密集程度高到不可能出现“绕不过去”的顶点，随便找都能串成圈。
Ore 定理更松弛一些：对任意一对不相邻的顶点 u 和 v，它们的度数之和至少为 n，那么这个图一定是 Hamilton 图。
Ore 定理其实是 Dirac 定理的推广。如果每个点度数都大于等于 n/2，那么任意两个不相邻点的度数之和自然大于等于 n。反过来，Ore 条件成立并不要求每个点都很高，只需要每对不相邻点“合起来足够高”即可。
考试题目里最常见的一种考法就是给你一个图，让你判断它一定是 Hamilton 图，你就检查这两个条件是否满足。但必须记得：这些条件只是充分条件，不是必要条件。不满足 Dirac 或 Ore 的图也可能是 Hamilton 图，也就是说，条件满足则一定有 Hamilton 回路，条件不满足则什么都说明不了，必须回到定义去构造。
除了这两个定理，还有一个考虑割点集的必要条件：如果在图中删去 k 个顶点后连通分量数大于 k，那么这个图一定没有 Hamilton 回路。注意这个条件是“否证”用的，如果删掉几个点后断裂成全不相连的多个部分，那就不可能有一条回路穿过所有顶点。考试时用这个必要条件和充分条件双管齐下，往往能快速得出答案。
4. 两种图的全年判定策略：从特征到反例的辨析框架
4.1 形态上的对比与常见混淆点
Euler 图和 Hamilton 图经常被放在同一张试卷里考，就是因为它们在定义上太对称了——一个管边，一个管顶点。我们用一个表格把核心特征整理清楚：
| 对比维度 | Euler 图 | Hamilton 图 |
|---|---|---|
| 关注对象 | 边 | 顶点 |
| 核心目标是 | 每条边恰好走一次 | 每个顶点恰好访问一次 |
| 回路存在条件 | 所有顶点度数均为偶数（充要） | 没有简单的充要条件 |
| 路径存在条件 | 恰有两个奇度顶点 | 也没有简单充要条件 |
| 常见充分条件 | 无特殊要求 | Dirac 定理、Ore 定理 |
| 判定复杂度 | 多项式时间可解 | NP 完全问题 |
| 经典应用 | 邮递员问题、一笔画 | 旅行商问题、排程问题 |
从这个表格能立刻看出两者最本质的差别：一个是有高效算法的问题，一个是目前公认找不到高效算法的问题。所以做题时如果只给一张图让你“判断类型”，先看边再看顶点，思路会顺畅得多。
4.2 经典反例为什么选“那些”图
我在给同学讲题时发现，很多人理解了定理还是不会辨析，核心问题在于没有积累足够多的反例直觉。图论里有一批经典图，专门用来打破各种“想当然”，遇到它们时几乎可以直接排除。
比如五边形加一个中心点，中心点只连一个边，这种结构在欧拉问题里很容易排除，因为总有顶点的度数是奇数。但在 Hamilton 问题的讨论里它提醒我们：哪怕中心点只连一条边，也可以出现在 Hamilton 路径的端点位置，却不能出现在 Hamilton 回路里，因为中心点度数为1，回路中每个顶点必须有进有出。
再比如两个团通过一条割边连接的结构，这种图在顶点数量很大时每个点的度数都不低，看似满足 Ore 条件的倾向，但那条割边把图分割成两个区域，Hamilton 回路必须穿越割边两次才能回到起点，可割边只能走一次，于是必然失败。这类“连接处太薄弱”的反例非常典型，考试中特别喜欢设计成这样的陷阱。
还有一种看似度数很高却不行的例子：把两个完全图各取一半，再用一个点把它们桥接起来。桥接点度数为 2，两个子图中每个点的度数都挺高。这时如果直接套 Dirac 定理，n/2 的阈值可能满足也可能不满足，但无论如何桥接点两侧无法同时形成闭合回路，最终也没有 Hamilton 回路。这些反例告诉我们：图的连通“瓶颈”比单个点度数更能左右 Hamilton 性质。
4.3 一张可复用的判定决策表
说了这么多理论，真正到了考场或者做项目里，我建议按下面的决策表来判断：
- 先看问题问的是“边”还是“顶点”。
- 如果是边，立即检查连通性和奇度顶点数。
- 如果是顶点，先尝试用必要条件否定——是否存在删去 k 个点后产生多于 k 个连通分量的情况。
- 如果不满足必要条件，必然不是 Hamilton 图，直接结束。
- 如果必要条件通过，再看是否满足 Dirac 或 Ore 充分条件。
- 满足充分条件，必须是 Hamilton 图，直接结束。
- 充分条件也不满足，只能回到定义，尝试手工构造 Hamilton 回路或路径。
这套流程在绝大多数考试题里都能顺利走完，因为出题人通常会设计成可以被充分条件或必要条件快速击穿的图。真正的难点在于最后一步——手工构造。构造 Hamilton 回路没有固定算法，但有几个经验技巧：优先走度数小的顶点，因为这些顶点选择余地小，越早安排越不容易卡死；优先利用“必须走”的桥接边；尝试对称结构对称地处理。
5. 考试与实战中的三类高频误判：踩坑经验分享
5.1 误踩“所有顶点都能进入回路”的坑
长期帮学弟学妹答疑下来，我发现最普遍的一个错误是：看到一个顶点度数为 2，就马上认为它能进入 Hamilton 回路。其实度数为 2 只是必要条件——回路中每个顶点的度数至少为 2。但它不能保证整张图存在 Hamilton 回路。度数 2 的顶点若位于图的边缘，它的两条边可能被强制纳入任何经过它的回环，但如果两条边引向同一个连通分支内部，路径就会局部打结，整个圈反而串不起来。
有一个很形象的例子：一个六边形里加一条内部对角线。每个顶点度数至少是 2，可经过包含对角线那个顶点的回路选择却可能被卡住。考试时这类图往往就是让你找出不可能的点。所以我的建议是：把“度数至少为 2”当作体检指标，而不是健康保证。
5.2 误用 Euler 条件去判 Hamilton 图的张冠李戴
第二大高频错误是拿“所有顶点度数为偶数”去判断 Hamilton 图是否存在。一个每个点度数都是偶数的图，可能压根没有 Hamilton 回路。原因前面说过了，Euler 条件管的是边的遍历，Hamilton 管的是顶点的遍历，两者在数学上完全不同。
反过来也常有人用 Dirac 条件去断言 Euler 回路存在，同样错。某个图顶点数很多且每个点度数都很高，说明它可能具有 Hamilton 回路，但高度数不能保证所有点度数都是偶数，所以不能推出存在 Euler 回路。
这种混淆的根源在于学的时候没有建立“一个概念对应一类问题”的框架。我建议每次做完一道题后都问自己一句：这道题究竟问的是每条边走一次，还是每个顶点走一次？这一句话能挡住大部分失误。
5.3 遗漏连通性导致的误判
第三种误判在 Euler 部分尤其常见：有同学数完奇度顶点直接说“能一笔画”，完全没检查图是否连通。比如一个图分为两坨，每坨内部都是闭合回路，所有点度数都是偶数，但它显然不能一笔画完——你从一坨走到另一坨就需要额外的边。
这类题画出错的原因很简单：做题太快，把定理的“连通”前提给丢了。连通性在 Euler 定理里是隐藏的前置条件，做题时必须先确认。我在考场上给自己定的顺序是：先看一眼图是不是一整块，再数奇度顶点。这个习惯帮我避免了好几次低级的扣分。
6. 一个完整案例的逐步拆解：从读题到最终判定
6.1 题目条件与图结构描述
为了让你把这些判定策略串起来，我们来看一个综合性例题。假设某图 G 有 6 个顶点，顶点分别记为 a、b、c、d、e、f。边的情况是：a 连接 b、c、d；b 连接 a、c、d、e；c 连接 a、b、d、e、f；d 连接 a、b、c、e；e 连接 b、c、d、f；f 连接 c、e。要求判断这张图是否存在 Euler 回路、Euler 路径、Hamilton 回路。
先把度数列出来：deg(a)=3，deg(b)=4，deg(c)=5，deg(d)=4，deg(e)=4，deg(f)=2。奇度顶点为 a 和 c 两个。
图的连通性比较直观，所有顶点都通过密集的边网连在一起，显然是连通图。
6.2 判定过程与最终结论
按照 Euler 判定规则：存在两个奇度顶点，所以不存在 Euler 回路，但存在 Euler 路径，起点为 a 或 c，终点为另一个奇度顶点。这一步就用了此前 2.2 的决策流程。
再看 Hamilton 回路，顶点数 n=6，Dirac 定理要求每个顶点度数不小于 3。我们发现 deg(f)=2，小于 3，所以不满足 Dirac 定理。再验证 Ore 定理：任意一对不相邻顶点。先列不相邻点对：a 与 e、a 与 f、b 与 f、d 与 f。逐一检查度数之和：deg(a)+deg(e)=3+4=7，deg(a)+deg(f)=3+2=5，deg(b)+deg(f)=4+2=6，deg(d)+deg(f)=4+2=6。要求不小于 n=6，其中 a 与 f 的和为 5，不满足 Ore 条件。
这说明两个经典充分条件都没通过，不能直接判定存在 Hamilton 回路。我们只能手工构造尝试。尝试构造回路：a-b-c-f-e-d-a。检验这条回路：a 与 b 相连，b 与 c 相连，c 与 f 相连，f 与 e 相连，e 与 d 相连，d 与 a 相连。所有顶点恰好出现一次，最后一个点回到起点，成功。所以这个图是一个 Hamilton 图。
这个案例非常典型地展示了为什么要充分条件不足时不要放弃，回到定义手工构造往往是有效的。同时也展示了 Euler 判定和 Hamilton 判定在同一张图上如何串行使用，各管各的，互不干扰。
6.3 案例背后的三个可迁移经验
通过这个例子，我想强调三个可迁移经验。
第一，判定顺序要固定。先判 Euler 再看 Hamilton，因为 Euler 的判定成本极低，几秒钟就出结果；Hamilton 可能需要尝试构造，放在后面更划算。
第二，手工构造 Hamilton 回路时，优先处理度数小的顶点。本例中 f 的度数最小，只有 2，它被迫连接 c 和 e，所以回路中 c 和 e 必须相邻于 f。从这个小入口出发，整个回路的结构就被迫固定了，再安排其他顶点就轻松很多。这条经验在我做过的无数构造题里都非常管用。
第三，做完必要条件和充分条件检查之后，如果还是不确定，画一张简化的结构图，把度数低的顶点和它们仅有的少数边用不同颜色标出来，很多原本模糊的结构会瞬间清晰。这不是什么高深技巧，但确实是我实测下来效率最高的辅助手段。
Euler 图与 Hamilton 图的真正难点不在于背下几条定理，而在于理解两种“遍历目标”的根本不同，以及学会在判定中灵活切换。把充要条件、充分条件、必要条件和手工构造这四层工具全部掌握，任何一张图摆在你面前，你都能像切西瓜一样干脆利落地给出答案。
