图论起源——欧拉图的相关问题

图论起源——欧拉图在信息学竞赛中时常出现，本文将简单地介绍一下。

一、引入

有这么一座城，城里有 $7$ 座桥。问是否有一条路径，可以 不重复的地走遍 $7$ 座桥。这就是著名的 七桥问题，在相当长的时间内都无人解答。直到 $1736$ 年，数学家欧拉经过研究发表了论文《哥尼斯堡的七座桥》，给出了解答。如下图：

他将七桥问题改成第二幅图，那么问题转化为：能否从无向图的一个顶点出发走出一条道路，每条边恰好经过一次。满足上述条件的路径叫 欧拉路径（eulerian path），也可以形象的称为“一笔画”。而含有欧拉路径的图叫 欧拉图。从那时起，图论作为数学的一个新的分支而诞生。因此，欧拉图可以说是 图论的起源，也是图论研究的重要的一部分。

而在信息学竞赛中，欧拉图也是图论题目的一个基本模型。本文将会详细地讲解欧拉图的概念、性质、判定、实现以及例题。同时因为本人才疏学浅，如果有何错误请各位指出。

二、定义

由于本文会出现一些图论的专业词汇，故给出一些词汇的定义，如果下文有不知道意思的词可以到这里来看。

度：

图 $G$ 中与顶点 $u$ 相连的边数称为图 $G$ 中顶点 $u$ 的度。特别地，对于有向图 $G$ ，进入顶点 $u$ 的边的条数称为顶点 $u$ 的入度；从顶点 $u$ 引出的边的条数称为顶点 $u$ 的出度。
桥：

若删去图 $G$ 中的边 $e$ 后，图的连通分量（也就是连通块）数量增加，则称 $e$ 为 $G$ 的桥。
欧拉路径：

通过无向图或者有向图中所有边 恰好一次的路径称作 欧拉路径。如下图 $(1->2->3->4->2)$ 即为一条欧拉路径：

欧拉回路：

通过无向图或者有向图中所有边 恰好一次的回路（相当于一个环）称作 欧拉回路。如下图 $(1->2->3->1)$ 即为一条欧拉回路：

半欧拉图：

有 欧拉路径 但没有 欧拉回路 的图（无向图或有向图）称为 半欧拉图。
欧拉图：

有 欧拉回路 的图（无向图或者有向图）称为 欧拉图（简称 E 图）。

三、定理

定理 $1$ ：

无向图 $G$ 是 欧拉图，当且仅当图 $G$ 连通且所有顶点的度都是偶数。

证明：首先证明 必要性。由于欧拉路径要遍历每一条边，所以任意两个点都是可以互相到达的，因此若图 $G$ 有欧拉路径，则其一定连通。因为欧拉回路的要求是走遍所有边恰好一次，不难发现，所有点的 “进出”次数 应该是一样的（出和入是对应的，一定会成对出现），也就是度数都为偶数。因此若图 $G$ 存在欧拉回路，则图 $G$ 一定连通且所有顶点度都是偶数。

其次证明 充分性。若从图 $G$ 中的任意一点 $u_1$ 出发沿一条边走向相邻的点 $v$ ，因为 $v$ 的度数是偶数，一定可以从 $v$ 沿一条边走向相邻的点，如此反复，每条边仅经过一次，最终一定会回到 $u_1$ ，得到一个圈 $C_1$ 。若 $C_1$ 就是图 $G$ ，定理得证；否则的话，由于图 $G$ 是连通的，所以在剩下的图中一定有一个和 $C_1$ 公共的顶点 $u_2$ ，从 $u_2$ 出发，和上面的流程类似，一定有一个圈 $C_2$ ，将两个圈拼起来任是一个回路。如此反复，一定有一刻得到的图是 $G$ ，定理得证。

如图：

定理 $2$ ：

无向图 $G$ 是 半欧拉图，当且仅当图 $G$ 连通且 $G$ 中仅有两个 奇度顶点。

证明：将 $G$ 的两个奇度顶点连接，由定理 $1$ 得 $G$ 是一个欧拉图，去掉环上的一边就变为了半欧拉图。

如图：

定理 $3$ ：

当有向图 D 的有向边看做无向边时连通，且所有的顶点的 出度和入度都相等 时，D 为 欧拉图。

证明：与定理 $1$ 类似。

如图：

定理 $4$ ：

当有向图 $D$ 的有向边看做无向边时连通，且除了两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的 出度与入度之差为 $1$ ，另一个顶点的 出度与入度之差为 $-1$ 时， $D$ 为 半欧拉图。

证明：同定理 $2$ 类似。

如图：

四、推论

由上面的定理我们可以得到一些推论。

推论 $1$ ：

若无向图 $G$ 连通，且仅有两个奇度顶点，其 欧拉路径 一定以这两个顶点为端点。
推论 $2$ ：

若有向图 $D$ 连通（指将有向边看做无向边时连通），且除 出、入度之差为 $1$ 、 $-1$ 的两个顶点 之外，所有顶点的 出度与入度都相等，其 欧拉路径 必定以 出、入之差为 $1$ 、 $-1$ 的顶点为端点。
推论 $3$ ：

欧拉图 中所有点的度数都是偶数。
推论 $4$ ：

对于无向图 $G$ 来说，若其是欧拉图，则其存在 圈分解。圈分解即用若干个圈（不重复经过顶点的回路）使图 $G$ 的每一条边恰好经过一次。如下面的欧拉图即可分解为两个圈：

证明：这和上面的定理 $1$ 的证明过程是一样的，事实上，该推论可以描述成 图中点度数均为偶数等价于存在圈分解。

五、判定

我们再对欧拉图的判定进行一下总结。

判断 欧拉路径 是否存在

无向图：
- 连通；
- 只有两个顶点度数为奇数；
- 其余所有顶点度数为偶数。
有向图：
- 连通；
- 有一个顶点出度比入度大 $1$ ，有一个顶点入度比出度大 $1$ ；
- 其余所有顶点的入度等于出度。

判断 欧拉回路 是否存在

无向图：
- 连通；
- 所有顶点度数都是偶数。
有向边：
- 连通（指将有向边看做无向边时连通）；
- 所有的顶点入度等于出度。

在做题时若需要判断一个图是不是欧拉图，就可以根据上面的几条进行判断。

六、实现

前面介绍了这么多，下面我们将会对如何在欧拉图中求出一条欧拉回路进行讲解。

求欧拉回路主要有两种算法： Fluery 算法和 Hierholzer 算法。本文主要讲解 Hierholzer 算法。

Fluery 算法

也称避桥法，是一种较暴力的算法。时间复杂度为 $O(m^2)$ ，效率不及 Hierholzer 算法，实用性不高，这里只是稍作介绍。

简单来说，其算法关键为每次选择下一条边优先选 不是桥 的边。
Hierholzer 算法

也称逐步插入回路法。时间复杂度为 $O(n+m)$ ，较 Fluery 算法更优，是算法竞赛中最常用的求欧拉路径的算法。

该算法的思路与定理 $1$ 的证明过程相似。从 任意一点 出发，不停沿 未走过 的边向前，直到 无法再走 为止。这时一定形成了一个回路，但还有边未被访问。这时再从未被访问过的点出发，在从这点走出一个回路，将这个回路与之前的回路拼接。如此反复，直到所有边都被访问过为止。

流程：
1. 任选 $G$ 中的一个顶点 $u_0$ ，从 $u_0$ 开始 DFS，通过未访问过的边遍历相邻的点。
2. 一直到无法遍历为止，将当前的结点 $u$ 加入路径数组 $P$ 中。；
3. 一直到所有的边都被访问过，此时的 $P$ 的反序即为所求的欧拉回路。
对于此处为何是 $P$ 的反序做下解释。因为 Hierholzer 算法是不断往下搜索的，直到最后无路可走为止。此时的点（即 无路可走 时的顶点）一定是满足条件的。若是正序的话，前面记录的顶点可能在继续往下搜索时不符合条件。因此所求的欧拉回路是 $P$ 的反序。同时由于是反序，我们可以用栈来记录路径。

注意，上面是在欧拉图中找欧拉回路，如果说是要找欧拉路径的话，就要记录每个点的度数，从奇度顶点出发。

有时候题目并不保证图是连通的，这是就需要提前判断图的连通性，可以用 并查集 来做。

代码（这里用邻接矩阵实现）：

void dfs(int u)
{
	for(int v=1;v<=n;v++)
		if(e[u][v])//若有边
		{
			e[u][v]--;//删边
			e[v][u]--;
			dfs(v);
		}		
	s.push(u);	//加入路径
 }

七、例题

P2731 [USACO3.3]骑马修栅栏 Riding the Fences

本题就是欧拉回路的板子题。需要注意的是：

本题有可能不是欧拉回路而是欧拉路径，那么此时就要从 度数为奇数 的点开始。
由于最后的答案是 $P$ 的反序，因此我们可以用栈来存。
本题需要输出 字典序小 的，因此需要用 vector 进行内部排序。
本题最小点不一定是 $1$ ，需要进行处理。

代码：

#include<stack>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1029;
int m,u,v;
int ind[N];//每个点的度数 
int minn=1e9;//点的最大值和最小值 
int vis[N][N],cnt;
vector<int>e[N]; 
stack<int>s;
void dfs(int u)
{
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(vis[u][v])
		{
			vis[u][v]--;//删边 
			vis[v][u]--;
			dfs(v);
		}	
	}
	s.push(u);
}
int main()
{
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		ind[u]++;
		ind[v]++;
		vis[u][v]++;
		vis[v][u]++;
		e[u].push_back(v);
		e[v].push_back(u); 
		minn=min(minn,min(u,v));
	}
	
	for(int i=minn;i<=m;i++)
		sort(e[i].begin(),e[i].end());
		
	int st=minn;
	
	for(int i=minn;i<=m;i++)
		if(ind[i]%2)
		{
			st=i;
			break;
		}
	
	dfs(st);
		
	while(!s.empty())
	{
		printf("%d\n",s.top());
		s.pop();
	}
	return 0;
}

UVA10129 单词 Play on Words

题意：

给出 $n$ 个单词，问是否可以将这些单词排成一个序列，满足每个单词的 第一个字母 和上一个单词的 最后一个字母相等。

思路：

每个单词的 首尾字母 就是图上的顶点，首尾字母的连线 即为图上的边。题目中的序列实际上就是求恰好经过每一条边的路径，即求 有向图 中的 欧拉路径。

至于判断是否存在欧拉路径，根据上文的内容即可解决：首先要判断 连通性；其次在 有向图 中，要么所有点 出度等于入度，要么 仅有一个顶点出度比入度大 $1$ ，仅有一个顶点入度比出度大 $1$ 。对其进行判断即可。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int N=37;
int t,in[N],out[N],n,u,v,in_num,out_num;
bool vis[N],e[N][N];
string s;

void init()
{
	in_num=0;
	out_num=0;
	memset(vis,false,sizeof(vis));
	memset(e,false,sizeof(e));
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
}

void dfs(int u)
{
	vis[u]=false;//搜索时将访问过的点标记为false 
	for(int i=1;i<=26;i++)
		if(e[u][i]&&vis[i])
			dfs(i);
}

bool check()
{
	init();
	
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		u=s[0]-'a'+1;
		v=s[s.size()-1]-'a'+1;
		e[u][v]=e[v][u]=true;//边 
		vis[u]=vis[v]=true;//判断连通性 
		out[u]++;//出度 
		in[v]++;//入度 
	}
	
	dfs(u);
	
	for(int i=1;i<=26;i++)
	{
		if(vis[i])//如果不连通，不存在欧拉路径 
			return false;
		if(in[i]-out[i]==1)//入度比出度大1的点
			out_num++;
		else if(in[i]-out[i]==-1)//出度比入度大1的点
			in_num++;
		else if(in[i]!=out[i])//除此之外的都不是欧拉路径
			return false;		
}
	if((in_num==1&&out_num==1)||(in_num==0&&out_num==0))
		return true;
	
	return false;
}


int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		if(check())
			printf("Ordering is possible.\n");
		else
			printf("The door cannot be opened.\n");
	}
	return 0;
}

其他例题：

P1341 无序字母对（找出 字典序最小 的欧拉回路）

P3520 [POI2011]SMI-Garbage（无向图中找欧拉回路）

P6066 [USACO05JAN]Watchcow S

把一条无向边当作两条有向边做即可。

八、参考文献

2018国家集训队论文《欧拉图相关的生成与计数问题探究》—— 陈通
oi-wiki
王陸的博客
DZYO 的博客

九、后记

事实上，欧拉图还有更多有趣的性质和问题，本文只是窥探了其冰山一角，希望能起到抛砖引玉的作用。

感谢 @爱彩虹的牛一直以来对我的支持和帮助。

感谢 @Acfboy 给我提出的的宝贵意见。

感谢 @PanH 学长对我的指导。

Creator's World