资源描述：
《图论课件超哈密尔顿图问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1图论及其应用应用数学学院2本次课主要内容(二)、E图和H图的关系超哈密尔顿图问题(一)、超H图与超H迹3定义1若图G是非H图，但对于G中任意点v,都有G-v是H图，则称G是超H图。(一)、超H图与超H迹定理1彼得森图是超H图。1765432彼得森图1098证明：(1)证明彼得森图是非H图。4若不然，设C是G的H圈。1654327彼得森图1098又对于边28，23来说，在前面情况下，必有一条在C中。分两种情形讨论。对于边12,17,15来说，必然有两条边在C中。不失一般性，假定17,12在C中，那么，56，54也必然在C中。51654327彼得森图1098但这样得到圈：17
2、(10)821。所以该情形不能存在。情形1：假如28在C中，则39，34在C中,从而7(10),8(10)在C中6但这样得到圈：123971。所以该情形也不能存在。情形2：假如23在C中，则86，8(10)在C中,从而39,79在C中.1654327彼得森图10981654327彼得森图1098上面推理说明，G中不存在H圈，即彼得森图是非H图。7由对称性，只需考虑下面两种情形:(a)G-1,（b）G-6(2)证明对任意点v，G-v是H图。(a)G-1中有H圈：54328(10)796536542107G-198(b)G-6中有H圈：54397(10)8215154327G-
3、61098由(1)与(2)，G是超H图。8定义2若G中没有H路，但是对G中任意点v，G-v存在H路，则称G是超可迹的。数学家加莱曾经猜想：不存在超可迹的图。但该猜想被Horton和Thomassen以构图的方式否定了。定理2Thomassen图是超可迹图。abdefcThomassen图ⅠⅡⅢⅣ9定理证明分为两部分:(1)证明G中不存在H路；(2)证明对G中任意点v，有G-v存在H路。(1)证明G中不存在H路。如图所示，将G用虚线分成对称的4部分：Ⅰ,Ⅱ,Ⅲ,Ⅳ。abdefcThomassen图ⅠⅡⅢⅣ假设G有H路P,设该路的起点为α，终点为β。不失一般性，设α∈Ⅰ∪｛a｝
4、。断言1：Ⅰ∪｛a｝中不存在以a,c,d三点中任意两点为端点的H路。若不然，将推出彼得森图是H图。10abdefcThomassen图ⅠⅡⅢⅣ断言2：Ⅰ∪Ⅱ∪｛a，b｝中不存在以a为端点的H路。若不然，设Q是一条以a为起点的Ⅰ∪Ⅱ∪｛a，b｝中的H路。那么，从a出发，沿着该路行走有两种可能:(1)遍历了Ⅰ中所有点之后，从c或d进入Ⅱ，但这形成了Ⅰ∪｛a｝中的以a,c或a,d为端点的H路，与断言1矛盾！(2)没有遍历完Ⅰ∪｛a｝中的顶点，假若从c进入Ⅱ，那么，必须遍历完Ⅱ∪｛b｝的所有顶点后，才能从e进入Ⅰ。但这也会与断言1产生矛盾。11abdefcThomassen图ⅠⅡⅢ
5、Ⅳ情形1：α=a所以，情形1不能成立！由前面假设：α∈Ⅰ∪｛a｝。我们沿着P作如下的行进：(1)假设是由a进入Ⅰ，要能够走完P,必须遍历Ⅰ∪Ⅱ的所有顶点后由b进入Ⅲ，但这与断言2矛盾！(2)假设是由a进入Ⅳ，要能够走完P,必须遍历Ⅲ∪Ⅳ的所有顶点后由b进入Ⅱ，但这也与断言2矛盾！12abdefcThomassen图ⅠⅡⅢⅣ情形2：α≠a所以，情形2也不能成立！我们沿着P作如下的行进：(1)假设是由α遍历了Ⅰ∪Ⅱ∪｛b｝所有顶点从a进入Ⅳ，这与断言2矛盾！同样，假设是由α遍历了Ⅰ∪Ⅱ∪｛a｝所有顶点从b进入Ⅳ，这也与断言2矛盾！(2)假设是由α开始，没有遍历Ⅰ∪Ⅱ∪｛a,b｝
6、而从a或b进入Ⅲ∪Ⅳ，那么，要走完P,都必须遍历完Ⅲ∪Ⅳ的所有顶点后，才能重新进入Ⅰ∪Ⅱ。但这要与断言2矛盾13综合上面的论述：得G中没有H路。(2)证明对G中任意点v，有G-v存在H路。由对称性：我们取b和Ⅲ中顶点逐一分析即可。例如：abdefcThomassen图ⅠⅡⅢⅣ综上所述：得Thomassen图是超可迹图。14关于H图的一些猜想1、加莱猜想：不存在超可迹的图。加莱猜想是错误的。Thomassen图否定了加莱猜想。加莱(1912---1992)匈牙利数学家。他和Erdos,托兰是当时匈牙利国家数学竞赛获胜者，后来成为一生的朋友。加莱深受哥尼的影响而对图论产生极大兴
7、趣，以至于他对图论基础理论做出了重大贡献，推动了图论与组合数学的迅速发展。同时，他也是最早认识所谓的“极小--极大定理”重要性的数学家之一。加莱为人谦虚低调，很少在公开场合露面。常常在赞扬别人工作时低估自己的成绩。不喜欢发表自己研究成果。152、泰特猜想：任何3连通3正则可平面图是H图。泰特猜想也是错误的。托特1946年构图否定了泰特猜想。46个点的托特图Lederberg等构造了最小的3连通3正则图非H图，有38个点。16如果泰特猜想正确，4色定理可得到证明。托特(1917---2002)英国著名数学家。1935
