文档介绍：第十五章欧拉图与哈密顿图
主要内容
欧拉图
哈密顿图
带权图与货郎担问题
1
欧拉图
历史背景:哥尼斯堡七桥问题与欧拉图
2
欧拉图定义

(1) 欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.
(2) 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路.
(3) 欧拉图——具有欧拉回路的图.
(4) 半欧拉图——具有欧拉通路而无欧拉回路的图.
几点说明:
规定平凡图为欧拉图.
欧拉通路是生成的简单通路,欧拉回路是生成的简单回路.
环不影响图的欧拉性.
3
上图中,(1) ,(4) 为欧拉图,(2),(5)为半欧拉图,(3),(6)既不是欧拉图,也不是半欧拉图. 在(3),(6)中各至少加几条边才能成为欧拉图?
欧拉图实例
4
无向欧拉图的判别法
无向图G是欧拉图当且仅当G连通且无奇度数顶点.
证若G 为平凡图无问题. 下设G为 n 阶 m 条边的无向图.
必要性设C 为G 中一条欧拉回路.
(1) G 连通显然.
(2) viV(G),vi在C上每出现一次获2度,所以vi为偶度顶点.
由vi 的任意性,结论为真.
充分性对边数m做归纳法(第二数学归纳法).
(1) m=1时,G为一个环,则G为欧拉图.
(2) 设mk(k1)时结论为真,m=k+1时如下证明:
5
无向欧拉图的判别法(续)
PLAY
从以上证明不难看出:欧拉图是若干个边不重的圈之并,见示意图3.
6
欧拉图的判别法
无向图G是半欧拉图当且仅当G 连通且恰有两个奇
度顶点.
证必要性简单.
充分性()
设u,v为G 中的两个奇度顶点,令
G =G(u,v)
则G 连通且无奇度顶点, 为欧拉图,因而
存在欧拉回路C,令
=C(u,v)
则为 G 中欧拉通路.
7
有向欧拉图的判别法
有向图D是欧拉图当且仅当D是强连通的且每个顶
点的入度都等于出度.
.
有向图D是半欧拉图当且仅当D是单向连通的,且
D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个
的出度比入度大1,而其余顶点的入度都等于出度.
.
G是非平凡的欧拉图当且仅当G是连通的且为若干
个边不重的圈之并.
.
8
例题
例1 设G是欧拉图,但G不是平凡图,也不是一个环,则
(G)2.
证只需证明G中不可能有桥(如何证明?)
上图中,(1),(2)两图都是欧拉图,均从A点出发,如何一次成功地走出一条欧拉回路来?
(1) (2)
9
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),(2)从A出发(其实从任何一点
出发都可以)的欧拉回路各一条.
10