资源描述:
《离散数学 欧拉图与哈密尔顿图ppt课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第四章欧拉图与哈密尔顿图主要内容一、欧拉图与中国邮路问题二、哈密尔顿图三、最短路问题与货郎担问题教学时数安排8学时讲授本章内容1本次课主要内容(一)、欧拉图及其性质(二)、Fleury算法(三)、中国邮路问题欧拉图与中国邮路问题21、欧拉图的概念(一)、欧拉图及其性质(1)、问题背景——欧拉与哥尼斯堡七桥问题结论:在一个点线连接的图形中,如果每个顶点关联偶数条边,并且点与点之间有路可行,则从某点出发,经过每条边一次且仅一次,可以回到出发点。3哥尼斯堡城(位于德国北部),在欧拉的生活与图论历史中扮演着非常重要角色
2、。因为它,产生了著名的欧拉图定理,因为它,产生了图论。注:一笔画----中国古老的民间游戏要求:对于一个图G,笔不离纸,一笔画成.(2)、欧拉图概念定义1对于连通图G,如果G中存在经过每条边的闭迹,则称G为欧拉图,简称G为E图。欧拉闭迹又称为欧拉环游,或欧拉回路。欧拉图41324132非欧拉图有欧拉迹非欧拉图无欧拉迹123442、欧拉图的性质定理1下列陈述对于非平凡连通图G是等价的:(1)G是欧拉图;(2)G的顶点度数为偶数;(3)G的边集合能划分为圈。证明:(1)→(2)由(1),设C是欧拉图G的任一欧拉回路
3、,v是G中任意顶点,v在环游中每出现一次,意味在G中有两条不同边与v关联,所以,在G中与v关联的边数为偶数,即v的度数为偶数,由v的任意性,即证明(2)。(2)→(3)由于G是连通非平凡的且每个顶点度数为偶数,所以G中至少存在圈C1,从G中去掉C1中的边,得到G的生成5(二)、Fleury算法该算法解决了在欧拉图中求出一条具体欧拉环游的方法。方法是尽可能避割边行走。1、算法(1)、任意选择一个顶点v0,置w0=v0;8(2)、假设迹wi=v0e1v1…eivi已经选定,那么按下述方法从E-{e1,e2,…,ei
4、}中选取边ei+1:1)、ei+1与vi+1相关联;2)、除非没有别的边可选择,否则ei+1不能是Gi=G-{e1,e2,…,ei}的割边。(3)、当(2)不能执行时,算法停止。例3在下面欧拉图G中求一条欧拉回路。dcbafeg图Ghji9解:dcbafeg图Ghji例4某博物馆的一层布置如下图,其中边代表走廊,结点e是入口,结点g是礼品店,通过g我们可以离开博物馆。请找出从博物馆e进入,经过每个走廊恰好一次,最后从g处离开的路线。afedcbihgj10解:图中只有两个奇度顶点e和g,因此存在起点为e,终点为
5、g的欧拉迹。为了在G中求出一条起点为e,终点为g的欧拉迹,在e和g间添加一条平行边mafedcbihgjm用Fleury算法求出欧拉环游为:emgcfabchbdhgdjiejge所以:解为:egjeijdghdbhcbafcg11例4证明:若G有2k>0个奇数顶点,则存在k条边不重的迹Q1,Q2,…,Qk,使得:证明:不失一般性,只就G是连通图进行证明。设G=(n,m)是连通图。令vl,v2,…,vk,vk+1,…,v2k是G的所有奇度点。在vi与vi+k间连新边ei得图G*(1≦i≦k).则G*是欧拉图,因
6、此,由Fleury算法得欧拉环游C.在C中删去ei(1≦i≦k).得k条边不重的迹Qi(1≦i≦k):12例5设G是非平凡的欧拉图,且v∈V(G)。证明:G的每条具有起点v的迹都能扩展成G的欧拉环游当且仅当G-v是森林。证明:“必要性”若不然,则G-v有圈C。考虑G1=G-E(G)的含有顶点v的分支H。由于G是非平凡欧拉图,所以G1的每个顶点度数为偶数,从而,H是欧拉图。13H是欧拉图,所以存在欧拉环游T.对于T,把它看成v为起点和终点的一条欧拉迹,显然不能扩充为G的欧拉环游。这与条件矛盾!“充分性”若不然,设
7、Q=(v,w)是G的一条不能扩充为G的欧拉环游的最长迹,显然v=w,且Q包含了与v关联的所有边。即Q是一条闭迹。于是,G-v包含G-Q且G-Q的每个顶点度数为偶数.于是,G-Q的非平凡分支是欧拉图,说明有圈,即G-v有圈,这与条件矛盾.14151617181920212223定理15.7定理15.82425(三)、中国邮路问题1962年,中国数学家管梅谷提出并解决了“中国邮路问题”1、问题邮递员派信的街道是边赋权连通图。从邮局出发,每条街道至少行走一次,再回邮局。如何行走,使其行走的环游路程最小?如果邮路图本身
8、是欧拉图,那么由Fleury算法,可得到他的行走路线。如果邮路图本身是非欧拉图,那么为得到行走环游,必须重复行走一些街道。于是问题转化为如何重复行走街道?262、管梅谷的结论定理2若W是图G中一条包含所有边的闭途径,则W在这样的闭途径中具有最短的长度当且仅当下列两个条件被满足:(1)每一条边最多重复经过一次;(2)在G的每一个圈上,重复经过的边的条数不超过圈长的一半。证明:“必要性”首