欧拉路与欧拉图 学习笔记
djwj233
2021-08-01 20:14:45
### 欧拉图的相关概念
设 $G=(V,E)$ 是一张图：
- 如果 $G$ 中存在一条**包含所有边的简单回路**，那么我们称此回路为**欧拉回路**（*Euler circuit*），$G$ 为**欧拉图**（*Euler graph*）或 **E 图**。
- 如果 $G$ 中存在一条**包含所有边的简单路**，那么我们称此回路为**欧拉路**（*Euler path*），$G$ 为**半欧拉图**（*semi Euler graph*）。
- 特别地，我们定义一张**平凡图**（*trivial graph*）（只由一个孤立结点组成的图）为欧拉图。（不清楚对于一般的零图是否有此结论）
注意，**半欧拉图中不包含欧拉回路**。
结合一笔画问题，**从任意一个点开始**都可以一笔画完的图是欧拉图，必须**从某个点开始**才能一笔画完的图是半欧拉图。
要注意区分欧拉图与**哈密尔顿图**（*Hamilton graph*）的差异：
哈密尔顿回路指从一个点出发，不重不漏地经过**每个点**的回路，而欧拉回路的定义中是**边**。
### 欧拉图的基本性质
- **性质：一张无向连通图 $G$ 是非平凡的欧拉图，当且仅当它可被表示为一些环的并**。
证明：把欧拉回路分段，使每一段都是简单环。必要性同理。
- **性质：一张无向连通图 $G$ 是欧拉图，当且仅当图中每个结点的度数均为偶数**。（常用于欧拉图的判定，下同）
证明：**（必要性）**设 $G$ 有欧拉回路 $v_1\ e_1\ v_2\ e_2\cdots\ v_m\ e_{m}\ (v_1)$。
我们发现，$v_i$ 的出现一次便意味着存在与之相连的两条边 $e_{i-1}$ 和 $e_i$。（特别地，$v_1$ 的出现是 $e_1$ 和 $e_m$）
那么，对所有的点 $x$，若它在回路中出现了 $k$ 次，那么它的度 $d(x)$ 就是 $2k$，一定是一个偶数。
**（充分性）**我们任取一个度数不为 $0$ 的点 $v_1$，从 $v_1$ 出发经过与其相连的一条边 $e_1$ 到达 $v_2$。
由于 $v_2$ 的度数为偶数，且一定大于零（存在一条边 $e_1$ 与之相连），因此 $d(v_2)\geq 2$，至少还有一条边 $e_2$ 与之相连。
设 $e_2$ 的另一个结点是 $v_3$，同上过程可以找到 $v_4$ 与之相连，以此类推。
由于边数是有限的，因此这个过程一定会停止。停止的唯一可能是在 $v_1$ 处（由于有 $e_1$ 的存在），因此我们得到了一条回路 $C$。
删去这条回路和当前度数为 $0$ 的点，我们得到一张新图 $G^\prime$。
若 $G$ 不是空图，那么类似对必要性的证明，我们可以得到 $C$ 把每个点的度数都减去了一个非负偶数，因此 $G^\prime$ 中每个结点的度数仍均为偶数。
由于 $G$ 连通，因此 $G^\prime$ 和回路中至少有一个交点 $v_1^\prime$。我们从 $v_1^\prime$ 出发重复刚才的过程，得到一条新的回路 $C^\prime$，然后将 $C^\prime$ 并入 $C$。
重复以上 找环-并入-删边 的过程，每次图的规模都会缩小，最终一定会得到一个空图。此时的回路便是包含了所有边的简单回路。
这便说明了 $G$ 是欧拉图。证毕。
- **性质：一张有向图 $G$ 是欧拉图，当且仅当其基图连通，且图中每个结点的出度等于入度**。
证明与上一性质类似，此处略去。
- **性质：一张无向连通图 $G$ 是半欧拉图，当且仅当图中有且仅有两个点的度数为奇数**。（常用于半欧拉图的判定，下同）
证明：**（必要性）**设 $G$ 有欧拉路 $v_1\ e_1\ v_2\ e_2\cdots\ v_{m-1}\ e_{m-1}\ v_m$。
我们发现，$v_i(1<i<m)$ 的出现一次便意味着存在与之相连的两条边 $e_{i-1}$ 和 $e_i$。
（特别地，$v_1$ 的出现只有一条 $e_1$，$v_m$ 的出现只有一条 $e_m$）
那么，对所有的点 $x$，若它在通路中除了头尾以外的部分出现了 $k$ 次，而且它不是头也不是尾，那么它的度 $d(x)$ 就是 $2k$，一定是一个偶数。
如果 $x$ 是头或尾（依据欧拉路的定义 $x$ 不可能既是头又是尾），那么他的度 $d(x)$ 就是 $2k+1$，一定是一个奇数。这样的点有且仅有两个。
**（充分性）**由于 $G$ 是连通图，所以一定存在一条连接这两个点的通路。
删去这条路，图中每个点的度数都是偶数。由上文第二条性质可知，每个连通块内都存在一条欧拉回路。
依次将其并入原有的通路，便得到了一条 $G$ 中的欧拉路。这便说明了 $G$ 是半欧拉图。 证毕。
- **性质：一张有向图 $G$ 是半欧拉图，当且仅当其基图连通，且图中存在两点 $u,v$ 满足 $d^+(u)=d^-(u)+1,d^-(v)=d^+(v)+1$，其余每个结点的出度等于入度**。
证明与上一性质类似，此处略去。
- **性质：若无向连通图 $G$ 的奇点（度为奇数的点）数为 $k$，至少需要用 $\dfrac{k}{2}$ 笔画成。**
证明：这其实是上面一些性质的扩展，而且我们由握手原理易知 $k$ 一定是偶数。
证明的方法其实类似上面，此处不作展开。
- **性质：可以用加边的方式把一个非欧拉图变成欧拉图。**
具体地，对含有 $k$ 个奇点的无向连通图，至少要加 $\dfrac{k}{2}$ 条边；
对基图连通的有向图，至少要加的边数应为：
$$
\dfrac{\sum\limits_{x=1}^n|d^+(x)-d^-(x)|}{2}
$$
### Fleury 算法
*Fleuly* 算法（弗洛莱算法）又称**避桥法**，是用于求欧拉路或欧拉回路的算法。
算法的主要流程是每次选择下一条边的过程中**优先选择**一条不为桥的边。（因为桥意味着走过去就再也走不回来了）
由于每次删一条边都要再跑一遍 *Tarjan*，因此复杂度是 $\Theta(m(n+m))=\Theta(m^2)$ 的，效率较低。
可以依赖动态图进行一些优化，不过实践意义不大。
### Hierholzer 算法
*Hierholzer* 算法又称**逐步插入回路法**，也是用于求欧拉路或欧拉回路的算法。
算法的流程与性质中的证明类似，具体地：
- 我们先在图中任意找出一条回路。
- 任取一条目前回路中的点，将其替换为一条简单回路。这可以采用递归的形式进行
- 以此类推，可以找到一条欧拉回路。
如果从路开始的话，就可以找到一条欧拉路。
但是，这样暴力实现的复杂度还是用于 $\Theta(m^2)$ 的，怎么进行优化呢？
我们发现，引起复杂度退化的一个主要原因是我们在访问到一个点时，会多次访问那些**已经经过的边**。
那么，我们只要**在搜索时直接把经过的边删去**即可做到 $\Theta(n+m)$ 的复杂度。
（蓝书上的做法，一般不用）由于递归深度是 $\Theta(m)$ 的，因此容易爆栈。可以考虑用一个栈模拟 DFS 的过程。
### 例题
- [P2731 [USACO3.3]骑马修栅栏 Riding the Fences](https://www.luogu.com.cn/problem/P2731)
这是无向图的板子。由于数据范围极小，因此可以采用邻接矩阵配合各种暴力。
还有，这题有重边。
```c++
void dfs(int x)
{
for(int y=1;y<=n;y++)
if(g[x][y]>=1) {
g[x][y]--, g[y][x]--;
dfs(y);
}
ans[++cnt]=x;
}
```
- [P7771 【模板】欧拉路径](https://www.luogu.com.cn/problem/P7771)
这是有向图的板子。由于邻接表的特性，倒着加边可以帮助我们取到字典序最小。
```C++
void dfs(int x)
{
while(true)
{
int i=head[x];
while(i&&vis[i]) i=Next[i];
head[x]=i;
if(i==0) break;
vis[i]=true, dfs(ver[i]);
}
ans[++cnt]=x;
}
```
- [UVA10735 混合图的欧拉回路 Euler Circuit](https://www.luogu.com.cn/problem/UVA10735)
这题包着个欧拉回路的外皮，实际上没法用 *Hierholzer* 算法做，需要跑网络流。
这说明，***Hierholzer* 算法只能在单纯的有向图和无向图中使用，无法在混合图上跑**。
- [P3520 [POI2011]SMI-Garbage](https://www.luogu.com.cn/problem/P3520)
我们发现只有初始权值和最终权值不同的需要一次修改，别的都不需要。
那么我们只需要把这些边全都加入图中，对每个连通块跑一遍 *Hierholzer* 即可。
输出有点麻烦，需要用一个栈去维护。具体看代码。
（LOJ 上的数据比这里强一万倍，那上面就是蓝书中提到的 DFS 爆栈题)
```c++
void solve(int rt)
{
R[cur=1]=rt;
while(cur) {
int x=R[cur], i=head[x];
while(i&&vis[i]) i=Next[i];
head[x]=i;
if(i==0) {
if(ins[x]) {
res.clear();
res.push_back(x);
while(st[top]!=x) {
res.push_back(st[top]);
ins[st[top]]=false, top--;
}
res.push_back(st[top]), ins[st[top]]=false, top--;
v.push_back(res);
}
ins[x]=true, st[++top]=x;
cur--; continue;
}
vis[i]=vis[i^1]=true;
R[++cur]=ver[i];
}
}
```
[Code](https://loj.ac/s/1209545)
- [#10110. 「一本通 3.7 练习 4」太鼓达人](https://loj.ac/p/10110)
这是一道经典题。
我们把每个 $2^{k-1}$ 位的二进制作为一个结点，表示当前的末尾。然后对所有可能的转移连边。
比如，$k=3$ 时，我们有结点 $\texttt{00},\texttt{01},\texttt{10},\texttt{11}$。
- 由于 $\texttt{00}$ 可以变为 $\texttt{000},\texttt{001}$，因此我们从 $\texttt{00}$ 出发向 $\texttt{00}$、$\texttt{01}$ 各连一条有向边；
- 由于 $\texttt{01}$ 可以变为 $\texttt{010},\texttt{011}$，因此我们从 $\texttt{01}$ 出发向 $\texttt{10}$、$\texttt{11}$ 各连一条有向边；
- 由于 $\texttt{10}$ 可以变为 $\texttt{100},\texttt{101}$，因此我们从 $\texttt{10}$ 出发向 $\texttt{00}$、$\texttt{01}$ 各连一条有向边；
- 由于 $\texttt{11}$ 可以变为 $\texttt{110},\texttt{111}$，因此我们从 $\texttt{11}$ 出发向 $\texttt{10}$、$\texttt{11}$ 各连一条有向边。
然后我们要求每种转移（就是代表着连续 $k$ 位的二进制）出现且仅出现一次，这便是一个欧拉回路的问题。
```c++
void dfs(int x)
{
if(g[0][x]!=-1) {
int tmp=g[0][x];
g[0][x]=-1;
dfs(tmp);
}
if(g[1][x]!=-1) {
int tmp=g[1][x];
g[1][x]=-1;
dfs(tmp);
}
ans[++cnt]=x;
}
int main()
{
cin>>k;
n=(1<<(k-1))-1;
fo(i,0,n) fo(j,0,1) g[j][i]=((i<<1|j)&n);
dfs(0);
printf("%d ",(1<<k));
int cur=k-2;
fo(i,1,cur) putchar('0');
while(cur<(1<<k)) {
printf("%d",ans[cnt]&1);
cnt--, cur++;
}
puts("");
return 0;
}
```