欧拉图

Tangninghaha · 2025-01-10 07:54:17 · 算法·理论

定义

通路：图中一条路径。或者更准确地，可以表述为一个序列 u_1,u_2,\cdots,u_n，对于所有 1\le i<n 满足 u_i 和 u_{i+1} 之间有边的序列称为一条通路。

回路：满足起点和终点在同一点的通路。

欧拉回路：经过每条边恰好一次的 回路。

欧拉图：具有欧拉回路的图。

欧拉路径：经过每条边恰好一次的 通路。

半欧拉图：具有欧拉路径而没有欧拉回路的图。容易发现，具有欧拉回路则必定具有欧拉路径。

判定

一个图是欧拉图或欧拉路径的必要条件：

• 无向图非零度顶点连通。
• 有向图非零度顶点弱连通。

除满足上述条件外，

• 一个无向图是欧拉图当且仅当：顶点度数均为偶数。
• 一个无向图是半欧拉图当且仅当：恰有 2 个奇数度数节点。
• 一个有向图是欧拉图当且仅当：每一个节点入度等于出度。
• 一个有向图是半欧拉图当且仅当：至多一个顶点满足出度与入度差为 1（若存在则为起点），至多一个顶点满足入度与出度差为 1（若存在则为终点），其余顶点入度等于出度，且存在顶点的入度不等于出度（否则是欧拉图）。

根据定义，一个欧拉图具有欧拉回路，一个欧拉图或半欧拉图具有欧拉通路。

Hierholzer 算法

也被称为逐步插入回路法。

假设现在有一个回路 / 通路，图上有一部分边未经过，该算法通过遍历这些未经过的边来找到一条新的回路 / 通路，并用新回路来代替原来的点。

具体实现上，可以设计一个递归来求解，算法流程如下：

• 尝试对当前通路 / 回路上的一个点 x 进行拓展：
  • 遍历 x 的所有出边，
  • 如果该边没有遍历过，则遍历该边
  • 将 x 加入栈中

从判定时得到的起点开始进行这个算法，最后栈中存放的就是欧拉路径经过的节点（逆序）。

为什么要使用栈呢？如果一个图是半欧拉图，那么从这个点进行拓展可能找不到一个回路，只能找到一个通路（通向终点）。并且至多只有一个出边会出现这样的情况（否则与半欧拉图定义相悖）。

这时候，如果顺序输出，那么答案会先进入这个通路，就走不出来了。

举个例子，假设 x 出边有三个点 a,b,c，从 a 和 c 出发能够找到一条回路，而从 b 出发会找到一条通路。

假设此时枚举边的顺序是 a 到 b 到 c，那么会先递归进入 a，递归这条回路会到达 x，这条回路此时没有入栈。递归进入 b 后找到一条通路，只能退出递归，b 通路会入栈。回到 x，遍历 c 的回路，这条回路又会到达 a。最后 c 的回路先入栈，a 的回路后入栈。这样输出方案的时候，也是 a 到 c 的顺序。

很多题目要求输出字典序最小的路径，只要按照字典序从小到大遍历出边，即可保证得到的是最小字典序（不理解再看一下上面一段）。

常用思路

如果题目要求“恰好一次”，可能是欧拉路径。

记得判定连通性！