欧拉回路

定义

欧拉回路通常用来解决”一笔画”问题。具体而言就是询问一张图上是否存在一条回路使得它经过所有的边一次。如果有，那么求出这条回路。

例如，在下面这个图里面：

一条欧拉回路是1 - 4 - 2 - 3 - 4 - 5 - 2 - 1。

存在性

无向图

考虑在走一条欧拉回路的时候，如果不是起点，我们每进入一个点，就一定会走出去。如果是起点，每出去一次，就一定又会回来一次。这说明如果有欧拉回路，那么每个点的度数应当是偶数。

同时，从另一方面来讲，如果某个点的度数是奇数，那么在某一次进入这个点之后，我们就出不来了。如果起点的度数是奇数，那么之后必定有一次无法回到起点。

总而言之，对于无向图，每个点的度数必须是偶数。

此外考虑当图不连通时，一般是没有欧拉回路的。但是如果有连通块上本来就没有边，像下面这样：

此时1这个点是不需要考虑的。但是并不意味着大小为$1$的连通块就不必考虑，因为它们可能有自环，如同下面这样：

但是很多的这样的连通块不行，我们的程序在判定的时候需要注意这些细节：

有向图

有向图与无向图是类似的。同样按照之前的方式考虑，进入一点就意味着需要出来，那么就说明每个点的入度与出度相同。

此外考虑连通性，与无向图类似，我们要求这个图只存在一个有边的强连通分量。

构造算法

如果满足了存在性的要求，那么这张图将被称为欧拉图。

构造一条欧拉回路看上去是可以随意走的，因为你每走一个点总能保证你有地方出去。但是这样的算法却不能保证你走过了每一条边。举一个经典的例子：

在这张无向图中，一条欧拉回路是1 - 2 - 4 - 5 - 2 - 3 - 1。如果采用随便走的策略，那么有可能走出1 - 2 - 3 - 1这样的路径就终止了。

这是因为欧拉回路实际上是由一些环以点相交构成的。观察上面正确的欧拉回路，可以发现它是由1 - 2 - 3 - 1和2 - 4 - 5 - 2构成的。

因此正确的方法应当是实现一个DFS搜索，每搜到一个环就将其插入之前的欧拉回路中，这样可以实现欧拉回路的构造。

实际上我们没有必要显式地实现插入环，而是可以通过下面这个DFS来实现：

1
2
3
4
5
6
7
8
9

tour = []  # 欧拉回路

def construct(x):
    for e in x.adj:
        x.adj.remove(e)  # 边被访问
        construct(e.either(x))  # 沿着边走下去
        tour.append(e)

# 最后将tour中的边倒序输出就是欧拉回路

这里关键是为什么是先递归后将边加入欧拉回路，并且需要倒序输出。假设现在正在考虑$u$，那么就可能会有一些环会从$u$开始并且以$u$结束，那么它们在之后的递归中又会回到$u$，因此我们先将后面的环放入欧拉回路是没有问题的。如果从$u$出发后就回不来了，那么这条”不归路应当在那些会回到$u$的环之后插入。所以这个DFS就保证了这一点。

此外，对于每一条访问过的边，我们应当将其删除 (或者使用其它方法保证之后不会再次遍历)。否则当我们进入一个点多次的时候，这些边也会遍历多次，复杂度就会变得很高。

事实上，这个无向图的构造算法对有向图也通用。

判定算法

为什么要先说构造算法然后再说判定算法呢？以为构造算法可以帮助我们判定图的连通性，而在构造之前，我们需要保证基础的度数限制是满足的。

如果度数限制满足以后，那么图中的每一个连通块 (或者强连通分量) 都可以使用之前的构造算法构造出欧拉回路。因此我们只用找到一个有边的连通块 (或强连通分量) 就可开始构造。如果构造完之后图中依然有边剩余，那么说明这张图没有欧拉回路。

完整的判定算法如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def evaluate(G):
    if G is directed:
        for v in G:
            if v.indegree != v.outdegree:
                return False
    else:
        for v in G:
            if v.degree % 2 > 0:
                return False

    for v in G:
        if len(v.adj) > 0:
            construct(v)
            break

    return len(tour) == len(G.E)

其他

欧拉路径

与欧拉回路相似，欧拉路径是一条经过所有边的路径。由于欧拉路径比欧拉回路少一条边，所以在无向图上，当且仅当存在两个点的度数是奇数。而在有向图上，则必须存在一个点入度比出度大$1$，以及另一个点出度比入度大$1$。对于有向图，只要满足单联通即可。

中国邮递员问题

假设现在有一张联通的无向图，保证度数为奇数的点的个数是偶数，问你最短的经过所有边至少一次的环的长度。

之所以称其为邮递员问题，因为原问题是在邮递员送信的背景下提出的。

假设图的边数为$m$，那么欧拉回路可以给出一个$2m$条边的方案。因为我们将原图中每一条边都复制一遍，我们将得到一张$n$个点$2m$条边的图，并且由于每个点的度数都被乘以$2$，那么这张新图必定存在欧拉路径，同时也可以给出上述问题的一个答案。