欧拉回路的算法演示

欧拉图中欧拉回路的算法，演示，及分析

设G为欧拉图，一般来说G中存在若干条欧拉回路，下面介绍两种求欧拉回路的算法。

1．Fleury算法，能不走桥就不走桥：

（1）任取v0∈V(G)，令P0=v0.

（2）设Pi=v0e1v1e2…eivi已经行遍，按下面方法来从E(G)-{e1,e2,…,ei}中选取ei+1：

（a）ei+1与vi相关联；

（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,…,ei}中的桥。

（3）当（2）不能再进行时，算法停止。

可以证明，当算法停止时所得简单回路Pm=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路。

例15.2 图15.4(1)是给定的欧拉图G。某人用Fleury算法求G中的欧拉回路时，走了简单回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(观看他的错误走法)，无法行遍了，试分析在哪步他犯了错误?

解 此人行遍v8时犯了能不走桥就不走桥的错误，因而他没行遍出欧拉回路。当他走到v8时，G-{e2,e3,e14,e10,e1,e8}为图15.4(2)所示。此时e9为该图中的桥，而e7,e11均不是桥，他不应该走e9，而应该走e7或e11，他没有走，所以犯了错误。注意，此人在行遍中，在v3遇到过桥e3，v1处遇到过桥e8，但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的。