Fleury算法的证明 2)(证明含所有边)假设P没有包括G中所有的边，令Gn中所有 非零度顶点集合为S(非空)，令S'=Vc-S,则vm∈S'。 考察序列ee2,9+1,…,em。假设j是满足y∈S而+1∈S的最大下标。 因为Pm的终点在S中，因此e+1一定是G,中的割边。 令e是在G中与v相关联的异于e+1的边（非零度点一定有），根据算法选择 ©+1（割边）的原则，e也一定是割边。但是，Gm中任意顶点的度数必是偶 数，e在Gn中的连通分支是欧拉图，e在Gn的某个 欧拉回路中，不可能是G的割边。矛盾。 e ej-1 S
(2) (证明含所有边)假设P m没有包括G中所有的边，令Gm中所有 非零度顶点集合为S（非空）,令S ' =VG -S,则vmS ' 。 考察序列e1 ,e2 ,…ej ,ej+1 ,…,em。假设j是满足vjS, 而vj+1S’的最大下标。 因为Pm的终点在S’中，因此ej+1一定是Gj中的割边。 令e是在Gj中与vj相关联的异于ej+1的边(非零度点一定有), 根据算法选择 ej+1 (割边)的原则，e也一定是割边。但是，Gm中任意顶点的度数必是偶 数，e在Gm中的连通分支是欧拉图，e在Gm的某个 欧拉回路中，不可能是Gj的割边。矛盾。 vm S’ S vj+1 ej+1 vj v e Fleury算法的证明
有向欧拉图 ▣有向图中含所有边的有向简单回路称为有向欧拉回路。 口含有向欧拉回路的有向图称为有向欧拉图。 下面的等价命题可以用于有向欧拉图的判定： 口若G是弱连通的有向图，则下列命题等价： 口G中含有向欧拉回路。 口G中任一顶点的入度等于出度。 口G中所有的边位于若干个边互不相交的有向简单回路当中。 (证明与无向欧拉图类似。)
有向欧拉图 有向图中含所有边的有向简单回路称为有向欧拉回路。 含有向欧拉回路的有向图称为有向欧拉图。 下面的等价命题可以用于有向欧拉图的判定： 若G是弱连通的有向图，则下列命题等价： G中含有向欧拉回路。 G中任一顶点的入度等于出度。 G中所有的边位于若干个边互不相交的有向简单回路当中。 (证明与无向欧拉图类似。)