转:http://sjtulibing.spaces.live.com/blog/cns!2F17193726A8CFC0!128.entry
欧拉回路简介:
定义:
在一个图中,寻找一条只通过每条边一次的路径,这叫做欧拉路径,如果起点和终点是同一点,那么这条回路叫做欧拉回路.
判定一个图中是否存在欧拉回路:并不是每个图都存在欧拉回路.以下分三种情况:
无向图:每个点的度数是偶数,则存在欧拉回路.
有向图:每个结点的入度等于出度,则这个有向图中存在欧拉回路.
总结:以上两种情况很简单,其原理归根结底是每个结点进入和出去的路径条数相等,就存在欧拉回路.还有一种更加复杂的情况.那就是混合图.
混合图:(有时边是单向的,有时边是无向的,就像城市交通网络,有的街道是单向的,有的街道是双向的)找一个给每个无向边定向的策略,这样就可以把图转化成为有向图,使每个顶点的入度与出度是相等的,这样就会存在欧拉回路.
具体过程如下:新建一个图,对于原图中的无向边,在新图中新加一个顶点e(i);对于原图中的每一个顶点J,在新图中建一个顶点V(I),对于原图中每一个顶点J和K之间有一条无向边I,那么在新图中从E(I)出发,添加两条边,分别连向V(J)和V(K),容量都是1.
在新图中,从源点向所有的E(I)都连一条容量为1的边..
对于原图中每一个顶点j,它原本都有一个入度in、出度out和无向度un。显然我们的目的是要把所有无向度都变成入度或出度,从而使它的入度等于总度数的一半,也就是(in
+ out + un) /
2(显然与此同时出度也是总度数的一半,如果总度数是偶数的话)。当然,如果in已经大于总度数的一半,或者总度数是奇数,那么欧拉回路肯定不存大。如果in小于总度数的一半,并且总度数是偶数,那么我们在新图中从v(j)到汇点连一条边,容量就是(in
+ out + un) / 2 – in,也就是原图中顶点j还需要多少入度。
按照这个网络模型算出一个最大流,如果每条从v(j)到汇点的边都达到满流量的话,那么欧拉回路成立。
//待补充
分享到:
相关推荐
这里以构建一个度全部相同的欧拉回路,并输出欧拉回路的路径 1.构建欧拉回路 连通主要是靠树来保证,首先建立一个度为k的完全图,其中会有很多需要主要的地方 (1)首先构造树 =>保证顶点连通 (2)将度的点...
欧拉回路C++程序 随机输入任意点数,给出图中存在的欧拉回路
欧拉回路性质与应用探究欧拉回路性质与应用探究欧拉回路性质与应用探究
图论——欧拉回路的Fleury算法 根据离散数学教材中思想 实现求欧拉回路。
欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关的几类典型问题。最后对欧拉回路的模型进行了总结,...
关于算法与图论中有向图的欧拉回路的判断,判断一个有向图是否有欧拉回路
有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。 一共两个子任务: 无向图。 有向图。 输入格式 第一行一个整数 t,表示子任务编号。t∈{1,2},如果 t=1 ...
自己用C写的无向图找欧拉回路的一个例子。主要用于数据结构的学习
实现了欧拉回路的程序实现即遍历图输出欧拉回路
对欧拉回路的实验报告,有利于大家更好地理解欧拉回路,对要实验报告的人很适合。本算法使用c语言编写的 如需其他语言请自行更改。
找欧拉回路,本程序实现了对一个欧拉图形找其欧拉回路
寻找欧拉回路c++,不解释,大家都懂.最多可以生成230000个节点。大家试一下
有图论中的很多知识,比如图论概念,类型等,还有欧拉回路与汉密尔顿路
本资源主要内容为有向图的无向图的欧拉回路的判定,使用的编程语言为JAVA,并采用邻接表作为图的存储结构,使用并查集判断图是否连通,利用图的遍历算法得到一条有效的欧拉回路,最后通过界面将欧拉路径动态显示在...
求图的欧拉回路的算法,有注释,c++版的,自己写的,O(n)的复杂度
【摘要】欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关
实验_38_如何构建欧拉回路.pdf
Catenyms poj hoj 欧拉回路输出路径
有无向欧拉回路(邻接阵) template 有无向欧拉回路(邻接阵) template 有无向欧拉回路(邻接阵) template 有无向欧拉回路(邻接阵) template
欧拉回路题集,适用于算法爱好者,内含 欧拉回路的多种题型