定义

欧拉回路是指一条遍历图 GG 中每条边恰好一次的回路。

当 GG 为有向图和无向图时，判定定理不尽相同。

  • 当 GG 为有向图时，GG 存在欧拉回路的充要条件是 GG 是强连通的且 ∀v∈V,din(v)=dout(v)\forall v\in V,d_{in}(v)=d_{out}(v)；
  • 当 GG 为无向图时，GG 存在欧拉回路的充要条件是 GG 是连通的且 ∀v∈V,d(v) is even\forall v\in V,d(v)\text{ is even}。

这两个条件的必要性都是显然的，下文我们只对充分性进行证明，证明方法是证明 Hierholzer 算法能构造出一个合法的欧拉回路。

Hierholzer 算法

如果 GG 是强连通有向图，且每一个点的入度等于出度，我们可以直接使用 Hierholzer 算法构造出一条欧拉回路，伪代码如下：

1
2
3
4
5
6
7
8
9
stk = []
def dfs(u):
    for e(u, v) in adj[u]:
        remove(e)
        dfs(v)
    stk.append(u)
# Arbitrarily choose vertex
dfs(1)
reverse(stk)

  1. 递归的终点必定是某个递归的起点。

    由于这个图入度等于出度，所以 DFS 找出的每一条路径的中间节点必然是入度和出度同时减一。如果终点不是起点，那么必然能够继续走下去。

  2. 这个压栈的方式可以构造出一个合法的欧拉回路。

    如果只有一个环，那么这个算法后序压栈并且逆序输出自然是正确的。

    如果有多个环，假设最开始的环起点是 v1v_1 终点是 vmv_m，那么栈中的元素应当形如 p(vm),vm,…,p(v2),v2,p(v1),v1p(v_m),v_m,\dots,p(v_2),v_2,p(v_1),v_1，其中 p(x)p(x) 表示 xx 调用 DFS 后入栈的元素按照入栈顺序排列得到的序列。

    当我们最终逆序输出时，viv_i 后面是 R(p(vi))R(p(v_i))，然后才是 vi+1v_{i+1}。我们可以认为它走了一个环路之后又从 vi+1v_{i+1} 继续走，这是一个合法的欧拉回路。

    因为这一定是有限个环，所以最终合并出来的也一定是一个合法的欧拉回路。

  3. 必定遍历了所有的边。

    假设 DFS 结束了，已访问的边集是 E1E_1，未访问的边集是 E2E_2，我们用反证法证明 E2=∅E_2=\varnothing。

    因为 E1≠∅E_1\neq \varnothing 是算法显然能够保证的，我们假设 E2≠∅E_2\neq \varnothing，则两个集合都是 EE 的非空真子集。

    设 V1V_1 是 E1E_1 的边的端点集合，V2V_2 同理，任取 v1∈V1,v2∈V2v_1\in V_1,v_2\in V_2。

    由于 GG 是强连通的，那么 v1,v2v_1,v_2 之间存在路径 PP，设 ww 是路径 PP 上第一个在 V2V_2 中的节点，也就是说，存在 e=(u,w)e=(u,w) 使得 u∈V1,w∈V2u\in V_1,w\in V_2。

    既然 u∈V1u\in V_1，那么 uu 就被 DFS 遍历过了，那么 ww 也被 DFS 遍历过了，于是 ww 的出边都在 E1E_1 中。

    但是，DFS 执行完后， ww 在 G2=(V,E2)G_2=(V,E_2) 中的入度仍然等于出度，又因为 ww 的出边不在 E2E_2 中，所以 ww 的入边也不在 E2E_2 中，这就与 w∈V2w\in V_2 产生了矛盾。

如果 GG 是连通无向图，我们只需要删除的时候把反向边也删掉即可，证明方法基本一样。