欧拉回路的定义

欧拉回路的判断(无向图存在欧拉回路的充要条件 有向图存在欧拉回路的充要条件 混合图存在欧拉回路条件 无向图欧拉回路解法)

欧拉回路的定义

图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。

具有欧拉回路的图称为欧拉图（简称E图）。

欧拉回路的判断

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

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

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

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

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

混合图存在欧拉回路条件

要判断一个混合图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之间互相建立容量为无限大的边。如果此网络的最大流等于∑|Ii-Oi|/2，那么就存在欧拉回路。

无向图欧拉回路解法

求欧拉回路的一种解法

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

int num = 0;//标记输出队列

int match[MAX];//标志节点的度，无向图，不区分入度和出度

void solve(int x)

{

if(match[x] == 0)

Record[num++] = x;

else

{

for(int k =0;k<=500;k++)

{

if(Array[x][k] !=0 )

{

Array[x][k]--;

Array[k][x]--;

match[x]--;

match[k]--;

solve(k);

}

}

Record[num++] = x;

}

}

pascal代码:

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

program euler;

const maxn=10000;{顶点数上限}

maxm=100000;{边数上限}

type tnode=^tr;

tr=record

f,t:longint;{边的起始点和终止点}

al:boolean;{访问标记}

rev,next:tnode;{反向边和邻接表中的下一条边}

end;

var n,m,bl:longint;{顶点数，边数，基图的极大连通子图个数}

tot:longint;

g:array[1..maxn] of tnode;

d:array[1..maxn] of longint;{顶点的度}

fa,rank:array[1..maxn] of longint;{并查集中元素父结点和启发函数值}

list:array[1..maxm] of tnode;{最终找到的欧拉回路}

o:boolean;{原图中是否存在欧拉回路}

procedure build(ta,tb:longint);{在邻接表中建立边(ta, tb)}

var t1,t2:tnode;

begin

t1:=new(tnode);

t2:=new(tnode);

t1^.f:=ta;

t1^.t:=tb;

t1^.al:=false;

t1^.rev:=t2;

t1^.next:=g[ta];

g[ta]:=t1;

t2^.f:=tb;

t2^.t:=ta;

t2^.al:=false;

t2^.rev:=t1;

t2^.next:=g[tb];

g[tb]:=t2;

end;

procedure merge(a,b:longint);{在并查集中将a, b两元素合并}

var oa,ob:longint;

begin

oa:=a;

while fa[a]<>a do a:=fa[a];

fa[oa]:=a;

ob:=b;

while fa[b]<>b do b:=fa[b];

fa[ob]:=b;

if a<>b then begin

dec(bl);{合并后，基图的极大连通子图个数减少1}

if rank[a]=rank[b] then inc(rank[a]);

if rank[a]>rank[b] then fa[b]:=a else fa[a]:=b;

end;

end;

procedure init;{初始化}

var i,ta,tb:longint;

begin

fillchar(fa,sizeof(fa),0);

fillchar(rank,sizeof(rank),0);

fillchar(d,sizeof(d),0);

readln(n,m);

for i:=1 to n do fa[i]:=i;

bl:=n;

for i:=1 to m do begin

readln(ta,tb);

build(ta,tb);

inc(d[tb]);

inc(d[ta]);

merge(ta,tb);

end;

end;

procedure search(i:longint);{以i为出发点寻找欧拉回路}

var te:tnode;

begin

te:=g[i];

while te<>nil do begin

if not te^.al then begin

te^.al:=true;

te^.rev^.al:=true;

search(te^.t);

list[tot]:=te;

dec(tot);

end;

te:=te^.next;

end;

end;

procedure main;{主过程}

var i:longint;

begin

o:=false;

for i:=1 to n do

if d[i]=0 then dec(bl);{排除孤立点的影响}

if bl<>1 then exit;{原图不连通，无解}

for i:=1 to n do

if odd(d[i]) then exit;{存在奇点，无解}

o:=true;

for i:=1 to n do

if d[i]<>0 then break;

tot:=m;

search(i);{从一个非孤立点开始寻找欧拉回路}

end;

procedure print;{输出结果}

var i:longint;

begin

if not o then writeln('No solution.') else begin

writeln(list[1]^.f);

for i:=1 to m do writeln(list[i]^.t);

end;

end;

begin

init;

main;

print;

end.

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

求欧拉回路的思路：

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

具体步骤：

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

2。如果该点有相连的点，那么就列一张表，遍历这些点，直到没有相连的点。

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

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