《离散数学 第2版 教学课件 ppt 作者 王元元 离散第19讲(原) 欧拉图与哈密顿图》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第19讲(原) 欧拉图与哈密顿图（51页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：宋丽华 单位：计算机理论教研室,理工大学指挥自动化学院,PowerPoint Template_Sub,图的基础知识,路径、回路及连通性,欧拉图与哈密顿图,图的矩阵表示,欧拉图与哈密顿图,离散数学第19讲,Page 117 to 122,-4-,第19讲 欧拉图与哈密顿图,回顾,顶点的度数 握手定理：d(v)=2m 拟路径、路径、闭路径 通路、回路 定理8-4：有拟路径则有通路 定理8-5：有闭路径则有回路 连通 无向图G连通 有向图G连通 强连通、单向连通、弱连通,-5-,第19讲 欧拉图与哈密顿图,问题引入,交通网 问题1：工兵团巡逻维护 巡逻路线能否不重复？
2、 巡逻路线如何最短？ 数学模型？ 问题2：汽车团送给养 送给养地能否不重复？ 送给养路线如何最短？ 数学模型？,-6-,第19讲 欧拉图与哈密顿图,欧拉图与欧拉路径,定义： 图G称为欧拉图(Euler graph)，如果图G上有一条经过G的所有顶点、所有边的闭路径。 图G称为欧拉路径(Euler walk)，如果图G上有一条经过G所有顶点、所有边的路径。,注意：欧拉图分无向欧拉图与有向欧拉图,-7-,第19讲 欧拉图与哈密顿图,例,-8-,第19讲 欧拉图与哈密顿图,哈密顿图与哈密顿通路,定义： 无向图G称为哈密顿图(Hamilton graph)，如果G上有一条经过所有顶点的回路(也称这一回
3、路为哈密顿回路)。 无向图G称有哈密顿通路(非哈密顿图)，如果G上有一条经过所有顶点的通路(非回路)。,-9-,第19讲 欧拉图与哈密顿图,例,-10-,第19讲 欧拉图与哈密顿图,欧拉图与哈密顿图判断,（a）既为欧拉图又为哈密顿图； （b）是欧拉图而非哈密顿图； （c）是哈密顿图却非欧拉图； （d）既非欧拉图也非哈密顿图,（a） (b) (c) (d),欧拉图与哈密顿图是两类不同的图,-11-,第19讲 欧拉图与哈密顿图,欧拉路径与哈密顿通路,（a）既有欧拉路径又有哈密顿通路； （b）有欧拉路径而无哈密顿通路； （c）有哈密顿通路却无欧拉路径； （d）既无欧拉路径也无哈密顿通路。,（a） (
4、b) (c) (d),欧拉路径与哈密顿通路也是两类不同的图,-12-,第19讲 欧拉图与哈密顿图,欧拉图应用,“清扫道路”,-13-,第19讲 欧拉图与哈密顿图,欧拉图应用,判断一笔画问题,-14-,第19讲 欧拉图与哈密顿图,我们面临的问题,如何判断欧拉图 定理8-11 如何具体求解路径 算法 弗罗莱（Fleury）算法,-15-,第19讲 欧拉图与哈密顿图,欧拉图的性质,G为一欧拉图 G显然是连通的 各顶点的度均为偶数 由于G本身为一闭路径，它每经过一个顶点一次，便给这一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的次数的两倍，从而均为偶数。,-16-,第19讲 欧拉图与哈密顿图,欧
5、拉图的充要条件,定理8.11 有限无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。 证明 对G的边数归纳。 当m = 1时，G必定为单顶点的环，显然为欧拉图。,-17-,第19讲 欧拉图与哈密顿图,定理8.11充分性证明,设边数少于m时成立，现考虑有m条边的图G。 从G的任一顶点v0出发经关联边e1“进入”v1，若deg(v1)为偶数，则必可由v1再经关联边e2进入v2，如此进行下去，每边仅取一次。由于G是连通的且结点是有限的，故必可达到v0结点停下，得到一条闭路径H：v0e1 v1 e2 vi ei+1 ek v0,v0,v1,v2,vk-1,-18-,第19讲 欧拉图与哈密顿图,
6、定理8.11充分性证明,从图G中删去H的所有边，所得图记为G，其各顶点的度数仍均为偶数。,v0,v1,v2,vk-1,-19-,第19讲 欧拉图与哈密顿图,定理8.11充分性证明,考虑G的各连通分支，据归纳假设，它们都是欧拉图。因此各有闭路径Hi。 由于G连通，各连通分支都与H共有一个或若干个公共顶点，因此，各闭路径Hi与H一起构成一个经过所有边的闭路径。这就是说，G是一个欧拉图。,H1,H2,H3,-20-,第19讲 欧拉图与哈密顿图,欧拉图的充要条件,定理8.11 有限无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。 有限有向图G为欧拉图，当且仅当G是弱连通的，并且每个顶点的出度
7、与入度相等。,-21-,第19讲 欧拉图与哈密顿图,欧拉路径的充要条件,定理8.12 无向图G为欧拉路径(非欧拉图)，当且仅当G连通，并且恰有两个顶点的度是奇数。 有向图G为欧拉路径(非欧拉图)，当且仅当G弱连通，并且恰有两个顶点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多1。,-22-,第19讲 欧拉图与哈密顿图,哥尼斯堡七桥问题,根据欧拉图充要条件，很容易解决。,-23-,第19讲 欧拉图与哈密顿图,科学家简介,列昂哈德欧拉(1707-1783） 欧拉是瑞士巴塞尔一位牧师之子，13岁进入巴塞尔大学，开始神学生涯。在大学里受伯努利影响转向数学，16岁取得哲学硕士学位。17
8、27年加入圣彼得堡的科学院，1741年到柏林科学院，1766年回到圣彼得堡直到去世。 欧拉在数学许多领域做出贡献，包括数论、组合以及分析在诸如音乐和造船上的应用等。他写的书籍和文章数量在1100部以上，另外还有非常多的生前未能发表的著作，以至去世后用了47年才发表完。他的全集的出版工作由瑞士自然科学协会负责，目前还在进行中，预期将超过75卷。,科学家简介,-24-,第19讲 欧拉图与哈密顿图,判断欧拉图,n个结点的完全图Kn是欧拉图吗？ n为奇数(大于1) 时是 n个结点的连通k-正则图是欧拉图吗？ n为偶数时是 k为偶数时是, ,-25-,第19讲 欧拉图与哈密顿图,欧拉图应用,“清扫道路”
9、,-26-,第19讲 欧拉图与哈密顿图,欧拉图应用,判断一笔画问题,-27-,第19讲 欧拉图与哈密顿图,欧拉图应用,“蚂蚁赛跑问题”：下图中，在结点v2，v3上的两只蚂蚁跑过图的所有边（必须一次）到达目标v4，谁花费的时间多？（假设蚂蚁通过每一条边所花费时间相同）。,-28-,第19讲 欧拉图与哈密顿图,问题引入,交通网 问题1：工兵团巡逻维护 巡逻路能否不重复？ 巡逻路如何最短？ 数学模型？ 问题2：汽车团送给养 送给养地能否不重复？ 送给养路如何最短？ 数学模型？,-29-,第19讲 欧拉图与哈密顿图,欧拉图应用,中国邮递员问题 一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局
10、，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？ 我国管梅谷教授于1962年首先提出并发表 如何用图论的语言来描述？,用图论的语言来描述，即在一个带权图G中，能否找到一条闭合的拟路径C，使C包含G的每条边最少一次且C的权值最小？,-30-,第19讲 欧拉图与哈密顿图,中国邮路问题解决思路,如果街区图是一个欧拉图，一定有欧拉回路， 问题也就迎刃而解了。 若街区图不是欧拉图，则必然有一些街道要被重复走过才能回到原出发点。 显然要在奇度点间加重复边。 如何使所加的边长度最少？ 归结为求奇度点间的最小匹配,-31-,第19讲 欧拉图与哈密顿图,哈密顿图的充分条件,定理8.1
11、3： 设图G为具有n个顶点的简单无向图，如果G的每一对顶点的度数之和都不小于n1 （d(u)+d(v) n-1 ），那么G中有一条哈密顿通路； 如果G的每一对顶点的度数之和不小于n （ d(u)+d(v) n ），且n3，那么G为一哈密顿图。 （奥尔定理）,-32-,第19讲 欧拉图与哈密顿图,奥尔定理证明,反证法。假设存在这样的图，满足条件但不是哈密顿图。在所有这样的图中，设G是边数最大的。因为G不是完全图，所以存在u,v不相邻，则G上加边形成图G,G有哈密顿回路，且回路必包含 。把该边从回路中删除，得到G中的哈密顿通路P：u=v1,v2,vn=v,可以断言对2jn, 如果 在G中，则 不在
12、G中，否则G中存在哈密顿回路C:u=v1,vj,vj+1,vn=v,vj-1,vj-2,v2,v1=u。 于是从u到vj(2jn)共有d(u)条边，这就给出了d(u)个不与v相邻的vj-1(1j-1n-1)，所以d(v) (n-1)-d(u)，即d(u)+d(v) n-1，矛盾。,-33-,第19讲 欧拉图与哈密顿图,哈密顿通路存在的构造证明,首先G为一连通图。 （反证） 若G为不连通图，G由若干连通分支所组成。令v1，v2分属于连通分支G1，G2；G1，G2各有n1，n2个顶点。显然n1n，n2n，于是d(v1) n11 ，d(v2) n21，从而d (v1)+d(v2) n1+n22n1，
13、与题设矛盾。 用构造扩充的方法在G中构作出一条长为n1的通路。 令P为G中任意一条长为p1(pn)的通路，设其顶点序列为v1,v2,vp 。我们将这一通路扩充到长为p 。,-34-,第19讲 欧拉图与哈密顿图,哈密顿通路存在的构造证明,P为长p1的通路v1,v2,vp (1)如果有v v1，v2，vp，它与v1或vp间有边相关联，那么可立即扩充P为长度为p的通路。 (2)如果v1，vp均只与原通路P上的顶点相邻，我们可以证明G中有一条包含v1, v2,vp，长度为p的回路C。 如果v1与vp相邻，那么我们已经如愿。 如果v1与某个vk(kp)相邻，而vp与vk-1 相邻，那么我们便可得到包含v
14、1，v2，vp的回路：(v1，v2，vk-1 ,vp , vp-1 , ，vk , v1）,V1 v2 vk-1 vk vk+1 vp-1 vp,-35-,第19讲 欧拉图与哈密顿图,哈密顿通路存在的构造证明,长度为p的回路C不存在，则出现矛盾。 若vp不与vi1-1 ,vi2-1 , , vir-1中任何一个相邻，那么d (vp) p-r-l，因而d (v1) + d (vp) r+prl = p1n1 与题设矛盾，因此不可能发生。 将回路扩充为通路。 重复过程(l)，(2)不断扩充通路P，直至它的长度为n1 ，这时便得到G中的一条哈密顿通路。,V1 v2 vk-1 vk vk+1 vp-1
15、 vp,v,-36-,第19讲 欧拉图与哈密顿图,背景知识,哈密顿“周游世界” 游戏 哈密顿1859年提出一个名叫“周游世界”的游戏，用一个正十二面体的20个顶点代表20个大城市 (如左下图) ,这个正十二面体同构于一个平面图(如右下图),要求沿着正十二面体的棱寻找一条旅行路线,通过每个城市恰好一次又回到出发城市 。,-37-,第19讲 欧拉图与哈密顿图,科学家简介,威廉罗万哈密顿(1805-1865） 1805年8月4日生于爱尔兰都柏林；1865年9月2日 卒于都柏林三岁能读英语，会算术；五岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；九岁便熟悉了波斯语，阿拉伯语和印地语 。1823年7月7日，哈密顿以入学考试第一名的成绩进入著名的三一学院， 1832年，哈密顿成为爱尔兰皇家科学院院士 ，1837年，哈密顿被任命为爱尔兰皇家科学院院长 。 研究工作涉及不少领域，成果最大的是光学、力学和四元数他研究的光学是几何光学，具有数学性质；力学则是列出动力学方程及求解；因此哈密顿主要是数学家但在科学史中影响最大的却是他对力学的贡献哈密顿量是现代物理最重要的量。,-38-,第19讲 欧拉图与哈密顿图,例题,例8.13： (1) 顶点数目不少于3的完全图都是哈密顿图。 (2)
