- hzoi044 的博客
图论--欧拉回路
-
hzoi044
@
2024-7-27 11:18:27
1.定义#
如果图GG(有向图或者无向图)中所有边一次仅且一次行遍所有顶点的通路称作欧拉通路。
如果图GG中所有边一次仅且一次行遍所有顶点的回路称作欧拉回路。
具有欧拉回路的图成为欧拉图(简称EE图)。具有欧拉通路但不具有欧拉回路的图成为半欧拉图。
顶点可以经过多次
画个图分辨一下：
- 欧拉通路：
- 欧拉回路：
简单来讲就是欧拉回路能够回到起点
2.定理及推论#
欧拉通路和欧拉回路的判定是很简单的
无向图GG存在欧拉通路的充要条件是：#
GG为连通图，并且GG仅有两个奇度节点(度数为奇数的顶点)或者无奇度节点
推论1：
- 当GG是仅有两个奇度节点的连通图时，GG的欧拉通路必以此两个节点为端点
- 当GG是无奇度节点的连通图时，GG必有欧拉回路
- GG为欧拉图(存在欧拉回路)的充分必要条件是GG为无奇度节点的连通图
有向图DD存在欧拉通路的充要条件是：#
DD为有向图，DD的基图联通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而在这两个顶点中一个顶点的出度与入度只差为11，另一个顶点的出度与入度之差为**−**1−1
推论2：
- 当DD除出、入度之差为11，−1−1的两个顶点之外，其余顶点的出度与入度都相等时，DD的有向欧拉通路必以出、入度之差为11的顶点作为始点，以出、入度之差为**−**1−1的顶点作为终点
- 当DD的所有顶点的出、入度都相等时，DD中存在有向欧拉回路
- 有向图DD为有向欧拉图的充分必要条件是DD的基图为连通图，并且所有的顶点的出、入度都相等
3.欧拉通路回路存在的判断#
根据定理和推论，我们可以很好的找到欧拉通路回路的判断方法
A.判断欧拉通路是否存在的方法#
- 有向图：图连通，有一个顶点出度大于入度11，有一个顶点入度大于出度11，其余都是出度=入度
- 无向图：图联通，只有两个顶点是奇数度，其余都是偶数度
B.判断欧拉回路是否存在的方法#
- 有向图：图联通，所有的顶点出度=入度
- 无向图：图联通，所有的顶点都是偶数度
4.欧拉回路的应用#
- 哥尼斯堡七桥问题
- 一笔画问题
- 旋转鼓轮的设计
5.欧拉回路的判断#
DFSDFS#
邻接矩阵的时间复杂度为O(n2**)**O(n2)
邻接表的时间复杂度为O(n+e)O(n+e)
如果，重边太多的话，邻接表会挂掉:）
原题卡这个，所以我们要写邻接矩阵
const int N=1005;
int n,m;
int in[N];
bool vis[N],G[N][N];
void dfs(int x){
vis[x]=1;
for(int i=1;i<=n;i++){
if(G[x][i]&&!vis[i]){
dfs(i);
}
}
}
int main(){
while(~scanf("%d",&n)&&n){
m=read();
memset(G,0,sizeof G);
memset(vis,0,sizeof vis);
memset(in,0,sizeof in);
for(int i=1,x,y;i<=m;i++){
x=read();y=read();
G[x][y]=G[y][x]=1;
in[x]++;in[y]++;
}
dfs(1);
bool flag=1;
for(int i=1;i<=n;i++){
if(!vis[i]){
flag=0;
break;
}
if(in[i]%2){
flag=0;
break;
}
}
if(flag)puts("1");
else puts("0");
}
}
并查集#
const int N=1005;
int n,m;
int in[N],fa[N];
int find(int x){
return x==fa[x]?x:x=find(fa[x]);
}
void union_set(int x,int y){
x=find(x);y=find(y);
if(x!=y)fa[x]=y;
}
int main(){
while(~scanf("%d",&n)&&n){
m=read();
for(int i=1;i<=n;i++){
fa[i]=i;
in[i]=0;
}
for(int i=1,x,y;i<=m;i++){
x=read();y=read();
in[x]++,in[y]++;
union_set(x,y);
}
bool flag=1;int totrt=0;
for(int i=1;i<=n;i++){
if(in[i]%2){
flag=0;
break;
}
if(find(i)==i){
totrt++;
}
}
//只有一个根且没有入度为奇数的点
if(flag&&totrt==1)puts("1");
else puts("0");
}
return 0;
}
6.欧拉回路的求解#
板子题：骑马修栅栏
题目保证有解。
A.DFS搜索求解欧拉回路#
基本思路：利用欧拉定理判断出一个图存在欧拉回路或欧拉通路后，选择一个正确的起始顶点，用DFS算法遍历所有的边(每条边只遍历一次)，遇到走不通就回退。在搜索前进方向上将遍历过的边按顺序记录下来。这组边的排列就组成了一条欧拉通路或回路。
const int N=2005;
int m,Min,Max;
int G[N][N],in[N];
int path[N],cnt;
void dfs(int x){
for(int i=Min;i<=Max;i++){
if(G[x][i]){
G[x][i]--;
G[i][x]--;
dfs(i);
}
}
path[++cnt]=x;
}
void print_path(){
for(int i=cnt;i>=1;i--){
printf("%d\n",path[i]);
}
}
int main(){
m=read();Min=505,Max=0;
for(int i=1,x,y;i<=m;i++){
x=read();y=read();
G[x][y]++;G[y][x]++;
in[x]++,in[y]++;
Max=max(Max,max(x,y));
Min=min(Min,min(x,y));
}
for(int i=Min;i<=Max;i++){
if(in[i]%2){
dfs(i);
print_path();
return 0;
}
}//欧拉通路
dfs(Min);//欧拉回路
print_path();
return 0;
}
B.Fleury(佛罗莱)算法#
- Fleury算法是对DFS爆搜的一种改进，使用DFS漫不经心的随意走效率是不高的，Fleury是一种有效的算法
求法：
设GG为一无向欧拉图，求GG中一条欧拉回路的算法为：
- 任取GG中一顶点v0v0，令P0**=v0**P0=v0
- 假设沿Pi**=v0e1v1e2**...eiviPi=v0e1v1e2...eivi走到顶点vivi，按下面方法从E(G)−e1,e2**,...,ei中选E(G)−e1,e2,...,ei中选ei+**1ei+1
- ei**+1ei+1与v**ivi相关联
- 除法无别的边可供选择，否则ei**+1ei+1不应该是Gi=G−e1**,e2**,...,ei**Gi=G−e1,e2,...,ei中的桥
- 当2.无法进行时算法停止
可以证明的是，当算法停止时，所得到的简单回路Pm**=v0e1v1e2**...emvmPm=v0e1v1e2...emvm为GG中一条欧拉回路
我个人感觉是把大连通块分成了零散的几个小连通块然后分块连接(?)
关键是能不走桥就不走桥，实在无路可走了才会去走桥
const int N=2005;
int n,m;
int top,sta[N];
bool G[N][N];
void dfs(int x){
sta[++top]=x;
for(int i=1;i<=n;i++){
if(G[x][i]>0){
G[x][i]=G[i][x]=0;
dfs(i);
break;
}
}
}
void Euler(int x){
bool brige;
top=1;
sta[top]=x;
while(top>=0){
brige=0;
for(int i=1;i<=n;i++){
if(G[sta[top]][i]>0){
brige=1;
break;
}
}
if(!brige){
printf("%d ",sta[top--]);
}
else {
top--;
dfs(sta[top+1]);
}
}
}
int main(){
n=read();m=read();
for(int i=1,x,y;i<=m;i++){
x=read();y=read();
G[x][y]=1;
G[y][x]=1;
}
int num=0,start=1;
for(int i=1;i<=n;i++){
int deg=0;
for(int j=1;j<=n;j++)
deg+=G[i][j];
if(deg%2){
start=i;
num++;
}
}
if(num==0||num==2)Euler(start);
else {
puts("No Euler path");
}
return 0;
}