图论课件-哈密尔顿

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