欧拉回路与二分图匹配.doc

欧拉回路：给定一个无向图，找出一条经过每条边有且仅有一次的路径，这条路径就叫做欧拉路径。如果这条路径的起点和终点是同一个点的话，这条路径就叫做欧拉回路。
定理1：无向图G具有一条欧拉路，当且仅当G是连通的，且有不超过两个奇度定点。
推论：无向图G具有一条欧拉回路，当且仅当G是连通的，且所有定点的度数都为偶数。
欧拉回路算法：
procedurefinc_circuit(nodei);{递归找圈}
{Circuitpos表示当前的输出序列长度，circuit表示输出路径}
ifnodeI没有邻接点then
begin
circuit(circuitpos)=nodeI;{加入序列}
circuitpos=circuitpos+1;
end
else
while(nodei有邻接点)do
begin
delete_edges(nodej,nodei);{删除边（I,j）}
find_circuit(nodej);{继续递归找圈}
end;
circuit(circuitpos)=nodeI{加入序列}
circuitpos=circuitpos+1

procedureouler
circuitpos=0;{初始化}
finc_circuit(node1);{递归求解}

欧拉回路非递归算法：
constmaxn=100;
var
e,_a,_b,{e表示边数}
nsequence,i,j,n,{nsequence记录输出序列的长度}
dep:integer;{dep为栈指针}
ok:boolean;
map:array[0..maxn,0..maxn]ofinteger;{记录无向图}
stack,sequence:array[0..maxn*maxn]ofinteger;{栈，输出序列}
begin
fillchar(map,sizeof(map),0);
assign(input,'oula.in');
reset(input);
read(n,e);
fori:=1toedobegin{以边的方式读入}
read(_a,_b);
inc(map[_a,_b]);
end;
dep:=1;stack[1]:=1;nsequence:=0;
whiledep>0dobegin
j:=stack[dep];
ok:=false;
fori:=1tondoifmap[j,i]>0thenbegin{是否存在邻接点}
dec(map[j,i]);
dec(map[i,j]);
ok:=true;
inc(dep);stack[dep]:=i;{入栈}
break;
end;
ifnotokthenbegin
inc(nsequence);
sequence[nsequence]:=stack[dep];{加入输出序列}
dec(dep);
end;
end;
fori:=1tonsequencedowrite(sequence[i],'');
writeln;
end.

递归程序：
constmaxn=100;
var
e,a,b,nsequence,i,j,n:integer;
map:array[0..maxn,0..maxn]ofinteger;
sequence:array[0..maxn*maxn]ofinteger;
procedurerecursion(location:integer);
varok:boolean;
i:integer;
begin
ok:=false;
fori:=1tondoifmap[location,i]>0thenbegin
dec(map[location,i]);dec(map[i,location]);
ok:=true;
recursion(i);
end;
ifnotokthenbegin
inc(nsequence);
sequence[nsequence]:=location;
end;
end;
begin
fillchar(map,sizeof(map),0);
assign(input,'oula.in');reset(input);
assign(output,'oula.out');rewrite(output);
read(n,e);
fori:=1toedobegin
read(a,b);
inc(map[a,b]);
inc(map[b,a]);
end;
nsequence:=0;
recursion(1);
fori:=1tonsequencedowrite(sequence[i],'');
writeln;
end.

图的匹配
二分图：设G是一个图。如果存在Vc的一个划分X,Y，使得G的任何一条边的一个端点在X中，另一个端点在Y中，则称G为二分图，