euler · 一笔画

Euler path：度数判据与 Hierholzer

1736 年，Euler 处理了一个关于 Königsberg 的消遣问题：城里七座桥横跨 Pregel 河，能否走一条路线，把每座桥不重不漏地经过一次。他的回答不止是「不能」，还给出了一套判断任意图能否做到的办法，以及一个方法论上的转向——河有多宽、桥有多长、街道朝哪个方向，与答案全都无关，剩下的只有「哪块陆地与哪块陆地相连」。这篇论文 [1] 通常被算作图论的起点。

本页是 graph 系列的一员。拓扑排序管的是点之间的先后，本页管的是边的遍历，两者都靠一个局部量（in-degree 与度数）把全局问题压成一条可验证的条件。把「每条边走一次」换成「每个点走一次」，得到的是 Hamilton 圈：度数够高就一定绕得回来讨论的那个问题，难度天差地别，§4 专讲这一对照。

1 · 七桥问题的抽象

Königsberg 的地形里，只有连通关系进入模型：四块陆地缩成四个点，七座桥缩成七条边。同一对陆地之间有两座桥，模型里就有两条端点相同的边，这种允许重边的图叫 multigraph。抽象完之后，原问题变成：能否在这张图上走一条路线，每条边恰好经过一次。

定义 1.1（Euler path 与 Euler circuit） 图上的一条 walk，若把每条边恰好用一次，称为一条 Euler path；若它的起点与终点重合，称为一条 Euler circuit。Euler circuit 是 Euler path 的特例。

判据的全部依据是一次计数。设某个点既不是起点也不是终点，路线每穿过它一次，就用掉与它关联的两条边：一条进来，一条出去。若路线穿过它 $m$ 次，它的度数就是 $2m$ ，必为偶数。起点与终点不重合时，起点多出最初那条出边、终点多出最末那条入边，两者的度数各为奇数；起点与终点重合时，这一出一入又凑成一对，度数仍为偶数。

于是奇度点的个数只能是 0 或 2，别无第三种可能。Königsberg 四块陆地的度数是 3、5、3、3，四个全是奇数，判据到此已经关上了门。

2 · 度数判据

定理 2.1（无向图） 设图 $G$ 中带边的点连通。 $G$ 有 Euler circuit 当且仅当每个点的度数都是偶数； $G$ 有 Euler path 当且仅当奇度点恰有两个，且这两个点只能作为路线的两端。

证明必要性即 §1 的计数：路线穿过一个点必成对消耗它的边，只有两端可以落单。充分性由 §3 的 Hierholzer 构造给出。该构造在度数条件下必定输出一条用尽全部边的通路，构造成功本身就是存在性的证明。∎

有向图上，同一笔账要按方向分开记。路线穿过一个点时，用掉的是一条入边加一条出边，入度与出度必须相等；起点多出一条出边，终点多出一条入边。

定理 2.2（有向图） 设图中带边的点在忽略方向后连通。有 Euler circuit 当且仅当每个点的入度等于出度；有 Euler path 当且仅当恰有一个点的出度比入度多 1（它是唯一可能的起点）、恰有一个点的入度比出度多 1（它是唯一可能的终点），其余各点入出度相等。

警示 · 连通性这个前提不能省。两个互不相连的三角形，每个点的度数都是 2，全偶条件成立，却显然没有一条路线能同时走遍两个三角形的边。度数判的是「局部收支平衡」，连通判的是「这些边是否属于同一个连通块」，两者缺一不可。本页的判据实现把连通性单独检查一遍，只看带边的点，孤立点不影响结论。

图 2-1 · 五张图上的度数判据。可切换无向与有向的例子，对照度数表与判定结论；奇度点标红，判据给出的合法起点另作标记。

3 · Hierholzer 的栈式构造

判据说存在，不等于知道怎么走。最朴素的走法是贪心：站在当前点上，随便挑一条没走过的边走过去，走不动就停。这个办法会卡住。双三角图（两个三角形共用中心点 C）从 A 出发，按字典序依次是 A→B→C→A，三条边走完就回到了起点，而 C 另一侧的三条边一条也没碰到。贪心不回头，走到 A 就没有下文。

Hierholzer 1873 年的做法 [2] 把「走不动」变成一次转身而非终止：维护一个栈，栈顶的点若还有未用的边，就走过去并把对端压栈；若没有了，就把栈顶弹出、追加到封存序列，然后从新的栈顶继续探。栈空时，把封存序列整个翻转，就是要找的路线。

正确性来自度数条件：一次弹栈意味着当前点的边已用尽，而在全偶的图上，从某点出发的一段行走要么还能继续，要么必然已经回到了出发点。所以每次「走不动」时消耗掉的都是一个闭合回路，弹栈只是把这个回路按顺序拆开、嵌进已有的序列里。栈式写法把「找回路、把回路接进已有回路」这两件事合并成了同一次遍历，代价是 $O(V + E)$ 。

实现里有一处与直觉不合的地方。栈式写法在连通图上从不停在半路：弹栈之后还会从前一个点继续探，所以它总能把每条边都用掉，哪怕这张图根本没有 Euler path。Königsberg 从 A 起跑，七条边一条不剩地被消费完，弹栈序列翻转后是 A B A D B C D B。失败的表现不是「走不动」，而是这条序列在第 6 个位置接不上——D 与 B 之间的两条边早已用尽。本页的测试最初按「走不完」断言，四个起点全部落空，判据只好改写成「翻转后的序列是否处处相连」。教科书讲这段算法时通常先假定判据成立，于是不会遇到这一情形。

图 3-1 · 朴素贪心与 Hierholzer 的单步对照。可切换策略、图与起点：贪心在双三角图上三步即卡死，Hierholzer 则把封存序列一路补成完整路线；在 Königsberg 上可见边被用尽而序列断开。

4 · 走边与走点的分界

把定义里的「每条边恰好一次」改成「每个点恰好一次」，得到的是 Hamiltonian path 与 Hamiltonian cycle。两个定义的差别小到只有一个词，判定难度却分处两端：Euler 判据是一次线性扫描，而判断一张图有没有 Hamiltonian cycle 是 Karp 1972 年列出的 21 个 NP-complete 问题之一 [3]，至今没有多项式算法。

差别的来源可以说得很具体。度数是一个可加的局部量：每条边给两端各贡献 1，而任何路线穿过一个点时必成对消耗它的边。「能不能一笔画」的答案完全由这条奇偶性质决定，验证它只需把每条边给两端各记一次。点的约束没有这样的账本——「这个点已经用过了」这件事无法折算成它邻边上的任何守恒量，于是没有局部判据可查，只剩把各种走法搜一遍。

图 4-1 · 在同一批图上穷举 Hamiltonian cycle。可切换图，观察回溯搜索的路径压栈与撤销，并与该图的 Euler 判据结论对照。

同一批图上跑下来，两个判据互不蕴含，方向还相反。Königsberg 没有 Euler path，却有 Hamiltonian cycle A→B→C→D→A，搜索扩展 3 个节点就撞上了它；双三角图有 Euler circuit，却没有 Hamiltonian cycle：中心点 C 是割点，任何经过它两次的路线都不合法，搜索扩展 12 个节点后穷尽全部分支才确认。需要说明的是，五个点的图上这两个数字都很小，指数与线性的分野在这种规模上根本显不出来；显出来的是判据的形状差异：一边是一次扫描，另一边是一棵必须走到底的搜索树。

建议 · 这个分界在基因组 assembly 里有一个著名的现身。把测序读段两两 overlap 建图、读段作点，拼接就成了求 Hamiltonian path，规模一大即不可行；改用 de Bruijn 图，把长度 $k$ 的子串作点、读段作边，同一个拼接任务就成了求 Euler path，规模再大也是线性 [4]。问题没变，建模换了一次，难度就从 NP-complete 落回 P。

5 · 参考文献

Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 128–140.
Hierholzer, C. (1873). Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6(1), 30–32.
Karp, R. M. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, 85–103.
Pevzner, P. A., Tang, H., & Waterman, M. S. (2001). An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences, 98(17), 9748–9753.