欧拉路径与哈密尔顿环

1.定义:

奇点 度数为奇数的点

欧拉路径 一笔画路径

欧拉回路 一笔画且能回到起点的路径

欧拉图GG能一笔画而且可以回到起点

半欧拉图GG能一笔画但路径的起点和终点不相同

哈密尔顿环 指不重复走过所有的点,最后还能回到起点的回路

2.欧拉图/半欧拉图的判定:

  • 无向图的判定:

欧拉图 GG联通且所有顶点的度均为偶数

半欧拉图 GG联通且有两个顶点的度为奇数,其他为偶数

  • 有向图的判定:

欧拉图 GG的基图联通且所有顶点的入度=出度

半欧拉图 GG的基图联通且存在顶点uu的入度比出度大11vv的入度比出度小11,其他所有顶点的入度==出度

(基图:忽略有向图所有边的方向得到的无向图)

3.欧拉路径/欧拉回路的查找算法:

1)暴力算法

深度优先遍历,用邻接矩阵表示图,当顶点数和边数都很小的话可行。

若寻找欧拉回路,从任意一个点开始遍历;若寻找欧拉路径 ,则从一个奇点开始dfsdfs

dfsdfs时,如果所有边都被遍历,就返回路径;若否则枚举与当前节点连接的未标记的边遍历。

#include<bits/stdc++.h>
using namespace std;
const int N=25; 
int n,m;
bool vis[N][N];
int path[N<<1];
void dfs(int pos,int way){
	if(way==m+2){
		for(int i=1;i<way;i++) printf("%d ",path[i]);
		printf("\n");
		return ;
	}
	for(int i=1;i<=n;i++){
		if(i==pos) continue;
		if((!vis[pos][i])||(!vis[i][pos])) continue;
		vis[pos][i]=false;vis[i][pos]=false;
		path[way]=i;
		dfs(i,way+1);
		vis[pos][i]=true;vis[i][pos]=true;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	if(n+1>m) return 0;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		vis[u][v]=true;
		vis[v][u]=true;
	}
	path[1]=1;
	dfs(1,2);
	return 0;
} 

2)Fleury算法 O(m+n)O(m+n)

本质思路是:考虑到欧拉环的两个性质(见“5.欧拉图的性质”),我们可以只遍历一遍就可以找到一个欧拉环。首先随便找一个环,显然它的欧拉路径可求。再在剩下的图中找欧拉路径,这样递归下去,最后一个一个合并,得到最终的欧拉路径。

用两个栈维护答案,一个是搜索栈,表示搜索顺序;一个是结果栈,用来记录结果。

这里我们考虑找一条欧拉路径。从一个奇点开始搜索,先把这个点压入栈,在类似dfs搜索与这个点相连的点并删去连接边,直到搜到一个已经没有出度的点为止。此时不断弹出栈,将弹出的点加入结果栈中,直到有一个点还有出度。此时继续搜索即可。

最后,结果栈中的数,就是一条欧拉路径遍历的点。

下面的代码是用邻接表建边,如果要找出字典序最小的一组遍历,要用邻接矩阵。

这种维护方法,本质上和思路一样。直到有一个点没有出度,就是找到了一个环。不断出栈是为了找到这个环和其他边的连接点。

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m;
struct Edge{
	int u,v;
	int next;
	bool vis;
}edge[N<<1];
int head[N],tot=0;
int outd[N];
int conn[N<<1];
void add_edge(int u,int v){
	outd[u]++;tot++;
	edge[tot].u=u;
	edge[tot].v=v;
	edge[tot].next=head[u];
	edge[tot].vis=false;
	head[u]=tot;
}
stack<int>q,ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);add_edge(v,u);
		conn[tot]=tot-1;conn[tot-1]=tot;
	}
	for(int i=1;i<=n;i++){
		if(outd[i]%2==1){
			q.push(i);
			break;
		}
	}
	while(!q.empty()){
		int t=q.top();q.pop();
		if(outd[t]==0) ans.push(t);
		else{
			q.push(t);
			for(int i=head[t];i;i=edge[i].next){
				if(edge[i].vis==true||edge[conn[i]].vis==true) continue;
				q.push(edge[i].v);
				outd[t]--;outd[edge[i].v]--;
				edge[i].vis=true;edge[conn[i]].vis=true;
				break;
			}
		}
	}
	while(!ans.empty()){
		printf("%d ",ans.top());ans.pop();
	}
	return 0;
}

4.哈密尔顿环的查找算法:

暴力算法:

利用深度优先搜索(dfsdfs)即可。

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=25;
bool vis[N];
bool w[N][N];
int tot=0;
int path[N];
void dfs(int pos,int way){
	if(way==n+1&&pos==1){
		tot++;
		for(int i=1;i<way;i++) printf("%d ",path[i]);
		printf("1\n");
		return ;
	}
	path[way]=pos;
	for(int i=1;i<=n;i++){
		if(i==pos) continue;
		if(!w[pos][i]) continue;
		if(vis[i]) continue;
		vis[i]=true;
		dfs(i,way+1);
		vis[i]=false;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		w[u][v]=true;
		w[v][u]=true;
	}
	dfs(1,1);
	printf("%d\n",tot);
	return 0;
}

注意:查找哈密尔顿环没有更好的算法,因为此问题被证明为NPC问题。

5.欧拉图的性质:

1)设CC是欧拉图GG的一个简单回路,将CC中的边从GG中删去得到GG',则GG'的每一个极大连通子图都有一条欧拉回路。

2)设C1,C2C_1,C_2GG的两个没有公共边但至少有一个公共顶点的简单回路,则C1,C2C_1,C_2可以合并成简单回路CC'

Stay hungry, stay foolish.