欧拉迹 | Codeboy's Blog

形式陈述

在有限无向多重图 $G=(V,E)$ 中，欧拉迹是一个按边身份记录的迹

v_0,e_1,v_1,\ldots,e_m,v_m,

其中 $e_i$ 连接 $v_{i-1}$ 与 $v_i$ ，而 $e_1,\ldots,e_m$ 恰好把 $E$ 中每条边列出一次。顶点可以重复，边不能重复。若 $v_0=v_m$ ，称为欧拉回路；否则称为开放欧拉迹。

这里允许平行边与自环：两条端点相同的边仍是两个不同对象，自环对度数贡献 $2$ 。因此多重图中只写顶点序列未必足以指定走过哪条边，应同时记录边的身份。若 $E=\varnothing$ 且 $V\ne\varnothing$ ，本页允许单个顶点构成长度为零的欧拉回路；无顶点的空图另作约定。

直觉

欧拉迹要完成的是“每项连接任务执行一次”。顶点只是转接站，多次回到同一个站点并没有重复任务。闭合路线中，进入一个顶点的边端必须与离开的边端配对；开放路线只在起终点各留下一个未配对边端。这解释了为什么存在性由度数奇偶和含边部分的连通性控制。

这个要求与Hamilton 路与圈不同：后者逐一访问顶点，前者逐一使用边。一个交汇点可以成为欧拉路线反复经过的枢纽，却可能阻断 Hamilton 圈。

例子与边界

令两组三角形共享顶点 $w$ ，边集为 $\{wa,ab,bw,wc,cd,dw\}$ 。路线

w,a,b,w,c,d,w

依次用完六条不同边，因而是欧拉回路。共享点 $w$ 的度为 $4$ ，其余四点的度为 $2$ ；路线中三次写出 $w$ 完全合法。这张“8”字图没有 Hamilton 圈，因为删除 $w$ 后两组三角形的剩余顶点彼此分离。

一个简单圈沿圈走一周就是欧拉回路；路径图从一端走到另一端就是开放欧拉迹。反之，两个不相交的圈虽然所有度数均为偶数，却无法由一条迹覆盖。孤立顶点不含待走边，不妨忽略。

一棵至少有一条边的树若存在欧拉迹，就必须是路径图。原因是树的每条边都是桥，经过一条桥进入分支后不能再沿同一条边返回；任何真正的分叉都会使一条路线漏掉某个分支。等价地，非路径树至少有三个叶子，并因此不可能只有两个奇度顶点。

无向欧拉迹反向走仍是欧拉迹；只有闭合欧拉回路可以在任意出现位置切开、循环移位后继续闭合。有向图还必须遵守边方向，不能直接套用无向度数判定或任意反转。

推论与应用

对至少有一条边的图，Euler 道判定给出完整标准：非孤立部分连通，并且奇度顶点数为零或二。零个奇点对应回路；两个奇点对应以它们为两端的开放迹。

Hierholzer 构造沿未用边走出闭合子迹，再在已有路线上的交点插入剩余闭合子迹，直到每条边都被使用。上述“8”字图正是两条闭合子迹在 $w$ 处拼接的最小直观模型。

道路巡检在每条道路都需检查一次时产生欧拉模型；若道路必须重复才可完成，则转向邮递员问题。DNA 片段组装中，以相邻短串为顶点、观测到的片段为有向边，可把重叠拼接转成有向欧拉迹；重复片段必须保留为不同边，不能被简单图去重。

参考资料

Mitchel T. Keller、William T. Trotter，Applied Combinatorics，在线版，访问于 2026 年，§5.3 “Eulerian and Hamiltonian Graphs”，定理 5.13。
Misha Lavrov，Start Doing Graph Theory，在线版，访问于 2026 年，第 8 章 “Euler Tours”，定义 8.1、定理 8.4。