欧拉究竟是怎样解决“七桥问题”的

欧拉路径和欧拉回路判断方法如下：1、欧拉路径。无向图判断法，图连通，有且仅有两个奇点，一个点为起点，另一个点为终点；有向图判断法，有两个点的入度不等于出度，且其中一个点的入度比出度大1，另一个点的出度比入度大1。2、欧拉回路。无向图判断法，图连通，无奇点；有向图判断法，所有点的入度等于出度。判断图是否连通的方法：无向图用dfs访问，看看点是否全部被访问；有向图先转化为无向图，然后再用dfs判定。判断奇点数的方法：奇点数若为0则任意指定起点，奇点数若为2则指定起点为奇点。欧拉路径：从图中一个结点出发走出一条道路，每条边恰好经过一次。欧拉回路：从图中任意点出发，每条边恰好经过一次，最终回到起点。欧拉回路是数学家欧拉在研究著名的德国哥尼斯堡（Koenigsberg）七桥问题时发现的。具有欧拉回路的图称“欧拉图”，具有欧拉路径但不具有欧拉回路的图称“半欧拉图”。找出欧拉回路或欧拉路径可采用深度优先搜索。

若图G中存在这样一条路径，使得它恰通过G中每条边一次，则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉回路。 具有欧拉回路的图称为欧拉图。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。 无向图存在欧拉回路的充要条件： 一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。 有向图存在欧拉回路的充要条件： 一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

欧拉回路不一定是初级回路，需要判定。1、无向图存在欧拉回路的充要条件一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。2、有向图存在欧拉回路的充要条件一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。3、混合图存在欧拉回路条件要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下：假设有一张图有向图G"，在不论方向的情况下它与G同构。并且G"包含了G的所有有向边。那么如果存在一个图G"使得G"存在欧拉回路，那么G就存在欧拉回路。扩展资料注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。

第一眼看见，比划一下，就知道，在所有桥都只能走一遍的前提下，不能把这个地方所有的桥都走遍。 也就是说，如果遍历这个图，必须要重复经过某些边。 为了纪念欧拉，在一个图G中包含G的所有结点和边的 回路 称为 欧拉回路 ,包含G的所有结点和边的 路径 称为 欧拉路径 也就是说，如果欧拉路径闭合，就成了欧拉回路 注意 回路 的概念：从v i 到v i 的、长度非0的、不存在 重复边 的路径 所以上文所说的科尼斯堡七桥并不是欧拉回路。 在图G中存在欧拉回路的前提条件为： 关于一个图中是否存在欧拉回路，需要先说明两个概念： 由于欧拉回路的性质：只能经过每条边一次，所以，对于每一个结点，至少需要有 2n 条边连接该结点（n = 0,1,2,...n），n = 0时，G中只含有一个结点v，则称路径(v)是G的欧拉回路。 也就是说，图G中存在欧拉回路的充要条件是G中每个结点都是偶结点。 设图G存在欧拉回路，则回路的起点和终点是同一结点，含有一条出边和一条入边，所以该结点为偶结点，以此类推，每个结点都连接有 2n (n = 0,1,2,...n) 条边。 图G中存在欧拉路径的充要条件和G中存在欧拉回路的充要条件有些相似： 若奇结点的个数为0，则图G中存在欧拉回路，欧拉回路也是欧拉路径的一种。 将两个奇结点相连，可知这是欧拉回路 (v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 ,v 3 ,v 1 ) 欧拉路径(v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 ,v 3 ),起点和终点分别是两个奇结点 关于欧拉回路和欧拉路径的介绍就到此了，谢谢大家！

无向图欧拉回路解法求欧拉回路的一种解法下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。C语言代码，不全，请不要直接粘贴。 intnum=0;//标记输出队列intmatch[MAX];//标志节点的度，无向图，不区分入度和出度voidsolve(intx){if(match[x]==0)Record[num++]=x;else{for(intk=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代码:求无向图的欧拉回路（递归实现） programeuler;constmaxn=10000;{顶点数上限}maxm=100000;{边数上限}typetnode=^tr;tr=recordf,t:longint;{边的起始点和终止点}al:boolean;{访问标记}rev,next:tnode;{反向边和邻接表中的下一条边}end;varn,m,bl:longint;{顶点数，边数，基图的极大连通子图个数}tot:longint;g:array[1..maxn]oftnode;d:array[1..maxn]oflongint;{顶点的度}fa,rank:array[1..maxn]oflongint;{并查集中元素父结点和启发函数值}list:array[1..maxm]oftnode;{最终找到的欧拉回路}o:boolean;{原图中是否存在欧拉回路}procedurebuild(ta,tb:longint);{在邻接表中建立边(ta,tb)}vart1,t2:tnode;begint1:=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;proceduremerge(a,b:longint);{在并查集中将a,b两元素合并}varoa,ob:longint;beginoa:=a;whilefa[a]<>adoa:=fa[a];fa[oa]:=a;ob:=b;whilefa[b]<>bdob:=fa[b];fa[ob]:=b;ifa<>bthenbegindec(bl);{合并后，基图的极大连通子图个数减少1}ifrank[a]=rank[b]theninc(rank[a]);ifrank[a]>rank[b]thenfa[b]:=aelsefa[a]:=b;end;end;procedureinit;{初始化}vari,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);fori:=1tondofa[i]:=i;bl:=n;fori:=1tomdobeginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;proceduresearch(i:longint);{以i为出发点寻找欧拉回路}varte:tnode;beginte:=g[i];whilete<>nildobeginifnotte^.althenbeginte^.al:=true;te^.rev^.al:=true;search(te^.t);list[tot]:=te;dec(tot);end;te:=te^.next;end;end;proceduremain;{主过程}vari:longint;begino:=false;fori:=1tondoifd[i]=0thendec(bl);{排除孤立点的影响}ifbl<>1thenexit;{原图不连通，无解}fori:=1tondoifodd(d[i])thenexit;{存在奇点，无解}o:=true;fori:=1tondoifd[i]<>0thenbreak;tot:=m;search(i);{从一个非孤立点开始寻找欧拉回路}end;procedureprint;{输出结果}vari:longint;beginifnotothenwriteln("Nosolution.")elsebeginwriteln(list[1]^.f);fori:=1tomdowriteln(list[i]^.t);end;end;begininit;main;print;end.注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。具体步骤：1。如果此时与该点无相连的点，那么就加入路径中2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。4。这个其实是个递归过程。

图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<oi的点从i连到汇点一条容量为(oi-ii) 2,那么就存在欧拉回路. 编辑本段解法 无向图欧拉回路解法 求欧拉回路的一种解法 下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路. 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.这个其实是个递归过程.

欧拉回路是必须经过所有节点。根据查询相关资料信息显示，欧拉回路需要经过每个节点，并且需要记录每个节点的度数，依次来判断是否存在欧拉回路。欧拉回路是指若图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Eulerpath)。

欧拉路径包括欧拉路（不形成回路）和欧拉回路两种情况。连通无向图，当有零个奇数度节点，即没有奇数度节点，此时所有节点度数都是偶数，一定有欧拉回路。具有欧拉回路的图称为欧拉图。连通无向图，当只有两个奇数度节点，其他节点度数都为偶数时，一定有欧拉路。

欧拉回路是经过所有边一次然后回到原点，哈密顿是经过所有节点一次然后回到原点，tsp问题就是哈密顿回路

图 G 的一个回路,若它通过 G 中每条边一次且仅一次,则称为欧拉回路。而具有这种回路的图称为欧拉图(简称 E 图).或者：一副图，寻找一条只通过每条边一次的路径叫做欧拉路径．如果这条路径的起点和终点是同一点，那么这条路径叫做欧拉回路．有关的问题即是欧拉回路问题，建议参考哥尼斯堡七桥问题或一笔画问题。欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。

一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图可以用邻接矩阵或者邻接表，做一次DFS或者BFS访问各个节点判断入度出度就行

if (){ mov ax, 10 mov bx, 0 mov cx, 0 mov dx, 0 add bx, ax add cx, bx add dx, cx loop if}

怎么判断是不是欧拉图？相关内容如下：欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。对欧拉图的一个现代扩展是蜘蛛图，它向欧拉图增加了可以连接的存在点。这给予欧拉图析取特征。欧拉图已经有了合取特征(就是说区定义了有着与起来的那些性质的对象在区中的存在)。所以蜘蛛图允许使用欧拉图建模逻辑或的条件。从相关定理判断：1.无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点( G 的所有结点度数为偶数)；2.无向连通图G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点；3.有向连通图 D 是欧拉图，当且仅当该图为连通图且 D 中每个结点的入度=出度；4.有向连通图 D 含有欧拉通路，当且仅当该图为连通图且 D 中除两个结点外，其余每个结点的入度=出度，且此两点满足 deg-(u)-deg+(v)=±1 。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的入度=出度）；5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环；6.如果图G是欧拉图且 H = G-uv，则 H 有奇数个 u,v-迹仅在最后访问 v ；同时，在这一序列的 u,v-迹中，不是路径的迹的条数是偶数。

先设置一个判断迷宫能否被破坏的过程或函数，再用广搜对每一个位置的一切可能性进行试验，每试一次就判断一次，如果条件成立，就保存这一种方法的能量耗损和破坏的路径，每个位置的每一个可能性都检查完后，找出最佳方案

无解

我只知道欧拉图这是数学家欧拉提出的.用几个圆圈表示几个概念的外延关系.下面是一个欧拉图，图片点击可以放大

发布会日日日日日日日日日日日日日日日日

若G是欧拉图，则每个点度数均为偶数。每添加一个环，每个点奇偶度不变。若添加一条边，该边连接两点度数各+1。奇数+1为偶数。现有K个奇度数节点，需使该K个点度数均变为偶，则至少加k/2条边。

不一定,这样的反例有很多：　　对于一个有向图,只要有一个经过所有结点的环路,就成为强连通图.不妨构造一个强连通图,其所有边恰好构成一个环,串联了所有结点；如：a1→a2→a3→……→a1；　　此时,这个图中恰好有一...

欧拉图 h 欧拉通路(回路)与欧拉图 通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图. 欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画. h欧拉图或通路的判定 (1) 无向连通图G是欧拉图ÛG不含奇数度结点(G的所有结点度数为偶数):(定理1) (2) 非平凡连通图G含有欧拉通路ÛG最多有两个奇数度的结点；(定理1的推论) (3) 连通有向图D含有有向欧拉回路(即欧拉图)ÛD中每个结点的入度＝出度 连通有向图D含有有向欧拉通路ÛD中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝±1. (定理2) 欧拉图是普通逻辑学中的重点之一,图论的一部分,可以直观的表示概念间的关系,刑事侦查逻辑里有实际用途. ..

#include "SqStack.h" //堆栈的常见操作#include "Queue.h"//队列的常见操作typedef int Graph[200][200];int v,e;void DFS(Graph &G,SqStack &S,int x,int t){int k=0,i,m,a;Push(S,x);for(i=t;i<v;i++)if(G[i][x]>0){k=1;G[i][x]=0; //删除此边G[x][i]=0;DFS(G,S,i,0);break;}//if,forif(k==0){Pop(S);GetTop(S,m);G[x][m]=1;G[m][x]=1;a=x+1;if(StackLength(S)!=e){Pop(S);DFS(G,S,m,a);}//ifelsePush(S,x);}//if}//DFSint BFSTest(Graph G){int a[200],x,i,k=0;LinkQueue Q;InitQueue(Q);EnQueue(Q,0);for(i=0;i<v;i++)a[i]=0;a[0]=1;while(!QueueEmpty(Q)){DeQueue(Q,x);for(i=0;i<v;i++)if(G[x][i]>0)if(a[i]!=1){a[i]=1;EnQueue(Q,i);}//if}//whilefor(i=0;i<v;i++)if(a[i]==0){k=1;break;}if(k==1)return 0;elsereturn 1;}void Euler(Graph &G,int x){int m;SqStack S;InitStack(S);DFS(G,S,x,0);printf("该图的一个欧拉回路为：");while(!StackEmpty(S)){GetTop(S,m);printf("->v%d",m);Pop(S);}//while}void InputM1(Graph &G){int h,z;printf("Please input顶点数和边数 ");scanf("%d",&v);scanf("%d",&e);for(int i=0;i<v;i++)for(int j=0;j<v;j++)G[i][j]=0;printf("please int the邻接矩阵的值(起点(数字)终点(数字))： ");for(int i=0;i<e;i++){scanf("%d",&h);scanf("%d",&z);G[h-1][z-1]=1;G[z-1][h-1]=1;}//for}//InputM1int main(){int i,j,sum,k=0;Graph G;InputM1(G);if(BFSTest(G)==0){printf("该图不是连通图! ");exit(0);}//iffor(i=0;i<v;i++){sum=0;for(j=0;j<v;j++)sum+=G[i][j];if(sum%2==1){k=1;break;}//if}//forif(k==1) printf("该图不存在欧拉回路！ ");elseEuler(G,0);return 1;}

这是一个无解问题

存在偶度数的点，就一定存在简单回路。每个顶点的度数都是偶数，存在欧拉回路。一个路径包括每个边恰好一次，该路径称为欧拉路径。一个回路是欧拉路径，称为欧拉回路。具有欧拉回路的图称为欧拉图。

通过图（无向图或有向图）中所有边且每边仅通过一次通路称为欧拉通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。

可以，这四个概念两两之间互斥

欧拉路径和欧拉回路欧拉路径：从某结点出发一笔画成所经过的路线叫做欧拉路径。欧拉回路：在欧拉路径的基础上又回到起点。a、凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为 终点画完此图。 　　b、凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另 一个奇点终点。 　c、其他情况的图都不能一笔画出。(有偶数个奇点除以2便可算出此图需几笔画成。)欧拉回路和欧拉路径的判断欧拉回路：无向图：每个顶点的度数都是偶数，则存在欧拉回路。有向图：每个顶点的入度都等于出度，则存在欧拉回路。欧拉路径：无向图：当且仅当该图所有顶点的度数为偶数 或者 除了两个度数为奇数外其余的全是偶数。有向图：当且仅当该图所有顶点 出度=入度 或者 一个顶点 出度=入度+1，另一个顶点 入度=出度+1，其 他顶点 出度=入度。

这不是显然的么？

谢谢您的信任，这个我也不是太明白，不过我可以给你提供参考，希望对你有帮助。参考： http://www.docin.com/p-54454502.html

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

都是欧拉图

欧拉图 h 欧拉通路(回路)与欧拉图 通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图. 欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画. h欧拉图或通路的判定 (1) 无向连通图G是欧拉图ÛG不含奇数度结点(G的所有结点度数为偶数)定理1) (2) 非平凡连通图G含有欧拉通路ÛG最多有两个奇数度的结点；(定理1的推论) (3) 连通有向图D含有有向欧拉回路(即欧拉图)ÛD中每个结点的入度＝出度 连通有向图D含有有向欧拉通路ÛD中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝±1. (定理2)

srdfsdfvsdv

由欧拉回路可知，一笔不可能画完，所以至少需要两笔以上，图中有8个点，12条线，，每个点连接3条线，设N为点，则线与点的公式满足1.5N，可知N为偶数..因为三条线不可能一笔画完，一笔画完的条件需满足0或者2个奇点+若干偶点.即是说最优策略是消除2个奇点以及若干条偶线段，剩下奇数-偶数=奇数，既是1.5N-N=0.5N，0.5N-1条奇数线段+第1次笔画次数=0.5N.....N为8，代入公式可得8*0.5=4次，至少需要4次。由该定理引申可得，且结合欧拉回路，若所有点发散的线段为奇数组成的一个连通图，公式为笔画次数0.5n次，其中n为点数。

18世纪，在哥尼斯堡城风景秀美的普莱格尔河上有7座别致的拱桥，将河中的两个岛和河岸连结（如下图）。城中的居民经常沿河过桥散步。城中有位青年很聪明，爱思考，有一天，这位青年给大家提出了这样一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是举世闻名的七桥问题，当时的人们始终没有能找到答案。大数学家欧拉从朋友那里听到这个问题，很快便证明了这样的走法不存在。欧拉是这样解决问题的：把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，思考过程如下图：伟大的数学家欧拉，睿智地把这样一个实际问题抽象成了一个由点线组成的简单的几何图形，把要解决的问题转化成图（二）的一笔画问题了。这样一个抽象化的过程是欧拉解决这个问题时最精彩的思考，也是最值得我们学习的地方。因为图（二）不能一笔画成，所以人们不能一次走遍7座桥。1736年，欧拉把这题的结果发表在圣彼得堡科学院学报上，欧拉对“七桥问题”的研究是图论研究的开始，可以说，正是这个问题的研究使其成为“图论”的鼻祖。那么欧拉是如何判断图（二）不可以一笔画成呢？为了便于大家看懂，结合这个例子，我用自己的语言来说明一下一笔画问题的解题思路：这个图形中共有4个点7条线，每个点都是若干条路线的公共端点。如果一个点是偶数条线的公共端点，我们称这个点为双数点（或偶点）；如果一个点是奇数条线的公共端点，我们称这个点为单数点（或奇点）。图（二）中A点是5条线的公共端点，B、C、D点都是3条线的公共端点，因此图（二）有4个奇点。一般，我们把起笔的点称为起点，停笔的点称为终点，其它的点称为路过点。显然一笔画图形中所有路过点如果有进去的线就必须有出来的线，从而每个点连接的线数必须有偶数个才能完成一笔画，如果路过点中出现奇点，必然就会出现没有走过的路线或重复路线。因此在一笔画图形中，只有起点和终点可以是奇点（起点可以只出不进，终点可以最后进这个点就不出了），也就是说最多只能有两个奇点，以一个奇点为起点，另一个奇点为终点。因为图（二）有4个奇点，因此图（二）不能一笔画成。另外两点说明：一、一笔画图形中所有的线必须是连续的，因为笔不离纸，如果一个图形由两个断开的部分组成，肯定不能一笔画。例如“国”这个字就不能一笔写出来。二、一笔画图形中的奇点都是成对出现的（因为每条线都有两个端点，所有线的端点和是偶数），图形中没有奇点，都是偶点时，可以一笔画成，但起点和终点必须选择同一点。结合以上说明，解决一笔画问题，第一步是找出图中所有点，判断其是奇点还是偶点；第二步是根据奇点的个数作出正确的判断；第三步是让孩子用铅笔试着画一画，验证自己的判断。希望楼主能够采纳。。。。。。

图中包含0或2个奇数度结点且连通！欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。对欧拉图的一个现代扩展是蜘蛛图，它向欧拉图增加了可以连接的存在点。这给予欧拉图析取特征。欧拉图已经有了合取特征(就是说区定义了有着与起来的那些性质的对象在区中的存在)。所以蜘蛛图允许使用欧拉图建模逻辑或的条件。

详细描述一下算法。回答你的问题时，只答程序有关的，算法是你的，需要你提供

#include "SqStack.h" //堆栈的常见操作#include "Queue.h"//队列的常见操作typedef int Graph[200][200];int v,e;void DFS(Graph G,SqStack S,int x,int t){int k=0,i,m,a;Push(S,x);for(i=t;i<v;i++)if(G[i][x]>0){k=1;G[i][x]=0; //删除此边G[x][i]=0;DFS(G,S,i,0);break;if(k==0){Pop(S);GetTop(S,m);G[x][m]=1;G[m][x]=1;a=x+1;if(StackLength(S)!=e){Pop(S);DFS(G,S,m,a);}//ifelsePush(S,x);}//if}//DFSint BFSTest(Graph G){int a[200],x,i,k=0;LinkQueue Q;InitQueue(Q);EnQueue(Q,0);for(i=0;i<v;i++)a[i]=0;a[0]=1;while(!QueueEmpty(Q)){DeQueue(Q,x);for(i=0;i<v;i++)if(G[x][i]>0)if(a[i]!=1){a[i]=1;EnQueue(Q,i);}//if}//whilefor(i=0;i<v;i++)if(a[i]==0){k=1;break;}if(k==1)return 0;elsereturn 1;}void Euler(Graph G,int x){int m;SqStack S;InitStack(S);DFS(G,S,x,0);printf("该图的一个欧拉回路为：");while(!StackEmpty(S)){GetTop(S,m);printf("->v%d",m);Pop(S);}//while}void InputM1(Graph G){int h,z;printf("Please input顶点数和边数 ");scanf("%d",v);scanf("%d",e);for(int i=0;i<v;i++)for(int j=0;j<v;j++)G[i][j]=0;printf("please int the邻接矩阵的值(起点(数字)终点(数字))： ");for(int i=0;i<e;i++){scanf("%d",h);scanf("%d",z);G[h-1][z-1]=1;G[z-1][h-1]=1;}//for}//InputM1int main(){int i,j,sum,k=0;Graph G;InputM1(G);if(BFSTest(G)==0){printf("该图不是连通图! ");exit(0);}//iffor(i=0;i<v;i++){sum=0;for(j=0;j<v;j++)sum+=G[i][j];if(sum%2==1){k=1;break;}//if}//forif(k==1) printf("该图不存在欧拉回路！ ");elseEuler(G,0);return 1;}

本图有四个奇数顶点，所以没有办法一笔画成。定理一连通的无向图 有欧拉路径的充要条件是：中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。连通的无向图 是欧拉环（存在欧拉回路）的充要条件是：中每个顶点的度都是偶数。证明：必要性：如果一个图能一笔画成，那么对每一个顶点，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。充分性：如果图中没有奇顶点，那么随便选一个点出发，连一个环。如果这个环就是原图，那么结束。如果不是，那么由于原图是连通的， 和原图的其它部分必然有公共顶点 。从这一点出发，在原图的剩余部分中重复上述步骤。由于原图是连通图，经过若干步后，全图被分为一些环。由于两个相连的环就是一个环，原来的图也就是一个欧拉环了。如果图中有两个奇顶点 和 ，那么加多一条边将它们连上后得到一个无奇顶点的连通图。由上知这个图是一个环，因此去掉新加的边後成为一条路径，起点和终点是 和 。证毕。连通无向图有欧拉路径的充要条件也可以写作“图中奇顶点数目不多于2个”，这是因为奇顶点数目不可能是1个。实际上，连通无向图中，奇顶点的数目总是偶数。对于不连通的无向图，如果有两个互不连通的部分都包含不止一条边，那么显然不能一笔画。只有当此图的边全都在某一个连通部分中即其它的连通部分都是一个个孤立的顶点，度数为0），并满足连通无向图关于一笔画的充要条件，而该图才能一笔画。也即是说，可以一笔画的（无向）图如果不是连通图，就必定是一个可以一笔画的连通图与若干个孤立顶点的组合。除了用顶点的度数作为判定的充要条件，还可以用图中边的特性来作为欧拉回路存在的判定准则。连通的无向图 中存在欧拉回路，等价于图所有的边可以划分为若干个环的不交并。具体来说，等价于存在一系列的环，使得图里的每一条边都恰好属于某一个环。定理二如果连通无向图 有 个奇顶点，那么它可以用 笔画成，并且至少要用 笔画成。证明：将这 个奇顶点分成 对後分别连起，则得到一个无奇顶点的连通图。由上知这个图是一个环，因此去掉新加的边後至多成为 条欧拉路径，因此必然可以用 笔画成。但是假设全图可以分为 条欧拉路径，则由定理一知，每条链中只有不多于两个奇顶点，于是 。因此必定要 笔画成。

　　若图G中存在这样一条路径，使得它恰通过G中每条边一次，则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉回路。 　　具有欧拉回路的图称为欧拉图。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。 　　无向图存在欧拉回路的充要条件： 　　一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。 　　有向图存在欧拉回路的充要条件： 　　一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

以下判断基于此图的基图连通。无向图存在欧拉回路的充要条件一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。有向图存在欧拉回路的充要条件一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。混合图存在欧拉回路条件要判断一个混合图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，那么就存在欧拉回路。

欧拉回路不一定是初级回路，需要判定。1、无向图存在欧拉回路的充要条件一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。2、有向图存在欧拉回路的充要条件一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。3、混合图存在欧拉回路条件要判断一个混合图G（V,E）（既有有向边又有无向边）是欧拉图，方法如下：假设有一张图有向图G"，在不论方向的情况下它与G同构。并且G"包含了G的所有有向边。那么如果存在一个图G"使得G"存在欧拉回路，那么G就存在欧拉回路。扩展资料注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。

图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<Oi的点从i连到汇点一条容量为(Oi-Ii)/2的边。如果对于节点U和V，无向边（U，V）∈E，那么U和V之间互相建立容量为无限大的边。如果此网络的最大流等于∑|Ii-Oi|/2，那么就存在欧拉回路。编辑本段解法无向图欧拉回路解法求欧拉回路的一种解法下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。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=recordf,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;begint1:=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;beginoa:=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 begindec(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;beginfillchar(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 beginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;procedure search(i:longint);{以i为出发点寻找欧拉回路}var te:tnode;beginte:=g[i];while te<>nil do beginif not te^.al then beginte^.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;begino:=false;for i:=1 to n doif d[i]=0 then dec(bl);{排除孤立点的影响}if bl<>1 then exit;{原图不连通，无解}for i:=1 to n doif odd(d[i]) then exit;{存在奇点，无解}o:=true;for i:=1 to n doif d[i]<>0 then break;tot:=m;search(i);{从一个非孤立点开始寻找欧拉回路}end;procedure print;{输出结果}var i:longint;beginif not o then writeln("No solution.") else beginwriteln(list[1]^.f);for i:=1 to m do writeln(list[i]^.t);end;end;begininit;main;print;end.注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。具体步骤：1。如果此时与该点无相连的点，那么就加入路径中2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。4。这个其实是个递归过程。

欧拉路径包括欧拉路（不形成回路）和欧拉回路两种情况。 连通无向图，当有零个奇数度节点，即没有奇数度节点，此时所有节点度数都是偶数，一定有欧拉回路。具有欧拉回路的图称为欧拉图。 连通无向图，当只有两个奇数度节点，其他节点度数都为偶数时，一定有欧拉路。

欧拉路径和欧拉回路判断方法如下：1、欧拉路径。无向图判断法，图连通，有且仅有两个奇点，一个点为起点，另一个点为终点；有向图判断法，有两个点的入度不等于出度，且其中一个点的入度比出度大1，另一个点的出度比入度大1。2、欧拉回路。无向图判断法，图连通，无奇点；有向图判断法，所有点的入度等于出度。判断图是否连通的方法：无向图用dfs访问，看看点是否全部被访问；有向图先转化为无向图，然后再用dfs判定。判断奇点数的方法：奇点数若为0则任意指定起点，奇点数若为2则指定起点为奇点。欧拉路径：从图中一个结点出发走出一条道路，每条边恰好经过一次。欧拉回路：从图中任意点出发，每条边恰好经过一次，最终回到起点。欧拉回路是数学家欧拉在研究著名的德国哥尼斯堡（Koenigsberg）七桥问题时发现的。具有欧拉回路的图称“欧拉图”，具有欧拉路径但不具有欧拉回路的图称“半欧拉图”。找出欧拉回路或欧拉路径可采用深度优先搜索。

图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<Oi的点从i连到汇点一条容量为(Oi-Ii)/2的边。如果对于节点U和V，无向边（U，V）∈E，那么U和V之间互相建立容量为无限大的边。如果此网络的最大流等于∑|Ii-Oi|/2，那么就存在欧拉回路。编辑本段解法无向图欧拉回路解法求欧拉回路的一种解法下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。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=recordf,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;begint1:=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;beginoa:=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 begindec(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;beginfillchar(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 beginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;procedure search(i:longint);{以i为出发点寻找欧拉回路}var te:tnode;beginte:=g[i];while te<>nil do beginif not te^.al then beginte^.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;begino:=false;for i:=1 to n doif d[i]=0 then dec(bl);{排除孤立点的影响}if bl<>1 then exit;{原图不连通，无解}for i:=1 to n doif odd(d[i]) then exit;{存在奇点，无解}o:=true;for i:=1 to n doif d[i]<>0 then break;tot:=m;search(i);{从一个非孤立点开始寻找欧拉回路}end;procedure print;{输出结果}var i:longint;beginif not o then writeln("No solution.") else beginwriteln(list[1]^.f);for i:=1 to m do writeln(list[i]^.t);end;end;begininit;main;print;end.注意record中的点的排列是输出的倒序，因此，如果要输出欧拉路径，需要将record倒过来输出。求欧拉回路的思路：循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。具体步骤：1。如果此时与该点无相连的点，那么就加入路径中2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。4。这个其实是个递归过程。

这一题是错误的，存在欧拉路的充要条件是有2个奇点但欧拉图中，是有欧拉回路，没有奇点

欧拉通路（回路）与欧拉图通过图的每条边一次且仅一次，而且走遍每个结点的通路（回路），就是欧拉通路（回路）。存在欧拉回路的图就是欧拉图。欧拉回路要求边不能重复，结点可以重复。笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画。欧拉图或通路的判定。(1）无向连通图是欧拉图；7不含奇数度结点（7的所有结点度数为偶数）:（定理1)(2）非平凡连通图7含有欧拉通路；7最多有两个奇数度的结点；（定理1的推论）(3）连通有向图4含有向欧拉回路（即欧拉图）；4中每个结点的入度＝出席连通有向图4含有向欧拉通路4中除两个结点外，其余每个结点的入度＝出席，且此两点满足deg－(u)－deg＋(v)＝±1。（定理2)

七桥问题1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支-----图论与几何拓扑。也由此展开了数学史上的新进程。问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。目录故事背景推断方法最终成果故事背景 七桥问题七桥问题Seven Bridges Problem18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。有关图论研究的热点问题。18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如左图上）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点后来大数学家欧拉把它转化成一个几何问题（如左图下）——一笔画问题。他不仅解决了此问题，且给出了连通图可以一笔画的重要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2.编辑本段推断方法当Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动。Konigsberg城中有一条名叫Pregel的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最后回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成.欧拉的这个考虑非常重要，也 著名数学家欧拉非常巧妙，它正表明了数学家处理实际问题的独特之处——把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。接下来，欧拉运用图中的一笔画定理为判断准则，很快地就判断出要一次不重复走遍哥尼斯堡的7座桥是不可能的。也就是说，多少年来，人们费脑费力寻找的那种不重复的路线，根本就不存在。一个曾难住了那么多人的问题，竟是这么一个出人意料的答案！编辑本段最终成果问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。而利用普通数学知识，每座桥均走一次，那这七座桥所有的走法一共有5040种，而这么多情况，要一一试验，这将会是很大的工作量。但怎么才能找到成功走过每座桥而不重复的路线呢？因而形成了著名的“哥尼斯堡七桥问题”。1735年，有几名大学生写信给当时正在俄罗斯的彼得斯堡科学院任职的天才数学家欧拉，请他帮忙解决这一问题。欧拉在亲自观察了哥尼斯堡七桥后，认真思考走法，但始终没能成功，于是他怀疑七桥问题是不是原本就无解呢？1736年，在经过一年的研究之后，29岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题，同时开创了数学新一分支---图论。在论文中，欧拉将七桥问题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。并由此得到了如图一样的几何图形。 若我们分别用A、B、C、D四个点表示为哥尼斯堡的四个区域。这样著名的“七桥问题”便转化为是否能够用一笔不重复的画出过此七条线的问题了。若可以画出来，则图形中必有终点和起点，并且起点和终点应该是同一点，由于对称性可知由B或C为起点得到的效果是一样的，若假设以A为起点和终点，则必有一离开线和对应的进入线，若我们定义进入A的线的条数为入度，离开线的条数为出度，与A有关的线的条数为A的度，则A的出度和入度是相等的，即A的度应该为偶数。即要使得从A出发有解则A的度数应该为偶数，而实际上A的度数是5为奇数，于是可知从A出发是无解的。同时若从B或D出发，由于B、D的度数分别是3、3，都是奇数，即以之为起点都是无解的。有上述理由可知，对于所抽象出的数学问题是无解的，即“七桥问题”也是无解的。由此我们得到:欧拉回路关系由此我们可知要使得一个图形可以一笔画，必须满足如下两个条件：1. 图形必须是连通的。2. 途中的“奇点”个数是0或2。我们也可以依此来检验图形是不是可一笔画出。回头也可以由此来判断“七桥问题”，4个点全是奇点，可知图不能“一笔画出”，也就是不存在不重复地通过所有七桥。欧拉的这个考虑非常重要，也非常巧妙，它正表明了数学家处理实际问题的独特之处——把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。 七桥问题1736年，欧拉在交给彼得堡科学院的《哥尼斯堡7座桥》的论文 加里宁格勒地理报 告中，阐述了他的解题方法。他的巧解，为后来的数学新分支——拓扑学的建立奠定了基础。七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为 欧拉定理。对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。此题被人教版小学数学第十二册书收录.在95页。此题也被人教版初中第一册收录．在121页。一笔画：■⒈凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。■⒉凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。■⒊其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)

一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图是连通图。一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。可以用邻接矩阵或者邻接表，做一次DFS或者BFS访问各个节点判断入度出度就行。扩展资料：1、无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点( G 的所有结点度数为偶数)；2、无向连通图G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点；3、有向连通图 D 是欧拉图，当且仅当该图为连通图且 D 中每个结点的入度=出度；参考资料来源：百度百科-欧拉图

　欧拉图　　h 欧拉通路(回路)与欧拉图 通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图. 　　欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画. 　　h欧拉图或通路的判定　　(1) 无向连通图G是欧拉图ÛG不含奇数度结点(G的所有结点度数为偶数):(定理1)　　(2) 非平凡连通图G含有欧拉通路ÛG最多有两个奇数度的结点；(定理1的推论)　　(3) 连通有向图D含有有向欧拉回路(即欧拉图)ÛD中每个结点的入度＝出度　　连通有向图D含有有向欧拉通路ÛD中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝±1. (定理2) 　　----------------------------------　　修订内容　　欧拉图是普通逻辑学中的重点之一,图论的一部分,可以直观的表示概念间的关系,刑事侦查逻辑里有实际用途.　　相容关系:同一关系,交叉关系,包含关系.　　不相容关系:不相容关系,矛盾关系.