子图G,若G没有边，则(3)成立。否则，G的每个非平 凡分支是度数为偶数的连通图，于是又可以抽取一个圈。 反复这样抽取，E(G)最终划分为若干圈。 (3)→(1) 设C,是G的边划分中的一个圈。若G仅由此圈组成， 则G显然是欧拉图。 否则，由于G连通，所以，必然存在圈C2,它和C有 公共顶点。于是，CUC2是一条含有C与C2的边的欧拉 闭迹，如此拼接下去，得到包含G的所有边的一条欧拉 闭迹。即证G是欧拉图。 推论1连通图G是欧拉图当且仅当G的顶点度数为偶。 推论2连通非欧拉图G存在欧拉迹当且仅当G中只有两 个顶点度数为奇数
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 子图G1 ,若G1没有边，则(3)成立。否则，G1的每个非平 凡分支是度数为偶数的连通图，于是又可以抽取一个圈。 反复这样抽取，E(G)最终划分为若干圈。 (3)→(1) 设C1是G的边划分中的一个圈。若G仅由此圈组成， 则G显然是欧拉图。 否则，由于G连通，所以，必然存在圈C2 ,它和C1有 公共顶点。于是，C1∪C2是一条含有C1与C2的边的欧拉 闭迹，如此拼接下去，得到包含G的所有边的一条欧拉 闭迹。即证G是欧拉图。 推论1 连通图G是欧拉图当且仅当G的顶点度数为偶。 推论2 连通非欧拉图G存在欧拉迹当且仅当G中只有两 个顶点度数为奇数
例1下面图中谁是欧拉图？谁是非欧拉图但存在欧拉 迹？准是非欧拉图且不存在欧拉迹？ G G 解：G是欧拉图；G2是非欧拉图，但存在欧拉迹；G 中不存在欧拉迹。 例2证明：若G和H是欧拉图，则G×H是欧拉图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 例1 下面图中谁是欧拉图？谁是非欧拉图但存在欧拉 迹？谁是非欧拉图且不存在欧拉迹？ G1 G2 G3 解：G1是欧拉图；G2是非欧拉图，但存在欧拉迹；G3 中不存在欧拉迹。 例2 证明：若G和H是欧拉图，则 G H 是欧拉图
证明：首先证明：对任意u∈V(G),v∈VH山，有： d(u)+d(v)=d((u,v)) 事实上，设z是u的任意一个邻点，一定有(u,v)的一个 邻点（亿，v),反之亦然。同理，对于v的任意一个邻点w, 一定有(u,v)的一个邻点(u,w),反之亦然。即：(u,v)在乘 积图中邻点个数等于u在G中邻点个数与v在H中邻点个 数之和。 所以，G,H是欧拉图，那么G×H顶点度数为偶数。 其次证明：G×H是连通的。 ∀(4，y),(42,2)∈V(G×H 由于G,H都是欧拉图，所以都连通。设最短的(u1,u2)路
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 证明：首先证明：对任意u ∈V(G), v ∈V(H),有： d u d v d u v ( ) ( ) (( , )) + = 事实上，设z是u的任意一个邻点，一定有(u, v)的一个 邻点(z, v),反之亦然。同理，对于v的任意一个邻点w， 一定有(u, v)的一个邻点(u, w), 反之亦然。即: (u, v)在乘 积图中邻点个数等于u在G中邻点个数与v在H中邻点个 数之和。 所以，G ,H是欧拉图，那么 G H 顶点度数为偶数。 其次证明： G H 是连通的。 1 1 2 2 ( , ),( , ) ( ) u v u v V G H 由于G, H都是欧拉图，所以都连通。设最短的(u1 , u2 )路
最短的(w1V2)路分别为4xx2.x山2 y1y2.ymV2 那么，由乘积图的定义：在乘积图中有路： (山1，Y)(x1,Y).(xk,Y1)(u2,1)(u2,y)(u2,ym)u2,y2) 这样，我们证明了G×H是连通的且每个顶点度数为偶 数。即它是欧拉图。 (二)、Fleury(弗勒里)算法 该算法解决了在欧拉图中求出一条具体欧拉环游的方 法。方法是尽可能避割边行走。 算法： (1)、 任意选择一个顶点V,置WVo;
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 最短的(v1 , v2 )路分别为： u x x x u 1 1 2 2 k 1 1 2 2 m v y y y v 那么，由乘积图的定义：在乘积图中有路： 1 1 1 1 1 2 1 2 1 2 2 2 ( , )( , ) ( , )( , )( , ) ( , )( , ) u v x v x v u v u y u y u v k m 这样，我们证明了 是连通的且每个顶点度数为偶 数。即它是欧拉图。 G H (二)、Fleury(弗勒里)算法 该算法解决了在欧拉图中求出一条具体欧拉环游的方 法。方法是尽可能避割边行走。 算法: (1)、 任意选择一个顶点v0 ,置w0=v0 ;
(2)、假设迹w=voe1Y1.eY已经选定，那么按下述方 法从E-(e1,e2,e,)中选取边e+i 1)、e+1与v相关联； 2)、除非没有别的边可选择，否则e#1不能是 G=G(e1,e2,e}的割边。 (3)、当(2)不能执行时，算法停止。 例3在下面欧拉图G中求一条欧拉回路。 图G 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 (2)、 假设迹wi=v0e1v1.eivi已经选定，那么按下述方 法从E-｛e1 ,e2 ,.,ei｝中选取边ei+1: 1)、 ei+1与vi相关联； 2)、除非没有别的边可选择，否则ei+1不能是 Gi=G-｛e1 ,e2 ,.,ei｝的割边。 (3)、 当(2)不能执行时，算法停止。 例3 在下面欧拉图G中求一条欧拉回路。 d c b a f e g 图G h j i