欧拉路径与欧拉回路

1. 什么是欧拉迹？

欧拉迹（也称欧拉路径）是穿过图的一条路线，它恰好经过每条边一次。你可以多次经过同一个顶点，但绝不能两次走同一条边。

它回答了一个出人意料地实用的问题：给定一个由道路、管道或电缆构成的网络，我能否在不重复任何连接的情况下走遍全部？

2. 欧拉路径与欧拉回路

这两个术语密切相关，但并不相同：

• 欧拉路径经过每条边一次，可以在不同的顶点开始和结束。
• 欧拉回路是一条闭合的欧拉迹——它经过每条边一次，并回到起始顶点。

每条欧拉回路都是欧拉迹，但反之不成立。一个图支持哪一种，完全取决于其顶点的度数。

3. 柯尼斯堡七桥问题

普鲁士城市柯尼斯堡被一条河分成四块陆地，由七座桥相连。市民们想知道，能否散步一次，恰好走过每座桥一次并回到起点。

1736 年，莱昂哈德·欧拉证明了这样的路线并不存在。他把每块陆地看作一个顶点、每座桥看作一条边，并做出关键观察：每当你经一座桥进入一块陆地，就必须经另一座桥离开，因此每个"途经"顶点都需要偶数座桥。柯尼斯堡的四个顶点都连着奇数座桥，使得这条路线不可能实现。这一证明被公认为图论的诞生。（参见我们的图论的历史。）

4. 度数规则：何时存在？

顶点的度是与它相连的边的数量。欧拉的洞见为连通图给出了简单而精确的规则：

• 当且仅当每个顶点的度都为偶数时，存在欧拉回路。
• 当且仅当恰好两个顶点的度为奇数时，存在开放的欧拉路径——且必须从其中一个开始、在另一个结束。
• 若超过两个顶点的度为奇数，则不存在欧拉路径。

此外图还必须是连通的。否则，只需数一数奇数度的顶点即可。

5. 如何找到它：Fleury 与 Hierholzer 算法

一旦确定欧拉迹存在，两种经典算法可以把它构造出来：

Fleury 算法

每次走一条边，除非别无选择，否则绝不走桥（一条删去后会使图不连通的边）。它易于理解，但不断检查桥使其相对较慢。

Hierholzer 算法

高效之选，时间复杂度为 O(E)。先沿边形成一个闭环，然后反复在当前路径上找一个仍有未使用边的顶点，并在那里拼入另一个环。当没有未使用的边时，这些环合并成一条欧拉回路。

6. 欧拉 vs 哈密顿

两者常被混淆，但它们是完全不同的问题：

• 欧拉路径经过每条边一次。
• 哈密顿路径经过每个顶点一次。

关键差别在于计算难度：判断欧拉迹是否存在很容易（数奇数度即可），而判断哈密顿路径是否存在是 NP 完全问题——属于计算机科学中最难的一类。旅行商问题就是一个著名的哈密顿式挑战。

7. 现实应用

• 路线巡检（中国邮递员问题）：寻找覆盖每条街道的最短路线——邮件投递、垃圾收集、扫雪、街道清扫。
• DNA 测序：现代基因组组装根据短读段构建 De Bruijn 图，并寻找欧拉路径来重建序列。
• 网络维护：对电信或公用事业网络中的每条链路恰好检测一次。
• "一笔画"图形：不抬笔画出一个图形的经典谜题，正是一个欧拉迹问题。