欧拉回路和欧拉路径的学习笔记。
例题:[UOJ 117] 、 [LOJ 10105] 、 [Luogu 2731] 。
一些定义
一个图,若能够找到一条路径,使得可以遍历完所有的边且不重复,则这样的图称为欧拉图,这条路径称为欧拉路径,若路径闭合也称为欧拉回路。
一些定理
以下大量文字摘自维基百科。
定理一
- 连通的无向图有欧拉路径的充要条件是:图中度数是奇数的顶点数量是 $0$ 或 $2$ 。
- 连通的无向图有欧拉回路的充要条件是:图中所有点的度数都是偶数。
证明一
- 必要性:如果一个图能够一笔画成,那么对于除了起点和终点的其他顶点,总有路径中连向点的边数与这个点的出边数相同,即这个点的度数为偶数。而对于起点和终点,若起点和终点相同,则这个点的度数也为偶数;否则这两个点的度数为奇数。即图中度数为奇数的点的数量是 $0$ 或 $2$ 。
- 充分性:
- 如果图中没有度数为奇数的点,则任选一点出发,连一个环。如果这个环就是原图则结束。若不是,由于图是连通的,该环与原图的其他部分必然有公共顶点,从该点出发,在原图的剩余部分中重复上述步骤。由于原图是连通图,经过若干步后,全图被分为一些环。由于两个相连的环就是一个环,原来的图也就是一条欧拉回路。
- 如果图中有两个度数为奇数的顶点 $u$ 和 $v$ ,那么将他们连边后,得到一个无奇数度数的点的连通无向图,由上知这是一个环,因此去掉新加的边后,成为一条路径,起点和终点是 $u$ 与 $v$ 。至此证毕。
定理二
如果连通无向图有 $2k$ 个奇数度数的顶点,那么它可以且至少可以用 $k$ 笔画成。
证明二
将这 $2k$ 个奇数度数的顶点分成 $k$ 对后分别连起,则得到一个无奇数度数顶点的连通图。由上知这个图是一个环,因此去掉新加的边后至多成为 $k$ 条欧拉路径,因此必然可以用 $k$ 笔画成。但是假设全图可以分为 $q$ 条欧拉路径,则由定理一知,每条链中只有不多于两个奇顶点,于是 $2q\ge 2k$。因此必定至少要 $k$ 笔画成。
有向图的欧拉路径
- 一个连通的有向图可以表示为一条欧拉回路的充要条件是:每个顶点的出度和入度都相等。
- 一个连通的有向图可以表示为一条不闭合的欧拉路径的充要条件是:某一个点的出度比入度多 $1$ ,另一个点的出度比入度少 $1$ ,前者为起点而后者为终点。
证明方式类似证明一。
Hierholzer算法
Hierholzer算法是一种可以在时间复杂度 $O(|E|)$ 内求出无向图或有向图的欧拉路径(如果有的话)的算法。
算法流程
首先要判断这个图有没有欧拉路径,判断方法就是前面的定理。
然后,任选择一个顶点 $u$ 开始 dfs 。枚举 $u$ 的每条出边(若是无向图则为无向边) $e=(u,v)$ ,将这条边删去并 dfs 点 $v$ ,结束后将这条边加入答案序列。
最后再判断答案是否合法(指图是否不连通,图只要连通则必定合法),若合法,该序列倒序即为欧拉路径。
无论是否为欧拉回路均可以找到。
由于选择了一条边之后便将其删去,所以时间复杂度是 $O(|E|)$ 。
参考代码
1 |
|
一些套路
哈密顿路径和欧拉路径相对,指的是遍历一个图的所有点且不重复的路径,可以不经过所有的边。
有时一个题目可以转化成哈密顿路径或欧拉路径。
然而图上找哈密顿路径是 NP 问题,所以基本是用欧拉路径做。