欧拉回路

如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。

如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。

具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

欧拉回路发现

这个问题可抽象为一个如图2所示的数学意义上的图，其中4个结点分别表示与4块陆土Il 对应，如结点C对应河岸C，结点A对应岛A等，而结点之间的边表示7座桥。

1）欧拉路：通过图中所有边的简单路。

2）欧拉回路：闭合的欧拉路。

3）欧拉图：包含欧拉回路的图。

欧拉回路判断

以下判断基于此图的基图连通。

无向图存在欧拉回路的充要条件

一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。

有向图存在欧拉回路的充要条件

一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

混合图存在欧拉回路条件

要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下：

假设有一张图有向图G'，在不论方向的情况下它与G同构。并且G'包含了G的所有有向边。那么如果存在一个图G'使得G'存在欧拉回路，那么G就存在欧拉回路。

其思路就将混合图转换成有向图判断。实现的时候，我们使用网络流的模型。现任意构造一个G'。用Ii表示第i个点的入度，Oi表示第i个点的出度。如果存在一个点k，|Ok-Ik|mod 2=1，那么G不存在欧拉回路。接下来则对于所有Ii>Oi的点从源点连到i一条容量为(Ii-Oi)/2的边，对于所有Ii<Oi的点从i连到汇点一条容量为(Oi-Ii)/2的边。如果对于节点U和V，无向边（U，V）∈E，那么U和V之间互相建立容量为1的边。如果此网络的最大流等于∑|Ii-Oi|/2，那么就存在欧拉回路。

欧拉回路解法

无向图欧拉回路解法

求欧拉回路的一种解法

下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。

C语言代码，不全，请不要直接粘贴。

int num=0;//标记输出队列int match;//标志节点的度，无向图，不区分入度和出度void solve(int x){if (match==0)Record=x;else{for(int k=0;k<=500;k++){if(Array!=0){Array--;Array--;match--;match--;solve(k);}}Record=x;}}

pascal代码:

求无向图的欧拉回路（递归实现）

program euler;const maxn=10000;{顶点数上限}maxm=100000;{边数上限}typetnode=^tr;tr=recordf,t:longint;{边的起始点和终止点}al:boolean;{访问标记}rev,next:tnode;{反向边和邻接表中的下一条边}end;varn,m,bl:longint;{顶点数，边数，基图的极大连通子图个数}tot:longint;g:arrayoftnode;d:arrayoflongint;{顶点的度}fa,rank:arrayoflongint;{并查集中元素父结点和启发函数值}list:arrayoftnode;{最终找到的欧拉回路}o:boolean;{原图中是否存在欧拉回路}procedurebuild(ta,tb:longint);{在邻接表中建立边(ta,tb)}vart1,t2:tnode;begint1:=new(tnode);t2:=new(tnode);t1^.f:=ta;t1^.t:=tb;t1^.al:=false;t1^.rev:=t2;t1^.next:=g;g:=t1;t2^.f:=tb;t2^.t:=ta;t2^.al:=false;t2^.rev:=t1;t2^.next:=g;g:=t2;end;proceduremerge(a,b:longint);{在并查集中将a,b两元素合并}varoa,ob:longint;beginoa:=a;whilefa<>adoa:=fa;fa:=a;ob:=b;whilefa<>bdob:=fa;fa:=b;ifa<>bthenbegindec(bl);{合并后，基图的极大连通子图个数减少1}ifrank=ranktheninc(rank);ifrank>rankthenfa:=aelsefa:=b;end;end;procedureinit;{初始化}vari,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);fori:=1tondofa:=i;bl:=n;fori:=1tomdobeginreadln(ta,tb);build(ta,tb);inc(d);inc(d);merge(ta,tb);end;end;proceduresearch(i:longint);{以i为出发点寻找欧拉回路}varte:tnode;beginte:=g;whilete<>nildobeginifnotte^.althenbeginte^.al:=true;te^.rev^.al:=true;search(te^.t);list:=te;dec(tot);end;te:=te^.next;end;end;proceduremain;{主过程}vari:longint;begino:=false;fori:=1tondoifd=0thendec(bl);{排除孤立点的影响}ifbl<>1thenexit;{原图不连通，无解}fori:=1tondoifodd(d)thenexit;{存在奇点，无解}o:=true;fori:=1tondoifd<>0thenbreak;tot:=m;search(i);{从一个非孤立点开始寻找欧拉回路}end;procedureprint;{输出结果}vari:longint;beginifnotothenwriteln('Nosolution.')elsebeginwriteln(list^.f);fori:=1tomdowriteln(list^.t);end;end;begininit;main;print;end.

注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。

求欧拉回路的思路：

循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。

具体步骤：

1。如果此时与该点无相连的点，那么就加入路径中

2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。

3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。

4。这个其实是个递归过程。