欧拉回路.docVIP

三、欧拉回路1、欧拉路：在无孤立顶点的图中，若存在一条路，经过图中每条边一次且仅一次，则称此路为欧拉路。如下图1（左）中存在一条从顶点1到顶点6的欧拉路。后面的例题（一笔画问题）本质上就是判断一个图是否存在欧拉路。2、欧拉回路：在无孤立顶点的图中，若存在一条路，经过图中每条边一次且仅一次，且回到原来位置，则称此路为欧拉回路。如下图1（右）中任意两个顶点之间都存在欧拉回路。著名的柯尼斯堡七桥问题（图论起源）本质上就是讨论一个图的欧拉回路问题。图13、欧拉图：存在欧拉回路的图，称为欧拉图，上图1（右）所示的图就是一个欧拉图。4、定理1：存在欧拉路的条件：图是连通的，且存在0个或2个奇点。如果存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。5、定理2：存在欧拉回路的条件：图是连通的，且不存在奇点。6、哈密尔顿图：在无孤立顶点的连通图中，若存在一条路，经过图中每个顶点一次且仅一次，则称此图为哈密尔顿图。7、哈密尔顿环：是一条沿着图的n条边环行的路径，它访问每一个顶点一次且仅一次，并且返回到它的开始位置。图38、寻找欧拉回路的算法3的情形，下面介绍一种基于递归的经典算法框架：?find_circuit(结点i)；i有邻居时{??选择任意一个邻居j；(i,j)；find_circuit（结点j）；}circuit[circuitpos]=结点i；circuitpos:=circuitpos+1；find_circuit。如果是寻找欧拉路径，对一个奇点执行find_circuit。算法的时间复杂度为O(m+n)。 5、寻找一个图的欧拉回路的算法实现 [参考程序]program?ex5;const??maxn=100;varg:array[1..maxn,1..maxn]?of?longint;???du:array[1..maxn]?of?longint;???circuit:array[1..maxn]?of?longint;???n,e,circuitpos,i,j,x,y,start:longint; procedure?find_circuit(i:longint);var?j:longint;begin牋牋?,cfor?j:=1?to?n?do牋牋牋牋?:=1?if?g[i,j]=1?then牋牋牋牋牋牋,j]=1?begin牋牋牋牋牋牋牋牋?=1?theng[i,j]:=0;牋牋牋牋牋牋牋牋?;?theng[j,i]:=0;牋牋牋牋牋牋牋牋?;?thenfind_circuit(j);牋牋牋牋牋牋ircuitend;牋牋?;circuitpos:=circuitpos+1;牋牋?cucircuit[circuitpos]:=i;end; begin牋牋?cufillchar(g,sizeof(g),0);牋牋?lcread(n,e);牋牋?d(for?i:=1?to?e?do牋牋??ibegin牋牋牋牋牋=1?tread(x,y);牋牋牋牋牋x,y);g[x,y]:=1;牋牋牋牋牋]:=1;g[y,x]:=1;牋牋牋牋牋]:=1;du[x]:=du[x]+1;牋牋牋牋牋:=du[du[y]:=du[y]+1;牋牋?y]end; 牋牋?; start:=1;牋牋?rtfor?i:=1?to?n?do牋牋牋牋?:=1?if?du[i]?mod?2?=1?then????????????start:=i; ?????circuitpos:=0;?????find_circuit(start); ?????for?i:=1?to?circuitpos?do?write(circuit[i],?);?????writeln;end. 9、寻找哈密尔顿环的算法 四、应用举例例6、一笔画问题（one.pas,one.exe）[问题描述]?No?Solution！”。 [输入格式]?one.in，共n+1行，第1行为图的顶点数n，接下来的n行（每行n个数据）为图的邻接矩阵，G[i,j]=1表示顶点i和顶点j有边相连，G[i,j]=0表示顶点i和顶点j无边相连。 [输出格式]?one.out，若能一笔画出，输出一笔画出的顶点先后顺序，否则输出“No?Solution！”。 [样例输入]60?1?0?0?1?11?0?1?1?0?1????????0?1?0?1?0?0????????0?1?1?0?1?1????????1?0?0?1?0?11?1?0?1?1?0 [样例输出]5---1---2---3---4---2---6---4---5---6---1 [参考程序]pr