15欧拉图和哈密顿图.ppt

第15章 欧拉图与哈密顿图 哈密顿 1805年8月4日生于爱尔兰都柏林；1865年9月2日卒于都柏林．力学、数学、光学．哈密顿的父亲阿其巴德(Archibald Rowan Hamilton)为都柏林市的一个初级律师．哈密顿自幼聪明，被称为神童．他三岁能读英语，会算术；五岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；九岁便熟悉了波斯语，阿拉伯语和印地语．14岁时，因在都柏林欢迎波斯大使宴会上用波斯语与大使交谈而出尽风头． 匈牙利数学家厄多斯 保罗?厄多斯(1913-1996)是一位匈牙利的数学家。 其父母都是匈牙利的高中数学教师。 1983年以色列政府颁给十万美元“沃尔夫奖金”（WolfPrize）就是由他和华裔美籍的陈省身教授平分。 厄多斯是当代发表最多数学论文的数学家，也是全世界和各种各样不同国籍的数学家合作发表论文最多的人。他发表了近1000多篇的论文，平均一年要写和回答1500多封有关于数学问题的信。他可以和任何大学的数学家合作研究，他每到一处演讲就能和该处的一两个数学家合作写论文，据说多数的情形是人们把一些本身长期解决不了的问题和他讨论，他可以很快就给出了问题的解决方法或答案，于是人们赶快把结果写下来，然后发表的时候放上他的名字，厄多斯的新的一篇论文就这样诞生了。 本章内容 15.1 欧拉图 15.2 哈密顿图 15.3 带权图与货郎担问题 基本要求 作业 15.1 欧拉图 历史背景－－哥尼斯堡七桥问题 欧拉图 定义15.1 通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。 说明 欧拉通路是图中经过所有边的简单的生成通路(经过所有顶点的通路称为生成通路)。 欧拉回路是经过所有边的简单的生成回路。 举例 无向欧拉图的判定定理 定理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为非平凡的连通图可知，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,…,G ?s都是欧拉图， 因而都存在欧拉回路C ?i，i＝1,2,…,s。 最后将C还原（即将删除的边重新加上）， 并从C上的某顶点vr开始行遍，每遇到v*ji，就行遍G ?i中的欧拉回路C ?i，i＝1,2,…,s，最后回到vr， 得回路vr…v*j1…v*j1…v*j2…v*j2…v*js…v*js…vr， 此回路经过G中每条边一次且仅一次并行遍G中所有顶点， 因而它是G中的欧拉回路（演示这条欧拉回路）， 故G为欧拉图。 半欧拉图的判定定理 定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。 证明 必要性。设G是m条边的n阶无向图，因为G为半欧拉图， 因而G中存在欧拉通路(但不存在欧拉回路)， 设Г＝vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路，vi0≠vim。 ?v∈V(G)，若v不在Г的端点出现，显然d(v)为偶数， 若v在端点出现过，则d(v)为奇数， 因为Г只有两个端点且不同，因而G中只有两个奇数顶点。 另外，G的连通性是显然的。 半欧拉图的判定定理 定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。 证明 充分性。设G的两个奇度顶点分别为u0和v0， 对G加新边（u0,v0），得G ?＝G∪(u0,v0)， 则G ?是连通且无奇度顶点的图， 由定理15.1可知，G ?为欧拉图， 因而存