弗罗莱（Fleury）算法求欧拉Euler通路回路.doc
版权申诉
5星 · 超过95%的资源 47 浏览量
2022-05-06
11:28:05
上传
评论
收藏 215KB DOC 举报 
弗罗莱（Fleury）算法,求欧拉（Euler）通路/回路
算法及分析 2009-09-20 17:11:54 阅读 807 评论 0 字号：大中小
1、基本概念：
（1）定义
欧拉通路(欧拉迹)—通过图中每条边一次且仅一次，并且过每一顶点的通路。
欧拉回路(欧拉闭迹)—通过图中每条边一次且仅一次，并且过每一顶点的回路。
欧拉图—存在欧拉回路的图。欧拉图就是从一顶出发每条边恰通过一次又能回到出发顶点
的那种图，即不重复的行遍所有的边再回到出发点。
通路和回路－称 v
i
e
1
e
2
…e
n
v
j
为一条从 v
i
到 v
j
且长度为 n 的通路，其中长度是指通路中边的
条数．称起点和终点相同的通路为一条回路。
简单图－不含平行边和自回路的图。
混合图－既有有向边，也有无向边的图
平凡图－仅有一个结点的图
完全图－有 n 个结点的且每对结点都有边相连的无向简单图，称为无向完全图；有 n 个结
点的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图。
（2）欧拉图的特征：
无向图
a）G 有欧拉通路的充分必要条件为：G 连通，G 中只有两个奇度顶点(它们分别是欧拉通路
的两个端点)。
b）G 有欧拉回路(G 为欧拉图)：G 连通，G 中均为偶度顶点。
有向图
a）D 有欧拉通路：D 连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶
点中，一个顶点的入度比出度大 1，另一个顶点的入度比出度小 1。
b）D 有欧拉回路(D 为欧拉图)：D 连通，D 中所有顶点的入度等于出度。一个有向图是欧
拉图，当且仅当该图所有顶点度数都是 0。
2、弗罗莱（Fleury）算法思想－解决欧拉回路
Fleury 算法：
任取 v0∈V(G)，令 P0=v0；
设 Pi=v0e1v1e2…ei vi 已经行遍，按下面方法从中选取 ei+1：
资源评论
小陈不在线4612023-11-18资源内容详细，总结地很全面，与描述的内容一致，对我启发很大，学习了。
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减3.57元 开通VIP
