线 构造欧拉回路 思想：在画欧拉回路时，已经经过的边不能再用。因此， 在构造欧拉回路过程中的任何时刻，假设将已经经过的边 删除，剩下的边必须仍在同一连通分支当中
构造欧拉回路 思想：在画欧拉回路时，已经经过的边不能再用。因此， 在构造欧拉回路过程中的任何时刻，假设将已经经过的边 删除，剩下的边必须仍在同一连通分支当中
构造欧拉▣路-Fleury:算法 902 算法： ·输入：欧拉图G ● 输出：简单通路P=voeivie2,eYe+1,emYm,其中包含了 Ec中所有的元素。 1.任取vo∈VG令P。=Vo; 2.设P=VeY1e2,eY,按下列原则从Ec-{e1,e2,,e}中选择e+1 (a)et与v,相关联； (b)除非别无选择，否则e+1不应是G-{e,e2,e}中的割边。 3.反复执行第2步，直到无法执行时终止
构造欧拉回路-Fleury算法 算法： 输入：欧拉图G 输出：简单通路P = v0 e1 v1 e2 ,…,ei vi ei+1 ,…,em vm , 其中包含了 EG中所有的元素。 1. 任取v0VG , 令P0 =v0 ; 2. 设Pi =v0 e1 v1 e2 ,…,ei vi , 按下列原则从EG -{e1 ,e2 ,…,ei }中选择ei+1。 (a) ei+1与vi相关联； (b) 除非别无选择，否则ei+1不应是G-{e1 ,e2 ,…,ei }中的割边。 3. 反复执行第2步，直到无法执行时终止
Fleury2算法的证明 ·算法的终止性显然。 ●设算法终止时，Pm=Voe1V12…,eY+1,emVm ·其中诸e,互异是显然的。只须证明： ()Pm是回路，即v。Vm。 (2)Pm包括了G中所有的边。 令G=G-{e1,e2…,e} (I)(证明是回路)假设vym。由算法终止条件，在Gm中已 没有边与Ym相关联。假设除最后一次外，Vm在Pm中出现 k次，则vm的度数是2k+1,与G中顶点度数是偶数矛盾
Fleury算法的证明 算法的终止性显然。 设算法终止时，Pm = v0 e1v1 e2 ,…,eivi ei+1,…,emvm, 其中诸ei互异是显然的。只须证明： (1) Pm是回路，即v0 =vm。 (2) Pm包括了G中所有的边。 令Gi =G-{e1 ,e2 ,…,ei } (1) (证明是回路)假设v0 vm。由算法终止条件，在Gm中已 没有边与vm相关联。假设除最后一次外，vm在Pm中出现 k次，则vm的度数是2k+1, 与G中顶点度数是偶数矛盾
Fleury算法的证明（续） (2)(证明含所有边)假设P没有包括G中所有的边，令Gm中所 有非零度顶点集合为S(非空)，令S=Vc-S,则vm∈S。 考察序列e1,e2…c,e+1,em。假设j是满足y,∈S,而V1∈S”的最大下标。 如果没有这样的j,G就不连通，矛盾。因为Pm的终点在S中，因此e+1 一定是G,中的割边。 令e是在G中与v,相关联的异于e+1的边（非零度点一定有），根据算法选择 e1(割边)的原则，e也一定是割边。但是，Gm中任意顶点的度数必是偶 数，e在Gm中的连通分支是欧拉图，e在Gm的某个 欧拉回路中，不可能是G的割边。矛盾
Fleury算法的证明(续) (2) (证明含所有边)假设Pm没有包括G中所有的边，令Gm中所 有非零度顶点集合为S（非空）, 令S' =VG -S, 则vmS' 。 考察序列e1 ,e2 ,…ej ,ej+1 ,…,em。假设j是满足vjS, 而vj+1S’的最大下标。 如果没有这样的j，G就不连通，矛盾。因为Pm的终点在S’中，因此ej+1 一定是Gj中的割边。 令e是在Gj中与vj相关联的异于ej+1的边(非零度点一定有), 根据算法选择 ej+1 (割边)的原则，e也一定是割边。但是，Gm中任意顶点的度数必是偶 数，e在Gm中的连通分支是欧拉图，e在Gm的某个 欧拉回路中，不可能是Gj的割边。矛盾。 vm S’ S vj+1 vj ej+1 v e