（运筹学与控制论专业论文）图中存在独立圈及指定条件因子的度条件.pdf

山东大学博士学位论文 图中存在独立圈及指定条件因子的度条件 高云澍 山东大学数学学院 运筹学与控制论 摘要 图论的研究始于2 0 0 多年前关于图论的第一篇论文是1 7 3 6 年e u l e r 发表的， 他用图的方法解决了哥尼斯堡( k j n i g s b e r g ) 七桥问题二十世纪六十年代以来，图 论在科学界异军突起，活跃非凡图论中有很多著名的问题，如哈密尔顿间题，四 色问题，中国邮递员问题等并且，应用图论来解决化学，计算机科学，生物学等 学科问题已显示出极大的优越性图论作为离散数学的一个重要分支，受到了各 方面的普遍重视 本文考虑简单有限图，这些图不包含环以及重边设g 表示一个简单图哈 密尔顿圈问题是图论中非常著名的问题之一图中过每个顶点的圈，称为图的 哈密尔顿圈图的哈密尔顿圈问题，是图论中的一个非常著名的间题图g 中 的k 因子指的是图g 中的k 正则子图，这里k 是一个正整数关于k 一因子的存在性， 应用t u t t e 的定理，人们得至i j 了许多有意义的结果，然而，在本论文中，我们主要关 注2 一因子的存在性显然，一个哈密尔顿圈可以被看成是仅有一个分支的2 因子 因此，对于给定的图，找到2 一因子存在性的条件是很困难的过程常用的技巧是先 找出一个顶点数目极小的包装，然后扩充成为2 因子 本文研究了图论中的几个问题，具体地，我们研究了包含哈密尔顿圈的k 一因 子存在性问题，图g 中相互独立的子图( 特别是圈) 以及2 一因子的存在性条件上述 问题可以概括地描述如下：设f 是具有给定结构的连通子图，七是一个正整数，保 证顶点数目满足i v ( g ) i k l v ( f ) i 的图g 中包含k 个点不相交的f 存在的最小度条件 或者不邻接的最小度和条件是多少? 上述问题是极值图论中的很基本的问题对 于非完全图g ，定义c r 2 ( g ) ：= m i n d g ( x ) - i - 如t y ) l x y 譬e ( g ) ) ；如果g 是一个完全图， 令c r 2 ( g ) ：= 全文共分为八章第一章，我们给出了一个简短而又相对完整的 引言首先，我们给出了一些基本的术语和定义然后，我们介绍了2 一因子理论及 独立圈理论的背景和进展最后，我们列出了本文的主要结果 山东大学博士学位论文 在第二章，我们给出了包含哈密尔顿圈的k 因子的度条件设k 为满足k 2 的 正整数，并且设图g 的定点数目n 足够大如果砌为偶数，图g 中的最小度至少 为k 并且m a x d 6 ( x ) ，如( ) ，) l ( r t + a ) 2 对每一对不相邻接的工和y 都成立，这里， 当k 为奇数时，口= 3 当k 为偶数时，口= 4 我们证明了图g 中存在一个k 因子( 亦 即七一正则子图) 包含任意给定的哈密尔顿圈c ，只要g e ( c ) 是连通的通过构造 例子，我们同时说明了度条件是最好可能的以及连通条件是必须的 在第三章，我们考虑二分图g 中存在2 一因子的度条件使得2 因子的每一个分 支为长为4 的圈并且刚好包含一个指定的顶点首先，我们找到了二分图g 的一个 包装，使得每一个分支或者为长为4 的圈，或者为长为6 的圈，然后我们把包装拓展 为需要的2 因子我们的主要结果如下：设k 是一个正整数并且g = ( n ，屹；e ) 是 一个二分图，其中l v l i = l v 2 i = n 2 k - i - 2 如果如( 力+ 如l 华l 对于每 一对顶点x v l 和y v 2 都成立，则对于图g 中任意的k 个不相同顶点z l z k ， 图g 中存在一个2 因子包含k + 1 个相互独立的圈c l ，g + l 使得对于每一 个f l ，k ) ，z i y ( c i ) 并且i c i l = 4 在第四章，我们探索存在2 因子存在的c r 2 ( g ) 条件，使得2 因子每一个分 支为带弦的4 圈事实上，我们证明了如果图g 的阶数r 4 七+ 3 并且0 r 2 ( g ) n + k ，, 贝i j g 中存在2 因子包含k + 1 个相互独立的圈c l ，q + l ，使得对于每一 个f ( i ，k 一1 ，c i 为带弦的4 圈且i c k i 4 紧接着，我们证明了如果图g 的 阶数n 4 k 并且旷2 ( g ) n + k ，则g 存在2 一因子包含k 个相互独立的圈使得其中 的k 一1 个为带弦的4 圈与此同时，我们证明了阶数条件以及c r 2 ( g ) 条件都是最好 可能的 在第五章，我们考虑了关于相互独立的三角形和四边形的包装问题对于 阶数n 3 s + 4 ( k j ) 图g ，其中s 是两个正整数k 使得1 s 毛我们证明了如 果矿2 ( g ) n + s ，则图g 包含k 个相互独立的圈c l ，c 七，使得对于1 4 k 并且o r 2 ( g ) n + k 则g 中存在2 因 子包含七个相互独立的圈使得其中的k 1 个为带弦的四边形 在第五章，我们感兴趣的是图中相互独立的三角形以及四边形的存在性，我 们的结果如下 定理5 3 设s 和k 为两个整数使得1 s k 如果阶数为n 3 s + 4 ( k s ) 的图g 满 足c r 2 ( g ) n + s , 贝t j g 包含k 个相互独立的圈c l ，g ，使得对于1 i s ，i c i i = 3 ； 对于5 8 k 2 2 + 1 2 ) k + 3 a + 1 6 的 图，其中，当七为奇数时口= 3 ；当七为偶数时口= 4 如果加为偶数，6 ( g ) 忌并 - 臣c r 2 ( g ) n + 口则g 中存在k 一因子包含给定的哈密尔顿圈 在本章中，我们改进了定理2 5 定理2 6 ：设足2 为整数，g 为阶数n 1 2 ( k 一2 ) 2 + 2 ( 5 一o ) ( 足一2 ) 一口的图，其中， 当七为奇数时口= 3 ；当七为偶数时口= 4 如果砌为偶数，6 ( g ) 忌并且对g 中每一对 不相邻的顶老u c w v ，m a x d ( x ) ，d ( y ) l 伽+ a ) 2 则g 中存在k - 因子包含给定的哈密 尔顿圈c 只要g e ( c ) 是连通的 本章主要结果发表在d i s c r e t em a t h e m a t i c s ，3 0 9 ( 2 0 0 9 ) 2 3 7 3 2 3 8 1 7 山东大学博士学位论文 2 2 主要结果 为了得到主要结果，我们首先给出t u t t e 的确保图中存在k 一因子的定理 定理2 7 ：( t u t t e 【7 2 1 ) 设g 为图忌1 为整数则图g 包钒一因子当且仅当 o c ( s ，t ，j i ；：) = j i = i s l + ( d g - s ( 曲- k ) - h g ( s ，t ，七) 0 r e r 对于y ( g ) 的所有点不相交的子集和s 和丁都成立，这里 g ( s ，l 七) 表示g 一( s u 丁) 中 的分支d 的数目，使得k i d l + e g ( y ( d ) ，t ) 兰1 ( m o d2 ) 另外，不管g 中是否有k - 因 子，对于y ( g ) 的所有点不相交的子集和s 和丁，我们始终有钻( s ，t ，k ) 三k i v ( g ) i ( m o d2 ) 我们称上述定理中的分支d 为奇分支令t o ( g ) 表示图g 的分支数并且 令d ( g ) 表示图g 中含有奇数阶数的分支个数我们先给出几个命题 命题1 如果定理2 6 的条件是满足的，k 3 并且对于g 中的任意哈密尔顿 圈c ，g e ( c ) 是连通图则对于acy ( g ) ，t o ( g e ( c ) 一a ) i a i + 1 ，除非七= 3 并且g 中存在3 一因子包含c 证明：令h ：= g e ( c ) 假设存在acy ( g ) 使得t o ( h a ) i a l + 2 如果a = 0 ， 显然矛盾因此，不妨i l 4 o 令c l ，c 2 ，c 甜为h a 的分支不失一般性，不 妨i 殳1 c l i i c 2 i l e l 由于h 是连通图并且根据假设，山2 ，因此存在 点置v ( c f ) 使得n ( x i ) n a o ，这里f 1 ，2 ，u ) 我们断言粗在工f ，x i x l ，x 2 ，x i a i + i l 使得工，和殉是不相邻的要不然，我们 不妨设在圈c 中，v ( c 1 ) 中的所有点跟y ( c 2 ) 的点都相邻并且i c l i i c 2 l 2 如 果i a i 2 ，贝, l t o ( n a ) 4 如果i c 2 i = 2 ，则对于u l y ( c 1 ) ，e c ( u l ，y ( c 2 ) ) = 2 并 且对u 3 y ( c 3 ) ，h 1u 3 岳e ( g ) 如果i c 2 i _ 1 ，今l u ll = v ( c o r x 及l u ：) - - y ( c 2 ) ， n u l u 2 e ( g ) 因此，存在u 3 v ( c 3 ) 使得u l u 3 叠e ( c ) 或者u 2 u 3 叠e ( c ) 从而， 只需考虑i a l = l 并且u ( 日一a ) = 3 显然，i c i i = 1 并且i c 2 i 2 ，记a = z ) 如 果i c 2 i = 1 ，则y ( c 2 ) = x 2 根据x l 和x 2 的对称性，沿着圈c ，存在两种类型的结构， 分别见图1 和图2 ，这e v ( c 3 ) = v ( p ) u “1 如果i c 2 l = 2 ，i e - , v ( c 2 ) = x 2 ，) 因此， 根据z e ( g ) 或者z 莹e ( g ) ，存在三种类型的结构，这e v ( c 3 ) = v ( p ) u h ) ， 8 山东大学博士学位论文 z 图2 1 t y p e1 z 图2 2 t y p e2 见图3 注意到在每一种情况下，由于如( 工1 ) = 3 ，则七= 3 ，此时口= 3 另 外，注意到型2 不会出现由于n 是偶数，则对于每一对不相邻的点w l ，w 2 y ( 娜，m a x l d h ( w 1 ) ，d h ( w 2 ) 墨，由定理2 2 ，g e ( c ) 包含哈密尔顿圈，于是g 包 含两条边不相交的哈密尔顿囹由于，l 是偶数，g 一层( c ) 包含i 因子，记为厂则， e ( c ) u 厂构成了3 一因子使得其包含c z 图2 3t y p ei x z 图2 5t y p e2 c 3 五 9 z 图2 4b p ei 山东大学博士学位论文 由上面的断言以及定理2 6 的条件，不妨设_ ，在日中的最小度至少；碧jn + t 。r - 4 从而 掣妇( 巧) i v ( c j ) l 一1 + i a i 于是，对于每一个i 工都有 i v ( g ) i 掣一陋l + 1 考虑到j 陋i + 1 t , x g t 3 口4 ，我们得到 n ， i a i + b 4 1y ( g ) + 1 , 4 1 + 2y ( c f ) 2 i a i + 2 ( 掣一k 4 1 + 1 ) ：n + 1 y ( g ) + y ( c f ) + 2 ( 竿一1 ) = n + 1 i f - 盾c 。1 命题2 设g 为满足定理2 6 的图如果对于g 中的任意哈密尔顿圈c ，h = g e ( c ) 是连通图并且k 3 则g 中存在3 因子包含哈密尔顿圈c 证明：假设对于任意给定的哈密尔顿圈c ，g 中不存在3 因子包含c ，则g e ( c ) 不包含1 因子根据- t u t t e 的1 因子定理 7 3 1 ，存在子集acy ( g ) 使得o ( h a ) i a i 根据定理2 6 的条件，3 n 是偶数， 就与命题1 矛盾 于是，l 为偶数a k 而o ( h a ) i , 4 i + 2 ，这 口 命题3 设gg 为满足定理2 6 的图如果对于g 中的任意哈密尔顿圈c ，h - , - g e ( c ) 是连通图并且k 3 则对于任意的0 a y ( h ) ，w ( h a ) i a i + 5 一口， 除非| | ：= 3 并且g 中存在3 因子包含c 证明：很明显可以由命题1 得到 口 定理2 6 的证昵反证由定理2 2 ，图g 包含哈密尔顿圈，因此k 3 令h ：= g e ( c ) ，p ：= k 一2 注意到在下面的证明中，对于每一个哈密尔顿圈c ， g e ( c ) 是连通图显然，y ( 日) = y ( g ) 并且p 1 ， a n ( x ) = d ( x ) 一2 p f o ra l l 工y ( 日) ， ( 2 - 1 ) 1 0 山东大学博士学位论文 由于c 为g 中的哈密尔顿圈，我们有 m a 】【i 妇( “) ，t i n ( v ) 掣 对于每一对不相邻的点“，v y ( 奶都成立( 2 2 ) 二 显然，g 中存在期望的因子当且仅当日中存在p 因子假设日中不存在这样的因子， 则根据定理2 7 ，存在y ( 日) 的两个点不相交的子集s 和丁使得 o n ( s ，l p ) = p l s l + ( 缸s ( x ) - p ) - h n ( s ，t ，p ) - 2 ( 2 - 3 ) j 丁 我们选择s 和丁使得i 丁i 尽可能小，在此前提下i s l 尽可能大另外，我们选 择p 使得其尽可能地小 由命题2 ，我们看到日中存在1 因子因此在下面的证明中，p 2 断言1 1 t l 例s + 1 证明：我们首先证明日中存在p 一2 ) 一因子如种= 2 ，很显然是对的因此不妨 设j d 3 根据p 的取法，日中存在p 一2 ) 因子由定理2 7 ，我们得到铅( s ，t ，p - 2 ) 0 根据奇分支的定义，注意g , j h n ( s ，l p ) = h n ( s ，t , p 一2 ) ，于是一2 铅 ，l p ) 一 o n ( s ，t ，p 一2 ) = 2 i s i _ 2 1 t i ，这就意味着i t i i s l + 1 口 由断言1 ，很明显得到丁0 断言2 2 i s i n 一印+ 口一3 证明： 假设2 i s l n 一印+ 口一2 ，亦即，n 一2 i s i 6 p 一口+ 2 则i 丁i l s i = n 一2 i s l i v ( h ) 一( su 丁) l 6 p 一口+ 2 一h n ( s ，t ，p ) 由( 2 3 ) ， d n - s ( x ) p i t i - p l s l + h n ( s ，丁，p ) - 2 x e t p ( i t i i s l ) + h n ( s ，t ，p ) 一2 p ( 6 p 一口+ 2 一h n ( s ，t ，p ) ) + h h ( s ，t ，p ) 一2 p ( 6 , o a + 2 ) 一2 ， 山东大学博士学位论文 由于刀 1 2 p 2 + 2 ( 5 - a ) p - a ，我彳f 得到j 丁i i s l + 1 一印+ 譬 6 p 2 + ( 3 一a ) p 2 结合断言1 ，我们有 艇丁妇一s ( x ) ，j d ( 6 p o + 2 ) 一2 百旷 丌j 一 j d ( 6 p 一口+ 2 ) 一2 冬_ 丌j 一 1 2 p ( j 6 p - 而a 百+ 2 ) - 4 1 印2 + 2 ( 5 一a ) p a 从而 幽一s ( 曲i t i - 3 ( 2 - 4 ) 记t o = 协t i 妇一s ( 力= o ) 则由断言1 1 - f f n l s i - i - l t l 2 1 s i + 1 因此，当，l 为 偶数时，n 2 i s l + 2 由a 的定义以及砌是偶数，我们得到，l 2 1 s i + 2 当口= 3 时；并 且，l 2 i s i + 1 - 3 口= 4 时在任何一种情况下，对任意的x t o ，都有妇( 曲l s l 下n + a - 4 由不等式( 2 4 ) 得到i t o i 3 ，于是存在两个点工和y t o 使得x y 垡e ( g ) 从而 丁n + a m a x d ( x ) 加) ) i s l + i n c ( x ) l n + 1 秀碴 断言7 g 【丁】是图g 中的完全子图 口 证明：如果对于x ，y y ( 丁) ，x y 垡e ( g ) ，我们不妨设d ( 曲n + f a ，则由断言3 与断 言6 ， 半d ( 力p ( x ，s ) + a u - s ( x ) + 2 i s l + p 一2 + h h ( s ，t , p ) + 2 p + 4 + i s i 注意到p 2 ，由断言2 ，n + 口2 g o + 4 + l s l ) 2 p + 8 + n 一6 p + o 一3 = n + 口一和+ 5 - i s l - h n ( s ，t ，p ) - 1 从而矛盾因此不妨 设i 丁i p 则i t i = p 或者p + 1 由断言7 ，对于任意的x t ，妇一s ( x ) d r ( 工) p 一3 ， 这意味着p 3 如果e h ( u ，t ) p 一4 ，则l s i 4 根据断言7 ，g 丁】是完全图， 则旧( g 【丁 ) l = i t i ( i t l 一1 ) 2 由于c 为哈密尔顿圈，i e ( g 丁】) i 1c l l t i 一1 因此， 妇一s ( x ) 2 i ( g 【丁】) e ( c ) i 1 4 山东大学博士学位论文 l t i ( i t i 一1 ) 一2 ( i t i 一1 ) = ( i t l 一1 ) ( i t l 一2 ) 从而，由断言6 j x 及i s l 4 我们得到 o n ( s ，t ，p ) = p l s i + ( d h - s ( x ) - p ) - h n ( s ，l 力 艇r p l s i + ( i t i 一1 ) ( i t i 一2 ) - p i t l h n ( s ，瓦p ) 4 , o + i t i z 一( p + 3 ) i t i 一2 = ( i t i 一3 ) ( i t i 一力+ p 一2 ( 2 5 ) 注意到p 3 ，如果i t i = p ，则眙岱，r ，p ) 1 ，与( 2 3 ) 矛盾因此，l t i = p + i ， j 勘j l t i 3 ，如果联合( 2 5 ) ，我们有锯( s ，l p ) 1 ，矛盾从而，e n ( u ，z ) = p 一3 如 果i t i = p + 1 ，则据断言7 ，对x t ，a n - s ( x ) p 一2 由于i e ( g 【刀) nc i i t i _ 1 ， 于是( s ，t ，p ) 即一p 一1 ) 一8 = 劲一7 一1 ，与( 2 3 ) 矛盾这样，我们只需 考虑i t i = p ，由断言7 ，对于任意的x t ，d u - s p 一3 注意到日是连通图并 且j d 3 ，从而，鼬( s ，t ，p ) 助+ c o 一3 ) c o 一2 一p ) 一1 0 = p 一4 - 1 ，与不等式 ( 2 3 ) 矛盾我们完成了断言8 的证明 口 根据断言6 ，h n ( s ，t ，p ) 4 我们通过下面的四个断言来完成定理的证明 断言a h h ( s ，t ，p ) 4 证明：要不然，由断- 9 8 ，2 i c l i l c 2 i i c 3 i l q i ，因此存在u l y ( c 1 ) 以 * u 2 y ( c 2 ) 使得蹦l “2 星e ( g ) 如果d ( h 1 ) 丁n + o r ，则据断言1 ，断言2 以及断言5 ， n i s i + l t i + l c i i + i c z i + l c 3 i + i c 4 i 2 1 s i + 1 + 4 l c l i 2 i s i + 1 + 2 ( n 一2 i s i 一印+ 口+ 2 ) n + 1 矛盾从而，d ( u 1 ) n + 1 。 断言b h h ( s ，t ，p ) 2 口 证明：反证假定b ( s ，丁，力= 2 首先我们证明m l = r a i n 妇- s ( x ) l x t ) p 要不然，m 1 = p + 1 ，由不等式( 2 3 ) ，2 = h l y ( s ，t ，p ) p l s i + ( m l p ) i t i + 2 ，从 而sut = 0 ，矛盾于是，m l p 考虑至, l l s l + 妇一s ( x 1 ) 6 ( p ，贝 l l s i p m 1 联合( 2 3 ) ，我们有 2 = h i - k s ，t ，p ) p l s i + ( ，竹l 一, o ) l t i + 2 j d ( p m 1 ) + ( m l p ) i t i + 2 = ( p m 1 ) ( p i r l ) + 2 2 ( 2 - 6 ) 考虑到p m l ，上述不等式当i t l p 时成立除非例= p + 1 当l t i = p + 1 ，由断 言7 ，m 1 i t i 一3 = p 一2 显然，m l p 一1 如果i s l = 0 ，贝 l m l = p ，从而不等式 ( 2 - 6 ) 仍然成立因此，l s l 1 如果i s l = 1 ，则m l p 一1 由断言8 以j 3 l t 的极小性， o h ( s ，t ，p ) p + ( p + l 一2 ) ( j d 一1 一p ) + 2 ( j d p ) 一2 = p p 一1 = - 1 ，与( 2 3 ) 矛盾 从而，i s i 2 由断言8 以及丁的极小性，眙( s ，丁，p ) 劲+ p + 1 3 ) ( i d 一2 一p ) + 3 ( p 一1 一j d ) 一2 = - 1 ，与( 2 3 ) 又一次矛盾 所以，由不等式( 2 - 6 ) 可以得到p m 1 ) 一l t i ) = 0 这意味着i s i + m l = p 并 旦p = m l 或者p = l t i 注意至 j l r l m l + 1 p + l ，当i t i = p 时，m l = p 一1 或者p ，此 时i s l = 1 或者i s i = 0 我们考虑下面两种情况 恃形俾j 俐= 1 ，i t i = p 并且对任意的x t ，d h s ( 曲= p 一1 此时，对于任意的工t ，半 d ( 曲p 一1 + i s l + i n c ( x ) 1 根据断言7 ，g 丁】为 完全图，则p g ( 丁，h 一( su 丁) ) = 0 ，从而，对任意的“l v ( c 1 ) ， d ( “1 ) ! 二掣一l + i s l + i u c ( “1 ) i = 半 d 1 ) = m l + i n c ( x o i = p - i - 2 另一方面，由断言7 ，不等 式( 2 - 3 ) 以及对任意的x t ，d n = p ，存在至多一个点坳y ( c j ) o = 1 或 者2 ) 使得u j 盹( 力o 丁) 由断言8 ，i c l i 2 ，于是我们可以找到) ，y ( c i ) 使 得x y 岳e ( 脚类似于情形( b 1 ) ，我们有 a n ( y ) 生婴塑一1 + i s i = 气半 n + 1 ( 2 7 ) 矛盾i n 9 r l d ( u 1 ) 1 2 p 2 + 2 ( 5 一口汩一口，我们得至 n - l s u t u c l i 0 9 + 3 ) 6 0 + 1 ) + 1 艇r 如一s ( x ) + 1 于是存在u 2 v ( g ) su t u c l 使得e g ( u 2 ，t ) = 0 由于p 2 ，根据断言7 和( 2 8 ) ，d ( x ) = i t i 一1 p + 3 n + 1 ， 上述矛盾意味着m = 2 或者3 如果是前者，我们将证明l s | - 0 要不然，设圳1 如果m l = p 或者j d + 1 ，由于p 2 ，x x 而o ( s ，t ，j d ) p l s i + ( m l - p ) i t i - - h h ( s ，t ，p ) p 一3 一1 ，与( 2 3 ) 矛盾于是m 1 p 一1 ，由丁uc 1 n o ( x ou 协1 ) ，我们得到 丁i + 2 i tuc 1 l 妇一s ( x 1 ) + i x 1 ) i + i 0 ( 工1 ) f l ( tuc 1 ) i m l + 1 + 2 p + 2 ( 2 9 ) 有上式得到i z i p 首先假设i 丁i = p 则i c l i = 2 ，m l = j d 一1 并- 目- i n c ( x 1 ) n ( t u c i ) i _ 2 如果i s i 2 ，则眙( s ，t ，p ) p 一3 一l ，矛盾因此蚓= l ，通过类似于情 形( b 1 ) 的讨论，我们导出与( 2 2 ) 矛盾的结论因此只有情形i t i p 一1 如 果i t i p 一2 ，考虑至i j i s i + 幽- s ) 一p 双h ) 一p 0 ，则一2 翰 ，t ，p ) = p l s i + 工r ( 妇一s ( x ) 一p ) 一h h ( s ，t ，p ) 2 1 s i + 艇r ( 1 s i + 巧日一s ( d p ) 一h n ( s ，t ，p ) 2 1 s l h n ( s ，t ，p ) 2 i s i 一3 一1 ，与( 2 - 3 ) 矛盾因止匕i 丁i = p 一1 则一2 o h ( s ，t ，p ) = l s l + l r ( i s i + 巧日一s ( 曲p ) 一j z 月( s ，t ，p ) j r ( i s l + d 日一s ( 石) p ) + l s i 一3 l s i 一3 一2 ， 这就说明对于任意的x t ，i s i + d h s ( x ) = p 并且例= 1 特别地，m l = 妇- s ( x 1 ) = p i s i = p 一1 通过类似于情形( b 1 ) 的讨论，我们可以导出矛盾 不失一般性，不妨设“2 v ( c 3 ) 由于s = 0 ，则对于任意的x v ( c 3 ) ，e g ( x ，t ) 0 另一方面，由断言3 ，对任意的x t ，d 白( 工) p + 1 注意 1 8 山东大学博士学位论文 到l g i n - 2 可p + a 一+ 2 p + 1 ，i c l l 2 - ) f - _ e tuc i n o ( x 1 ) u 忸1 ) ，存在1 ，c 3 使 得e g ( 1 ，丁) = 0 ，这就与下列事实矛盾：e g ( x , r ) 0 对任意的工v ( c 3 ) 都成立到 此我们完成了断言c 的证明 n 断言d h n ( s ，t ，p ) 1 证明：否则，由( 2 3 ) ，我们得到 _ p - ， - 1 h h ( s ，t ，p ) 一2 p l s l - i - ：( 谚日s ( 劝- p ) ( 2 一l o ) ：百 如果i t i p ，则由( 2 一1 0 ) 可以得至l j - 1 p l s i + 艇r ( 妇心( 力一p ) 艇r ( i s l + 妇( 曲一力0 ，矛盾因此有i t i = p + 1 如果m l p ，则由( 2 1 0 ) ，- 1 p l s i + 施r ( 如一s ( 功一p ) p l s l ，矛盾a k 而m l p 一1 注意到例+ d h - 8 ( x 1 ) 6 ( h ) p ，则例p m l 1 如果i s i = 1 ，则m l = p 一1 ，由m 1 的定义，对任 意的x y ( 丁) ，谚h - s ( 功p 一1 另外，i e ( g 丁】) nc i i t i 一1 ，则砩f ( s ，丁，p ) p + 6 0 + 1 1 ) ( 9 1 一p ) + ( i d p ) 一1 = - 1 ，这就与( 2 3 ) 矛盾从而l s l 2 由 于g 【丁】是完全图，则i e ( g 【丁】) i = i t i ( i t i 一1 ) 2 又因为c 是图g 中的哈密尔顿圈， 则i e ( g 【丁】) nc i i t i 1 于是 ：妇一s ( 工) 2 1 e ( g t i ) e ( c ) i 备 l t i ( i t i 1 ) 一2 ( i t i 一1 ) = ( i t i 一1 ) ( i t i 一2 ) 由于i s i 2 并且i 丁l = p + i ，则 铅( s ，t ，p ) i s i + ( i t l 一1 ) ( i t i 一2 ) - p i t i h n ( s ，t ，p ) 印一劲一1 = 一1 这就与( 2 3 ) 矛盾 至此，我们完成了定理2 6 的证明 口 2 3 几点注记 注记1 显然，6 ( g ) 忌以及加为偶数为存在k 一因子所必须的注意到定理2 4 不能 用于证明g e ( c ) 中存在正则因子考虑文献【5 8 】中用过的图g = 墨+ 如+ 局+ 2 a 1 9 山东大学博士学位论文 ，这里f 为很大的正整数则g 满足0 r e t y p e 型条件并且对于任意的哈密尔顿圈c ， g e ( c ) 都是连通的注意到6 g e ( c ) k 一2 对于任意的x y ( g ) ，我们有 l t - i - 2 口一1 ，i f 石y ( 墨) ， d ( 劝= ，l l ， i f 工y ( k 五) ， it + 4 0 一1 ，i fx y ( 墨+ 2 口) 尽管如此，g e ( c ) 中存在x ，y y ( 墨) 使得 d g 一以c ) ( 功+ d b 层( c ) ( ) ，) = 2 ( i 墨i - i - i 如1 ) 一2 4 = 2 ( t + 2 口) 一6 = ，z 一6 ， 因此我们不能应用定理2 - 3 于g e ( c ) 来确保存在 一2 ) 因子特别地，对 于y ( 墨) 中任意不相邻的点工和) ，m a x a g e ( c ) ( 工) ，如一e ( c ) ：d ( x ) +一+ 戈匆南 另一方面，很容易看到g 包含三对不相邻的点对 x l ，y 2 ， y l ，x 3 p , ：z 及l x 2 ，y 3 ，则， 艇v t e ) d ( x ) 3 尘乒= 4 n + 1 ，与( 3 - 1 ) 矛盾 口 由g 的选取，存在v 1 ，1 ，v 2 ，比) 使得g 包含k 一1 个可允许的 圈c l c 2 ，g l 关于 1 ，l ，1 ：2 ，魄l 一 v ) 且1 ，仨v ( e i l - ：c i ) 我们选择v 1 ，l ，1 , 2 ，取j 以及k 1 个可允许圈c l ，q l 关于 v l ，v k j _ 1 1 ，) 使得 七一l 俐尽可能小( 3 - 2 ) 扛1 山东大学博士学位论文 注意到 c l ，艮1 ) 中至少有j 1 个4 一圈 在约束条件( 3 2 ) 下，我们选择1 ， v l ，v 2 ，v k 署n k 一1 可允许 圈c l ，c 2 ，q l 关于 v l ，v k ) _ ( v ，使得 ( 3 - 3 ) 在约束条件( 3 2 ) 和( 3 3 ) t ，我们选择1 ，1 1 ，l ，v 2 ，v k ，k 一1 个可允许 圈c 1 ，q ，艮l 关于 1 ，l ，攻l 一 v 以及路p ，使得 a ( v ，p ) 尽可能大 ( 3 - 4 ) 令p = x i x 2 x t 为m 中的最长v 路使得x i v 1 由g 的极大性，m 中存在长 至少为3 的v 路，因此，t 4 不失一般性，设v = v k 且对于每一个f 1 ，2 ，k 一 1 ) ，v i y ( c i ) 记日= 旨g ，则肘= g y ( h ) 并且i 朋i = 2 川显然，m 2 为方便起见，在下面的证明中，分别用丁1 ，乃和q m ，o k 一1 表 示c 1 q l 中z 个相互独立的4 一圈以及k z 1 个相互独立的6 - 圈，记h r = u 名1 乃并且= u k j _ - m iq f ，其中，s z + l k 由于，l 2 s + 3 ( k s ) ， 则n = 2 l + 3 ( k 一1 一d + m 且m z s + 3 令t = 2 r + q ，其中q = o 或者1 我 们的证明包含几个断言 断言3 2 ：t = 2 m ，亦即，p 为m 中的哈密尔顿路 证明：要不然，设t ld ( x ，m r ) 8 1 + 1 2 ( k 一1 一d + s 一1 2 ( k 一1 一d = 8 l + s ( 3 - 6 ) j 劬) 由于s 1 ，则存在乃既使得e ( 巧，p ) 9 由引理3 5