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中顶点度数是偶数矛盾