欧拉回路

定义

令$G=(V,E)$是一个图

  • 欧拉回路:图$G$中经过每一条边有且只有一次的回路
  • 欧拉路径:图$G$中经过每一条边有且只有一次的路径
  • 欧拉图:存在欧拉回路的图
  • 半欧拉图:存在欧拉路径的图

部分图中的术语定义

  • 度数:对于无向图$G$,其中一点$u$的度数为与其连接的边的个数
  • 入度&出度:对于有向图$G’$,其中一点$u$的入度为指向$u$的边的个数,出度为$u$指向其它点的边的个数
  • 基图:忽略有向图的所有边的方向,得到的无向图称为该有向图的基图

性质

对于无向图$G$

  • 若无向图$G$存在欧拉回路,当且仅当$G$为连通图且所有点的度数为偶数

  • 同理,若无向图$G$存在欧拉路径,当且仅当$G$中除了两个度数为奇数的点,其它点的度数均为偶数

对于有向图$G’$

  • 若有向图$G’$存在欧拉回路,当且仅当$G’$为连通图且所有点的入度等于出度
  • 同理,若有向图$G’$存在欧拉路径,当且仅当存在一点$u$的入度=出度+1,一点$v$的入度+1=出度,其它所有点的入度等于出度

同时还有一个有用的性质

  • 设$C$是欧拉图$G$中的一个简单回路,将$C$从$G$中删去得到$G’$,则$G’$的每一个极大连通子图都是一个欧拉图

还有一个套路

  • 对于图$G$,其一笔画的次数为该图度数为奇数的点的个数/2

代码思路

  • 从图中找到一个简单回路$C$
  • 删去该回路
  • 在剩余极大联通子图中继续递归
  • 合并所有简单回路$C$
1
2
3
4
5
6
7
8
9
10
11
12
// 无向图
vector<int> ans;
inline void DFS(int u)
{
for ( int &i = Begin[u]; i; i = Next[i] ) // Begin[u]随i改变而改变,对于已经遍历过的边不需要重复遍历
{
int v = To[i], c = i / 2;
if ( vis[c] ) continue ; vis[c] = true; // 判重
DFS(v);
ans.push_back(c); // 记录C
}
}

有向图类似,只需要将记录边和判重的代码稍微修改即可

感兴趣的可以做做欧拉回路模板题