欧拉回路中,顶点度数到底是什么?

欧拉回路中,顶点度数到底是什么?
欧拉回路中,顶点度数到底是什么?

欧拉回路中,顶点度数到底是什么?
图G的一个回路,若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路.
具有欧拉回路的图称为欧拉图（简称E图）.
无向图存在欧拉回路的充要条件
一个无向图存在欧拉回路,当且仅当该图所有顶点度数都是偶数且该图是连通图.
有向图存在欧拉回路的充要条件
一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图,或者 一个顶点的度数为1,另一个度数为-1,其他顶点的度数为0.
混合图存在欧拉回路条件
要判断一个混合图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编辑本段解法
无向图欧拉回路解法
求欧拉回路的一种解法
下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路.
C语言代码,不全,请不要直接粘贴.
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.这个其实是个递归过程.