离散数学课件15欧拉图与哈密顿图.ppt
《离散数学课件15欧拉图与哈密顿图.ppt》由会员分享,可在线阅读,更多相关《离散数学课件15欧拉图与哈密顿图.ppt(39页珍藏版)》请在三一文库上搜索。
1、第15章 欧拉图与哈密顿图,离 散 数 学,中国地质大学本科生课程,数学家欧拉,欧拉,瑞士数学家,欧拉是科学史上最多产的一位杰出的数学家,他从19岁开始发表论文,直到76岁,他一生共写下了886本书籍和论文,其中在世时发表了700多篇论文。彼得堡科学院为了整理他的著作,整整用了47年。在他双目失明后的17年间,也没有停止对数学的研究,口述了好几本书和400余篇的论文。,欧拉对物理力学、天文学、弹道学、航海学、建筑学、音乐都有研究!有许多公式、定理、解法、函数、方程、常数等是以欧拉名字命名的。欧拉写的数学教材在当时一直被当作标准教程。19世纪伟大的数学家高斯曾说过“研究欧拉的著作永远是了解数学的
2、好方法”。欧拉还是数学符号发明者,他创设的许多数学符号,例如,i,e,sin,cos,tg,f (x)等等,至今沿用。,哈密顿,1805年8月4日生于爱尔兰都柏林;1865年9月2日卒于都柏林力学、数学、光学哈密顿的父亲阿其巴德(Archibald Rowan Hamilton)为都柏林市的一个初级律师哈密顿自幼聪明,被称为神童他三岁能读英语,会算术;五岁能译拉丁语、希腊语和希伯来语,并能背诵荷马史诗;九岁便熟悉了波斯语,阿拉伯语和印地语14岁时,因在都柏林欢迎波斯大使宴会上用波斯语与大使交谈而出尽风头,哈密顿工作勤奋,思想活跃发表的论文一般都很简洁,别人不易读懂,但手稿却很详细,因而很多成果
3、都由后人整理而得仅在三一学院图书馆中的哈密顿手稿,就有250本笔记及大量学术通信和未发表论文爱尔兰国家图书馆还有一部分手稿 他的研究工作涉及不少领域,成果最大的是光学、力学和四元数他研究的光学是几何光学,具有数学性质;力学则是列出动力学方程及求解;因此哈密顿主要是数学家但在科学史中影响最大的却是他对力学的贡献哈密顿量是现代物理最重要的量,当我们得到哈密顿量,就意味着得到了全部。,匈牙利数学家厄多斯,保罗厄多斯(1913-1996)是一位匈牙利的数学家。 其父母都是匈牙利的高中数学教师。 1983年以色列政府颁给十万美元“沃尔夫奖金”(WolfPrize)就是由他和华裔美籍的陈省身教授平分。 厄
4、多斯是当代发表最多数学论文的数学家,也是全世界和各种各样不同国籍的数学家合作发表论文最多的人。他发表了近1000多篇的论文,平均一年要写和回答1500多封有关于数学问题的信。他可以和任何大学的数学家合作研究,他每到一处演讲就能和该处的一两个数学家合作写论文,据说多数的情形是人们把一些本身长期解决不了的问题和他讨论,他可以很快就给出了问题的解决方法或答案,于是人们赶快把结果写下来,然后发表的时候放上他的名字,厄多斯的新的一篇论文就这样诞生了。,本章内容,15.1 欧拉图 15.2 哈密顿图 15.3 带权图与货郎担问题 基本要求 作业,15.1 欧拉图,历史背景哥尼斯堡七桥问题,欧拉图是一笔画出
5、的边不重复的回路。,欧拉图,定义15.1 通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图,具有欧拉通路而无欧拉回路的图称为半欧拉图。 说明 欧拉通路是图中经过所有边的简单的生成通路(经过所有顶点的通路称为生成通路)。 欧拉回路是经过所有边的简单的生成回路。,举例,欧拉图,半欧拉图,无欧拉通路,欧拉图,无欧拉通路,无欧拉通路,无向欧拉图的判定定理,定理15.1 无向图G是欧拉图当且仅当G是连通图,且G中没有奇度顶点。 证明 若G是平凡图,结论显然成立。 下面设G为非平凡图,设G
6、是m条边的n阶无向图, 并设G的顶点集Vv1,v2,vn。 必要性。因为G为欧拉图,所以G中存在欧拉回路, 设C为G中任意一条欧拉回路,vi,vjV,vi,vj都在C上, 因而vi,vj连通,所以G为连通图。 又viV,vi在C上每出现一次获得2度, 若出现k次就获得2k度,即d(vi)2k, 所以G中无奇度顶点。,定理15.1的证明,充分性。由于G为非平凡的连通图可知,G中边数m1。 对m作归纳法。 (1)m1时,由G的连通性及无奇度顶点可知, G只能是一个环,因而G为欧拉图。 (2)设mk(k1)时结论成立,要证明mk+1时,结论也成立。 由G的连通性及无奇度顶点可知,(G)2。 无论G是
7、否为简单图,都可以用扩大路径法证明G中必含圈。,定理15.1的证明,设C为G中一个圈,删除C上的全部边,得G的生成子图G , 设G 有s个连通分支G 1,G 2,G s, 每个连通分支至多有k条边,且无奇度顶点, 并且设G i与C的公共顶点为v*ji,i1,2,s, 由归纳假设可知,G 1,G 2,G s都是欧拉图, 因而都存在欧拉回路C i,i1,2,s。 最后将C还原(即将删除的边重新加上), 并从C上的某顶点vr开始行遍,每遇到v*ji,就行遍G i中的欧拉回路C i,i1,2,s,最后回到vr, 得回路vrv*j1v*j1v*j2v*j2v*jsv*jsvr, 此回路经过G中每条边一次
8、且仅一次并行遍G中所有顶点, 因而它是G中的欧拉回路(演示这条欧拉回路), 故G为欧拉图。,定理15.2 无向图G是半欧拉图当且仅当G是连通的,且G中恰有两个奇度顶点。 证明 必要性。设G是m条边的n阶无向图,因为G为半欧拉图, 因而G中存在欧拉通路(但不存在欧拉回路), 设vi0ej1vi1vim-1ejmvim为G中一条欧拉通路,vi0vim。 vV(G),若v不在的端点出现,显然d(v)为偶数, 若v在端点出现过,则d(v)为奇数, 因为只有两个端点且不同,因而G中只有两个奇数顶点。 另外,G的连通性是显然的。,半欧拉图的判定定理,定理15.2 无向图G是半欧拉图当且仅当G是连通的,且G
9、中恰有两个奇度顶点。 证明 充分性。设G的两个奇度顶点分别为u0和v0, 对G加新边(u0,v0),得G G(u0,v0), 则G 是连通且无奇度顶点的图, 由定理15.1可知,G 为欧拉图, 因而存在欧拉回路C ,而CC -(u0,v0)为G中一条欧拉通路, 所以G为半欧拉图。,半欧拉图的判定定理,有向欧拉图的判定定理,定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的,且D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个的出度比入度大1,而其余顶点的入度都等于出度。(举例),定理15.5 G是非平凡的欧
10、拉图当且仅当G是连通的且为若干个边不重的圈的并。,例15.1,例15.1 设G是非平凡的且非环的欧拉图,证明: (1)(G)2。 (2)对于G中任意两个不同顶点u,v,都存在简单回路C含u和v。 证明 (1)由定理15.5可知,eE(G),存在圈C,e在C中, 因而p(G-e)p(G),故e不是桥。 由e的任意性(G)2,即G是2边-连通图。 (2)u,vV(G),uv,由G的连通性可知,u,v之间必存在路径1,设G G-E(1),则在G 中u与v还必连通, 否则,u与v必处于G 的不同的连通分支中, 这说明在1上存在G中的桥,这与(1)矛盾。 于是在G 中存在u到v的路径2,显然1与2边不重
11、, 这说明u,v处于12形成的简单回路上。,求欧拉图中欧拉回路的算法,Fleury算法,能不走桥就不走桥 (1) 任取v0V(G),令P0v0。 (2) 设Piv0e1v1e2eivi已经行遍,按下面方法来从 E(G)-e1,e2,ei中选取ei+1: (a) ei+1与vi相关联; (b) 除非无别的边可供行遍,否则ei+1不应该为 GiG-e1,e2,ei中的桥。 (3)当(2)不能再进行时,算法停止。 说明 可以证明,当算法停止时所得简单回路 Pmv0e1v1e2emvm(vmv0) 为G中一条欧拉回路。,Fleury算法示例,例15.2,下图是给定的欧拉图G。某人用Fleury算法求G
12、中的欧拉回路时,走了简单回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(观看他的错误走法),无法行遍了,试分析在哪步他犯了错误?,解答 此人行遍v8时犯了能不走桥就不走桥的错误,因而他没行遍出欧拉回路。 当他走到v8时,G-e2,e3,e14,e10,e1,e8为下图所示。,此时e9为该图中的桥,而e7,e11均不是桥,他不应该走e9,而应该走e7或e11,他没有走,所以犯了错误。注意,此人在行遍中,在v3遇到过桥e3,v1处遇到过桥e8,但当时除桥外他无别的边可走,所以当时均走了桥,这是不会犯错误的。,15.2 哈密顿图,历史背景:哈密顿周游世界问题与哈密顿图,哈密
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 课件 15 欧拉图 哈密
链接地址:https://www.31doc.com/p-3068215.html