4欧拉图.ppt

1
七桥问题
七桥问题(Seven bridges of Königsberg problem): River Pregel, Kaliningrad, Russia
2
一笔画
3
欧拉图
1. 七桥问题,一笔画,欧拉通(回)路,欧拉图
2. 判定欧拉图的充分必要条件
3. 求欧拉回路的算法
4. 中国邮递员问题
4
Leonhard Euler
Leonhard Euler(1707~1783):
人类有史以来最多产的数学家.
1736年,“七桥问题”,图论和拓扑学诞生
A
D
c
d
a
b
f
C
g
B
e
5
欧拉图(Eulerian)
欧拉通路(Euler trail): 经过图中所有边的简单通路
欧拉回路(Euler tour/circuit): 经过图中所有边的简单回路
欧拉图(Eulerian): 有欧拉回路的图
半欧拉图(semi-Eulerian): 有欧拉通路但没有欧拉回路的图
6
无向半欧拉图的充分必要条件
定理1: 设G是无向图,则
G是欧拉图 G连通且无奇数度顶点。
证明:思路:若欧拉回路总共k次经过顶点v,则d(v)=2k.
思路:(构造法)一个个的回路寻找
7
(必要性)
设G具有欧拉回路,即有点边序列, v0 = vk
其中顶点可能重复出现,但边不重复。因为欧拉回路经过图G的所有顶点,故图G必是连通的。
对任意一个不是端点的顶点vi,在欧拉回路中每当vi出现一次,必关联两条边,故vi虽可重复出现,但d(vi)必是偶数。对于端点,因 v0 = vk ,则d(v0)为偶数,即G中无奇数度顶点。
8
(充分性)
若图G是连通图且无奇度顶点,我们构造一条欧拉回路如下:
(1)任取一个顶点v0开始构造一条回路,即从v0出发,经关联边e1进入v1,因d(v1)为偶数,则必有另一条关联边e2,可由v1再经关联边e2 进入v2,如此进行下去,每边仅取一次。由于G是连通的,故必可回到顶点v0,得到上述一条回路L1 : 。
9
(充分性续)
(2)若L1通过了G的所有边,则L1就是欧拉通路。
(3)若G中去掉L1(首先去掉L1的边,再去掉孤立点)后得到子图G’,则G’中每个顶点度数为偶数,因为原来的图是连通的,故L1与G’至少有一个顶点vi重合,在G’中由vi 出发重复(1)的方法得到回路L2。
(4)当L1与L2组合在一起,如果恰是G,则G有欧拉通路,否则重复(3)的方法得到回路L3。以此类推,直到得到一条经过图G中所有边的欧拉通路。
10
无向欧拉图的充分必要条件
定理2: 设G是无向图,则
G是半欧拉图 G连通且有两个奇数度顶点。