第二节欧拉图.pptVIP

第二节欧拉图;历史背景：哥尼斯堡七桥问题与欧拉图

（1）（2）

图1

其实，欧拉图是一笔画出的边不重复的回路.;一、欧拉图的定义

1、欧拉图的定义

定义1

（1）欧拉通路——经过图中每条边一次且

仅一次行遍所有顶点的通路.

（2）欧拉回路——经过图中每条边一次且

仅一次行遍所有顶点的回路.

（3）欧拉图——具有欧拉回路的图.

（4）半欧拉图——具有欧拉通路而无欧拉

回路的图.;几点说明：

＊规定平凡图为欧拉图.

＊欧拉通路是生成的简单通路，欧拉回路

是生成的简单回路.

＊环不影响图的欧拉性.;易知，图2中，（1）、（4）为欧拉图，（2）、（5）为半欧拉图，（3）、（6）既不是欧拉图，

也不是半欧拉图.在（3），（6）中各至少加几

条边才能成为欧拉图？;二、欧拉图的判别法

1、无向欧拉图的判别法

定???1无向图G是欧拉图当且仅当G连通且

无奇度数顶点.

证若G为平凡图无问题.下设G为n阶m条

边的无向图.;充分性对边数m做归纳法（第二数学归纳法）.

（1）m=1时，G为一个环，则G为欧拉图.

（2）设m?k（k?1）时结论为真，m=k+1时

如下证明：;因而它们都是小欧拉图.设C1?,C2?,…,Cs?

是G1?,G2?,…,Gs?的欧拉回路.

（b）将C1上被删除的边还原，从C1上某一

顶点出发走出G的一条欧拉回路C.;设u,v为G中的两个奇度顶点，令G?=G?(u,v)

则G?连通且无奇度顶点，由定理15.1知G?为

欧拉图，因而存在欧拉回路C，令?=C?(u,v)

则?为G中欧拉通路.;定理4有向图D是半欧拉图当且仅当D是单

向连通的，且D中恰有两个奇度顶点，其中

一个的入度比出度大1，另一个的出度比入

度大1，而其余顶点的入度都等于出度.

本定理的证明类似于定理1.

定理5G是非平凡的欧拉图当且仅当G是连

通的且为若干个边不重的圈之并.

可用归纳法证定理5.;例1设G是欧拉图，但G不是平凡图，也不是

一个环，则?(G)?2.

证只需证明G中不可能有桥（如何证明？）

（1）（2）

图中，（1），（2）两图都是欧拉图，均

从A点出发，如何一次成功地走出一条欧拉

回路来？;三、Fleury算法

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中一条欧拉回路.

用Fleury算法走出例1中(1)，(2)从A出发

（其实从任何一点出发都可以）的欧拉回

路各一条.;小结

一、欧拉图的定义

二、欧拉图的判别法

三、Fleury算法