一笔画问题揭秘：轻松掌握欧拉图与欧拉回路的奥秘

0 前言

我们或多或少都接触过一笔画问题。一笔画问题，即给出一份图，要求使用连续的一笔画过所有的边。换句话说，就是能否通过一笔不间断地画出一个图形，使得每条线段恰好被画过一次。今天我们来看看如何“秒解”这种一笔画问题。

1 欧拉图与欧拉回路

解决一笔画问题的模型是欧拉图与欧拉回路。我们先简单看下定义。

欧拉图：在一个无向图中，如果存在一条回路，这条回路经过图中的每条边恰好一次，并且最终回到起点，那么这条回路被称为欧拉回路，这个图被称为欧拉图。

欧拉回路：如果一个连通的无向图包含至少一条欧拉回路，那么这个图被称为欧拉图。

简而言之，从一个点出发，如果可以不重复地走过所有边并回到原点，那么走过的这条路就是欧拉回路。一个图，如果有欧拉回路，那么这个图就是欧拉图。

这里需要留意的点是，一笔画问题有时不要求回到原点，能走完所有边即可。而欧拉回路要求最后是回到原点的。事实上，这种走完所有边但是不走回原点的路径，叫欧拉通路，我们后面会提到。现在我们先专注于欧拉回路问题，后续我们提到的一笔画，都视作要求回到原点的。

2 欧拉定理

2.1 描述

显然，不是对于所有的图，都是可以画出回到原点的一笔画的。既然如此，我们就必须能够判断一个图是否能画出一笔画。现在我就来教教大家如何快速判断。

显然，一个图如果不是连通的，那必然无法一笔画，因此我们的讨论范围是连通图，并且我们把讨论范围定为无向图。

一个连通无向图能不能画出欧拉回路，只有一个很简单的判断条件：所有点的度是偶数。

事实上，一个连通的无向图具有欧拉回路当且仅当图中所有顶点的度数都是偶数，而这，就是图论中著名的欧拉定理。

给我们一个连通无向图，我们判断这个图是否有欧拉回路，只需要判断是不是所有点的度数都是偶数即可。如果所有点的度数都是偶数，那么就存在欧拉回路，这个图是欧拉图。如果并非所有点的度数都是偶数，那么这个图就不是欧拉图。就这么简单。

这时候就有人会问了，为什么是所有点的度数都是偶数，原理是什么？

2.2 证明

必要性：对于一个连通无向图，如果存在欧拉回路，那么所有点的度数都是偶数。

证明过程：对于一个欧拉回路，每当经过一个顶点时（除了起点/终点），都会以一条边进入该顶点，再以另一条边离开该顶点。因此，对于除起点/终点之外的每个顶点，进入的边数等于离开的边数，这些顶点的度数为偶数。由于起点/终点是同一个顶点，它既被进入也被离开，所以它的度数也必须为偶数。

充分性：对于一个连通无向图，如果所有点的度数都是偶数，那么存在欧拉回路。

证明过程：Fleury 算法是一种构造性证明方法，后面讲到 Fleury 算法再具体讲。

3 半欧拉图与欧拉通路

半欧拉图：如果一个无向图中存在一条经过每条边恰好一次的路径，但不一定是闭合的，那么该图称为半欧拉图。
欧拉通路：从一个顶点开始，经过图中的所有边恰好一次到达另一个顶点的路径。
特征：在半欧拉图中，除了起点和终点外，所有其他顶点的度数都是偶数。起点和终点的度数可以是奇数（起点多了一条出的边，终点多了一条入的边）。

4 欧拉通路问题转化为欧拉回路问题

解决欧拉通路问题，我们需要先确定起点和终点，即定位到两个度数为奇数的点，分别作为起点和终点。

之后，为了方便处理欧拉通路问题，我们通常将其转化为欧拉回路问题。方法是添加一条从终点指向起点的边，形成一个欧拉图。这样，原问题就变成了寻找这个新图中的欧拉回路。

总之，求解欧拉通路和欧拉回路最大的不同在于起点和终点的选择，其他的地方都十分相似。

下面我们来看看在欧拉图里找欧拉回路的 Fleury 算法。

5 Fleury 算法

5.1 算法流程

Fleury 算法是一种较为直观的算法，用于判断并找到欧拉通路或回路。该算法的思想是在每一步选择中避免断桥（断桥是指如果删除某条边会导致图分裂成两个或多个不连通部分的边。），即避免在当前阶段移除唯一通往其他未访问顶点的边。具体步骤如下：

1. 判断图是否是欧拉图。
2. 从任意一个顶点开始。
3. 在每一步中，如果当前顶点有多条边可选，选择除了桥以外的任意一条边。桥是指如果移除这条边，图将不再保持连通。
4. 删除所选边，并移动到这条边的另一端。
5. 重复步骤3和4，直到所有边都被访问过。

5.2 算法例子

看下面这个例子，假设我们从 1 点开始，每次选择非断桥的边走，从 1 走到了 2，从 2 走到了 4，接下来，我们有 3 种走法，走 3 或走 5 或走 6，那么接下来我们应该怎么走呢。

假设我们走了 3，我们会发现，我们接下来只能走到 1，再也无法走到 5、6、7

事实上，从 4 到 3 这条边正是断桥，它将未走的边分成了不连通的两部分（1 到 3 这条边与其他未走的边不连通了），导致无法再继续走得到欧拉回路。

但是只要我们选择的是 5 或 6 这两个非断桥边，那么剩下的边仍然是连通的。

希望通过这个例子，你能更了解什么是断桥边，以及在算法过程中避免选择断桥边。

5.3 算法原理

首先我们先证明，如果一个图存在欧拉通路，那么从起点出发，一定有边是非断桥。

反证法：如果从起点出发所有边都是断桥，那么无论走哪一条，都会导致图分裂成多个不连通的图，一定不存在欧拉通路，这与我们的条件（图存在欧拉通路）矛盾。

好了，我们证明了，只要有欧拉通路，从起点出发就一定有非断桥。

接下来我们用归纳法证明算法的可行性。

这个归纳法的核心在于，始终维持了删去边之后图的欧拉性质，并且以当前点为新起点存在欧拉通路回到原起点。

记起点为 \(u\)，\(u\) 也是终点。记走过 \(n\) 条边后所处的位置为 \(p_n\)，删除走过的 \(n\) 条边后的图为 Gn。

我们来证明：当我们走过 \(n\) 条边时，删除走过的 \(n\) 条边，当前图为 \(G_n\)，起点 \(u\) 和当前点 \(p_n\) 度数同时为偶数（当 \(u= p_n\)）或同时为奇数（当 \(u \ne p_n\)），非起点和非当前点度数均为偶数，满足半欧拉图性质，必然存在从当前点到起点的欧拉通路，同时对于 \(G_n\) 和当前点（新起点） \(p_n\)，一定有非断桥的存在。

• 当我们走过 \(n = 0\) 条边时，删除走过的 \(n = 0\) 条边，当前图为 \(G_0 = G\)，起点 \(u\) 和当前点 \(p_0 = u\) 度数同时为偶数（当 \(u= p_0\)）或同时为奇数（当 \(u \ne p_0\)），非起点和非当前点度数均为偶数，满足半欧拉图性质，必然存在从当前点到起点的欧拉通路，同时对于 \(G_0\) 和当前点（新起点） \(p_0\)，一定有非断桥的边存在。
• 假设走过 \(n = k\) 条边时，删除走过的 \(n = k\) 条边，当前图为 \(G_k\)，起点 \(u\) 和当前点 \(p_k\) 度数同时为偶数（当\(u = p_k\)）或同时为奇数（当\(u \ne p_k\)），非起点和非当前点度数均为偶数，满足半欧拉图性质，必然存在从点前点到起点的欧拉通路，同时对于 \(G_k\) 和当前点（新起点） \(p_k\)，一定有非断桥的便存在。
• 由于对于 \(G_k\) 和当前点 \(p_k\)，一定有非断桥的存在，我们选择一条非断桥的边，并删除这条边，得到 \(G_{k+1}\) 和新起点 \(p_{k+1}\)。如果 \(u = p_k\)，此时 \(p_k = u\) 度数同时为偶数，那么删除边后，\(u\) 的度由偶数变为奇数，\(p_{k+1}\) 的度由偶数变为奇数。如果 \(u \ne p_k\)，此时 \(p_k\)，\(u\) 度数同时为奇数，那么删除边后，\(p_k\) 的度由奇数变为偶数，\(p_{k+1}\) 的度由偶数变为奇数。所以，仍然有起点 \(u\) 和当前点 \(p_{k+1}\) 的度数同时为偶数（当 \(u = p_{k+1}\)）或同时为奇数（当 \(u \ne p_{k+1}\)），非起点和非当前点度数均为偶数，满足半欧拉图性质，必然存在从当前点到起点的欧拉通路，同时对于 \(G_{k+1}\) 和当前点（新起点） \(p_{k+1}\)，一定有非断桥的边存在。

一直这样走，当 n 为所有的边数，便走完了所有的边，即可得到欧拉回路。

为了让大家更简单地理解这个证明过程，可以看下面这种更直观的过程说明。

在最开始，所有点的度数都是偶数，存在欧拉回路。（如果最开始度数不全是偶数，那么欧拉回路便不存在，无需计算）

接下来，选择任意非桥的边走过去并删除这条边，这时，起点和当前所在点的度数变为奇数，其余所有点的度数都是偶数，这时候便满足了半欧拉图的性质，因此必然存在从当前点到原起点的欧拉通路。

我们继续走，选择任意非桥的边走过去并删除这条边，对于除了起点和当前点，我们中间经过的所有点的度数都仍然是偶数，因为经过的点有进就有出，而起点和当前点所在点的度数都为奇数或都为偶数（如果当前点在原起点，则为偶数；如果当前点不在原起点，则为奇数），这时候便满足半欧拉图的性质，必然存在从当前点到原起点的欧拉通路。

一直这样走，直到走完所有的边，便可得到欧拉回路。

这种避免“断桥”的核心在于，始终维持了删去边之后图的欧拉性质，并且以当前点为新起点存在欧拉通路回到原起点。

6 Hierholzer 算法

解决欧拉图的算法还有复杂度更低的 Hierholzer 算法，如果大家感兴趣，请在评论区留言，我再进行补充。