《图论课件超哈密尔顿图问题.ppt》由会员分享，可在线阅读，更多相关《图论课件超哈密尔顿图问题.ppt（28页珍藏版）》请在三一办公上搜索。
1、1,图论及其应用,应用数学学院,2,本次课主要内容,(二)、E图和H图的关系,超哈密尔顿图问题,(一)、超H图与超H迹,3,定义1 若图G是非H图，但对于G中任意点v,都有G-v是H图，则称G是超H图。,(一)、超H图与超H迹,定理1 彼得森图是超H图。,证明：(1)证明彼得森图是非H图。,4,若不然，设C是G的H圈。,又对于边28，23来说，在前面情况下，必有一条在C中。分两种情形讨论。,对于边12,17,15来说，必然有两条边在C中。不失一般性，假定17,12在C中，那么，56，54也必然在C中。,5,但这样得到圈：17(10)821。所以该情形不能存在。,情形1：假如28在C中，则39，
2、34在C中,从而7(10),8(10)在C中,6,但这样得到圈：123971。所以该情形也不能存在。,情形2：假如23在C中，则86，8(10)在C中,从而39,79在C中.,上面推理说明，G中不存在H圈，即彼得森图是非H图。,7,由对称性，只需考虑下面两种情形:(a)G-1,（b）G-6,(2)证明对任意点v，G-v是H图。,(a)G-1中有H圈：54328(10)7965,(b)G-6中有H圈：54397(10)8215,由(1)与(2)，G是超H图。,8,定义2 若G中没有H路，但是对G中任意点v，G-v存在H路，则称G是超可迹的。,数学家加莱曾经猜想：不存在超可迹的图。但该猜想被Hor
3、ton和Thomassen以构图的方式否定了。,定理2 Thomassen图是超可迹图。,9,定理证明分为两部分:(1)证明G中不存在H路；(2)证明对G中任意点v，有G-v存在H路。,(1)证明G中不存在H路。,如图所示，将G用虚线分成对称的4部分：,。,假设G有H路P,设该路的起点为，终点为。,不失一般性，设 a。,断言1：a 中不存在以a,c,d三点中任意两点为端点的H路。,若不然，将推出彼得森图是H图。,10,断言2：a，b 中不存在以a 为端点的H路。,若不然，设Q是一条以a为起点的 a，b 中的H路。那么，从a出发，沿着该路行走有两种可能:(1)遍历了中所有点之后，从c或d进入，但
4、这形成了 a 中的以a,c或a,d为端点的H路，与断言1矛盾！,(2)没有遍历完 a 中的顶点，假若从c进入，那么，必须遍历完 b 的所有顶点后，才能从e进入。但这也会与断言1产生矛盾。,11,情形1：=a,所以，情形1不能成立！,由前面假设：a。,我们沿着P作如下的行进：,(1)假设是由a进入，要能够走完P,必须遍历 的所有顶点后由b进入，但这与断言2矛盾！,(2)假设是由a进入，要能够走完P,必须遍历 的所有顶点后由b进入，但这也与断言2矛盾！,12,情形2：a,所以，情形2也不能成立！,我们沿着P作如下的行进：,(1)假设是由遍历了 b所有顶点从a进入，这与断言2矛盾！同样，假设是由遍历
5、了 a所有顶点从b进入，这也与断言2矛盾！,(2)假设是由开始，没有遍历 a,b而从a或b进入，那么，要走完P,都必须遍历完的所有顶点后，才能重新进入。但这要与断言2矛盾,13,综合上面的论述：得G中没有H路。,(2)证明对G中任意点v，有G-v存在H路。,由对称性：我们取b和中顶点逐一分析即可。例如：,综上所述：得Thomassen图是超可迹图。,14,关于H图的一些猜想,1、加莱猜想：不存在超可迹的图。,加莱猜想是错误的。Thomassen图否定了加莱猜想。,加莱(1912-1992)匈牙利数学家。他和Erdos,托兰是当时匈牙利国家数学竞赛获胜者，后来成为一生的朋友。,加莱深受哥尼的影响
6、而对图论产生极大兴趣，以至于他对图论基础理论做出了重大贡献，推动了图论与组合数学的迅速发展。同时，他也是最早认识所谓的“极小-极大定理”重要性的数学家之一。,加莱为人谦虚低调，很少在公开场合露面。常常在赞扬别人工作时低估自己的成绩。不喜欢发表自己研究成果。,15,2、泰特猜想：任何3连通3正则可平面图是H图。,泰特猜想也是错误的。托特1946年构图否定了泰特猜想。,Lederberg等构造了最小的3连通3正则图非H图，有38个点。,16,如果泰特猜想正确，4色定理可得到证明。,托特(1917-2002)英国著名数学家。1935年，入剑桥三一学院学习化学，并攻读了化学研究生，撰写了2篇化学论文。
7、但是，他的兴趣是数学。在剑桥，他结识了3位数学专业的本科学生并成为终身朋友，合作发表数学论文。二战后，托特回到剑桥攻读数学研究生。研究生期间，发表了关于图的因子分解论文。在他的数学博士论文中，复兴了拟阵理论(惠特尼引入的).1948年博士毕业后，受20世纪伟大的几何学家Coxeter邀请前往多伦多大学任教，成为组合数学杰出学者。5年后到滑铁卢大学工作直到1984年退休。,托特是20世纪伟大的数学家之一，在近代数学史上占有一定的地位。主要功绩是提出并证明了图的完美匹配定理。,17,托特还喜欢写诗，在1969年写了一首反映图论的诗：,哥尼斯堡的一些市民，,漫步在河畔。,在普雷格尔河旁，,有七座桥相
8、伴。,“Euler,我们一起散步吧！”,那些市民在召唤。,“我们在这七座桥上漫步，,经过每座桥仅一次。”,“你们做不到”，Euler大声吼道。,“结果就是这样，,岛屿作为顶点，,四个点有奇数度”。,从哥尼斯堡到哥尼的书，,图论的传说正是如此，,而且越来越精彩，,绽放在密歇根和耶鲁,18,该猜想错误。Meredith构图对猜想进行了否定。,3、纳什威廉斯猜想：每个4连通4正则图是H图。,Meredith图是由彼得森图的每个顶点嵌入一个K3,4作成。,19,该猜想错误。Coxeter构图对猜想进行了否定。,4、托特猜想：每个3连通3正则偶图是H图。,20,该猜想是正确的，已经得到证明。,5、普鲁默
9、猜想：每个2连通图的平方是H图。,定义：图G的平方G2是这样的图:,值得一提的是：在H问题研究中，H图中H圈的计数问题也是一个研究方向。,21,定理：每个3正则H图至少有3个生成圈。,我院张先迪、李正良教授曾经也研究过H图中H圈的计数问题。90年在系统科学与数学学报上发表文章：“有限循环群上Cayley有向图的H回路”，得到了该类图的H圈的计数公式。,(二)、E图和H图的关系,从表面上看，E图与H图间没有联系。因为我们可以不费力地找到:(1)E图但非H图；(2)E图且H图；(3)H图但非E图;(4)非E图且非H图.,22,定义3 设G是图，G的线图L(G)定义为：,特别地，定义G的n次迭线图L
10、n(G)为：,1、线图概念,23,(1)线图L(G)顶点数等于G的边数；若e=u v是G的边，则e作为L(G)的顶点度数为：d(e)=d(u)+d(v)-2.,2、线图的性质,(2)若G=(n,m),则线图L(G)边数为：,证明：由线图的定义，L(G)有m个顶点。对于G中任一顶点v，关联于该顶点的d(v)条边将产生L(G)中 条边。所以L(G)中的总边数为：,24,(3)一个图同构于它的线图，当且仅当它是圈。,(4)若图G和G1有同构的线图，则除了一个是K3而另一个是K1,3外，G和G1同构。(证明比较复杂),3、从线图的角度考察E图与H图的关系,定义4 称Sn是图G的n次细分图，是指将G的每条边中都插入n个2度顶点。,又记：,25,定理3(1)若G是E图，则L(G)既是E图又是H图。(2)若G是H图，则L(G)是H图。,注：该定理逆不成立。,定理4 一个图G 是E图的充要条件是L3(G)为H图,26,定理5（Chartarand）若G 是n个点的非平凡连通图，且不是一条路，则对所有mn-3，Lm(G)是H图。,27,作业,请总结本章内容,28,Thank You!,
