[刷论文笔记帖]欧拉回路 - jcvb

[刷论文笔记帖]欧拉回路

jcvb posted @ 2013年6月15日 21:22 with tags 欧拉回路 , 1139 阅读

(UPD 这篇里面写的代码是可以退化成O(n^2)的。。。当时比较弱)

 

2007《欧拉回路性质与应用探究》

·欧拉回路:经过每条边仅一次的回路
欧拉路径:经过每条边仅一次的路径

·存在欧拉回路的充要条件:
无向图:连通。每个点度数为偶数
有向图:基图(即无向版本)连通。每个点入度等于出度
·存在欧拉路径但不存在欧拉回路的充要条件
无向图:连通。除两个点度数为奇数外,其他点度数为偶数
有向图:基图连通。一个点的入度等于出度+1,一个点的出度等于入度+1,其他点入度等于出度
水题HDU1878:无向图的欧拉回路是否存在。是否连通用并查集判,然后统计一下度数即可。
HDU1116:单词接龙,论文上的例题。有向边表示单词,两个结点分别代表首尾字母。判欧拉回路。
HDU3018:判断一个无向图至少需要几笔画成。分别考虑每个连通分量:如果是欧拉图则需1笔,如果有两个奇点也只需1笔,否则记奇点个数为k(易证这个k一定是偶数),则需要k/2笔。因为每一笔路径可以消除两个奇点。

·求无向图的欧拉回路
在保证欧拉回路存在的情况下(需要事先判断),可以DFS求得欧拉回路。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct edge{int v,next,vis;}e[1000];int etot;
int g[1000];int n,m;
void ae(int u,int v){
	e[etot].v=v;e[etot].vis=0;e[etot].next=g[u];g[u]=etot++;
	e[etot].v=u;e[etot].vis=0;e[etot].next=g[v];g[v]=etot++;
}
int stk[1000];int top=0;
void dfs(int u){
	for (int i=g[u];~i;i=e[i].next)if(!e[i].vis){
		e[i].vis=e[i^1].vis=1;
		dfs(e[i].v);
		stk[++top]=i;
	}
}		
int main()
{
	memset(g,-1,sizeof(g));etot=0;
	scanf("%d%d",&n,&m);
	while(m--){
		int u,v;
		scanf("%d%d",&u,&v);
		ae(u,v);
	}
	dfs(1);
	for (int i=top;i>=1;i--)printf("%d->%d\n",e[stk[i]^1].v,e[stk[i]].v);
	return 0;
}

·求有向图的欧拉回路
类似上面的DFS。无向的两条边改为一条即可。
·求无向图的欧拉路径
同上,但DFS起点必须是图中的一个奇点
·求有向图的欧拉路径
同上,但DFS起点必须是满足出度=入度+1的那个点

·非递归版本
自己手写一个栈替代系统栈

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct edge{int v,next,vis;}e[1000];int etot;
int g[1000];int n,m;
void ae(int u,int v){
	e[etot].v=v;e[etot].vis=0;e[etot].next=g[u];g[u]=etot++;
	e[etot].v=u;e[etot].vis=0;e[etot].next=g[v];g[v]=etot++;
}
int stk[1000];int top=0;
int sysstk[1000],inedge[1000],cur[1000];int systop=0;
void dfs(int st){
	sysstk[++systop]=st;cur[systop]=g[st];
	while(systop){		
		if(cur[systop]==-1){			
			if(systop!=1)stk[++top]=inedge[systop];
			systop--;
		}else{
			int i=cur[systop];cur[systop]=e[cur[systop]].next;
			if(!e[i].vis){
				e[i].vis=e[i^1].vis=1;
				sysstk[++systop]=e[i].v;cur[systop]=g[e[i].v];inedge[systop]=i;
			}			
		}
	}
}
int main()
{
	memset(g,-1,sizeof(g));etot=0;
	scanf("%d%d",&n,&m);
	while(m--){
		int u,v;
		scanf("%d%d",&u,&v);
		ae(u,v);
	}
	dfs(1);
	for (int i=top;i>=1;i--)printf("%d->%d\n",e[stk[i]^1].v,e[stk[i]].v);
	return 0;
}


·中国邮路问题
带边权无向图,从某个点出发并最终回到这个点,要求每条边至少走过一次。求最小总路程。
首先必须得是连通图。算出每对奇点之间的最短路径,做一次最小权匹配(费用流/KM),把匹配边添加到原图上去,这时图上就全是偶点了,求欧拉回路即可。
·中国邮路问题有向版本
首先必须得是强连通图。记d(v)=d的入度-d的出度。建立超级源S、超级汇T。原图中的边费用设为边权,容量为INF。对于d(v)>0的点v,由S连向v,费用为0,容量为d(v);对于d(v)<0的点v,由v连向T,费用为0,容量为-d(v)。求最小费用最大流。然后对于有流量的边(u,v),在原图中再添加f(u,v)次重边。求欧拉回路即可。

·随机欧拉图
搜到一篇论文http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%203.PDF
如果在图G上从点v开始,沿着未访问过的边随意行走,最终总能形成一条欧拉回路,那么称图G由v“任意可遍历”(好奇怪的术语)。
图G由v任意可遍历的充要条件是图G中的所有环都经过v。


 

Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee