欧拉路径与哈密尔顿环
1.定义:
奇点 度数为奇数的点
欧拉路径 一笔画路径
欧拉回路 一笔画且能回到起点的路径
欧拉图 图G能一笔画而且可以回到起点
半欧拉图 图G能一笔画但路径的起点和终点不相同
哈密尔顿环 指不重复走过所有的点,最后还能回到起点的回路
2.欧拉图/半欧拉图的判定:
- 无向图的判定:
欧拉图 G联通且所有顶点的度均为偶数
半欧拉图 G联通且有两个顶点的度为奇数,其他为偶数
- 有向图的判定:
欧拉图 G的基图联通且所有顶点的入度=出度
半欧拉图 G的基图联通且存在顶点u的入度比出度大1,v的入度比出度小1,其他所有顶点的入度=出度
(基图:忽略有向图所有边的方向得到的无向图)
3.欧拉路径/欧拉回路的查找算法:
1)暴力算法
深度优先遍历,用邻接矩阵表示图,当顶点数和边数都很小的话可行。
若寻找欧拉回路,从任意一个点开始遍历;若寻找欧拉路径 ,则从一个奇点开始dfs。
dfs时,如果所有边都被遍历,就返回路径;若否则枚举与当前节点连接的未标记的边遍历。
#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)
本质思路是:考虑到欧拉环的两个性质(见“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.哈密尔顿环的查找算法:
暴力算法:
利用深度优先搜索(dfs)即可。
#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)设C是欧拉图G的一个简单回路,将C中的边从G中删去得到G′,则G′的每一个极大连通子图都有一条欧拉回路。
2)设C1,C2是G的两个没有公共边但至少有一个公共顶点的简单回路,则C1,C2可以合并成简单回路C′。
Stay hungry, stay foolish.