图论哈密尔顿图幻灯片.ppt
《图论哈密尔顿图幻灯片.ppt》由会员分享,可在线阅读,更多相关《图论哈密尔顿图幻灯片.ppt(32页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、图论课件哈密尔顿图1第1页,共32页,编辑于2022年,星期五本次课主要内容本次课主要内容(一一)、哈密尔顿图的概念、哈密尔顿图的概念(二二)、性质与判定、性质与判定哈密尔顿图哈密尔顿图2第2页,共32页,编辑于2022年,星期五1、背景、背景(一一)、哈密尔顿图的概念、哈密尔顿图的概念1857年,年,哈密尔顿发明了一个游戏哈密尔顿发明了一个游戏(IcosianGame).它是由它是由一个木制的正十二面体构成,在它的每个棱角处标有当时很有名一个木制的正十二面体构成,在它的每个棱角处标有当时很有名的城市。游戏目的是的城市。游戏目的是“环球旅行环球旅行”。为了容易记住被旅游过的城。为了容易记住被旅
2、游过的城市市,在每个棱角上放上一个钉子,再用一根线绕在那些旅游过的,在每个棱角上放上一个钉子,再用一根线绕在那些旅游过的城市上城市上(钉子钉子),由此可以获得旅程的直观表示。由此可以获得旅程的直观表示。十二面体3第3页,共32页,编辑于2022年,星期五哈密尔顿哈密尔顿(1805-1865),爱尔兰数学家。个人生活很不幸,爱尔兰数学家。个人生活很不幸,但兴趣广泛:诗歌、光学、天文学和数学无所不能。他的主要但兴趣广泛:诗歌、光学、天文学和数学无所不能。他的主要贡献是在代数领域,发现了四元数贡献是在代数领域,发现了四元数(第一个非交换代数第一个非交换代数),他认,他认为数学是最美丽的花朵。为数学是
3、最美丽的花朵。哈密尔顿把该游戏以哈密尔顿把该游戏以25英镑的价格买给了英镑的价格买给了J.JacquesandSons公司公司(该公司如今以制造国际象棋设备而著名该公司如今以制造国际象棋设备而著名),1859年获得专年获得专利权。但商业运作失败了。利权。但商业运作失败了。该游戏促使人们思考点线连接的图的结构特征。这就是图论该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题。历史上著名的哈密尔顿问题。2、哈密尔顿图与哈密尔顿路、哈密尔顿图与哈密尔顿路定义定义1如果经过图如果经过图G的每个顶点恰好一次后能够回到出发点,的每个顶点恰好一次后能够回到出发点,称这样的图为哈密尔
4、顿图,简称称这样的图为哈密尔顿图,简称H图。所经过的闭途径是图。所经过的闭途径是G的一的一个生成圈,称为个生成圈,称为G的哈密尔顿圈。的哈密尔顿圈。4第4页,共32页,编辑于2022年,星期五例例1、正十二面体是、正十二面体是H图。图。十二面体5第5页,共32页,编辑于2022年,星期五例例2下图下图G是非是非H图。图。证明:因为在证明:因为在G中,边中,边uv是割边,所以它不在是割边,所以它不在G的任意圈的任意圈上,于是上,于是u与与v不能在不能在G的同一个圈上。故的同一个圈上。故G不存在包括所有不存在包括所有顶点的圈,即顶点的圈,即G是非是非H图。图。图图Guv定义定义2如果存在经过如果存
5、在经过G的每个顶点恰好一次的路,称该路的每个顶点恰好一次的路,称该路为为G的哈密尔顿路,简称的哈密尔顿路,简称H路。路。uv图图G6第6页,共32页,编辑于2022年,星期五(二二)、性质与判定、性质与判定1、性质、性质定理定理1(必要条件必要条件)若若G为为H图,则对图,则对V(G)的任一非空顶点子集的任一非空顶点子集S,有:,有:证明:证明:G是是H图,设图,设C是是G的的H圈。则对圈。则对V(G)的任意非空子集的任意非空子集S,容易知道容易知道:所以,有:所以,有:7第7页,共32页,编辑于2022年,星期五注:不等式为注:不等式为G是是H图的必要条件,即不等式不满足时,图的必要条件,即
6、不等式不满足时,可断定对应图是非可断定对应图是非H图。图。例例3求证下图是非求证下图是非H图。图。证明:取证明:取S=2,7,6,则有:则有:543218769所以由定理所以由定理1知,知,G为非为非H图。图。G8第8页,共32页,编辑于2022年,星期五注意:满足定理注意:满足定理1不等式的图不一定是不等式的图不一定是H图。图。例如:著名的彼德森图是非例如:著名的彼德森图是非H图,但它满足定理图,但它满足定理1的不等的不等式。式。Peterson图图彼得森彼得森(1839-1910),丹麦哥本哈根大学数学教授。家境贫寒,丹麦哥本哈根大学数学教授。家境贫寒,因此而辍过学。但因此而辍过学。但19
7、岁就出版了关于对数的专著。他作过中岁就出版了关于对数的专著。他作过中学教师,学教师,32岁获哥本哈根大学数学博士学位,然后一直在岁获哥本哈根大学数学博士学位,然后一直在该大学作数学教授。该大学作数学教授。9第9页,共32页,编辑于2022年,星期五彼得森是一位出色的名教师。他讲课遇到推理困难时,总是说:彼得森是一位出色的名教师。他讲课遇到推理困难时,总是说:“这是显而易见的这是显而易见的”,并让学生自己查阅他的著作。同时,他是,并让学生自己查阅他的著作。同时,他是一位有经验的作家,论述问题很形象,讲究形式的优雅。一位有经验的作家,论述问题很形象,讲究形式的优雅。1891年,彼得森发表了一篇奠定
8、他图论历史地位的长达年,彼得森发表了一篇奠定他图论历史地位的长达28页页的论文。这篇文章被公认是第一篇包含图论基本结论的文章。的论文。这篇文章被公认是第一篇包含图论基本结论的文章。同时也是第一次在文章中使用同时也是第一次在文章中使用“图图”术语。术语。1898年,彼得森又发表了一篇只有年,彼得森又发表了一篇只有3页的论文,在这篇文章中,页的论文,在这篇文章中,为举反例构造了著名的彼得森图。为举反例构造了著名的彼得森图。10第10页,共32页,编辑于2022年,星期五2、判定、判定图的图的H性判定是性判定是NP-困难问题。到目前为止,有关的定理困难问题。到目前为止,有关的定理有有300多个,但没
9、有一个是理想的。拓展多个,但没有一个是理想的。拓展H图的实用特征仍图的实用特征仍然被图论领域认为是重大而没有解决的问题。然被图论领域认为是重大而没有解决的问题。图的哈密尔顿问题和四色问题被谓为挑战图论领域图的哈密尔顿问题和四色问题被谓为挑战图论领域150年智力极限的总和。三位数学年智力极限的总和。三位数学“诺奖诺奖”获得者获得者Erds、Whitney、Lovsz以及以及Dirac、Ore等在哈密尔顿问题上有等在哈密尔顿问题上有过杰出贡献。过杰出贡献。下面,介绍几个著名的定理。下面,介绍几个著名的定理。11第11页,共32页,编辑于2022年,星期五定理定理2(充分条件充分条件)对于对于n33
10、的单图的单图G G,如果,如果G G中有:中有:那么那么G是是H图。图。证明证明:若不然,设若不然,设G是一个满足定理条件的极大非是一个满足定理条件的极大非H简单图。简单图。显然显然G不能是完全图,否则,不能是完全图,否则,G是是H图。图。于是,可以在于是,可以在G中任意取两个不相邻顶点中任意取两个不相邻顶点u与与v。考虑图。考虑图G+uv,由,由G的极大性,的极大性,G+uv是是H图。且图。且G+uv的每一个的每一个H圈必然包圈必然包含边含边uv。12第12页,共32页,编辑于2022年,星期五所以,在所以,在G中存在起点为中存在起点为u而终点为而终点为v的的H路路P。不失一般性,设起点为不
11、失一般性,设起点为u而终点为而终点为v的的H路路P为:为:vnvn-1vi+1viv3v2v1P令:令:13第13页,共32页,编辑于2022年,星期五对于对于S与与T,显然,显然,另一方面:可以证明:另一方面:可以证明:所以:所以:否则,设否则,设那么,由那么,由由由vnvn-1vi+1viv3v2v1P这样在这样在G中有中有H圈,与假设矛盾!圈,与假设矛盾!14第14页,共32页,编辑于2022年,星期五于是:于是:这与已知这与已知矛盾!矛盾!注:该定理是数学家注:该定理是数学家Dirac在在1952年得到的。该定理被认为年得到的。该定理被认为是是H问题的划时代奠基性成果。问题的划时代奠基
12、性成果。Dirac曾经是丹麦奥尔胡斯大学知名教授,杰出的数学研曾经是丹麦奥尔胡斯大学知名教授,杰出的数学研究者。其父亲究者。其父亲(继父继父)是在量子力学中做出卓越贡献的物理学家狄是在量子力学中做出卓越贡献的物理学家狄拉克,拉克,1933年获诺贝尔物理学奖。年获诺贝尔物理学奖。Dirac发表关于发表关于H问题论文问题论文39篇。篇。他他1952年的定理将永载史册!年的定理将永载史册!15第15页,共32页,编辑于2022年,星期五1960年,美国耶鲁大学数学家年,美国耶鲁大学数学家奥勒(奥勒(Ore)院士考察不相邻院士考察不相邻两点度和情况,弱化了两点度和情况,弱化了Dirac条件条件,得到一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈密尔顿 幻灯片
限制150内