第四章-欧拉图与哈密尔顿图4-论及其应用课件.ppt

《第四章-欧拉图与哈密尔顿图4-论及其应用课件.ppt》由会员分享，可在线阅读，更多相关《第四章-欧拉图与哈密尔顿图4-论及其应用课件.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1Email:图论及其应用图论及其应用任课教师：杨春任课教师：杨春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彼得森图彼得森图10

2、98 又对于边又对于边28，23来说，在前面情况下，必有一条在来说，在前面情况下，必有一条在C中。中。分两种情形讨论。分两种情形讨论。对于边对于边12,17,15来说，必然有两条边在来说，必然有两条边在C中。不失一般性，中。不失一般性，假定假定17,12在在C中，那么，中，那么，56，54也必然在也必然在C中。中。6 但这样得到圈：但这样得到圈：123971。所以该情形也不能存在。所以该情形也不能存在。情形情形2：假如：假如23在在C中，则中，则86，8(10)在在C中中,从而从而39,79在在C中中.1654327彼得森图彼得森图10981654327彼得森图彼得森图1098 上面推理说明，

3、上面推理说明，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-61098 由由(1)与与(2)，G是超是超H图。图。8 定义定义2 若若G中没有中没有H路，但是对路，但是对G中任意点中任意点v，G-v存在存在H路，则称路，则称G是超可迹的。是超可迹的。数学家加莱曾经猜想：不存在

4、超可迹的图。但该猜想被数学家加莱曾经猜想：不存在超可迹的图。但该猜想被Horton和和Thomassen以构图的方式否定了。以构图的方式否定了。定理定理2 Thomassen图是超可迹图。图是超可迹图。abdefcThomassen图图10abdefcThomassen图图 断言断言2 2：a，b 中不存在以中不存在以a 为端点的为端点的H路。路。若不然，设若不然，设Q Q是一条以是一条以a a为起点为起点的的 a，b 中的中的H路。路。那么，从那么，从a出发，沿着该路行走出发，沿着该路行走有两种可能有两种可能:(1)遍历了遍历了中所有中所有点之后，从点之后，从c或或d进入进入，但这形，但这形

5、成了成了 a 中的以中的以a,c或或a,d为端点的为端点的H路，与断言路，与断言1矛盾！矛盾！(2)没有遍历完没有遍历完 a 中的顶点，假若从中的顶点，假若从c进入进入，那，那么，必须遍历完么，必须遍历完 b 的所有顶点后，才能从的所有顶点后，才能从e进入进入。但这也会与断言但这也会与断言1产生矛盾。产生矛盾。11abdefcThomassen图图 情形情形1：=a=a 所以，情形所以，情形1不能成立！不能成立！由前面假设：由前面假设：a。我们沿着我们沿着P作如下的行进：作如下的行进：(1)假设是由假设是由a进入进入，要能够走完，要能够走完P,必须遍历必须遍历 的所有顶点后由的所有顶点后由b进

6、进入入，但这与断言，但这与断言2 2矛盾！矛盾！(2)假设是由假设是由a进入进入，要能够走，要能够走完完P,必须遍历必须遍历 的所有顶点后的所有顶点后由由b进入进入，但这也与断言，但这也与断言2 2矛盾！矛盾！13 综合上面的论述：得综合上面的论述：得G中没有中没有H路。路。(2)证明对证明对G中任意点中任意点v，有，有G-v存在存在H路。路。由对称性：我们取由对称性：我们取b和和中顶点逐一分析即可。例如：中顶点逐一分析即可。例如：abdefcThomassen图图 综上所述：得综上所述：得Thomassen图是超可迹图。图是超可迹图。15 2、泰特猜想：任何、泰特猜想：任何3连通连通3正则可

7、平面图是正则可平面图是H图。图。泰特猜想也是错误的。托特泰特猜想也是错误的。托特1946年构图否定了泰特猜想。年构图否定了泰特猜想。46个点的托特图个点的托特图 Lederberg等构造了最小的等构造了最小的3连通连通3正则图非正则图非H图，有图，有38个个点。点。16 如果泰特猜想正确，如果泰特猜想正确，4色定理可得到证明。色定理可得到证明。托特托特(1917-2002)英国著名数学家。英国著名数学家。1935年，入剑桥三年，入剑桥三一学院学习化学，并攻读了化学研究生，撰写了一学院学习化学，并攻读了化学研究生，撰写了2篇化学篇化学论文。但是，他的兴趣是数学。在剑桥，他结识了论文。但是，他的兴

8、趣是数学。在剑桥，他结识了3位数位数学专业的本科学生并成为终身朋友，合作发表数学论文。学专业的本科学生并成为终身朋友，合作发表数学论文。二战后，托特回到剑桥攻读数学研究生。研究生期间，发二战后，托特回到剑桥攻读数学研究生。研究生期间，发表了关于图的因子分解论文。在他的数学博士论文中，复表了关于图的因子分解论文。在他的数学博士论文中，复兴了拟阵理论兴了拟阵理论(惠特尼引入的惠特尼引入的).1948年博士毕业后，受年博士毕业后，受20世世纪伟大的几何学家纪伟大的几何学家Coxeter邀请前往多伦多大学任教，成邀请前往多伦多大学任教，成为组合数学杰出学者。为组合数学杰出学者。5年后到滑铁卢大学工作直

9、到年后到滑铁卢大学工作直到1984年退休。年退休。托特是托特是20世纪伟大的数学家之一，在近代数学史上占有世纪伟大的数学家之一，在近代数学史上占有一定的地位。主要功绩是提出并证明了图的完美匹配定理。一定的地位。主要功绩是提出并证明了图的完美匹配定理。18 该猜想错误。该猜想错误。Meredith构图对猜想进行了否定。构图对猜想进行了否定。3、纳什、纳什威廉斯猜想：每个威廉斯猜想：每个4连通连通4正则图是正则图是H图。图。Meredith图图 Meredith图是由彼得森图的每个顶点嵌入一个图是由彼得森图的每个顶点嵌入一个K3,4作成。作成。19 该猜想错误。该猜想错误。Coxeter构图对猜想

10、进行了否定。构图对猜想进行了否定。4、托特猜想：每个、托特猜想：每个3连通连通3正则偶图是正则偶图是H图。图。Coxeter图图20 该猜想是正确的，已经得到证明。该猜想是正确的，已经得到证明。5、普鲁默猜想：每个、普鲁默猜想：每个2连通图的平方是连通图的平方是H图。图。定义：图定义：图G的平方的平方G2是这样的图是这样的图:1234G1234G2 值得一提的是：在值得一提的是：在H问题研究中，问题研究中，H图中图中H圈的计数问题圈的计数问题也是一个研究方向。也是一个研究方向。21 定理：每个定理：每个3正则正则H图至少有图至少有3个生成圈。个生成圈。我院张先迪、李正良教授曾经也研究过我院张先

11、迪、李正良教授曾经也研究过H图中图中H圈的计数圈的计数问题。问题。90年在年在系统科学与数学系统科学与数学学报上发表文章：学报上发表文章：“有有限循环群上限循环群上Cayley有向图的有向图的H回路回路”，得到了该类图的，得到了该类图的H圈圈的计数公式。的计数公式。(二二)、E图和图和H图的关系图的关系 从表面上看，从表面上看，E图与图与H图间没有联系。因为我们可以不图间没有联系。因为我们可以不费力地找到费力地找到:(1)E图但非图但非H图；图；(2)E图且图且H图；图；(3)H图但非图但非E图图;(4)非非E图且非图且非H图图.E且H图E图但非H图H但非E图非E且非H图22 定义定义3 设设

12、G是图，是图，G的线图的线图L(G)定义为：定义为：特别地，定义特别地，定义G的的n次迭线图次迭线图Ln(G)为：为：x3x1x4x2G2=L(G1)L(G2)=L(L(G1)x1x2 x3x4G1 1、线图概念、线图概念24 (3)一个图同构于它的线图，当且仅当它是圈。一个图同构于它的线图，当且仅当它是圈。(4)若图若图G和和G1有同构的线图，则除了一个是有同构的线图，则除了一个是K3而另一而另一个是个是K1,3外，外，G和和G1同构。同构。(证明比较复杂证明比较复杂)3、从线图的角度考察、从线图的角度考察E图与图与H图的关系图的关系 定义定义4 称称Sn是图是图G的的n次细分图，是指将次细

13、分图，是指将G的每条边中都的每条边中都插入插入n个个2度顶点。度顶点。GS(G)又记：又记：25定理定理3 (1)若若G是是E图，则图，则L(G)既是既是E图又是图又是H图。图。(2)若若G是是H图，则图，则L(G)是是H图。图。注：该定理逆不成立。注：该定理逆不成立。G1L(G1)G2L(G2)定理定理4 一个图一个图G 是是E图的充要条件是图的充要条件是L3(G)为为H图图 S2(G)GL3(G)26定理定理5（Chartarand）若）若G 是是n个点的非平凡连通个点的非平凡连通图，且不是一条路，则对所有图，且不是一条路，则对所有mn-3，Lm(G)是是H图。图。GL3(G)L(G)L2(G)28Thank You!