离散数学 欧拉图与哈密尔顿图.ppt
《离散数学 欧拉图与哈密尔顿图.ppt》由会员分享,可在线阅读,更多相关《离散数学 欧拉图与哈密尔顿图.ppt(39页珍藏版)》请在三一文库上搜索。
1、1,第四章 欧拉图与哈密尔顿图,主要内容,一、欧拉图与中国邮路问题,二、哈密尔顿图,三、最短路问题与货郎担问题,教学时数,安排8学时讲授本章内容,2,本次课主要内容,(一)、欧拉图及其性质,(二)、Fleury算法,(三)、中国邮路问题,欧拉图与中国邮路问题,3,1、欧拉图的概念,(一)、欧拉图及其性质,(1)、问题背景欧拉与哥尼斯堡七桥问题,结论:在一个点线连接的图形中,如果每个顶点关联偶数条边,并且点与点之间有路可行,则从某点出发,经过每条边一次且仅一次,可以回到出发点。,4,哥尼斯堡城(位于德国北部), 在欧拉的生活与图论历史中扮演着非常重要角色。因为它,产生了著名的欧拉图定理,因为它,
2、产生了图论。,注:一笔画-中国古老的民间游戏,要求:对于一个图G, 笔不离纸, 一笔画成.,(2)、欧拉图概念,定义1 对于连通图G,如果G中存在经过每条边的闭迹,则称G为欧拉图,简称G为E图。欧拉闭迹又称为欧拉环游,或欧拉回路。,5,2、欧拉图的性质,定理1 下列陈述对于非平凡连通图G是等价的:,(1) G是欧拉图;,(2) G的顶点度数为偶数;,(3) G的边集合能划分为圈。,证明: (1)(2),由(1),设 C是欧拉图G的任一欧拉回路,v是G中任意顶点,v在环游中每出现一次,意味在G中有两条不同边与v关联,所以,在G中与v关联的边数为偶数,即v的度数为偶数,由v的任意性,即证明(2)。
3、,(2)(3),由于G是连通非平凡的且每个顶点度数为偶数,所以G中至少存在圈C1,从G中去掉C1中的边,得到G的生成,8,(二)、Fleury算法,该算法解决了在欧拉图中求出一条具体欧拉环游的方法。方法是尽可能避割边行走。,1、 算法,(1)、 任意选择一个顶点v0,置w0=v0;,9,(2)、 假设迹wi=v0e1v1eivi已经选定,那么按下述方法从E-e1,e2,ei中选取边ei+1:,1)、 ei+1与vi+1相关联;,2)、除非没有别的边可选择,否则 ei+1不能是,Gi=G-e1,e2,ei的割边。,(3)、 当(2)不能执行时,算法停止。,例3 在下面欧拉图G中求一条欧拉回路。,
4、10,解:,例4 某博物馆的一层布置如下图,其中边代表走廊,结点e是入口,结点g是礼品店,通过g我们可以离开博物馆。请找出从博物馆e进入,经过每个走廊恰好一次,最后从g处离开的路线。,11,解:图中只有两个奇度顶点e和g,因此存在起点为e,终点为g的欧拉迹。,为了在G中求出一条起点为e,终点为g的欧拉迹,在e和g间添加一条平行边m,用Fleury算法求出欧拉环游为:,emgcfabchbdhgdjiejge,所以:解为:egjeijdghdbhcbafcg,12,例4 证明:若G有2k0个奇数顶点,则存在k条边不重的迹Q1,Q2,Qk,使得:,证明:不失一般性,只就G是连通图进行证明。,设G=
5、(n, m)是连通图。令vl,v2,,vk,vk+1,v2k是G的所有奇度点。,在vi与vi+k间连新边ei得图G*(1ik).则G*是欧拉图,因此,由Fleury算法得欧拉环游C.,在C中删去ei (1ik).得k条边不重的迹Qi (1ik):,13,例5 设G是非平凡的欧拉图,且v V(G)。证明:G的每条具有起点v的迹都能扩展成G的欧拉环游当且仅当G-v是森林。,证明:“必要性”,若不然,则G-v有圈C。,考虑G1=G-E(G)的含有顶点v的分支H。,由于G是非平凡欧拉图,所以G1的每个顶点度数为偶数,从而,H是欧拉图。,14,H是欧拉图,所以存在欧拉环游T. 对于T,把它看成v为起点和
6、终点的一条欧拉迹,显然不能扩充为G的欧拉环游。这与条件矛盾!,“充分性”,若不然,设Q=(v, w)是G的一条不能扩充为G的欧拉环游的最长迹,显然v = w,且Q包含了与v关联的所有边。即Q是一条闭迹。,于是,G-v包含G-Q且G-Q的每个顶点度数为偶数.,于是,G-Q的非平凡分支是欧拉图,说明有圈,即G-v有圈,这与条件矛盾.,15,16,17,18,19,20,21,22,23,24,定理15.7 定理15.8,25,26,(三)、中国邮路问题,1962年,中国数学家管梅谷提出并解决了“中国邮路问题”,1、问题,邮递员派信的街道是边赋权连通图。从邮局出发,每条街道至少行走一次,再回邮局。如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 欧拉图与哈密尔顿图 欧拉图 哈密尔顿
链接地址:https://www.31doc.com/p-2281290.html