资源描述：
《欧拉回路与二分图匹配》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、欧拉回路：给定一个无向图，找出一条经过每条边有且仅有一次的路径，这条路径就叫做欧拉路径。如果这条路径的起点和终点是同一个点的话，这条路径就叫做欧拉回路。定理1：无向图G具有一条欧拉路，当且仅当G是连通的，且有不超过两个奇度定点。推论：无向图G具有一条欧拉回路，当且仅当G是连通的，且所有定点的度数都为偶数。欧拉回路算法：procedurefinc_circuit(nodei);{递归找圈}{Circuitpos表示当前的输出序列长度，circuit表示输出路径}ifnodeI没有邻接点thenbeg
2、incircuit(circuitpos)=nodeI;{加入序列}circuitpos=circuitpos+1;endelsewhile(nodei有邻接点)dobegindelete_edges(nodej,nodei);{删除边（I,j）}find_circuit(nodej);{继续递归找圈}end;circuit(circuitpos)=nodeI{加入序列}circuitpos=circuitpos+1procedureoulercircuitpos=0;{初始化}finc_circ
3、uit(node1);{递归求解}欧拉回路非递归算法：constmaxn=100;vare,_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;{栈，输出序列}beginfillchar(map,sizeof(map)
4、,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>0dobeginj:=stack[dep];ok:=false;fori:=1tondoifmap[j,i]>0thenbegin{是否存在邻接点}dec(map[j,i]);dec(map[i,j])
5、;ok:=true;inc(dep);stack[dep]:=i;{入栈}break;end;ifnotokthenbegininc(nsequence);sequence[nsequence]:=stack[dep];{加入输出序列}dec(dep);end;end;fori:=1tonsequencedowrite(sequence[i],'');writeln;end.递归程序：constmaxn=100;vare,a,b,nsequence,i,j,n:integer;map:array[
6、0..maxn,0..maxn]ofinteger;sequence:array[0..maxn*maxn]ofinteger;procedurerecursion(location:integer);varok:boolean;i:integer;beginok:=false;fori:=1tondoifmap[location,i]>0thenbegindec(map[location,i]);dec(map[i,location]);ok:=true;recursion(i);end;ifn
7、otokthenbegininc(nsequence);sequence[nsequence]:=location;end;end;beginfillchar(map,sizeof(map),0);assign(input,'oula.in');reset(input);assign(output,'oula.out');rewrite(output);read(n,e);fori:=1toedobeginread(a,b);inc(map[a,b]);inc(map[b,a]);end;nseq
8、uence:=0;recursion(1);fori:=1tonsequencedowrite(sequence[i],'');writeln;end.图的匹配二分图：设G是一个图。如果存在Vc的一个划分X,Y，使得G的任何一条边的一个端点在X中，另一个端点在Y中，则称G为二分图，记做G＝（X,Y,E）。如果G中X的每个顶点都与Y的每个定点相邻，则称G为完全二分图。匹配的相关概念：设G=(V,E)是一个图，M是E的子集，如果M不含环且任意两边都不相邻，则称M为G的一个匹配。G中边数
