欧拉与哈密顿：遍历的两种完备性

上一篇我们学习了 DAG 和拓扑排序——利用”无环”这一性质，让所有依赖都能被线性排序、让最短/最长路径都能在 $O(V+E)$ 内求解。DAG 的核心是避免环。但如果图有环呢？如果我们不仅不回避环，还要追问：能不能走出一条完美的闭合回路——不多走一步、不少走一步？

这正是本文的问题。在 Part 1”探”的第四站，我们面对两个看起来非常相似的问题：

能不能不重复地走遍所有边？（欧拉路径/回路）
能不能不重复地走遍所有节点？（哈密顿路径/回路）

“边”和”节点”只差一个字。但这一个字的差别，将我们从多项式时间的优雅世界，带到 NP-complete 的深渊。这是你第一次直面 P vs NP。

算法范式：穷举搜索（Hierholzer 算法——系统地走遍所有边）、回溯（哈密顿暴力搜索——在排列空间中深度优先）

两种”走遍”：边 vs 节点

在正式定义之前，先直观感受这两种”遍历完备性”的差异。

欧拉路径（Euler path）要求经过图中每条边恰好一次——节点可以重复经过。如果路径的起点和终点相同，就叫欧拉回路（Euler circuit/tour）。

哈密顿路径（Hamiltonian path）要求经过图中每个节点恰好一次——某些边可以不被使用。如果路径首尾相连成环，就叫哈密顿回路（Hamiltonian cycle）。

用更精确的语言：

欧拉路径：找一条路径 $v_0, e_1, v_1, e_2, \ldots, e_m, v_m$ ，使得 $E$ 中每条边恰好出现一次
哈密顿路径：找一条路径 $v_0, v_1, \ldots, v_{n-1}$ ，使得 $V$ 中每个节点恰好出现一次

[1/10]从 A 出发

已走边：0/9已访问节点：1/6

欧拉回路：走遍所有 9 条边，每条恰好一次，回到起点。节点可以重复经过（A 经过 3 次）。

切换上面的按钮，观察两种回路的走法——欧拉回路走完了所有 9 条边（节点 A 被重复经过了 3 次），而哈密顿回路走完了所有 6 个节点（内部 3 条边没有被使用）。

欧拉路径：图论的诞生

七桥问题——历史上第一个图论问题

1736 年，德国柯尼斯堡（Konigsberg）的居民在想一个问题：能不能从城中某个地方出发，恰好走过七座桥各一次，然后回到起点？

数学家 Leonhard Euler 将这个问题抽象为图：四块陆地是四个节点，七座桥是七条边。他证明了这是不可能的——不是通过穷举所有路线，而是通过一个优雅的度数论证。

Euler 的推理非常简单但深刻：如果存在一条从 $s$ 出发经过每条边恰好一次又回到 $s$ 的回路，那么每次”进入”一个节点（消耗一条边）就必须”离开”该节点（再消耗一条边）。因此每个节点消耗的边数是偶数——即每个节点的度数必须是偶数。柯尼斯堡的四个节点度数分别是 3, 3, 5, 3——全是奇数，所以不存在欧拉回路。甚至连欧拉路径都不存在（需要恰好 0 或 2 个奇度节点，这里有 4 个）。

这就是图论的诞生——Euler 不仅解决了这个具体问题，还开创了用图的结构性质（度数）回答存在性问题的方法论。

存在性条件——只需数度数

Euler 的推理直接给出了欧拉路径/回路存在的充要条件。对于连通图：

无向图：

欧拉回路存在 $\Leftrightarrow$ 每个节点的度数 $\deg(v)$ 都是偶数（奇度节点数 = 0）
欧拉路径存在 $\Leftrightarrow$ 恰好有 0 个或 2 个奇度节点（若有 2 个，它们是路径的起点和终点）

有向图：

欧拉回路存在 $\Leftrightarrow$ 每个节点的入度等于出度： $\deg^+(v) = \deg^-(v), \forall v \in V$
欧拉路径存在 $\Leftrightarrow$ 至多一个节点 $\deg^+(v) = \deg^-(v) + 1$ （起点）、至多一个节点 $\deg^-(v) = \deg^+(v) + 1$ （终点），其余节点入度等于出度

为什么这个条件是充分的（不仅仅是必要的）？直觉是：只要度数条件满足，你从任意节点出发沿未走过的边随意走，一定不会被困在中途——因为每个中间节点进出的边数相等，只有起点/终点可能不平衡。走到走不动的时候，你必然回到了起点（回路）或终点（路径）。如果此时还有未走过的边，它们一定构成若干个子回路，可以被拼接（splice）到主回路中——这正是 Hierholzer 算法的核心思想。

判定复杂度

判定欧拉路径/回路是否存在，只需遍历所有边统计度数： $O(V + E)$ 。这是线性时间——甚至不需要实际找出路径就能判定。

Hierholzer 算法—— $O(E)$ 构造欧拉回路

知道存在之后，如何构造这条回路？Hierholzer (1873) 给出了一个优雅的 $O(E)$ 算法：

核心思想：不断走子回路，然后拼接成一条完整回路。

算法步骤：

Hierholzer(G):
    选择任意节点 v₀（若找欧拉路径，选一个奇度节点）
    stack = [v₀]
    circuit = []
    while stack is not empty:
        v = stack.top()
        if v 有未使用的邻边 (v, u):
            将 (v, u) 标记为已使用
            stack.push(u)
        else:
            stack.pop()
            circuit.append(v)
    return circuit (reversed)

逐项理解：

stack：模拟 DFS 走当前路径——沿着未走过的边一直深入
当栈顶节点没有未使用的边时，它被”弹出”并加入最终回路——这意味着从它出发的所有边都已走完
circuit：最终结果，存储的顺序是反向的（先弹出的是”最内层”的节点）

为什么是 $O(E)$ ？ 每条边被访问恰好一次（标记为已使用后不再访问），每个节点进出栈的总次数与它的度数成正比，所以总时间 $O(E)$ 。

数值走查：在上图的 5 节点 8 边图上，Hierholzer 的执行过程是：

从 A 出发，走 A→B→C→D→A，回到起点。这是一个子回路，消耗了 4 条边。
检查子回路上的节点——B 还有未使用的边（B-D 和 B-E）。
从 B 出发走新子回路：B→D→E→A→B，消耗剩余 4 条边。
将子回路嵌入主回路的 B 处：A→B→D→E→A→B→C→D→A。
所有 8 条边都走过了，得到完整的欧拉回路。

哈密顿路径：从优雅到深渊

问题定义

哈密顿路径问题看起来和欧拉路径”差不多”——只是把”每条边走一次”换成”每个节点走一次”。但计算复杂性的差别是天壤之别。

哈密顿路径（Hamiltonian path）问题：给定图 $G = (V, E)$ ，是否存在一条简单路径（不重复节点）恰好经过每个节点一次？

哈密顿回路（Hamiltonian cycle）问题：是否存在一个简单环恰好经过每个节点一次？

与欧拉问题的关键区别：

欧拉问题有简单的充要条件（度数奇偶性）→ $O(V+E)$ 判定
哈密顿问题没有已知的简单充要条件 → 没有已知的多项式时间判定算法

NP-completeness

Karp (1972) 在其里程碑式的论文中证明了哈密顿回路问题是 NP-complete 的。这意味着：

NP 中：如果有人给你一条候选路径，你可以在 $O(n)$ 时间内验证它是否是哈密顿路径（检查是否每个节点恰好出现一次）
NP-hard：如果你能在多项式时间内求解哈密顿回路，那你就能在多项式时间内求解所有 NP 问题——包括 SAT、图着色、子集和等上千个问题

目前人类已知的最好精确算法是动态规划（Held-Karp 算法），时间复杂度 $O(n^2 \cdot 2^n)$ ——比暴力的 $O(n!)$ 好，但仍然是指数级的。

暴力搜索与回溯

最直观的算法是回溯法：尝试所有可能的节点排列，检查每对相邻节点之间是否有边。

HamiltonianDFS(G, path, visited):
    if |path| = n:
        if (path[n-1], path[0]) ∈ E:  // 检查能否成环（回路版本）
            return path
        return null
    v = path.last()
    for each u ∈ N(v):
        if u ∉ visited:
            visited.add(u)
            path.append(u)
            result = HamiltonianDFS(G, path, visited)
            if result ≠ null: return result
            path.removeLast()
            visited.remove(u)
    return null

最坏情况下，搜索树有 $O(n!)$ 个叶子（ $n$ 个节点的所有排列）。剪枝可以在实际中大大减少搜索量——比如当某个未访问节点已经被”隔离”（没有与当前路径连接的未访问邻居）时，可以提前回溯。但从理论上说，没有任何已知的剪枝策略能将最坏复杂度降到多项式。

一些充分条件（但不是充要条件）

虽然没有完美的判定条件，数学家发现了一些充分条件——如果图足够”稠密”，哈密顿回路几乎一定存在：

Dirac 定理 (1952)：如果 $n \geq 3$ 且每个节点的度数 $\deg(v) \geq n/2$ ，则 $G$ 有哈密顿回路。

Ore 定理 (1960)：如果 $n \geq 3$ 且对于每对不相邻节点 $u, v$ ，都有 $\deg(u) + \deg(v) \geq n$ ，则 $G$ 有哈密顿回路。

这些条件本质上是说：图足够稠密（边足够多）时，哈密顿回路一定存在。但它们只是充分条件——有些稀疏图也有哈密顿回路（如环图 $C_n$ ），而满足条件的图的判定反而不是难点。真正难的是一般图。

P vs NP 的震撼对比

现在让我们把两个问题放在一起，直面这个计算复杂性中最令人震撼的对比：

两个问题的数学描述几乎一样——“走遍所有 X 恰好一次”，只是 X 从”边”变成了”节点”。但：

欧拉问题：1736 年 Euler 给出完美解决方案， $O(V+E)$ 判定， $O(E)$ 构造
哈密顿问题：288 年后的今天（2026 年），仍然没有多项式算法，被证明是 NP-complete

这不是”还没找到好算法”的问题。NP-completeness 意味着，除非 P = NP（绝大多数计算机科学家认为不太可能），哈密顿回路就不可能有多项式时间算法。

为什么一个如此容易，一个如此难？ 直觉上：

欧拉条件是局部的——每个节点只需检查自己的度数，不需要全局信息
哈密顿条件是全局的——你必须考虑节点之间的所有可能路径，这些路径的数量是指数级的

哈密顿与 TSP：加上权重，就是旅行商

哈密顿回路还有一个更著名的”升级版”——旅行商问题（Traveling Salesman Problem, TSP）。

TSP 的定义：给定一个完全图（每对节点之间都有边），每条边有权重 $w(u,v)$ （代表距离/成本），找一条权重和最小的哈密顿回路。

TSP 和哈密顿回路的关系：

哈密顿回路是 TSP 的判定版本：“权重和 $\leq W$ 的哈密顿回路是否存在？”
TSP 是哈密顿回路的优化版本：“在所有哈密顿回路中找权重和最小的”
因此 TSP 至少和哈密顿回路一样难——TSP 是 NP-hard

TSP 是组合优化中最经典的问题之一。我们将在 Art. 15: NP-hard 与近似算法中详细讨论 TSP 的近似算法。在这里只需要知道：哈密顿回路是 TSP 的核心子问题。

应用场景

DNA 测序组装——欧拉路径的杀手级应用

现代 DNA 测序技术（如 Illumina 短读段测序）将基因组打碎成数百万个短片段（reads），每个片段长度约 100-300 个碱基对。组装问题就是：如何从这些重叠的短片段还原出完整的基因组序列？

Pevzner 等人 (2001) 提出了一个优雅的解决方案——将问题转化为 de Bruijn 图上的欧拉路径问题：

选择参数 $k$ （k-mer 长度）
从每个 read 中提取所有长度为 $k$ 的子串（k-mer）
构建 de Bruijn 图：
- 节点 = 所有长度为 $k-1$ 的子串（(k-1)-mer）
- 有向边 = 每个 k-mer（从它的前 $k-1$ 个字符指向后 $k-1$ 个字符）
在这个有向图上找欧拉路径——走遍所有边恰好一次 = 使用了所有 k-mer = 还原了完整序列

为什么不用哈密顿路径？因为如果以 k-mer 为节点构图（overlap graph），组装问题就变成了找哈密顿路径——NP-complete！转换为 de Bruijn 图后，k-mer 变成了边，组装问题变成了找欧拉路径—— $O(E)$ ！同一个问题，换一种建模方式，从 NP-complete 变成了线性时间。 这正是图论建模思维的威力。

这一思想被 Velvet、SPAdes 等主流基因组组装工具采用，是现代基因组学的基石。

中国邮递员问题——欧拉路径的变体

“一个邮递员要走遍所在地区的每一条街道投递信件，他从邮局出发，投递完所有信件后回到邮局。怎样走使得总路程最短？” 这个问题由中国数学家管梅谷于 1962 年提出。

如果图恰好有欧拉回路（所有节点度数为偶数），答案就是欧拉回路——每条边走一次，没有浪费
如果有奇度节点，需要重复走某些边来”修复”度数的奇偶性。问题变成：用最小成本添加重复边，使所有节点度数变为偶数

对无向图，中国邮递员问题可以在多项式时间内求解（通过最小权完美匹配将奇度节点两两配对）。但对有向图和混合图，问题变成 NP-hard。

实际应用：除雪车路线规划、垃圾收集车路线、电路板检测设备的运动路径。

物流与制造——哈密顿问题的工程实例

物流路径规划：快递公司每天要配送数百个包裹到不同地址——这就是 TSP/VRP（Vehicle Routing Problem）。现实中无法精确求解大规模 TSP，使用各种近似和启发式算法（2-opt、LKH、OR-Tools）
芯片制造：PCB 钻孔机需要依次访问电路板上所有钻孔点，最小化总移动距离——这是 TSP 的一个实例
望远镜调度：天文望远镜需要在一个晚上观测多个天体目标，最小化调整方向的总时间——也是 TSP 变体

复杂度对比表

问题	判定复杂度（最坏）	构造复杂度（最坏）	复杂度类	关键条件/算法
欧拉路径/回路（无向图）	$O(V+E)$	$O(E)$	P	奇度节点数 $\in \{0, 2\}$ / Hierholzer
欧拉路径/回路（有向图）	$O(V+E)$	$O(E)$	P	$\deg^+ = \deg^-$ / Hierholzer
哈密顿路径/回路	$O(n^2 \cdot 2^n)$ *	$O(n^2 \cdot 2^n)$ *	NP-complete	Held-Karp DP / 回溯
TSP（最短哈密顿回路）	—	$O(n^2 \cdot 2^n)$ *	NP-hard	Held-Karp DP / 近似算法
中国邮递员（无向）	$O(V+E)$	$O(V^3)$	P	最小权完美匹配

*Held-Karp 是已知最优精确算法，仍为指数级

⚙️ 迭代机器视角 — Hierholzer (Euler circuit)

Hierholzer 算法是构造性算法——通过拼接回路段来构建 Euler 回路，不是在求解方程或优化问题。属于 COMP（组合构造）范式。

→ 框架详解：Art. 0A

🔁 迭代机器视角 — Hamilton path (backtracking)CST: 约束满足

Graph	隐式状态空间树
State[v]	当前路径 + visited 集合
SELECT	LIFO（DFS 回溯）
COMBINE	尝试扩展路径 → 检查约束
重入	可回退
TERMINATE	找到解或穷尽
求解方法	B&P

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文展示了图论中最令人震撼的对比之一——两个”看起来几乎一样”的问题，计算复杂度却天差地别：

欧拉路径/回路：走遍每条边恰好一次。判定条件极其简单（数度数），构造算法极其高效（Hierholzer, $O(E)$ ）。这是图论的起源——1736 年 Euler 解决七桥问题时开创了整个学科
哈密顿路径/回路：走遍每个节点恰好一次。NP-complete，288 年后仍无多项式算法。这是计算复杂性的核心问题之一
P vs NP 的第一次照面：一字之差（边 vs 节点），但前者在 P 中，后者在 NP-complete 中。这个差距提醒我们：问题的难度不在于它的描述有多复杂，而在于解空间的结构
应用：欧拉路径驱动了 DNA 测序组装和路线规划；哈密顿问题（TSP）是物流、制造、调度的核心

DAG（上一篇）保证了无环性，让线性时间算法成为可能。欧拉/哈密顿（本篇）追求闭合回路上的完备遍历。但图中还有一类极其重要的特殊结构——树。树是连通无环图，它同时满足”连通”和”无环”两个性质，比 DAG 更特殊。下一篇 Art. 5: 树上算法将展示：在树上，许多在一般图上困难的问题都有优雅高效的解——因为树没有环、没有多余的路径，它是图的”最经济”连通形式。

实现指引

算法	库	函数/方法
欧拉回路判定	NetworkX	`nx.is_eulerian(G)`
欧拉回路构造	NetworkX	`nx.eulerian_circuit(G)`
欧拉路径构造	NetworkX	`nx.eulerian_path(G)`
有向欧拉回路	NetworkX	`nx.is_eulerian(G)` (DiGraph)
哈密顿路径	NetworkX	无内置——需自行实现回溯或 DP
TSP 近似	NetworkX	`nx.approximation.traveling_salesman_problem(G)`
TSP 精确/启发式	Google OR-Tools	`ortools.constraint_solver.routing`
中国邮递员	NetworkX	`nx.eulerian_circuit(nx.eulerize(G))`
欧拉回路	igraph	无直接内置——可通过 DFS 自行实现