（运筹学与控制论专业论文）一个chvátalerdás型定理.pdf

： 硕士学位论文 m a s t e r st h e s l s 摘要 c h v 乱a i e r d 6 s 定理指出如果g 是阶数n 3 的图，且“g ) 口( g ) ，那么g 是 h a m i l t o n 图；如果茁( g ) 口( g ) ，那么g 是h a m i l t o n 连通图。我们在连通度足够大 的情况下用限制更弱的最小度和独立数条件之间的关系取代原有的连通度和独立 数条件之间的关系得到了一些新的结果。我们将证明如果g 是阶数为 的图，船充 分大，七是大于等于3 的正整数，使得h g ) 2 七2 + 4 七+ l ，万( g ) ( 刀+ 七2 2 七) j j ， 并且万( g ) 口( g ) + 七一2 ，那么g 是h a m i l t o n 连通图。 关键词：连通度；独立数；最小度；h a m i l t o n 连通 ： 硕士学位论文 m a s t e r st h e s i s a b s t r a c t t h ec h v 敬a l e r d 6 st h e o r e m si m p l yt h a ti fgi sag r a p ho fo r d e r 玎3w i t h “g ) 口( g ) ，t h e ngi sh a m i l t o n i a n ，a n di f “g ) 口( g ) ，t h e ngi sh a m i l t o n i a n - c o n n e c t e d w eg e n e r a l i z et h e s er e s u l t sb yr e p l a c i n gt h ec o n n e c t i v i t ya n di n d e p e n d e n c e n u m b e rc o n d i t i o n sw i t haw e a k e rm i n i m u m d e g r e ea n di n d e p e n d e n c en u m b e rc o n d i t i o n s i nt h ep r e s e n c eo f s u m c i e n tc o n n e c t i v i t y w es h o wt h a ti f gi sag r a p ho f o r d e r 押a n dj | 3i sap o s i t i v ei n t e g e rs u c ht h a t 缸g ) 2 七2 + 4 七+ l ， 万( g ) ( 刀+ 七2 2 七) 七，a n d 万( g ) 口( g ) + 七一2 ，t h e ngi s h a m i l t n n i a n c o n n e c t e d k e y w o r d s ：c o n n e c t i v i t y ；i n d e p e n d e n c en u m b e r ；m i n i m u md e g r e e ； h a m i l t o n i a n c o n n e c t e d 硕士学位论文 m a s t e r st i e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导_ 卜，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 万云霞 日期：汐沪年多月力日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名： 万云智 日期：舻6 月芝日 导师娩卯沈 日期：为才年月幻 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程”中的 规定享受相关权益。圆童途塞埕交后澄蜃；旦坐生；旦= 生；旦三生发查! 作者签名：乃i 锻 日期：学年多月2 ，日 导师签名：电p 耽 日期：别浔年月l 日 硕士学位论文 m a s t e r + st h e s l s 1 1 符号说明 第一节引言 本文讨论无向简单的连通有限图，没有说明的符号及术语，其含义与文【1 】 中一致。 常用符号： 如( v )点v 在h 中的度数 打( v ) 点v 在h 中的邻域 文g ) g 的最小度 口( g ) g 的独立数 戤g ) g 的连通度 尸k ，v 】从甜到v 的一条路 s +s 中点的后继点的集合 1 2 历史和研究现状 1 8 5 6 年，s i r w i l l i 锄h 狮i l t o n 设计了一种周游世界的游戏：给定世界上的2 0 个城市，用一个代表地球的十二面体的2 0 个顶点分别代表它们。现在要求沿十二 面体的边，走过每一个城市一次且仅仅一次，最后回到出发点。这个问题归结为求 一个圈，它过每点一次且仅一次。该圈称为h 锄i l t o n 圈，该问题称为h 郴i l t o n 问 题。它是图论中尚未解决的难题之一。 由于图的h 锄i l t o n 问题在实际中的应用越来越广泛，h 枷i i t o n 理论得到空前 发展。特别是近年来，关于它的文献著作不计其数。其中c h v a t a l 和e r d 6 s 给出了 两个经典的结论：( i ) ，如果图g 是阶数大于等于3 的图，且“g ) 口( g ) ，那么 g 是h 姗i l t o n 图；( i i ) ，如果图g 是阶数大于等于3 的图，且砥g ) 口( g ) ，那么 硕士学位论文 m a s t e r st h e s i s g 是h a m i l t o n 连通图。因为判断图的h a m i l t o n 性或h a m i l t o n 连通性与图的连通度、 最小度、点独立数等条件息息相关，所以研究图的连通度、最小度、点独立数对图 的h a m i l t o n 性或h a m i l t o n 连通性的影响是非常必要的。 本文主要研究在图g 的阶数足够大的情形下，在连通度、最小度、点独立数 等条件的限制下，图的h a m i l t o n 连通性情况。 2 硕士学位论文 m a s t e r st h e s j s 第二节预备 2 1 关于h a m i l t o n 问题 定义l一般地，设给了一个图g = ( v ，e ) ，是g 中的一个圈，若过g 的每个点一次且仅仅一次，则我们称是g 中h a m i l t o n 圈( 简称h 圈) 。类似地定 义h a m i l t o n 路( 简称h 路) 。若图g 中有h 圈，则称g 为h a m i l t o n 图( 简称h 图) 。 所谓h a m i l t o n 问题就是要给出一个图是h 图的特征描述。 定义2如果图g 中的任意两点“和v 之间都存在一条h 路，则称g 是 h a m ij t o n 连通图。 2 2 已知结果 关于图的h a m i l t o n 性有很多结果，其中由c h v 加l 和e r d 6 s 证明的两个经典的 结果如下： 定理l ( 【2 】) 如果图g 是阶数至少为3 的图，且砥g ) 口( g ) ，那么g 是h a m i l t o n 图。 定理2 ( 【2 】) 如果图g 是阶数至少为3 的图，且砥g ) 口( g ) ，那么g 是h a m i l t o n 连通图。 在【7 】中，j i l lr f a u d r e e 和r a l p hj f a u d r e e 以及c o l t o nm a 印锄t 等借助于 正整数七，并且限制了最小度条件以及点独立数条件得到了一个新的结果： 定理3 ( 【7 】) 设g 是一个阶数为，l 的图，满足j | f ( g ) 七， 万( g ) 0 + 七2 一七一1 ) ( 七十1 ) ，其中七2 为正整数。如果万( g ) 口( g ) + 七一2 ， 那么g 是h a m i l t o n 图。 硕士学位论文 m a s t e r st h e s i s 因为定理3 和定理l 一样也是讨论图中是否存在h 圈，根据其结果，类比定理 2 ，j i l ir f a u d r e e 和r a l p hj f a u d r e e 以及c o l t o nm a g n a n t 等提出如下猜想。 猜想l 设g 是一个阶数为 的图，七是一个大于等于3 的正整数，使得 以g ) j | ，文g ) ( n + j | 2 2 七) 七。如果万( g ) 口( g ) + 七一2 ，那么g 是h a m i l t o n 连 通图。 他们证明了如下的两个结果支持猜想l ：其中第一个结果和猜想有同样的最小 度和独立数条件，结论与猜想也一样，但是对图的连通度要求比猜想要更高；第二 个结果证实了猜想对七= 3 和七= 4 是成立的。 定理4 ( 【7 】)设g 是一个阶数为”的图，玎足够大，七是一个大于等于3 的正整数，使得砥g ) 24 足2 + l ，以g ) ( 姐+ 七2 2 七) 七。如果j ( g ) 理( g ) + 足一2 ， 那么g 是h 锄i l t o n 连通图。 定理5 ( 【7 】)设g 是一个阶数为，2 的图， 足够大，七= 3 或4 ，使得 “g ) j i ，以g ) 0 + 七2 2 七) 七。如果j ( g ) 口( g ) + | i 一2 ，那么g 是h a m i l t o n 连 通图。 明。 定理3 和定理5 的条件是最好条件，不能再减弱了，我们接下来可以举例说 2 3 一些极限图的例子 对于七2 ，令目l ( 七) = 足i + ( 七+ 1 ) 墨“) h 川) ， 挖三七m o d ( 七+ 1 ) 。因为在图 。( 七) 一墨中有( 七+ 1 ) 个连通分支，所以图何。( 七) 不是h 狮i l t o n 图。而且 h h 。( 七) ) = 七，以日。( 七) ) = ( 刀+ j | 2 一七一1 ) ( 七十1 ) ，当，l 足够大时，口( g ) = 七+ l 万( g ) 。 对于七2 ，令2 ( 七) = 墨，1 ) i + 1 ) + “玎+ 1 ) ( 七+ 1 ) ) 墨，丹兰七m o d ( 是+ 1 ) 。因为在 五 硕士学位论文 m a s t e r st h e s l s 2 ( 七) 一墨耐+ 1 ) 中有多于( 玎一七) ( 七十1 ) 个连通分支，所以图2 ( 七) 不是h a m i l t o n 图。而且有政h ：( i i ) ) = ( 竹+ 七2 一| i 一i ) ( j i + 1 ) ，以：( 后) ) = ( + 1 ) ( 七+ 1 ) = 以h ：( 七) ) 一( 七一2 ) 。 对于七3 ，令日3 ( 七) = k + 从( 一) 玎三0 m o d 七。因为日3 ( 七) 一k 中的连通分 支数和t 中的点数一样多，所以图，( 七) 不是h a m i l t o n 连通图。 胃。( j j ) ) = 七，以3 ( 七) ) = o + 七2 2 七) 老，当纷足够大时，口( 日，( 七) ) = 七万( g ) 。 对于七3 ，令h 4 ( 七) = k 。，i + ( 刀七) k h ，刀兰o m o d 七。因为h 4 ( j | ) 一k 。t 中的 连通分支数和k 小中的点数一样多，所以图。( 七) 不是h a m i l t o n 连通图。 文日。( 七) ) = ( ”+ 七2 2 j i ) 七，口( 日4 ( 七) ) = ”七= 万( 4 ( 七) ) 一( 七一2 ) 。 对于+ 1 ) 3 ( 朋+ 七2 2 七) 七 。如果 6 ( g ) 口( g ) + 七一2 ，那么g 是h a m i l t o n 连通图。 6 。： 硕士学位论文 m a s t e r st h e s i s 第三节定理6 的证明 3 1 定理3 的证明 在证明定理6 之前，我们先来看看定理3 的证明。为了方便我们后面的证明，我 们先给出几个定义： 定义3 给定正整数p ，q ( 9 = m i 概) + 鹅) + 一+ 也) ：h v 2 ，哆 是g 的独 立集) 。 定义4 给定正整数见，g 中的圈c 称为j d 一缈彪如果g c 的每个连通分支 都少于五个点。 有了这两个定义之后，我们可以给出f r a i s s e 在【5 】中的一个结果： 定理a ( 【5 】) 如果g 是阶数刀23 的七连通图，吒+ 。( g ) + 七( 七一1 ) ，那么g 含一个d 五一钞c 尼。 定理3 的证明：因为r ( g ) 七，所以g 是七连通的图，又吒+ 。( g ) ( 七+ 1 ) 万( g ) ， 而万( g ) ( ，l + 七2 一七一1 ) ( 七+ 1 ) ，所以( 七+ 1 ) 吠g ) 聪+ 七2 一七一1 ，l + 七2 一七，由定 理a 知道，g 中含皿一钞c 尼。选择一条最长的圈c ，则由d 五一缈彪的定义知道， 它必定是一条d 互一缈彪。如果c 是h a m i l t o n 圈，则结论已经成立，故假设c 不是 h 锄i l t o n 圈。设1 ，是g c 的某个分支比如说日中的一点。因为1 月l 七一l ，所以 ：一， 硕士学位论文 m a s t e r st h e s l s 如( v ) 七一2 ，进而4 ，( v ) 以g ) 一七十2 。设s = 坼( v ) ，让s + 表示按照c 上某个 定向s 在c 上的后继点的集合。因为c 是最长的么一钞f 彪，则s = s + u 和) 是个 独立集，其中所含点数至少为6 ( g ) 一七+ 3 。这与万( g ) 口( g ) + i | 一2 是矛盾的，因 此假设不成立，故c 是h a m i l t o n 圈。定理3 的证明完成。 定理3 实际上也可由o t a 在【6 】中的如下结论直接得到： 定理b ( 【6 】) 设g 是阶数刀3 的七连通图，且口( g ) ( 玎+ 1 ) “后+ 1 ) + 1 。如 果吼+ l ( g ) ”+ 七( 七一1 ) ，那么g 是h a m i 】t o n 图。 这是因为文g ) ( ”+ 七2 一j i 一1 ) ( 七+ 1 ) ，所以j ( g ) 一七+ 2 ( 丹+ 1 ) ( 七+ 1 ) ( 门+ 1 ) “七+ 1 ) + 1 而口( g ) ( 刀+ 1 ) ( 七+ 1 ) + 1 ，所以万( g ) 口( g ) + 七一2 ， 而 吒+ i ( g ) ( 七+ 1 ) 万( g ) + 七2 一七一l ，故吒+ l ( g ) 一十七( 七一1 ) ，又g 是h 锄i l t o n 图， 所以定理3 成立。 3 2 定理6 的证明 在证明定理6 之前，我们需要一个引理： 定理7 ( 【8 】) 设g 是一个至少有4 个顶点的2 - 连通图，“，w 是g 中的顶点。 如果矿( g ) 一函，v ，w ) 中的每个点的度数至少为d ，那么g 包含一条长度至少为d 的 0 ，v ) 路。 由定理7 可得如下引理： 硕士学位论文 m a s t e r st h e s i s 引理l 设g 是一个2 连通的图，w y ( g ) ，v v 矿( g ) 一加l d ( v ) d ，则对于g 中任意两个不同点甜，v ，g 中包含一条长度至少为d 的( z ，1 ，) 橱 。 定理6 的证明： 在g 中任取两个不同的点x 幂吵，设尸是一条从z 至吵的点数最多的路，设点数 为研，令日= g y ( p ) 。 断言一：j 坼( 日) l 酬g ) ，即日在尸上至多有口( g ) 个邻点。 设f = 2 七2 + 4 七十l ，则r ( g ) 2f 。我们证明h = g y ( 尸) 中的每个点在尸上至多 有口( g ) 个邻点。用反证法：假设h 中某个点v 在尸中至少有口( g ) + 1 个邻点，设这 些点的集合为s 。因为对p 中任意的定向，s 中至多有一个点没有后继点，所以 l s + l 吲一l 。因为p 是一条最长路，所以s + u v ) 一定是独立集，而且其阶数至少 为口( g ) + 1 。这是矛盾的，所以假设不成立，则= g y ( 尸) 中的每个点在尸上至 多有口( g ) 个邻点。 由断言一即得； 断言二：万( h ) 万( g ) 一口( g ) 七一2 断言三：m 砌舷+ 1 ) 设v 是日中最小度点，选取“y ( h ) 一如) 使办 ) = m i n 饥 ) l “y ( 片) 一和抖= d 。若d 0 + 七2 2 七) 七，故当，l 足够大时，m 也足够大，而f 是个常数，所以d ( 甩+ 七2 2 七) 七 由( 1 ) 得 硕士掌位论文 m a s t e r st h e s l s 又 即得 ，l 4 ( 万( g ) d ) + ( 七一4 ) ( 万( g ) 一2 d + 七一2 ) 一七+ l 疗+ 2 七2 9 七+ 7 一( 2 七+ 4 ) ( ( ，”一1 ) ( f 1 ) 一2 ) f 2 七2 + 4 七+ l = 七( 2 七+ 4 ) + l m 玎+ 2 七2 5 七+ 1 5 一( 埘一1 ) 七 ，”甩七“七+ 1 ) + 2 七2 7 七+ 2 2 尼“| j + 1 ) 即 i 尸| = ， ，庙( 七+ 】)li 故断言三成立。并且有 i 胃 ( j + 2 ) ( 甩七+ 2 七一2 j + 1 ) 一4 七+ l 刀一s l 万一g ，z ( s + 2 ) ( 甩七+ 2 七一2 s 1 ) 一4 七十l 2 s 2 一( 玎七+ 2 七一4 ) s + 刀一2 ，l 七 o 2 s 2 一( 疗七+ 2 七一4 ) s + 打一2 厅七= o ( 6 ) ( 7 ) 的两个根= 七一2 ，s 2 = ( 2 七) ，所以当七一2 ss 丹( 2 七) 一l 时，( 7 ) 式是矛盾的， 故我们假设s ”( 2 七) 一l ，前面我们已经证明了s 门( 七+ 1 ) 。 尸上有些点至少与s 中两个点相邻，设这些点的集合为r ，点的个数为，。如 果，占( g ) 一j ，那么在尸上至少存在( j ( g ) 一s 1 ) 个不同的“区间”，每个“区间 至少有p + 1 ) 2 个点在q 中没有邻点，而且其中有一个“区间”至少有g 个点，这 就是说 玎一g ，”( 万( g ) 一s 一2 ) ( s + 1 ) 2 + g + 万( g ) 一j ( 8 ) s 2 一( 万( g ) 一5 ) s 一3 万( g ) + 2 + 2 ，2 4 9 0 ( 9 ) 硕士学位论文 m a s t e r st h e s i s 然而，这与力( 2 七) 一l ( + 七2 2 后) 七，所以 s 2 一( 万( g ) 一5 ) j = s ( s 一万( g ) + 5 ) 5 ( s 一胛七一七+ 7 ) j ( “七+ 1 ) 一 七一七+ 7 ) 因此我们得到： = s ( 一珂“七( 七+ 1 ) ) 一七+ 7 ) 一( 珂( 2 七) 一1 ) ( 玎( 七( 后+ 1 ) ) + 七一7 ) j 2 一( 万( g ) 一5 ) s 一3 以g ) + 2 + 2 刀一4 9 一( 门“2 七) 一】) ( n “七( 七十1 ) ) + 七一7 ) 一3 ( 疗j i + 七一2 ) + 2 十2 h 一4 ( 七一1 ) 3 七3 + 4 七2 一七时，有 s 2 一( 吠g ) 一5 ) s 一3 文g ) + 2 + 2 疗一4 9 o 而当刀 3 七3 + 4 七2 一七时，此式矛盾! 至此，我们知道p 不是h a m ij t o n 路的假设是 不成立的，所以p 是h a m i l t o n 路。从而定理6 成立。 硕士学位论文 m a s t e r st h e s i s 结束语 本文首先研究了在连通度足够大的情况下用限制更弱的最小度和独立数条件 之间的关系取代原有的连通度和独立数条件之间的关系得到的一些新结果，如定理 3 、定理4 和定理5 ，不仅如此，通过对一些极限图的研究，我们知道定理3 和定理 5 是最好结果。在定理4 中，我们将连通度继续降小，将其原来的系数由4 j i 2 降为2 | i 2 ， 仍然满足h 锄i l t o n 连通性。但是这与猜想中的结果还有一定的差距，我们能否将 连通度的限制系数由七的二次系数降为一次或者更小呢? 对此，作者还将进一步探 索。 1 6 硕士学位论文 m a s t e r st h e s i s 参考文献 【l 】g c h a n r a n da n dl l e s n i a k ，g r a p ha n dd i g r a p h s ，c h a p m a na n dh a l l ，l o n d o n ， ( 1 9 9 6 ) 【2 】v c h v 矗t a la n dp ：e r d 6 s ，彳，z d 胞d 力j l z 口朋口f d 刀肠乃c f ，c 甜豇岛d i s c r e t em a t h 2 ，( 19 7 2 ) 1 1 1 1 1 3 【3 】g a d i r a c ，& l 朋pf 办p d 理m jd 力口6 s f 聊f 聊凰，p r o c l o n d o nm a t h s o c 2 ( 1 9 5 2 ) ， 6 9 8 1 【4 】h e n o m o t o ，乞d 馏p 町泌口聆矗z 口，g 它钞c 把s 加夕行f 配聊凰， r e s e a r c hr e p o r t ， d e p a r t m e n to fi n f o 肌a t i o ns c i e n c e ，u n i v e r s i t yo ft o k y o ( 19 8 0 ) 【5 】p f r a i s s e ，d a - 钞c 艮s8 df 比如印p 觑搬f 国埘声，曰a 柳出o 妇 钞c 彪s ，t h 芒s ed ed o c t o r a t d 芒t a t ，u n i v e r s i t d ep a r i s - s u d ，( 19 8 6 ) 【6 】k o t a ，( 乡c 彪sf 厅，d 岖矗p 旭卵r 汤e dv p 一配p jw 豇| 1 2 肠曙pd 匆g 陀ps “小，d i s c r e t em a t h 1 4 5 ( 1 9 9 5 ) ，2 0 卜2 1 0 【7 】j 川r f a u d r e e ，r a l p hj f a u d r e e 锄dc o i t o nm a g n a n t ，c 厅谢胁，- 蜀嘣两巧矽7 确已。旭m 只 p r e p r i n t 【8 】j a b o n d ya n db j a c k s o n ，上d ，咨p d f j b6 p f w p p 凹圮c 论d 理以比p s 口6 ，d c 七， a n n d i s c r e t em a t h 2 7 ( 19 8 5 ) ，