图论哈密尔顿图精品文稿.ppt

图论课件哈密尔顿图1第1页，本讲稿共32页本次课主要内容(一)、哈密尔顿图的概念(二)、性质与判定哈密尔顿图2第2页，本讲稿共32页1、背景、背景(一一)、哈密尔顿图的概念、哈密尔顿图的概念1857年，年，哈密尔顿发明了一个游戏哈密尔顿发明了一个游戏(IcosianGame).它是由一个木制的正十二面体构成，在它的每个棱角它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。游戏目的是处标有当时很有名的城市。游戏目的是“环球旅行环球旅行”。为了容易记住被旅游过的城市为了容易记住被旅游过的城市，在每个棱角上放上一，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上个钉子，再用一根线绕在那些旅游过的城市上(钉子钉子),由此可以获得旅程的直观表示。由此可以获得旅程的直观表示。十二面体3第3页，本讲稿共32页哈密尔顿哈密尔顿(1805-1865),爱尔兰数学家。个人生活很爱尔兰数学家。个人生活很不幸，但兴趣广泛：诗歌、光学、天文学和数学无所不幸，但兴趣广泛：诗歌、光学、天文学和数学无所不能。他的主要贡献是在代数领域，发现了四元数不能。他的主要贡献是在代数领域，发现了四元数(第第一个非交换代数一个非交换代数)，他认为数学是最美丽的花朵。，他认为数学是最美丽的花朵。哈密尔顿把该游戏以哈密尔顿把该游戏以25英镑的价格买给了英镑的价格买给了J.JacquesandSons公司公司(该公司如今以制造国际象棋设备而著名该公司如今以制造国际象棋设备而著名)，1859年获得专利权。但商业运作失败了。年获得专利权。但商业运作失败了。该游戏促使人们思考点线连接的图的结构特征。这该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题。就是图论历史上著名的哈密尔顿问题。2、哈密尔顿图与哈密尔顿路、哈密尔顿图与哈密尔顿路定义定义1如果经过图如果经过图G的每个顶点恰好一次后能够回到的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称出发点，称这样的图为哈密尔顿图，简称H图。所经过图。所经过的闭途径是的闭途径是G的一个生成圈，称为的一个生成圈，称为G的哈密尔顿圈。的哈密尔顿圈。4第4页，本讲稿共32页例例1、正十二面体是、正十二面体是H图。图。十二面体5第5页，本讲稿共32页例例2下图下图G是非是非H图。图。证明：因为在证明：因为在G中，边中，边uv是割边，所以它不在是割边，所以它不在G的任的任意圈上，于是意圈上，于是u与与v不能在不能在G的同一个圈上。故的同一个圈上。故G不存在不存在包括所有顶点的圈，即包括所有顶点的圈，即G是非是非H图。图。图Guv定义定义2如果存在经过如果存在经过G的每个顶点恰好一次的路，称的每个顶点恰好一次的路，称该路为该路为G的哈密尔顿路，简称的哈密尔顿路，简称H路。路。uv图G6第6页，本讲稿共32页(二二)、性质与判定、性质与判定1、性质、性质定理定理1(必要条件必要条件)若若G为为H图，则对图，则对V(G)的任一非空的任一非空顶点子集顶点子集S，有：，有：证明：证明：G是是H图，设图，设C是是G的的H圈。则对圈。则对V(G)的任意的任意非空子集非空子集S,容易知道容易知道:所以，有：所以，有：7第7页，本讲稿共32页注：不等式为注：不等式为G是是H图的必要条件，即不等式不满足图的必要条件，即不等式不满足时，可断定对应图是非时，可断定对应图是非H图。图。例例3求证下图是非求证下图是非H图。图。证明：取证明：取S=2,7,6,则有：则有：543218769所以由定理所以由定理1知，知，G为非为非H图。图。G8第8页，本讲稿共32页注意：满足定理注意：满足定理1不等式的图不一定是不等式的图不一定是H图。图。例如：著名的彼德森图是非例如：著名的彼德森图是非H图，但它满足定理图，但它满足定理1的的不等式。不等式。Peterson图彼得森彼得森(1839-1910)，丹麦哥本哈根大学数学教授。，丹麦哥本哈根大学数学教授。家境贫寒，因此而辍过学。但家境贫寒，因此而辍过学。但19岁就出版了关于对数的岁就出版了关于对数的专著。他作过中学教师，专著。他作过中学教师，32岁获哥本哈根大学数学博士岁获哥本哈根大学数学博士学位，然后一直在该大学作数学教授。学位，然后一直在该大学作数学教授。9第9页，本讲稿共32页彼得森是一位出色的名教师。他讲课遇到推理困难时，彼得森是一位出色的名教师。他讲课遇到推理困难时，总是说：总是说：“这是显而易见的这是显而易见的”，并让学生自己查阅他的著，并让学生自己查阅他的著作。同时，他是一位有经验的作家，论述问题很形象，讲作。同时，他是一位有经验的作家，论述问题很形象，讲究形式的优雅。究形式的优雅。1891年，彼得森发表了一篇奠定他图论历史地位的长达年，彼得森发表了一篇奠定他图论历史地位的长达28页的论文。这篇文章被公认是第一篇包含图论基本结论页的论文。这篇文章被公认是第一篇包含图论基本结论的文章。同时也是第一次在文章中使用的文章。同时也是第一次在文章中使用“图图”术语。术语。1898年，彼得森又发表了一篇只有年，彼得森又发表了一篇只有3页的论文，在这篇文页的论文，在这篇文章中，为举反例构造了著名的彼得森图。章中，为举反例构造了著名的彼得森图。10第10页，本讲稿共32页2、判定、判定图的图的H性判定是性判定是NP-困难问题。到目前为止，有关的困难问题。到目前为止，有关的定理有定理有300多个，但没有一个是理想的。拓展多个，但没有一个是理想的。拓展H图的实图的实用特征仍然被图论领域认为是重大而没有解决的问题。用特征仍然被图论领域认为是重大而没有解决的问题。图的哈密尔顿问题和四色问题被谓为挑战图论领域图的哈密尔顿问题和四色问题被谓为挑战图论领域150年智力极限的总和。三位数学年智力极限的总和。三位数学“诺奖诺奖”获得者获得者Erds、Whitney、Lovsz以及以及Dirac、Ore等在哈密等在哈密尔顿问题上有过杰出贡献。尔顿问题上有过杰出贡献。下面，介绍几个著名的定理。下面，介绍几个著名的定理。11第11页，本讲稿共32页定理定理2(充分条件充分条件)对于对于n33的单图的单图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页所以，在所以，在G中存在起点为中存在起点为u而终点为而终点为v的的H路路P。不失一般性，设起点为不失一般性，设起点为u而终点为而终点为v的的H路路P为：为：vnvn-1vi+1viv3v2v1P令：令：13第13页，本讲稿共32页对于对于S与与T,显然，显然，另一方面：可以证明：另一方面：可以证明：所以：所以：否则，设否则，设那么，由那么，由由由vnvn-1vi+1viv3v2v1P这样在这样在G中有中有H圈，与假设矛盾！圈，与假设矛盾！14第14页，本讲稿共32页于是：于是：这与已知这与已知矛盾！矛盾！注：该定理是数学家注：该定理是数学家Dirac在在1952年得到的。该定理被年得到的。该定理被认为是认为是H问题的划时代奠基性成果。问题的划时代奠基性成果。Dirac曾经是丹麦奥尔胡斯大学知名教授，杰出的数学曾经是丹麦奥尔胡斯大学知名教授，杰出的数学研究者。其父亲研究者。其父亲(继父继父)是在量子力学中做出卓越贡献的物是在量子力学中做出卓越贡献的物理学家狄拉克，理学家狄拉克，1933年获诺贝尔物理学奖。年获诺贝尔物理学奖。Dirac发表关发表关于于H问题论文问题论文39篇。他篇。他1952年的定理将永载史册！年的定理将永载史册！15第15页，本讲稿共32页1960年，美国耶鲁大学数学家年，美国耶鲁大学数学家奥勒（奥勒（Ore）院士考察不院士考察不相邻两点度和情况，弱化了相邻两点度和情况，弱化了Dirac条件条件，得到一个光耀千，得到一个光耀千秋的结果。秋的结果。Ore发表关于发表关于H问题论文问题论文59篇。篇。定理定理3(充分条件充分条件)对于对于n33的单图的单图G G，如果，如果G G中的任意中的任意两个不相邻顶点两个不相邻顶点u u与与v v，有：，有：那么，那么，G是是H图。图。注注:(1)该定理证明和定理该定理证明和定理2可以完全一致！可以完全一致！(2)该定理的条件是紧的。例如：设该定理的条件是紧的。例如：设G是由是由Kk+1的一个顶的一个顶点和另一个点和另一个Kk+1的一个顶点重合得到的图，那么对于的一个顶点重合得到的图，那么对于G16第16页，本讲稿共32页的任意两个不相邻顶点的任意两个不相邻顶点u与与v，有：，有：但但G是非是非H图。图。G=K1+2(K3)1976年，牛津大学的图论大师年，牛津大学的图论大师Bondy(帮迪帮迪)等在等在Ore定理基础上，得到图定理基础上，得到图G和它的闭包间的同哈密尔顿性。和它的闭包间的同哈密尔顿性。注：帮迪的书注：帮迪的书图论及其应用图论及其应用是一本经典必读教是一本经典必读教材。有中译本和习题解答。吴望祖译材。有中译本和习题解答。吴望祖译。17第17页，本讲稿共32页引理引理1对于单图对于单图G，如果，如果G中有两个不相邻顶点中有两个不相邻顶点u与与v，满足：满足：那么那么G是是H图当且仅当图当且仅当G+uv是是H图。图。证明：证明：“必要性必要性”显然。显然。“充分性充分性”若不然，设若不然，设G是非是非H图，那么图，那么G+uv的每个的每个H圈必然经过圈必然经过边边uv,于是于是G含有一条哈密尔顿含有一条哈密尔顿(u,v)路。路。vnvn-1vi+1viv3v2v1P18第18页，本讲稿共32页令：令：对于对于S与与T,显然，显然，另一方面：可以证明：另一方面：可以证明：所以：所以：否则，设否则，设那么，由那么，由由由19第19页，本讲稿共32页vnvn-1vi+1viv3v2v1P这样在这样在G中有中有H圈，与假设矛盾！圈，与假设矛盾！于是：于是：这与已知矛盾！这与已知矛盾！定义定义3在在n阶单图中，若对阶单图中，若对d(u)+d(v)n n 的的任意一对任意一对顶点顶点u与与v，均有，均有uadjv,则称则称G是闭图。是闭图。引理引理2若若G1和和G2是同一个点集是同一个点集V的两个闭图，则的两个闭图，则G=G1G2是是闭图闭图。20第20页，本讲稿共32页证明：任取证明：任取wV，有：，有：所以，对所以，对可得：可得：因因G1与与G2都是闭图，所以都是闭图，所以u与与v在在G1与与G2中都邻接，所中都邻接，所以，在以，在G中也邻接。故中也邻接。故G是闭图。是闭图。注：注：G1与与G2都是闭图，它们的并不一定是闭图。都是闭图，它们的并不一定是闭图。21第21页，本讲稿共32页例如：例如：定义定义4称称是图是图G的闭包，如果它是包含的闭包，如果它是包含G的极小闭图。的极小闭图。G1G2注：如果注：如果G本身是闭图，则其闭包是它本身；如果本身是闭图，则其闭包是它本身；如果G不不是闭图，则由定义可以通过在度和大于等于是闭图，则由定义可以通过在度和大于等于n的不相邻顶的不相邻顶点对间加边来构造点对间加边来构造G的闭图。例如：的闭图。例如：G22第22页，本讲稿共32页引理引理3图图G的闭包是唯一的。的闭包是唯一的。证明：设证明：设和和是图是图G的两个闭包，则：的两个闭包，则：所以，有：所以，有：又由引理又由引理2知，知，是闭图，且是闭图，且有：有：同理：同理：所以，所以，23第23页，本讲稿共32页定理定理4(帮迪帮迪闭包定理闭包定理)图图G是是H图当且仅当它的闭图当且仅当它的闭包是包是H图。图。证明：证明：“必要性必要性”显然。显然。“充分性充分性”：假设：假设G的闭包是的闭包是H图，我们证明图，我们证明G是是H图。图。假设假设G的闭包和的闭包和G相同，结论显然。相同，结论显然。若不然，设若不然，设ei(1ik)ik)是为构造是为构造G G的闭包而添加的所有边，的闭包而添加的所有边，由引理由引理1 1，G G是是H H图当且仅当图当且仅当G+eG+e1 1是是H H图，图，G+e1是是H图当且图当且仅当仅当G+e1+e2是是H图图,反复应用引理反复应用引理1，可以得到定理结，可以得到定理结论。论。由于完全图一定是由于完全图一定是H图，所以由闭包定理有：图，所以由闭包定理有：推论推论1：设：设G是是n33的单图，若的单图，若G G的闭包是完全图，则的闭包是完全图，则G G是是H H图。图。24第24页，本讲稿共32页由闭包定理也可以推出由闭包定理也可以推出Dirac和和Ore定理：定理：推论推论1：设：设G是是n33的单图。的单图。(1)若若(G)n/2,(G)n/2,则则G G是是H H图图(Dirac(Dirac定理定理););(2)若若对于对于G G中任意不相邻顶点中任意不相邻顶点u u与与v v，都有，都有d(u)+d(v)n,d(u)+d(v)n,则则G G是是H H图图.(Ore.(Ore定理定理)在闭包定理的基础上，在闭包定理的基础上，Chvtal和帮迪进一步得到图的和帮迪进一步得到图的H性的度序列判定法。性的度序列判定法。定理定理5(Chvtal度序列判定法度序列判定法)设简单图设简单图G的度序列是的度序列是(d1,d2,dn),这里，这里，d1dd2 2ddn n,并且并且n3.n3.若对任意的若对任意的mn/2,mm,m,或者或者d dn-m n-m n-m,n-m,则则G G是是H H图。图。证明方法：证证明方法：证G的闭包是完全图。的闭包是完全图。25第25页，本讲稿共32页证明：如果证明：如果G的闭包是的闭包是Kn，则，则G是是H图。图。否则，设否则，设u与与v是是G的闭包中不相邻接的且度和最大的两的闭包中不相邻接的且度和最大的两点，又假设：点，又假设：由于由于是是闭图闭图，u与与v是其中不是其中不邻邻接接顶顶点，所以：点，所以：于是，若取于是，若取，则，则对于这个对于这个m,由于：由于：所以在所以在G的闭包中至少有的闭包中至少有m个点与个点与v不邻接。不邻接。26第26页，本讲稿共32页由由u与与v的取法知：与的取法知：与v不邻接的不邻接的m个点中，个点中，u的度数最的度数最大。这就意味着：大。这就意味着：G中至少有中至少有m个点的度数不大于个点的度数不大于m,即：即：另一方面，由另一方面，由m的选取，的选取，G的闭包中有的闭包中有n-1-m个点与个点与u不不相邻接。而这些点中，相邻接。而这些点中，v的度最大。这意味着：在的度最大。这意味着：在G的闭的闭包中有包中有n-1-m个与个与u不邻接的点的度数小于等于不邻接的点的度数小于等于v的度数。的度数。但是，由：但是，由：以及以及u的度数不超过的度数不超过v的度数假设，的度数假设，G的闭包中至少有的闭包中至少有n-m个点的度不超过个点的度不超过n-m,从而在从而在G中至少有中至少有n-m个点的度数个点的度数严格小于严格小于n-m,即：即：27第27页，本讲稿共32页例例4求证下图是求证下图是H图。图。证明：在证明：在G中有：中有：354218769G因因n=9,所以，所以，m=1,2,3,428第28页，本讲稿共32页所以，由度序列判定法，所以，由度序列判定法，G是是H图。图。注注：哈密尔顿图研究简介哈密尔顿图研究简介哈密尔顿问题的研究一直是图论热点。研究历史大哈密尔顿问题的研究一直是图论热点。研究历史大致情况如下：致情况如下：(1)1952年年Dirac定理是研究的奠基性结果；定理是研究的奠基性结果；(2)1962年年Ore定理是定理是Dirac定理的重要推进；定理的重要推进；(3)1976年帮迪的闭包定理是年帮迪的闭包定理是Ore定理的重要推进；定理的重要推进；(4)1985年时任剑桥大学兼伦敦大学教授的年时任剑桥大学兼伦敦大学教授的Nicos在弱在弱化化Ore定理条件基础上推进了定理条件基础上推进了Ore定理；定理；(5)1996年年GSU计算机系五个特聘教授之一的计算机系五个特聘教授之一的Chen和和SCI杂志杂志图论杂志图论杂志编委编委Egawa及及SCI杂志杂志图论与组合图论与组合主编主编Saito等再进一步推进等再进一步推进Ore定理。定理。29第29页，本讲稿共32页(6)2007年年,赖虹建教授统一上面全部结果赖虹建教授统一上面全部结果(见美国见美国Appl.Math.Lett.),似已是似已是珠峰之极.值得一提的是，福州大学的值得一提的是，福州大学的范更华教授对范更华教授对H问题的研究问题的研究也取得重要成就，他得出也取得重要成就，他得出“范定理范定理”：范定理：若图中每对距离为范定理：若图中每对距离为2的点中有一点的度数至少是的点中有一点的度数至少是图的点数的一半，则该图存在哈密顿圈。图的点数的一半，则该图存在哈密顿圈。该成果获得中国该成果获得中国2005年度国家自然科学二等奖。年度国家自然科学二等奖。30第30页，本讲稿共32页 作业 P97-99 习题4：10,1231第31页，本讲稿共32页Thank You!32第32页，本讲稿共32页