离散复习资料之一（Fleury算法）
目录
学习引言：
下面介绍一下：“什么叫做欧拉回路?”
欧拉回路：有一条路从开始的位置到结束的位置都是同一个位置，经过了所有的点且通过了所有的边，通过的次数只能一次。比如著名的“哥尼斯堡七桥问题”
欧拉路：在欧拉回路的基础上面改一个条件。就是有一条路使得从开始的位置到结束的位置不是一个位置。
总结：具有一条经过所有边的简单回路,称欧拉回路,含欧拉回路的图称为欧拉图；如果图G中具有一条经过所有边的简单(非回路)路径,称欧拉路！
欧拉回路和欧拉路也有一个充分的判断条件。
欧拉回路：每一个结点都是偶结点。欧拉路：存在两个结点是奇结点。其余的是偶结点。
Fleury算法步骤如下：
1.任取Vo属于V（G），令Po = Vo 2.设Pi = Voe1V1e2.....eiVi,
如果E（G）-{e1,e2,...ei}中没有与Vi关联的边，则计算停止；
否则按下述的条件从E（G）-{e1,e2,e3...ei}中任取一条边ei+1；
（a）ei+1与vi相关联。
（b）除非无别的边可供选择，否则ei+1不应该选择Gi = G-{e1,e2,e3...ei}中的桥。
设ei+1=（Vi，Vi+1），把ei+1Vi+1加入Pi，
3.令i = i+1，返回2.
Fleury算法 个人解析：
他先把图形建立，随便选择开始点，把Vi的点 对应的边设置为ei+1。结束条件就是如果此时的这一点没有关联的边的时候则算法结束（简单的说就是存在可以找的到的一条欧拉回路的判断条件。）。否则你随便可以选择哪一条边走，选择边的时候，除非没有别的边可以提供你选择，否则不要去选择过桥。
以上就是他的计算方法，他的思路其实很简单，采用的思想选择含一点递归思想，就是不断的选择边，当时在选择边的时候有一种边叫做桥，在是不是选择过桥的时候，加一点条件就可以了。
重要概念_知识引入： 桥
通俗言语： 当你走过某一条边的时候，走过的边，将消失，但是如果当前位置点和未走过点之间，
没有边可走了，表示之前删除的那条边，称之为 [桥]。
标准言论： 桥指的是当你删除该条边后，当前图 由 [连通图] 变成了 [不连通图]，此时这条边
就表示 [桥]。
对于 [桥] 处理方式：“能不过桥，绝对不过桥。”
关于桥的样例解析：
下面来一个图，让我们去看求一条简单欧拉回路。要求：就是从1开始遍历所有的点，然后回到原点，组成一个简单的欧拉回路。
问题： 一个走了一些简单回路 v1e1 --> v2e2 --> v3e3 --> v4e14 --> v9e10 --> v1e8 --> v8e8 --> v9e2之后，无法进行下去试着分析一下他在哪一步出现了问题？
相关知识点：点分为 走过点 和 未走过点 。看图是否连通只需要看未走过点之间是否连通（当前停留点和未走过的点）。
原图如下：
演示：
第一步：V1e1
第二步：走V2e2
第三步：V3e3
第四步：V4e14
第五步：V9e10
第六步：V2e9
第七步：V8e8
桥 解析：
从上面我们可以看的出，就是最后的一次选择路径的时候，使得现存在的图，由连通图 变为 不连通图，所以那一条边是“桥”。注：是否连通，只要是看 出发点 到任何一个点 ，是否存在一条路径。存在则表示连通，不存在 则表示不连通。
桥 另一方面的解析：
我们知道 存在开始点 和 未走的点的图 不连通了。也就是V1 和 V7，V6，V5 的连通性是不连通的。因为他选择的路径是如下图：
桥 最后分析 ： 我们可以看到，存在一些点，未走过点，要想走完，就得一些边走第二遍，所以这是明显不可能。此时求得图，也不是欧拉回路图。欧拉回路中，要求就是点可以过几次，但是边只能过一次，而且起点和终点在同一点。 所以我们在选择边的时候只要记得选择的要求就可以了。
总结：
关于Fleury算法求欧拉回路的过程，主要 要注意的就是 [桥] 的概念，明白了桥的概念，就可以在路径选择方面，任意选择。
以上就是Fleury算法求欧拉回路的简单过程。【2019年8月20日，修】