欧拉图 学习笔记

在图论中，欧拉路径（Eulerian path）是经过图中每条边恰好一次的路径，欧拉回路（Eulerian circuit）是经过图中每条边恰好一次的回路。 如果一个图中存在欧拉回路，则这个图被称为欧拉图（Eulerian graph）；如果一个图中不存在欧拉回路但是存在欧拉路径，则这个图被称为半欧拉图（semi-Eulerian graph）。

CAUTION

此处定义中虽然使用「路径」一词，但严格说来此处使用的概念应该是「迹（trail）」。欧拉路径与欧拉回路仅能使用每条边恰好一次，但并没有对经过顶点的情况进行限制。

性质

以下我们假设所讨论的图 $G$ 中不存在孤立顶点。该假设不失一般性，因为对于存在孤立顶点的图 $G$，以下性质对从 $G$ 中删除孤立顶点后得到的图 $G^{\prime }$ 仍然成立。

对于连通图 $G$，以下三个性质是互相等价的：

1. $G$ 是欧拉图；
2. $G$ 中所有顶点的度数都是偶数（对于有向图，每个顶点的入度等于出度）；
3. $G$ 可被分解为若干条不共边回路的并。

以下我们对等价性进行证明。

若一个图 $G$ 是欧拉图，那么 $G$ 中所有顶点的度数都是偶数：考虑从任意顶点开始沿着欧拉回路走一圈，则每个点 $v$ 的度数等于离开点 $v$ 的次数加到达点 $v$ 的次数。又由于行动的轨迹是一个回路，则对于每个点 $v$，离开该点的次数等于到达该点的次数。这也就是说，每个点的度数都形如 $2k$，即偶数。 特别地，对于有向图，根据相同的证明过程，每个顶点的入度等于出度。

若一个图 $G$ 中所有顶点的度数都是偶数（或入度与出度相等），则它可被分解为若干条不共边回路的不交并：考虑从任意顶点 $u$ 开始，选择任意出边 $(u,v)$，走向对应的相邻顶点 $v$ 并删除 $(u,v)$，直到返回最初开始的顶点 $u$。可以证明该过程必定会最终回到 $u$：每当到达一个新的顶点 $v\ne u$ 时，根据上一条性质，该顶点剩余的度数为奇数，也就是说必定存在一条出边，该过程不会在点 $v$ 终止。（换句话说，该过程会且仅会在回到点 $u$ 时停止。）又因图 $G$ 中的边数是有限的，该过程必定会在有限步内停止，则最终必然可以返回 $u$ 并得到一条回路。注意到在前述证明中我们仅使用了点度数均为偶数的性质，且在找到并删除一条回路后剩下部分的图仍然满足该性质，我们可以不断重复该过程直到剩下的图为空图，从而将 $G$ 拆分为若干条不共边的回路。 更进一步地，每条回路都可以被从其多次经过的顶点处分解成若干简单环的不交并，所以上述性质中的简单回路亦可被替换为简单环。

若一个连通图 $G$ 可被分解为若干条不共边回路的不交并，则 $G$ 是欧拉图：对于一组不共边回路，每次从中选出两条有共同顶点的回路并将其合并为一条，重复该过程直到不存在有共同顶点的两条回路。 可以证明该过程结束时剩下的回路唯一。对于任意两条不共边回路 $P_1,P_2$，若 $P_1$ 与 $P_2$ 共点，则可以在共点处直接进行合并；否则，任取 $P_1$ 上的点 $v_1$ 与 $P_2$ 上的点 $v_2$，根据 $G$ 的连通性，存在连接 $v_1$ 和 $v_2$ 的路径 $e_1,e_2,\dots ,e_k$，其中的每条边 $e_i$ 都被一个回路 $C_i$ 包含，且 $P_1$ 与 $C_1$，$C_i$ 与 $C_{i+1}$，$C_k$ 与 $P_2$ 均存在共点（或者 $C_i=C_{i+1}$，此情况不影响证明）。此情况下，$P_1$ 与 $P_2$ 可以通过 $C_1,\dots ,C_k$ 进行合并。也就是说，任意两条回路都可以进行合并，最后剩下的回路必定唯一，且组成该回路的边集是所有不共边回路的并即 $E(G)$，该回路为 $G$ 上的欧拉回路，$G$ 为欧拉图。

以上的性质同时也构成了欧拉图的判断条件。具体地说，一个图是欧拉图当且仅当非零度顶点互相（强）连通，且顶点的度数都是偶数（或入度与出度相等）。

欧拉回路 / 欧拉路径的构造

此处我们介绍最常用的 Hierholzer 算法，该算法的核心思想为利用上述欧拉图性质中的第三点，即欧拉图可以被拆解为若干条不共边回路的并。 可以注意到，在上述证明中其实已经提到了完整可行的将不共边回路合并为欧拉回路的操作，且在使用合适的数据结构储存时（如使用类链表的结构储存环）实现并不困难。

算法的具体流程为先从图中找到一条回路作为当前回路，每次从当前回路中选取剩余度数不为零的点，从该点出发找到一条新的简单回路，并将该简单回路与当前回路合并，重复该过程直到当前回路中的所有点均无剩余度数，此时的当前回路即为欧拉回路。

该算法同样适用于有向图。对于半欧拉图，可以从图中找到一条连接两个奇度数点的路径作为当前路径，每次选取度数非零的点寻找简单回路并将其与当前路径合并，最后得到欧拉路径。

实现

Hierholzer 算法的伪代码如下：

$$\begin{array}{ll}1& \text{Input. }\text{The edges of the graph }e,\text{ where each element in }e\text{ is }(u,v)\\ 2& \text{Output. }\text{The vertex of the Euler Road of the input graph}.\\ 3& \text{Method. }\\ 4& \text{Function }\text{Hierholzer }(v)\\ 5& circle\leftarrow \text{Find a Circle in }e\text{ Begin with }v\\ 6& \text{if }circle=\varnothing \\ 7& \text{return }v\\ 8& e\leftarrow e-circle\\ 9& \text{for}\text{ each }v\in circle\\ 10& v\leftarrow \text{Hierholzer}(v)\\ 11& \text{return }circle\\ 12& \text{Endfunction}\\ 13& \text{return }\text{Hierholzer}(\text{any vertex})\end{array}$$

时间复杂度分析

Hierholzer 算法的时间复杂度为 $O(|E|+|V|)$。

注意到在前述正确性分析中，在欧拉图或半欧拉图上寻找简单回路（或半欧拉图的初始路径）的过程是 无需回溯 的，只要沿着剩下的边一直走就必定可以发现所求的回路或路径，且 每条边仅会被访问一次。 为了利用这一性质，在实现上应采取类链表的方式储存图中的边，如邻接表或链式前向星，以便每条边在被访问过后即刻删除之。如果采用朴素的邻接矩阵进行储存，则每次寻边耗时 $O(|V|)$，总复杂度为 $O(|V||E|)$。

如果需要输出字典序最小的欧拉路或欧拉回路，则需要将边排序，时间复杂度为 $\Theta (|E|\log |E|)$ 。

应用

有向欧拉图可用于计算机译码。

设有 $m$ 个字母，希望构造一个有 $m^n$ 个扇形的圆盘，每个圆盘上放一个字母，使得圆盘上每连续 $n$ 位对应长为 $n$ 的符号串。转动一周（$m^n$ 次）后得到由 $m$ 个字母产生的长度为 $n$ 的 $m^n$ 个各不相同的符号串。

构造如下有向欧拉图：

设 $S=\{a_1,a_2,\cdots ,a_m\}$，构造 $D=⟨V,E⟩$，如下：

$V=\{a_{i_1}{a}_{i_2}\cdots a_{i_{n-1}}|a_i\in S,1\le i\le n-1\}$

$E=\{a_{j_1}{a}_{j_2}\cdots a_{j_{n-1}}|a_j\in S,1\le j\le n\}$

规定 $D$ 中顶点与边的关联关系如下：

顶点 $a_{i_1}{a}_{i_2}\cdots a_{i_{n-1}}$ 引出 $m$ 条边：$a_{i_1}{a}_{i_2}\cdots a_{i_{n-1}}{a}_r,r=1,2,\cdots ,m$。

边 $a_{j_1}{a}_{j_2}\cdots a_{j_{n-1}}$ 引入顶点 $a_{j_2}{a}_{j_3}\cdots a_{j_n}$。

这样的 $D$ 是连通的，且每个顶点入度等于出度（均等于 $m$），所以 $D$ 是有向欧拉图。

任求 $D$ 中一条欧拉回路 $C$，取 $C$ 中各边的最后一个字母，按各边在 $C$ 中的顺序排成圆形放在圆盘上即可。