欧拉图

Vision271 · 2022-09-29 15:14:56 · 个人记录

概述

• 欧拉图相关问题主要是研究“一笔画”的可行性。

• 换言之，主要研究的是是否存在一条覆盖所有边的迹。

• 从这一意义上讲，说“欧拉路径”是不对的，各种欧拉路大部分情况下都不是路径。

定义

• 欧拉通路：一条覆盖所有边的迹。

• 欧拉回路：一条覆盖所有边的回路。

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

• 半欧拉图：有欧拉通路，但没有欧拉回路的图。

判定

无向图

• 所有非零度点必须共连通块。

• 半欧拉图：有且仅有 0 或 2 个点的度数为奇数。

• 欧拉图：0 个。

有向图

• 所有非零度点必须弱连通。

• 半欧拉图：

  • 有且仅有 0 或 2 个点的入度不等于出度。

  • 如果有，一定恰好是一个入度多。一个出度多。

• 欧拉图：

  • 所有非零度点必须强连通。

• 显然，可以 O(n\alpha) 地判定一张图的欧拉性。

求欧拉路

Hierholzer 算法

可以证明一件事情，就是从欧拉图的任意点/半欧拉图的 s 出发做 dfs，应当能找到一个欧拉路，但可能顺序不对。

考虑大环上套了小环的情况，有可能在分歧点没有进小环而是把大环跑完了，退栈到分歧点才进小环。

怎么把它按正确顺序输出？

我们观察到入栈序完全不连续，一定没希望。考虑出栈序。出栈序是连续的欧拉路！

故每当一个点出栈，把它扔进答案序列。最后倒序输出（有向半欧拉图上不倒序就不是欧拉通路了）。

复杂度为 O(n+m)。

注意，这里的 dfs 只是个说法，实际上我们是按某条边是否被访问决定是否更深地 dfs。换言之，一个点会被访问很多遍，它的边集也会被反复遍历，所以会被卡，需要当前弧优化。

求最小字典序欧拉路

• 将边排序就好，先进字典序小的点。

• 如果使用计数或基数排序可以做 O(n+m)，否则 O(n+m\log m)。

例题

P6628 [省选联考 2020 B 卷] 丁香之路

• 题意：有一个 n 个点的无向完全图，边 i\leftrightarrow j 的边权为 |i-j|，强制经过指定的 m 条边，求起点为 s，终点为 i\in[1,n] 的最短路径。

• 数据范围：n\leqslant 2500，m 中的边不重。

• 首先我们做一个简单考察，发现可以认为长度不为 1 的边意义不大，把它们略去得了，后面考虑用长为 1 的边来代表长不为 1 的边。

• 然后，每条需求边至少经过一次。我们知道如果是恰好一次那就是欧拉路径问题，当然我们这里还要“自选加边”，不过无论如何从度数入手开始考虑吧。

• 先把 m 条边暴力扔上去，然后检查每个点的度数，如果是奇数度数那就让它向右连边，把奇数度数转嫁给下一个点，直到转嫁到一个本身也是奇数度数的点为止。容易证明这样总是能转嫁完的，毕竟总度数一定是偶数。复杂度 O(n+m)。

• 但这样只是度数对了：有可能整张图依然不连通，同时我们没考虑 S,T。

• 先谈连通性。面对这些欧拉回路块，考虑到它们可能有某种嵌套关系（譬如 178 和 345），我们考虑并查集维护一下归属然后跑丐版 MST，即只建出相邻点的边（如果一个关键点和它的后继关键点不共块，那么连边）。复杂度 O(n\log n)。

• 发现这个问题无法处理。用一个 trick：把欧拉路径变成欧拉回路，即，预连一条 S\leftrightarrow T 的边，然后发现块间边一定是经过两次——过去再回来。复杂度是外层的 O(n)。

• 综上，总复杂度 O(n^2\log n+m)，足够通过本题。