（运筹学与控制论专业论文）度条件与过线性森林的圈.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 设k ，s ，f 为满足s f 的非负整数，f 是由f 条点不交的路构成的边数为k 的森 林，如果f 中恰有s 条路是单点，则称f 为( k , t ，s ) 一线性森林。不必考虑单点路的 个数时，可称f 为( 七，f ) 一线性森林。如果对于玎阶图g 中的每个( 七，f ) 一线性森林f ， 都存在g 中的一个哈密顿圈过凡则称g 是( 七，f ) 哈密顿的。r a l p hj f a u d r e e 等人 给出了g 是( 七，f ) 一哈密顿图的吒型条件。本文讨论了g 中其他长度的过( 七，f ，0 ) 线 性森林的圈，得到： 设k ，f 和n 是满足2 k + t 刀的正整数，g 是n 阶图，f 是( 忌，t ，0 ) 线性森林。 如果 ( i ) ( g ) 疗+ 七，当f = 最+ l ， ( i i ) 0 2 ( g ) n + k e ( 门，七) ，其它情况， 则对任意， m a x 4 ，k + 2 t ，2 ，g 中存在长为厂或厂+ 1 的圈过f 。 关键词：圈；线性森林；度；泛圈。 硕士学位论文 m a s t e r st h e s i s a b s t r a c t g i v e ni n t e g e r s 岛j ，tw i t h0 s ta n dk 0 ，a ( 七，f ，j ) 一l i n e a rf o r e s tfi sag r a p h t h a ti sv e r t e xd i s j o i n tu n i o no ftp a t h sw i t hat o t a lo fke d g e sa n dw i t hso ft h ep a t h sb e i n g s i n g l ev e r t i c e s i ft h en u m b e ro fs i n g l ev e a e xp a t h si sn o tc r i t i c a l ，t h ef o r e s tf w i l ls i m p l y b ec a l l e da ( 七，f ) 一l i n e a rf o r e s t ag r a p hgo fo r d e rni s ( 七，f ) 一h a m i l t o n i a ni ff o ra n y ( 七，f ) 一l i n e a rf o r e s tf t h e r ei sah a m i l t o n i a nc y c l ec o n t a i n i n gf a 吒( g ) c o n d i t i o nt h a t i m p l i e sag r a p hgi s ( 尼，t ) - h a m i l t i o n i a nw a sp r o v e db yr a l p hj f a u d r e ee ta 1 i nt h i s p a p e r , w ed i s c u s so t h e rl e n g t hc y c l e so fgc o n t a i n i n gag i v e n ( 七，t ，0 ) 一l i n e a rf o r e s t ，a n d p r o v et h ef o l l o wr e s u l t ： l e tgb ea g r a p ho f o r d e r 门a n d 毛fb e p o s i t i v ei n t e g e r sw i t h2 k + t n ，a n d l e t fb ea ，0 ) 一l i n e a r f o r e s t 矿 ( i ) c r 2 ( g ) 2 刀+ 七，w h e nf = 最+ l ，a n d ( i i ) 吒( g ) n + k - e ( n ，七) o t h e r w i s e ， t h e n f o ，a n y ，e m a x 4 ，k + 2 t ，z ，gh a sa c y c l eo f l e n g t hro ，- ，+ 1c o 甩t a i nf k e yw o r d ：c y c l e ；l i n e a rf o r e s t ；d e g r e e ；p a n c y c l i c 硕士学位论文 m a s t e r 。st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者摊：7 删嗍：加严歹月言j 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者 日期 日 导师签名：之冈犹 日期沙。7 年s 月巾 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回童诠塞握交卮进卮! 旦堂生；旦二生；旦三生发查! 作者豁7 蚋 日期：1 年f 月弓1 日 厶 日 ：可 九韧多 n w 月 生厶，、 午 叮 红 幻 签 ： 师期 宁日 硕士学位论文 m a s t e r 。st h e s i s 1 , 1 符号说明 第一节引言 l x i 集合x 的元素个数 l y ( g ) i 或i g l 图g 的阶数 i e ( g ) l 或蚓l 图g 的边数 g h i g ( 1 ，) r 、y ( 日) i “( v ) g 中点，在h 中的邻点个数 m ( v )g 中点v 在h 中的邻点集合 , f i g )图g 的最小度 0 2 ( g ) m i n d ( v , ) + d ( v 2 ) l v , ，v 2 y ( g ) ，啊v 2 仨e ( g ) ) c ， 长度为，- 的圈 毋。 长度为，的路 ? i x ，y 】p 中由点x 到点j ，的子路 尸( x ，y 】p 中x 的后继点到点y 的子路 1 2 研究背景及现状 哈密顿问题( 1 8 5 6 ) 由关于十二面体的一个数学游戏而起源，经历了一百多年， 吸引了大批图论学家的兴趣。特别是进入上世纪5 0 年代后，关于哈密顿问题的研 究进入了繁荣时期。同时，哈密顿问题也是图论中尚未解决的难题之一。 早在1 9 5 2 年d i r a c 首先给出了有关哈密顿图的度条件：设g 是，z 阶图，刀3 ， 若万( g ) 形2 ，则g 含有哈密顿圈。之后，更多关于哈密顿图性质的定理陆续被证 硕士学位论文 m a s t e r st h e s i s 明，如o r e 等人于1 9 6 0 年给出证明图的哈密顿性的经典结论。 图论的一个重要研究领域是解决关于圈的问题，这一领域经历了起步与发展的 过程，获得了很多有用的成果。这其中，一个特别的分支是解决有关过图中特定元 素的圈的问题，这些特定元素或者是点集，或者是点不交的路( 包括独立边集) ， 或者是路和点的组合( 线性森林) 。通过图的连通性进行研究，e n o m o t o 和h i r o h a t a 分别证明了圈与一条特定路的关系；胡智全老师等人作了进一步推广，证明了圈与 特定线性森林的关系。另外，对图的边参数进行研究，也有很多结论出现，特别是 对度条件j ( g ) 和盯：( g ) 的利用，p 6 s a 和k r o n k 证明了哈密顿圈与线性森林的关系， r j f a u d r e e 等人研究了其他长度的圈与线性森林的关系。 关于圈和线性森林关系的研究是很有意义的，对研究泛圈图和有序图也是有很 大帮助的。本文继续探讨度条件与含线性森林的圈之间的关系。 2 硕士学位论文 m a s t e r st h e s l s 2 1 基本概念 第二节概述 本文仅考虑无向简单有限图g = ( v ，e ) ，文中没有特别说明的符号及术语，其 含义与文【l 】中一致。 定义1 给定图g = ( v ，e ) ，是g 中一个圈，如果卢过g 的每一个点且仅过一 次，则称是g 中的哈密顿圈。如果图g 中有哈密顿圈，则称g 为哈密顿图。 定义2 设k 0 ，t 1 和0 s t 是整数。如果f 是由f 条点不交的路构成的图， 其中共有k 条边及s 条单点的路，则称，是( 七，j ) 线性森林。若不必考虑单点路的 个数，我们将f 称为( 七，f ) - 线性森林。 定义3 如果对于g 中的每个( 后，f ) 一线性森林r 都存在g 中的一个哈密顿圈过 f ，称图g 是( 七，f ) 哈密顿的。 如果圈c 对线性森林满足：v ( f ) g ( c ) ，e ( f ) e ( c ) ，则称c 是过线性森 林f 的圈。 定义4 设g 是行阶图，k 0 ，f 1 和s 0 是给定的满足s f 的整数，整数坍 满足k + f m 刀。如果对g 中任意( j ，f ，s ) 线性森林( 或者( 七，f ) 线性森林) 凡g 对每个，【m ，门】都存在一个长为，的圈c ，过f ，则称图g 是( 七，f ，s ，聊) 一泛圈的( 或 者( 尼，f ，m ) 一泛圈的) o 2 2 已知结论 多种形式的度条件被用来研究图的哈密顿性。最常用的度条件是一个图g 的最 小度，记为8 ( g ) 。同样常用的度条件是g 中不相邻顶点的度和的晟小值，记为 ( g ) 。 d i r a c 2 和o r e 3 】关于图的哈密顿性的经典结论，给出了存在生成圈的度条件。 定理1 ( 【2 】) 设g 为刀阶图，万3 。d ( g ) n 2 ，则g 为哈密顿图。 定理2 ( 【3 】) 设g 为n 阶图，刀3 。c r 2 ( g ) n ，则g 为哈密顿图。 关于图中过特定的点和边的长圈，已经有了很多的结论，其中有3 个定理如f 。 定理3 ( 【4 】) 设聊1 ，g 是( 肌+ 2 ) 一连通图，己+ 。是g 中一条路，则g 中存在长度 m i n v ( g ) ，o - 2 ( g ) - m 的圈过己+ 。 定理4 ( 【5 ) 设k 3 且m 1 ，g 是( m + 七一1 ) - 连通图，只+ l 是g 中一条路，则g 中 存在长度m i n v ( g ) ，吾吒( g ) 一所 的圈过己+ 。 定理5 ( 【6 】) 设k 3 ，m 0 且o s k ，g 是( m + k - 1 ) 一连通图，g 中子图f 是 ( 朋，f ，s ) - 线性森林，则g 有长度m i n v ( g ) ，壬吼( g ) 一m 的圈过f 。 p 6 s a 7 和k r o n k 8 】用度条件研究过特定点不交路( 线性森林) 的哈密顿圈， 得到下面的定理。 定理6 ( 【7 ，8 】) 设o f k 是整数，g 是”阶图。如果c r 2 ( g ) n + k ，则对任意( 七，t ，o ) 一 线性森林f ，存在g 的哈密顿圈过f 。并且c r 2 ( g ) 的下界对无穷多个n 是最好可能 的。 r a l p hj f a u d r e e 【9 】等人改进了p 6 s a 和k r o n k 的结果，给出了定理7 。同时，r a l p h j f a u d r e e 等人还研究了图g 中其他长度的过线性森林的圈。 定理7 ( 【9 】) 设k ，t 和刀是正整数，满足2 k + t 刀，g 是甩阶图，f 是( 七，f ) - 线性 森林。如果 4 ( i ) t r 2 ( g ) 疗+ 七，当f = 丑+ i u ( t o k , ， ( i i ) 吒( g ) n + k - e ( n ，后) ，其它情况， 贝i j g 郧一啦顿自勺，这- 里( 础) = 托嚣k 动：并且郴) 紫条件是最好 可能的。 定理8 ( 【9 】) 设七，和甩是满足2 k + t 胛的正整数，g 是，z 阶图。如果( g ) 刀+ 七， 则g 是( 七，f ，2 t + k ) 一泛圈的。并且( g ) 的下界对无穷多个刀是最好可能的。 定理7 证明了对于某些( 七，f ) 线性森林和某些聆，( g ) n + k - 1 能充分推导出 g 是( 七，f ) 哈密顿的，但是对于一般的厅，以吒( g ) n + k 为通用界限。 2 3 主要结论 本文主要是在定理7 给定的条件下，研究g 中长度在k + 2 t 到甩之间的过 ( 七，r ，o ) 一线性森林f 的圈长分配情况。 定理a 设k ，和拧是满足2 k + f n 的正整数，g 是n 阶图，f 是( 七，f ，0 ) 一线性森 林。如果 ( i ) c r 2 ( g ) 捍+ 七，当f = 最+ l ， ( i i ) 0 2 ( g ) n + k - e ( n ，七) ，其它情况， 则对任意，e m a x 4 ，k + 2 t ，甩 ，g 中存在长为，或一1 的圈过f 。 在定理a 中取，= n ，可知g 中必存在长为n 的圈过f ，所以定理a 是定理6 的一个推广。下面两例说明定理a 是最好可能的。 。 例1 设日= 吒+ 。+ ( q ( 柑_ 1 ) ：ju 畸( 柑刮： ) ，线性森林f 是+ 中的一条最+ 路。则 h 中没有哈密顿圈过f ，而盯：( h ) = n + k 一1 。 硕士学位论文 m a s t e r st h e s i s 例2 完全二部图b 2 气川h _ 1 - 啡，) ) 2 ( 础+ l + 咖 ) ) 2 满足甩 2 t + k + l + e ( n ，七) 。则吒( 曰) = n - 2 t - k - 1 - e ( n ，k ) ，且b 的生成线性森林至少含有t + l 十e ( ，z ，k ) 条路。对任意的 ( 七，f ，0 ) - 线性森林f ，设h ( k ，f ，刀) = f + b ( 见图1 ) ，b 不含f 条路的生成森林，所 以不存在日( 七，f ，z ) 的哈密顿圈过f ，而( h ( k ，f ，咒) ) = n + k - l - e ( n ，七) 。 图1 f = ( 后，f ，0 ) 一线性森林 6 3 1 相关定理 第三节主要结论的证明 为了证明定理a ，我们先来考察线性森林中路的长度只有0 或i 时的情况。 定理1 1 设g 是阶疗k + f 的图，其中k ，t 为满足k t 的j f 整数。设f 是g 中 ( 尼，f ，f 一七) 一线性森林。如果 ( i ) c r 2 ( g ) 刀+ 七，k = 1 时， ( i i ) 吒( g ) n + k - e ( n ，七) ，七2 时， 则当，2 时，g 存在过f 的圈c ，使得c y ( ，) 为孤立点图或空图。 证明：用反证法。设f 2 ，并且g 是边数最多的反例，则g y ( f ) 不是完全图。 设x ，y e 矿( f ) 是g 中两个不相邻点，由g 的最大性，g + x y 中存在过f 的圈d 使 d v ( f ) = 囝或d y ( f ) 为孤立点图。如果砂萑e ( d ) ，则d 是g 中使定理1 1 成 立的圈，所以x y e ( d ) 。设p - - - - u 。“：“口是g 中的一条路，满足 ( i ) e ( 尸) 2e ( f ) ，y ( 尸) 2v ( f ) ， ( i i ) ，u 。v ( f ) ， ( i i i ) p - v ( f ) 为孤立点图或空图， ( i v ) 在( i ) ，( i i ) ，( i i i ) 的前提下，i “：) r 、e ( f ) i 最大。 注意到，d 一砂为g 中满足( i ) ，( i i ) ，( i i i ) 的路，所以上面所选择的路尸是存在 的。 如果甜l “p e ( g ) 或者嘶，”p 在日= g 一矿( p ) 中有公共邻点z ，则z f ：“p 或者 比。材2 甜p z u ! 为满足定理1 1 的圈，故假设“p 仨e ( g ) r n n ( u 。) r 、( “p ) = o 。由此 7 得， 如( z ，。) + 幽( “p ) - i z i = ，z p 。 ( 1 ) 令爿= j l l - j 2 时，因为叱( ) + 叱( 甜j 口) 2 胛+ 七一e ( 门，七) ，因此e ( 刀，后) = 1 ，进而 如( 甜1 ) + 露( “，) = n + k 一1 ， 8 ( 2 ) ( 3 ) ( 4 ) 硕士学位论文 m a s t e r st h e s i s 并且 a n b l = i e ( f ) i ， ( 5 ) a u b = 1 ，p - 1 】。 ( 6 ) 如果u ：e ( f ) ，则1 彳n b ，从而材p e ( g ) ，与假设矛盾。这说明对任何 满足( i ) ，( i i ) ，( i i i ) 的路p = “l “2 埘，都：f f u , u 2 芒e ( f ) 。 。 设+ 。和u j u j + i 是p 上两条不被其它f 边间隔的f 边，坼分别是尸( 小u j ， p ( u j + l ，咋 中第一个f 中点。由( 5 ) 知，f ，a nb ，故坼，u j ( ) ，+ l ，”川( ) ( 如图3 ) 。 图3 如果材，“p e ( g ) ，则“f + l 咋却+ l 哆u s u d “p - 1 是g 中与p 的选取相矛盾的路 ( 如图4 ) 。因此 u s u j 口正e ( g ) ， 特别有s ，因为巧甜p e ( g ) 。 9 ( 7 ) ， ， ， 一 嘶 ， 一 一 一 吩 、 - ， - ， ， ， ， 站“ 嘶 图4 如果”。蚝e ( g ) ，则+ u s u s + r 洲p 是与尸的选取相矛盾的路( 如图5 ) 。因此 “l u x 仨e ( g ) 。 l嘶 z l i + i u s u ju j + i 嘶u p 图5 类似于( 7 ) 与( 8 ) ，可证 n ( u ，) nn ( u p ) y ( p ) ， n ( u t ) n n ( u 。) 矿( 尸) ， ( ( ) u n ( u p ) ) n y ( p ( “州，虬】) = a 。 ( 8 ) ( 9 ) ( 1 0 ) ( 1 1 ) 如果j i + 2 ，则s i + 3 ，由( i i ) 有i + 2 硭aub ，与( 6 ) 矛盾，所以s = f + 2 。 令日= m u 2 u t + l ， 乞2 甜“2 “f + 3 u p 。 令五= ，i l z f ，嘶+ 。e ( g ) ， 墨= ，1 1 ，f + 1 ，u 1 u i + ：e e ( g ) ) ， 则 五n r , 冲，“e e ( f ) ) = ， ( 1 2 ) 否则j ，五n x 使甜i 约+ l ，u i u i + 2 层( g ) 且坼嘶+ l 硭e ( f ) ，而坼+ l u i 嘶“”l “2 u t u “2 u i + 3 一丑， 是g 中与p 的选取相矛盾的路( 如图6 ) 。 1 0 一- 卜_ 卜一，- 。一 甜l蚴 1 + 1ii i + i ，1 i + 2 2 u s 吩 u j + 1i t 吻 ， ，- - - ， 由( 1 2 ) 得 如( ) + 叱( + ：) i y ( 眉) i + i 厶i 。 图6 令互= li + 2 l p - 1 ，u i + 2 u t + i e ( g ) ) ， 则 艺= ，i f + 2 ，p ，q 嘶e e ( g ) ) ， 五n k l i i + 2 l p ，u t u l + e ( f ) ) = 1 2 ， ( 1 3 ) ( 1 4 ) 否则了ic 五r 、艺使u l ，甜，u f + l e ( g ) 且嘶+ l 仨e ( f ) ， u i + l u i u l u l u t - 1 u i + 2 约+ l 嘶+ 2 z i p 是g 中与尸的选取相矛盾的路( 如图7 ) 。 ，- ， ， ， _ 卜_ 卜 i t l 、1 i i + ia i + 2 2 i s u j u j + 1 ，i t i u l + iu r 由于甜p 仨e ( g ) ，所以 k u 艺c i + 2 ，p 一1 】。 由( 1 4 ) ，( 1 5 ) 得 图7 噍( ) + 噍( 坼+ ：) = i 互| + i 艺i = i 置u 匕i + l 五ne ( i y ( 最) i 一1 ) + i 厶l 1 l ( 1 5 ) ( 1 6 ) 注意到s = f + 2 ，由( 1 3 ) ，( 1 6 ) 得 砟( ) + d a u 。) l y ( p ) l + i e ( f ) l 一1 = p + 七一1 。 ( 1 7 ) 又由( 1 0 ) 得 d n ( u 。) + 如( ”，) l h l = n - p 。 ( 1 8 ) 由( 1 7 ) ，( 1 8 ) 得 比( “1 ) + 如( 甜。) n + k 一1 ， 由于u 。萑e ( g ) ，如( “1 ) + 如( “，) n + k 一1 ，所以 如( “1 ) + 比( ) = n + k - 1 。 ( 1 9 ) 令置= ，i l ，p 一1 ，约蚝e ( g ) ， 匕= ll l p - 1 ，u 1 e ( g ) ) ， 则墨ne ll l p - 1 ，嘶+ l e ( f ) ) ， ( 2 0 ) 否则j ，墨n 匕使嘶+ l u s ，u i u p e ( g ) ，爿f _ r u ，“萑e ( f ) 。 情形1 ：，i 由于“e ( f ) ，所以， i d = z i s u 州h i l l ，“，_ 1 1 l t + 1 咋为过e ( f ) ne ( ) 中所有边的圈，f i , = 咋+ 。“l u j + l 为 起始边是f 边的路，并且舅u d 包含y ( f ) ( 如图9 ) 。由于矿( p - ) n 矿( d ) = 甜川) ， 1 2 硕士学位论文 m a s t e r st h e s i s 眉t j d 中有一条起始边为坼约+ 。的过f 的路，与p 的选取相矛盾。 - - _ i - - - - - - - 。- - - ，- ，- - 产s - 1 + - 乒卞运乡 ， ，j - - 。- ，- 综上所述，( 2 0 ) 为真。由( 2 0 ) 知 砟( 蚝) + 砟( ) = i 墨| + | 匕i = i 五u 巧i + l 五n 匕i j 【1 ，p l 】l + j e ( f ) l =p-i+后，(21) 又由( 9 ) 得 “( u s ) 4 - 以( 甜p ) 甩一p ， ( 2 2 ) 由( 2 1 ) ，( 2 2 ) 得 ( “。) + ( “p ) n + 七一1 ， 由于“，甜p 茌e ( g ) ，如( “，) + 吒 j 口) 胛+ 七一l ，所以 蟊( “，) + 如( “p ) = n + k 一1 。 ( 2 3 ) 由( 4 ) ，( 1 9 ) 和( 2 3 ) 得 2 ( d o ( u 。) + 吃( “，) + 叱( 甜p ) ) = 3 ( 甩+ 七一1 ) 。 因为e ( n ，k ) = 1 ，所以玎，k 奇偶性相同，故上式等号两边奇偶性不同，显然矛 盾。 所以反证法的假设不成立，定理1 1 成立。 ： 硕士学位论文 m a s t e r st h e s i s 定理1 2 设k = t = 1 ，g 是阶刀k + f 的图，f 是g 中( 七，f ，f 一七) 线性森林。如果 ( g ) 之以+ k ，则g 中存在过f 的长度不大于4 的圈。 证明：因为c r 2 ( g ) n + 后，g 中任意两个不相邻顶点之间至少有k + 2 个公共邻点。 k = t = 1 时，不妨设e = 叫是f 中的唯一边。假如x 和y 有公共邻点，则p = x y 在长 度为3 的圈上。如果x 和y 没有公共邻点，不失一般性，设z 是与x 相邻而与y 不 相邻的点，则z 和y 至少有2 个公共邻点，此时e 在长为4 的圈上。可见，f 要么 在长为3 的圈上，要么在长为4 的圈上。- 定理l - 3 设k = f 1 为整数，g 为阶7 1 k + f 的图，f 为g 中的( 尼，f ，0 ) 线性森林。 如果g 中存在长度为厂疗一l 的过f 的圈，并且 ( i ) c r 2 ( g ) n + k ，k = l 时， ( i i ) 吼( g ) n + k e ( n ，七) ，k 2 时， 则g 中存在长为，+ l 或，+ 2 的过f 的圈。 证明：用反证法。假设g 中不存在长为r + l 或，+ 2 的圈过f ，设d = v , v 2 咋h 是g 中过f 的长度为，n - 1 的圈，h = g - d a 。由于( g ) n + k - i ，g 为( k + 1 ) 一 连通图，不失一般性，设q z 为g 中连接d 和h 的边，并且m 吃萑e ( f ) 。由假设可 知，屹z 仨e ( g ) ，并_ 1 1n ( v 2 ) nn ( z ) c 矿( d t ) 。因此最= v 2 v 3 v p v , z 是g 9 z - tf 的长 为，+ 1 的路。( 如图1 0 ) 1 4 硕士学位论文 m a s t e r st h e s i s 图1 0 设p = “：坼+ 。是g 中一条路，满足 ( i ) e ( 尸) e ( f ) ，矿( p ) 三v ( f ) ， ( i i ) 在( i ) 的前提下，iu 。“：) n e ( f ) i 最大。 注意到，p o = v 2 嵋5 , v , z 为g 中满足( i ) 的路，所以上面选择的路p 是存在的。 如果u l u ，+ l e ( g ) 或者u l ，u ，+ l 在h = g y ( 尸) 中有公共邻点z ，则存在过f 的 长为r + l 的圈1 , i l z 2 “，+ i u i ，或过f 的长为r + 2 的圈“2 剧，+ l z u l ，故假设嘶甜，+ l 仨e ( g ) 且( ) 厂、( 甜川) = f 2 j 。因此， 如( ) + 如( “，+ ) 例= n - r - 1 。 ( 2 4 ) 令爿= 帅r ，u l u j + l e ( g ) ) ， b = j f l j ，u j 。e ( g ) ， 贝l j d n b c j u j 吩+ 。e ( f ) ) ， 否则 ，an b ：f f 芝u l 甜j + i ，“”，+ l e ( g ) h _ u j u p l 诺e ( f ) ，而“2 “”川u r u j + l u i 是过f 的长为，+ 1 的圈f 如图1 1 ) 。 1 5 图1 1 于是砟( ) + 砟( 甜，+ 。) = h + 例 = i a u b l + l a n b i | 1 ，厂州e ( f ) i =r+k，(25) ( 2 4 ) + ( 2 5 ) 得 比( 甜1 ) + 磊( “，+ 1 ) n + k 一1 。 ( 2 6 ) ( i ) k = 1 时，( g ) 刀+ 七，显然与( 2 6 ) 矛盾。 ( i i ) k 2 时，吒( g ) n + k - e ( n ，后) ， 因此e ( ，z ，七) = 1 ，进而 叱( 甜1 ) + 蟊( ，) = n + k 一1 ， ( 2 7 ) 并且 i a n b l = f e ( f ) i ， ( 2 8 ) a u b = 1 ，】。 ( 2 9 ) 如果u ：e ( f ) ，则l a nb ，从而”，+ l e ( g ) ，与假设矛盾。这说明对任 何满足( i ) 的路p = i g l u 2 1 , t r + l 都有u 2 萑e ( f ) 。同理“，“，+ l 仨e ( f ) 。 l g i u i + 。和甜叶+ l 是p 上两个不被其它f 边问隔的f 边，f y f - r j - i 最d 、。 因为“，“，+ l 岳e ( f ) ，所以， ，。令= u i + 2 ，= 吩+ 2 。由( 2 8 ) 知，an b ， 因此珥，甜n ( u ，+ i ) ，u t + l ，甜j + 1 n ( u 1 ) ( 如图1 2 ) 。 1 6 硕士学位论文 m a s t e r st h e s i s 图1 2 类似于定理1 1 中的( 7 ) ，( 8 ) 讨论可知，材l ，u s ，1 2 r + l 两两互不相邻。 因为“，“，+ l e ( g ) ，所以s j ，说明u i u i + l 和u j l l j + l 之间必定有中间点。由一f 的 最小性，u j + 2 u j + 3 仨e ( f ) ，所以扰，+ 2 仨y ( f ) 。故 ) n ( ) = a ， ( 3 0 ) 否则了z ( 材，+ 1 ) r 、虬( “。) ，当，歹+ 2 时，u i + l “f “，+ l “1 1 s z u ，+ l “，材，+ 3 是g 中与 p 的选择相矛盾的路( 如图1 3 ) ；当，= j + l 时，1 “，+ l u u s z 是g 中与尸的选 择相矛盾的路。所以( 3 0 ) 为真。 下证，( ) r 、( 甜。) = f 2 j ， 图1 3 ( 3 1 ) 否贝0 jj ， 0 ( ) n _ ( “，) 。因u r u ，+ l 仨e ( f ) ，故v ；+ l 萑v ( f ) ，从 u i + l 甜，甜l y z z f ，+ i “， 是g 中与尸的选择相矛盾的路( 如图1 4 ) 。所以( 3 1 ) 为真。 1 7 硕士学位论文 m a s t e r st h e s i s 材iu i + 15 + 2吩吩 1 啦2 丐+ 2 图1 4 由( 3 0 ) ，( 3 1 ) 知 九( z f l ) + 如( 甜，) r t - r - 1 ， 办( u s ) + 九( “，+ 1 ) ，l 一厂一1 。 类似于定理1 1 中( 1 7 ) ，( 2 1 ) 可证 ( 3 2 ) ( 3 3 ) 以( “1 ) + 砟( “，) ，+ 七， ( 3 4 ) 砟( m 。) + 砟( ”，+ i ) r + k 。( 3 5 ) 由( 2 7 ) ，( 3 2 ) - - ( 3 5 ) n - t 得，2 ( d 0 ( 甜。) + d 0 ( “，) + d 0 ( “，+ 1 ) ) = 3 ( 门+ 七一1 ) ，与e ( 门，尼) = l 矛盾。故定理1 3 成立。特别的，当g 中存在过f 的圈e 一。时，一定存在过f 的圈 g ，即过f 的哈密顿圈。_ 定理b 设七= f 1 为整数，g 为阶刀k + t 的图，f 为g 中的( 尼，t ，o ) 线性森林。如 果 ( i ) 吒( g ) 刀+ 后，k = 1 时， ( i i ) c r 2 ( g ) n + k e ( 刀，后) ，k 2 时， 则对任意，| m a x 4 ，k + 2 t ，刀 ，g 中存在长为，或，- + 1 的圈过f 。 证明：由定理1 1 和1 2 可知，g 中存在长度不超过m a x 4 ，k + 2 t ) 且过f 的圈，设 为巳。要证明定理b ，只需证明，时，g 中有长为厂或，+ 1n n r if 即可。 用归纳法证明。显然，- = 时，结论成立。 假设对给定的一个，- ，结论成立，下面证明结论对，+ 1 也成立，即证明存在c ， l r ， ， ， ， ， ， 一 - ， z， ， ， ， 硕士学位论文 m a s t e r st i t e s i s 或c + ：过f 。由假设可知，存在长为，或r + l 的圈过f ，如果不存在长为r + l 的圈 过凡则存在长为，的圈过凡再由定理1 3 可知，一定存在长为，+ 2 的圈过f 。特 别的，当，= n 时，g 中有过f 的长为n 的圈，即过f 的哈密顿圈。i 3 2 定理a 的证明 论。 当f 是一般的( k , t ，0 ) 一线性森林时，借助于定理b ，我们可以得到更普遍的结 定理a 的证明：当f 最+ 。时，设g 是含f 的n 阶图，吼( g ) n + k e ( 阼，七) 。考虑 图g ，在g 中去掉f 的路上所有内部点，再用一条单边路替代被去掉内部点的路， 得到g 。不妨设去掉了后一k 个内部点，这样，线性森林f 变成( 七，t ，0 ) 一线性森林f ， h e 。只含长度为l 的路，即f 。是( 七，k ，0 ) 一线性森林。因为g 的阶为刀i - 刀一k + k ， e ( 刀，七) = e ( 以- k ，o ) = e ( n - k ，o ) = e ( n ，七) ，所以吒( g ) n + k e ( n ，后) 一2 ( k 一尼- ) = 行+ 后- e ( n ，尼i ) 。由定理b 可知，对任意，m a x 4 ，k + 2 t ) 且，疗，g 中有长为， 或，+ 1 的圈过f 。在g 中将f 的每条边还原成g 中相应的路，则由g 中过f 的 圈得到g 中过f 的圈，同样，对任意，i m a x 4 ，k + 2 t ，乃 ，g 中存在长为，或，+ l 的圈过f 。 当f = 忍+ 。时，c r 2 ( g ) ，z + 七，类似的讨论，结论成立。l 1 9 硕士学位论文 m a s t e r st h e s i s 结束语 定理a 是一个关于( 后，f ，0 ) 线性森林的结论，这时线性森林并没有孤立点，但 是定理1 1 和1 2 证明了过( 尼，f ，卜- 七) 线性森林的圈的存在性，我们猜想定理1 3 可 能对( 七，t ，t 一后) 线性森林也能保持结论成立，如果这个猜想能被证明是真，则可以 将定理a 和b 推广到( 七，f ) 一线性森林的情况。 图g 的( 七，f ) 一哈密顿性是其( 后，f ，k + 2 f ) 一泛圈性的必要条件，定理8 中的图首 先应该满足定理7 中的吒( g ) 条件，令人感兴趣的问题是，定理8 是否和定理7 一 样有最好可能的( g ) 条件。事实上，r a l p hj f a u d r e e 等人已经提出如下猜想。 猜想1 设k ，t 和，z 是正整数，满足2 k + t 刀，g 是以阶图，f 是( 七，f ) 一线性森 林。如果 ( i ) o 2 ( g ) 疗+ 七，当f = 丑+ l u ( t - 1 ) k 1 ，并且 ( i i ) c r 2 ( g ) n + k - e ( n ，后) ，其它情况， 贝i jg 是( 后，f ，2 f + k ) 泛圈的。 上述猜想的实质就是对每个【七+ 2 f ，n _ l l ，t j ，g 中都存在过( 后，f ) 一线性森林的长 ，的圈，如果猜想成立，则是一个比较完美的结论。今后，我们将对猜想1 及其相 关问题进行继续的探讨。 硕士学位论文 m a s t e r st h e s i s 参考文献 【l 】1 r d i e s t e l ，g r a p ht h e o r y , 2 n de d i t i o n ，s p r i n g e r , 2 0 0 0 【2 】c ta d i r a c ，s o m et h e o r e m so na b s t r a c tg r