图论课件--哈密尔顿

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

1、图论及其应用应用数学学院1本次课主要内容(一)、哈密尔顿图的概念(二)、性质与判定哈密尔顿图21、背景(一)、哈密尔顿图的概念1857年，哈密尔顿发明了一个游戏(IcosianGame).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示。十二面体3哈密尔顿(1805---1865),爱尔兰数学家。个人生活很不幸，但兴趣广泛：诗歌、光学、天文学和数学无所不能。他的主要贡献是在代数领域，发现了四元数(第一个非交换

2、代数)，他认为数学是最美丽的花朵。哈密尔顿把该游戏以25英镑的价格买给了J.JacquesandSons公司(该公司如今以制造国际象棋设备而著名)，1859年获得专利权。但商业运作失败了。该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题。2、哈密尔顿图与哈密尔顿路定义1如果经过图G的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。所经过的闭途径是G的一个生成圈，称为G的哈密尔顿圈。4例1、正十二面体是H图。十二面体5例2下图G是非H图。证明：因为在G中，边uv是割边，所以它不在G的任意圈上，于是u与v不能在G的同一个圈上。故G

3、不存在包括所有顶点的圈，即G是非H图。图Guv定义2如果存在经过G的每个顶点恰好一次的路，称该路为G的哈密尔顿路，简称H路。uv图G6(二)、性质与判定1、性质定理1(必要条件)若G为H图，则对V(G)的任一非空顶点子集S，有：证明：G是H图，设C是G的H圈。则对V(G)的任意非空子集S,容易知道:所以，有：7注：不等式为G是H图的必要条件，即不等式不满足时，可断定对应图是非H图。例3求证下图是非H图。证明：取S=｛2,7,6｝,则有：543218769所以由定理1知，G为非H图。G8注意：满足定理1不等式的图不一定是H图。例如：著名的彼德森图是非H图，但它满足定理1的不等

4、式。Peterson图彼得森(1839----1910)，丹麦哥本哈根大学数学教授。家境贫寒，因此而辍过学。但19岁就出版了关于对数的专著。他作过中学教师，32岁获哥本哈根大学数学博士学位，然后一直在该大学作数学教授。9彼得森是一位出色的名教师。他讲课遇到推理困难时，总是说：“这是显而易见的”，并让学生自己查阅他的著作。同时，他是一位有经验的作家，论述问题很形象，讲究形式的优雅。1891年，彼得森发表了一篇奠定他图论历史地位的长达28页的论文。这篇文章被公认是第一篇包含图论基本结论的文章。同时也是第一次在文章中使用“图”术语。1898年，彼得森又发表了一篇只有3页的论文，在

5、这篇文章中，为举反例构造了著名的彼得森图。102、判定图的H性判定是NP-困难问题。到目前为止，有关的定理有300多个，但没有一个是理想的。拓展H图的实用特征仍然被图论领域认为是重大而没有解决的问题。图的哈密尔顿问题和四色问题被谓为挑战图论领域150年智力极限的总和。三位数学“诺奖”获得者ErdÖs、Whitney、Lovász以及Dirac、Ore等在哈密尔顿问题上有过杰出贡献。下面，介绍几个著名的定理。11定理2(充分条件)对于n≧3的单图G，如果G中有：那么G是H图。证明:若不然，设G是一个满足定理条件的极大非H简单图。显然G不能是完全图，否则，G是H图。于是，可以在

6、G中任意取两个不相邻顶点u与v。考虑图G+uv，由G的极大性，G+uv是H图。且G+uv的每一个H圈必然包含边uv。12所以，在G中存在起点为u而终点为v的H路P。不失一般性，设起点为u而终点为v的H路P为：vnvn-1vi+1viv3v2v1P令：13对于S与T,显然，另一方面：可以证明：所以：否则，设那么，由由vnvn-1vi+1viv3v2v1P这样在G中有H圈，与假设矛盾！14于是：这与已知矛盾！注：该定理是数学家Dirac在1952年得到的。该定理被认为是H问题的划时代奠基性成果。Dirac曾经是丹麦奥尔胡斯大学知名教授，杰出的数学研究者。其父亲(继父)是在量子力

7、学中做出卓越贡献的物理学家狄拉克，1933年获诺贝尔物理学奖。Dirac发表关于H问题论文39篇。他1952年的定理将永载史册！151960年，美国耶鲁大学数学家奥勒（Ore）院士考察不相邻两点度和情况，弱化了Dirac条件，得到一个光耀千秋的结果。Ore发表关于H问题论文59篇。定理3(充分条件)对于n≧3的单图G，如果G中的任意两个不相邻顶点u与v，有：那么，G是H图。注:(1)该定理证明和定理2可以完全一致！(2)该定理的条件是紧的。例如：设G是由Kk+1的一个顶点和另一个Kk+1的一个顶点重合得到的图，那么