2023年7月19日发(作者：)

欧拉回路基本概念+判断+求解1.定义如果图G（有向图或者⽆向图）中所有边⼀次仅且⼀次⾏遍所有顶点的通路称作欧拉通路。如果图G中所有边⼀次仅且⼀次⾏遍所有顶点的回路称作欧拉回路。具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉通路但不具有欧拉回路的图称为半欧拉图。2. 定理及推论欧拉通路和欧拉回路的判定是很简单的，请看下⾯的定理及推论。⽆向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者⽆奇度结点。推论1：1) 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。2) 当G是⽆奇度结点的连通图时，G必有欧拉回路。3) G为欧拉图（存在欧拉回路）的充分必要条件是G为⽆奇度结点的连通图。

有向图D存在欧拉通路的充要条件是：D为有向图，D的基图连通，并且所有顶点的出度与⼊度都相等；或者除两个顶点外，其余顶点的出度与⼊度都相等，⽽这两个顶点中⼀个顶点的出度与⼊度之差为1，另⼀个顶点的出度与⼊度之差为-1。推论2：1) 当D除出、⼊度之差为1，-1的两个顶点之外，其余顶点的出度与⼊度都相等时，D的有向欧拉通路必以出、⼊度之差为1的顶点作为始点，以出、⼊度之差为-1的顶点作为终点。2) 当D的所有顶点的出、⼊度都相等时，D中存在有向欧拉回路。3) 有向图D为有向欧拉图的充分必要条件是D的基图为连通图，并且所有顶点的出、⼊度都相等。

3.欧拉通路回路存在的判断根据定理和推论，我们可以很好的找到欧拉通路回路的判断⽅法，定理和推论是来⾃离散数学的内容，这⾥就给出简明的判断⽅法：A.判断欧拉通路是否存在的⽅法有向图：图连通，有⼀个顶点出度⼤⼊度1，有⼀个顶点⼊度⼤出度1，其余都是出度=⼊度。⽆向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。B.判断欧拉回路是否存在的⽅法有向图：图连通，所有的顶点出度=⼊度。⽆向图：图连通，所有顶点都是偶数度。4.欧拉回路的应⽤A.哥尼斯堡七桥问题B.⼀笔画问题C.旋转⿎轮的设计

5.欧拉回路的求解A. DFS搜索求解欧拉回路基本思路：利⽤欧拉定理判断出⼀个图存在欧拉回路或欧拉通路后，选择⼀个正确的起始顶点，⽤DFS算法遍历所有的边（每⼀条边只遍历⼀次），遇到⾛不通就回退。在搜索前进⽅向上将遍历过的边按顺序记录下来。这组边的排列就组成了⼀条欧拉通路或回路。#include#include#include#include#define MAX 2010using namespace std;int maps[MAX][MAX];int in[MAX];int t[MAX];int flag;int k;int Max,Min;int DFS(int x){ int i; for(i=Min;i<=Max;i++) { if(maps[x][i])///从任意⼀个与它相连的点出发 { maps[x][i]--;///删去遍历完的边 maps[i][x]--; DFS(i); } } t[++k]=x;///记录路径，因为是递归所有倒着记}int main(){ int n,i,x,y; Max=-9999; Min=9999; flag=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); maps[x][y]++; maps[y][x]++; Max=max(x,max(y,Max)); Min=min(x,min(y,Min)); in[x]++; in[y]++; } for(i=Min;i<=Max;i++) { if(in[i]%2)///存在奇度点，说明是欧拉通路 { flag=1; DFS(i); break; } } if(!flag)///全为偶度点，从标号最⼩的开始找 { DFS(Min); } for(i=k;i>=1;i--) { printf("%dn",t[i]); } return 0;}

B. Fleury(佛罗莱)算法Fleury算法是对DFS爆搜的⼀种改进，使⽤DFS漫不经⼼的随意⾛是效率不⾼的，Fleury是⼀种有效的算法。关键是能不⾛桥就不去⾛桥，实在⽆路可⾛了才去⾛桥

#include #include #include #include #include using namespace std;int ans[200];int top;int N,M;int mp[200][200];void dfs(int x){ int i; top++; ans[top]=x; for (i=1; i<=N; i++) { if(mp[x][i]>0) { mp[x][i]=mp[i][x]=0;///删除此边 dfs(i); break; } }}void fleury(int x){ int brige,i; top=1; ans[top]=x;///将起点放⼊Euler路径中 while(top>=0) { brige=0; for (i=1; i<=N; i++) /// 试图搜索⼀条边不是割边（桥） { if(mp[ans[top]][i]>0)///存在⼀条可以扩展的边 { brige=1; break; } } if (!brige)/// 如果没有点可以扩展，输出并出栈 { printf("%d ", ans[top]); top--; } else /// 否则继续搜索欧拉路径 { top--;///为了回溯 dfs(ans[top+1]); } }}int main(){ int x,y,deg,num,start,i,j; scanf("%d%d",&N,&M); memset(mp,0,sizeof (mp)); for(i=1;i<=M; i++) { scanf("%d%d",&x,&y); mp[x][y]=1; mp[y][x]=1; } num=0; start=1;///这⾥初始化为1 for(i=1; i<=N; i++) { deg=0; for(j=1; j<=N; j++) { deg+=mp[i][j]; } if(deg%2==1)///奇度顶点 { start=i; num++; } } if(num==0||num==2) { fleury(start); } else { puts("No Euler path"); } return 0;}