15欧拉图与哈密顿图.ppt

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

1、第15章欧拉图与哈密顿图离散数学中国地质大学本科生课程数学家欧拉欧拉，瑞士数学家，欧拉是科学史上最多产的一位杰出的数学家，他从19岁开始发表论文，直到76岁，他一生共写下了886本书籍和论文，其中在世时发表了700多篇论文。彼得堡科学院为了整理他的著作，整整用了47年。在他双目失明后的17年间，也没有停止对数学的研究，口述了好几本书和400余篇的论文。欧拉对物理力学、天文学、弹道学、航海学、建筑学、音乐都有研究！有许多公式、定理、解法、函数、方程、常数等是以欧拉名字命名的。欧拉写的数学教材在当时一直被当作标准教程。19世纪伟大的数学家高斯曾说

2、过“研究欧拉的著作永远是了解数学的好方法”。欧拉还是数学符号发明者，他创设的许多数学符号，例如π，i，e，sin，cos，tg，Σ，f(x)等等，至今沿用。哈密顿1805年8月4日生于爱尔兰都柏林；1865年9月2日卒于都柏林．力学、数学、光学．哈密顿的父亲阿其巴德(ArchibaldRowanHamilton)为都柏林市的一个初级律师．哈密顿自幼聪明，被称为神童．他三岁能读英语，会算术；五岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；九岁便熟悉了波斯语，阿拉伯语和印地语．14岁时，因在都柏林欢迎波斯大使宴会上用波斯语与大使交谈而出尽风头

3、．哈密顿工作勤奋，思想活跃．发表的论文一般都很简洁，别人不易读懂，但手稿却很详细，因而很多成果都由后人整理而得．仅在三一学院图书馆中的哈密顿手稿，就有250本笔记及大量学术通信和未发表论文．爱尔兰国家图书馆还有一部分手稿．他的研究工作涉及不少领域，成果最大的是光学、力学和四元数．他研究的光学是几何光学，具有数学性质；力学则是列出动力学方程及求解；因此哈密顿主要是数学家．但在科学史中影响最大的却是他对力学的贡献．哈密顿量是现代物理最重要的量，当我们得到哈密顿量，就意味着得到了全部。匈牙利数学家厄多斯保罗‧厄多斯(1913-1996)是一位匈牙利

4、的数学家。其父母都是匈牙利的高中数学教师。1983年以色列政府颁给十万美元“沃尔夫奖金”（WolfPrize）就是由他和华裔美籍的陈省身教授平分。厄多斯是当代发表最多数学论文的数学家，也是全世界和各种各样不同国籍的数学家合作发表论文最多的人。他发表了近1000多篇的论文，平均一年要写和回答1500多封有关于数学问题的信。他可以和任何大学的数学家合作研究，他每到一处演讲就能和该处的一两个数学家合作写论文，据说多数的情形是人们把一些本身长期解决不了的问题和他讨论，他可以很快就给出了问题的解决方法或答案，于是人们赶快把结果写下来，然后发表的时候放上

5、他的名字，厄多斯的新的一篇论文就这样诞生了。本章内容15.1欧拉图15.2哈密顿图15.3带权图与货郎担问题基本要求作业15.1欧拉图历史背景－－哥尼斯堡七桥问题欧拉图是一笔画出的边不重复的回路。欧拉图定义15.1通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。说明欧拉通路是图中经过所有边的简单的生成通路(经过所有顶点的通路称为生成通路)。欧拉回路是经过所有边的简单的生成回路。举例欧

6、拉图半欧拉图无欧拉通路欧拉图无欧拉通路无欧拉通路无向欧拉图的判定定理定理15.1无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。证明若G是平凡图，结论显然成立。下面设G为非平凡图，设G是m条边的n阶无向图，并设G的顶点集V＝{v1,v2,…,vn}。必要性。因为G为欧拉图，所以G中存在欧拉回路，设C为G中任意一条欧拉回路，vi,vj∈V，vi,vj都在C上，因而vi,vj连通，所以G为连通图。又vi∈V，vi在C上每出现一次获得2度，若出现k次就获得2k度，即d(vi)＝2k，所以G中无奇度顶点。定理15.1的证明充分性。由于G为

7、非平凡的连通图可知，G中边数m≥1。对m作归纳法。(1)m＝1时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图。(2)设m≤k(k≥1)时结论成立，要证明m＝k+1时，结论也成立。由G的连通性及无奇度顶点可知，δ(G)≥2。无论G是否为简单图，都可以用扩大路径法证明G中必含圈。定理15.1的证明设C为G中一个圈，删除C上的全部边，得G的生成子图G，设G有s个连通分支G1,G2,…,Gs，每个连通分支至多有k条边，且无奇度顶点，并且设Gi与C的公共顶点为v*ji，i＝1,2,…,s，由归纳假设可知，G1,G2,…

8、,Gs都是欧拉图，因而都存在欧拉回路Ci，i＝1,2,…,s。最后将C还原（即将删除的边重新加上），并从C上的某顶点vr开始行遍，每遇到v*ji，就行遍Gi中