《哈密顿图》PPT课件.ppt

《《哈密顿图》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、邢台学院数学系欢迎同学们！第三章欧拉图和哈密顿图欧拉（L.Euler,1707.4.15-1783.9.18）著名的数学家。生于瑞士的巴塞尔，卒于彼得堡。大部分时间在俄国和德国度过。他早年在数学天才贝努里赏识下开始学习数学,17岁获得硕士学位，毕业后研究数学,是数学史上最高产的作家。在世发表论文700多篇,去世后还留下100多篇待发表。其论著几乎涉及所有数学分支。欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的成就。在数学的各个领域，常常见到以欧来命名的公式、定理、和重要常数。课本上常见的如π、i、e、sin、cos、tg、△x、Σ、f(

2、x)等，都是他创立并推广的。欧拉还首先完成了月球绕地球运动的精确理论，创立了分析力学、刚体力学等力学学科，深化了望远镜、显微镜的设计计算理论。第一部分欧拉图1736年瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”(下称七桥问题)。这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生了能否“从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处”的问题。欧拉圈、欧拉图定义图G中的一圈，若它通过G中的每一条边(或弧)恰好一次，则称该圈为欧拉圈，具有这种圈的图称为欧拉无

3、向(或有向)图。定理1无向图G是欧拉图,当且仅当G是连通图,且G中没有奇度顶点。证：设G=是含有m条边的n阶非平凡无向图,其中:V={v1,v2,…,vn}。1).必要性因为G为欧拉图,所以,G中存在欧拉圈。设C是G中的欧拉圈,vi,vjV,vi,vj都在C上,因此,vi和vj是连通的,所以,G为连通图。又viV,vi在C上每出现一次获得2度。若出现k次就获得2k度,即:d(vi)=2k,所以,G中无奇度顶点。2).充分性由G为非平凡的连通图可知:G中边数m1。对m作归纳。(1)m=1时,由G的连通性和无奇度顶点可知:G只能是一个环

4、,因此,G为欧拉图。(2)设mk(k1)时,结论成立．要证明m=K+1时,结论也成立。由G的连通性和无奇度顶点可知:(G)2。用扩大路径法可以证明G中存在长度大于或等于3的圈。设C为G中一个圈,删除C上的全部边,得G的生成子图G’。设G’有s个连通分支G’1,G’2,…,G’s,每个连通分支至多有k条边,且无奇度顶点,并且设G’i与C的公共顶点为vji*(i=1..s)。由归纳假设可知:G’1,G’2,…,G’s都是欧拉图,因此,都存在欧拉圈C’i(i=1..s)。现在将C还原(即将删除的边重新加上),并从C上的某顶点vr开始进行遍历,每遇到v

5、ji*,就行遍G’i中的欧拉圈C’i(i=1..s),最后,回到vr,得圈C”:vr…vj1*…vj1*…vj2*…vj2*…vjs*…vjs*…vr。此圈C”经过G中每条边一次且仅一次。因此,C”是G中的欧拉圈(如右下图所示)。故,G为欧拉图。定理2连通图G具有欧拉路而无欧拉圈,当且仅当G恰有两个奇数度顶点.证:必要性:设连通图G从顶点a到顶点b有欧拉路C,但不是欧拉圈.在欧拉路C中,除第一边和最后一边外,,每经过G中顶点xi(包括a和b),都为顶点xi贡献2度,而C的第一边为a贡献1度,C的最后一条边为b贡献1度.因此,a和b的度数均为奇数,其余结

6、点度数均为偶数.充分性:设连通图G恰有两个奇数度结点,不妨设为a和b,在图G中添加一条边e={a,b}得G’,则G’的每个结点的度数均为偶数,因而G’中存在欧拉圈,故G中必存在欧拉路.●●●●●●●●●●●●●●●什么叫一笔画？什么样的图可以一笔画出？所谓图的一笔画，指的就是：从图的一点出发，笔不离纸，遍历每条边恰好一次，即每条边都只画一次，不准重复.从上图中容易看出：能一笔画出的图首先必须是连通图欧拉定理：①凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。②凡是只有两个奇点（其余均为偶点）的连通图，

7、一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。③其他情况的图，都不能一笔画出。“一笔划”问题？这是一些平面图形，请你思考图形能否一笔画出与什么有关？例1观察下面的图形，说明哪些图可以一笔画完，哪些能，为什么？对于可以一笔画的图形，指明画法例2下图是国际奥委会的会标，你能一笔把它画出来吗？构造欧拉圈思想：在画欧拉圈时，已经经过的边不能再用。因此，在构造欧拉圈过程中的任何时刻，假设将已经经过的边删除，剩下的边必须仍在同一连通分支当中。设G为欧拉图,通常情况下,G中存在若干条欧拉圈。下面介绍一种求欧拉圈的算法。1．Fleury算法(1)任取v

8、0V(G),令P0=v0(2)设Pi=v0e1v1e2…eivi已经遍历,按下面方法从E(G