（运筹学与控制论专业论文）图的独立圈和k因子.pdf

山东大学博士学位论文 图的独立圈和昆一因子 颜谨 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) 中文摘要 本文仅考虑有限简单图设g = ( u e ) 是一个图，g 的顶点数l g i = v ，边数 e ( g ) = l e l i 对g 的两个子图g 1 和g 2 ，我们用e ( g 1 ，g 2 ) 表示其一顶点在g i 中另一 顶点在g 2 中的边集，令e ( g 1 ，g 2 ) = i e ( c l ，g 圳特别地，对g 的一个顶点z 我们用 e ( z ，g 2 ) 表示e ( z ，g 2 ) 我们称日为g 的子图如果v ( h ) v ( g ) ，e ( h ) e ( g ) ， 特别地，子图日称为g 的支撑子图，若v ( h ) = v ( g ) 设h 是g 的一个子图， z v ( g ) ，n ( x ，h ) 表示z 在片中的邻集我们令d ( x ，日) = i ( ：e h ) i ，即d ( x 。h ) 是z 在日中的度，d ( x g ) 是z 在g 中的度，一般地，我们用d ( z ) 代替d ( x ，g ) 若 d ( z ) = 0 ，则z 称为g 的孤立顶点g 的最小度用d ( g ) 表示定义： 口o ( g ) = m i n d ( u ) + d ( t ，) ：“”害e ( g ) “， v ( g ) 对g ) 的一个子图u ，c u 1 表示被u 导出的g 的子图g 的一个子图集合称 为是相互独立的或顶点不相交的，如果它们中的任何两个元素在g 中没有公共顶 点设c ，p 分别是图g 的一个圈和一条路，用t ( c ) 和l ( p ) 分别表示c 和p 的长 度，即z ( g ) = j 矿( e ) ；，f ( p ) = f i ，( p ) j - 1 g 的一个哈密顿圈是g 的包含g 中所有顶 点的一个圈g 的一个1 因子是g 的一个1 一正则支撵子图，通常我们称1 因子 为完美对柴显然g 的一个l 一因子是覆盖g 的所有顶点的一个边集合g 的一拿 2 一因子是g 的一个2 正则支撑子图易见2 一因子的每一个连通分支为一个圈对 于二分图g ：( k ，k ：e ) 。定义 d l ，1 ( g ) = m i n d ( x ) + d ( y ) i x h ，y k 口11 l g ) = m i n d ( z ) + d ( y ) l z h ”k z ge 若i k i ：| k i ，则称g 是均衡的设g 和，是定义在v ( g ) 上的整数值函数，并且对 每个。v ( c ) 都有9 ( x ) s ，( 。) ，则g 的一个( g ，) - 因子是g 的一个支撑子图f ，使 得0so ( x ) sd f ( ) ，( z ) 对每个t v ( g ) 都成立若对所有9 ( x ) = ，( z ) = k ，称这 个( 9 ，) 因子为g 的一因子如果对g 的每条边e e ( g ) ，都存在g 的一个( 9 ，) 因子包含它，则称g 是( g ，) 一覆盖的设l y ( g ) k + l ，u 是v ( g ) 的子集，则一 个带缺损u 的上限半“因子是g 的一个支撑子图f ，使得对所有z v ( c ) 一c ， 有d f ( x ) = ，对所有z u ，有d f ( x ) 2k ；一个带缺损u 的下限半因子是g 的一个支撑子图f ，使得对所有。v ( a ) 一u ，有如( 口) = k ，对所有。u ，有 d e ( x ) 其它未见说明的符号与术语请见文献【l 】 山东大学博士学位论文 主要结果 哈密顿圈问题是图论中最著名的问题之一显然，哈密顿圈是含一个圈的2 因 子关于哈密顿国度条件的结果有很多，其中最经典的两个结果由d i r a c 和o r e 给 出 定理1 2 1 ( d i r a ci 3 1 ) 设g 是一个图，其顶点数n23 如果d ( g ) n 2 ，则g 有一个哈密顿圈 定理1 2 2 ( o r e 若g 是一个顶点数n 3 的图，并且口2 ( g ) 芝n ，则g 有一 个哈密顿圈 图的独立圈理论和2 因子理论是图的哈密顿圈理论的推广和延伸，它是图论 中非常有趣的一类问题，也是目前国内外研究的热门课题其理论研究日益成熟和 完善，而且它在计算机科学、通信网络设计中等都有重要应用关于图的独立圈理 论和2 因子理论的研究，主要集中在以下几个方面：图中含指定个数的独立圈和 2 因子；含指定长度的圈的2 因子；图中具有特定性质的独立圈和2 因子等等 本文主要研究了上述几个方面的问题，下面给出本文的主要结果 1 e n o m o t o 独立圈问题的证明 w a n g 在 6 0 中证明了如下结果： 定理211 。鲫设g = ( nk ：f ) 是一个二分图，满足m l = | 2 k + 1 ，其中 l 是一个整数若图g 的最小度d ( g ) + l ，则g 包含个相互独立的圈 e n o l n o t o 提出了下列问题： 问题2 1 2 ：3 = 2 _ ，若把上述结果的最小度条件替换为“d 】l ( g ) 之2 1 l2 ”，或更进 一步地替换为“4 1 i ( g ) 2 k + 2 ”，上述结论是否成立? 我们证明了定理2 1 4 ，解决了上述问题 定理2 1 4 设i 是一个整数，g = ( k ：e ) 是一个二分图，满足m l = i k l 2 k 十1 ，若o 1 1 ( g ) 2 k + 2 ，则g 包含k 个相互独立的圈 2 二分图中的独立圈与路 长为4 的圈称为4 一圈设g = ( h ，k ；e ) 是一个二分图w a n g 在文献 6 0 】中 证明了定理2 2 1 定理2 2 11 6 ( ”设g = ( h ，；刀) 是一个二分图满足i h i = f = 2 k ，其中 是 一个正整数如果g 的最小度至少为k + l ，则g 包含k 1 个相互独立的；圈和 一条长为3 的路，使得这条路与所有这女一1 个4 圈是相互独立的 i i 山东大学博士学位论文 定理2 2 1 中的最小度条件能否用o l , 1 ( g ) 代替? 定理2 2 2 回答了这个问题定 理2 2 2 的证明完全不同于定理2 2 1 的证明 定理2 2 2 设k 1 是一个正整数，g = ( k ，；e ) 是一个二分图，满足1 i = i i = 2 k 如果o l ，1 ( g ) 2 k + 1 ，则g 包含 ：一1 个相互独立的4 一圈和一条长为3 的路，使得这条路与所有k 一1 个4 一圈是相互独立的 附注定理2 2 2 中的度条件是最好的，我们用文献f 6 0 中的例子来说明设k 和m 是两个正整数并且m2k + l _ 设g l = ( a ，日；e 1 ) 和g 2 = ( x ，y ；场) 是两个相互 独立的完全二分图，使得i a l = l y i = l ，i b i = l x l = m 则g ，。由g 1 ，g 2 和在 b 与x 之间相互独立的m 条边构成显然，( 4 u x ，b u l ，) 是g 女。的分划易见 g 女。的每一个圈至少包含两个a u y 中的两个点因为i a u y l = 2 ( k 1 ) ，g t 。不 包含k 一1 个相互独立的4 圈和一条长为3 的路使得这条路与所有这k 一1 个4 圈 是独立的但d ( 。) + d t u ) = 2 k 对g 。中每一对不邻接的顶点。x 和b 都成 立 3 图中的独立圈与路 、 e r d 6 s 和f a u d r e el b l 】猜想如果g 是顶点数为4 的图并且其最小度至少为2 k 。 则g 包含k 个相互独立的4 圈j o h a n s s o n 证明了下面的定理： 定理2 3 i 6 2 】设g 是一个图满足i gj = 4 k 如果5 ( g ) 2 k ，则g 有一个支撑 子图由一1 个相互独立的i 圈和一条长为3 的路组成，使得这k 一1 个1 圈与这 条路是相互独立的 一个类似的结果由r a n d e r a t h 等在文献f 6 3 】给出对于定理2 3 1 中的最小度条 件6 ( g ) 2 k ，本文考虑其更一般的情况，我们用不同于定理2 3 1 的方法证明了定 理2 3 2 定理2 3 2 设k 是一个正整数，g = ( k e ) 是一个顶点数为4 的图如果 观( g ) 4 k 一1 ，则g 合相互独立的k 一1 个；，圈和一条长为3 的路，使得所有这 些4 圈和路是相互独立的 4 = 分图中相互独立的大圈和2 - 因子 b r a n d t 等f 圳】证明了若g 是一个图，其顶点数n 4 k ，并且对每- x 不相邻 的顶点“和”都有d ( “) + d ( ”) n ，则g 有一个2 因子恰含k 个顶点不相交的圈 对于二分图，w a n g 考虑了同样的问题【6 6 】，证明了如果g = ( ，k ；e ) 是一个二分 图满足i k i = 1 i = n22 k + l ，并且d ( g ) m 2 1 + l ，则g 有一个2 一因子恰含k 个 顶点不相交的圈c h e n 等e 6 7 3 和l i 等 6 8 】也给出了二分图g 有一个2 因子恰含 个顶点不相交的圈的度条件我们考虑二分图中含大圈的2 因子 i i i 山东大学博士学位论文 定理2 4 1 设s 3 和k 芝1 是两个整数，g = ( k ，：e ) 是一个二分图，满足 l kj = i kj 兰s k 如果图g 的最小度d ( g ) 2f ( 1 1 s ) n 1 + 1 则g 有一个2 一因子恰含 个顶点不相交的圈，使得每个圈的长度至少为2 s 关于g 含女个顶点不相交的大圈的结果，w a n g 证明了： 定理2 4 2 1 6 9 i 设g = ( ，；e ) 爰一个二分图，满足1 u 1 = i 1 s ，其中s 3 和三1 是两个整数如果图g 的最小度6 ( g ) 三( 8 一1 ) 女+ 1 ，则g 包含女个长至少 为2 5 的顶点不相交的圈 我们把定理2 , 4 2 中的最小度条件推广到吼1 ( c ) z ( s 一1 ) k + 2 ，证明了定理 24 4 定理2 4 4 设3 4 和k 1 是两个整数，g = ( k ，：e ) 是一个二分图满足 f k f = f k f s k + 1 ，如果o l , 1 ( g ) 22 ( s 1 ) 女+ 2 ，则g 包含k 个长至少为2 s 的相互 独立的圈 5 = 分圉中相互独立的指定长度的圈 本文考虑二分图中顶点不相交的4 圈我们证明了下面的结果 定理2 , 5 1 设m23 ，n 2 和k 1 为三个整数，g = ( m ：e ) 是一个二分 图满足1 l = l k = n22 k + 1 如果g 的最小度d ( g ) + 1 并且对g 中每一长为 2 m 的圈c ，都有。e 1 f g ) d 扛) 兰m ( n 十1 ) + 1 ，则g 包含女个顶点不相交的4 - 圈 显然4 一圈是二分图中的最小圈w a n g 在文献1 6 0 l 中提出了下列猜想：当 l h l = 1 k l = 2 k 时g 有一个2 因子含个顶点不相交的4 圈此猜想至今未得到 解决 附注定理2 5 1 中的度条件是最好的设k 是一个奇数，令g = ( a u u 拙 b u y u u ) ) 使得g l = ( a ，b ；e 1 ) 和g 2 = ( x 1 ，：励) 皆与k k k 同构，n ( a ) = bu f _ j ， ( ”) = 肖u u ，并且集合a 中的顶点通过k 条顶点不相交的边与集合y 匹配显然， g 是一个顶点数为2 ( 2 k + 1 ) 的均衡二分图而且对任一长为6 的圈c = “ z 9 n 轧，其中 z x ，可y ，a 并且b b ，者有1 2 r ( c l d ( z ) = 6 k + 6 = 3 ( n + 1 ) 一f 住+ l j + t 因为七是一个奇数，易见g i 和g 2 都至多包含( 一1 ) 2 个顶点不相交的4 - 圈，即 g l 和g 2 共包含k 一1 顶点不相交的4 - 圈如果g 包含k 个顶点不相交的4 - 圈：则 必存在口a ，b b ，z x 。y 使得g h 8 ，b o ， ，”) 】含一个4 - 圈但从g 的结构可以看出，g 【 口，b ，。，u ， 】不包含4 一圈 6 圈中含指定边的独立圈和2 - 因子 对一个二分图来说，垂圈是最小的圈，它在图的圈理论中有着重要的地位 w a n g 考虑了二分图中含指定边的顶点不相交的圈，证明了下面的定理 i v 山东大学博士学位论文 定理3 【1 1 4 2 1 设g = ( h ，k ：e ) 是一个二分图使得l h l = l k l = n 3 k ，其 中k 2 是一个整数假设对g 中任意一对不相邻的顶占、z 和y ，都有 d ( x ) + d ( v ) n + k ，则对g 中任意给定的 条独立的边e 1 ，g 包含个顶 点不相交的圈c 1 一，q 使得龟e ( q ) ，并且f ( g ) s6 ，i 1 ，一， ) 对于一般图，e g a w a 等在文献4 0 中还证明了下面的结果：设g 是一顶点数 为n 的图使得3 k 7 1 , 4 k ，k22 设e h 一e 是g 中条独立的边假设对g 中 任意一对不相邻的顶点z 和9 ，x ：= u l 2 k ， w h e r e i sap o s i t i v ei n t e g e r s u p p o s et h a tt h em i n i m u md e g r e ed ，gi sa tl e a s t + 1 t h e n g c o n t a i n s i n d e p e n d e n tc y c l e s e n o m o t o p r o p o s e dt h ef o l l o w i n gp r o b l e m ： p r o b l e m2 1 2 3 2 1 si t p o s s i b l et or e p l a c et h ea s s u m p t i o nj ( g ) k + 1w i t h5 l t ( g ) 2 女+ 2o ro - 1 1 ( g ) 2 k + 2i nt h e o r e m2 j jf t h e o r e m2 1 4s o l v e st h ea b o v ep r o b e m t h e o r e m2 1 4 l e tkb eap o s i t i v e i n t e g e ra n dg = ( k ，k ；e ) b eab i p a r t i t eg r a p h w i t hj h = f k l = n 2 k 妒盯1 1 ( g ) 2 k + 2 ，t h e ngc o n t a i n ski n d e p e n d e n tc y c l e s 2 i n d e p e n d e n tc y c l e sa n dp a t h si nb i p a r t i t eg r a p h s l e tg = ( h ，k ；e ) b ea b i p a r t i t eg r a p h i nf 6 0 ，w a n ga l s op r o v e dt h ef o l l o w i n gr e s u l t 山东大学博士学位论文 t h e o r e m2 2 11 6 0 l e tg = ( h k ；e ) b enb i p a ，t i t eg r a p hw i t hl l = 1 k 1 = 2 k w h e r eki sap o s i t i v ei n t e g e ) 1 玎d ( g ) 十1 ，t h e ngc o n t a i n s 一1i n d e p e n d e n tq u a d r i l a t e r a l s a n d8p a t h ( no r d e r 8 , a c ht h a tt h ep a t hi si n d e p e n d e n to ia l lt h ek 一1q a a d r i l a t e r a l q as i m i l a rq u e s t i o ni s p r e s e n t e d i si tp o s s i b l et or e p l a c et i l ea s s m n p t i o nd ( g ) w i t h 口1 1 ( g ) i nt h e o r e m2 2 1 7 t h e o r e m2 2 2a n s w e rt h eq u e s t i o n t h a ti s ，t h ea s s u m p t i o n 8 ( a ) + l i sr e p l a c e db yo - 1 ! ( g ) 2 k + 1 b u tt h ep r o o f o f t t m o r e m2 2 2i sd i f f e r e n tf r o m t h ep r o o fo ft h e o r e m2 2 1 t h e o r e m2 2 2 l e tk 1b ea ni n t e g e ra n dg = ( u ；e 1a b i p a r t i t eg r a p hw i t h j h = j l 乏 = 2 k s u p p o s et h a t 盯1 1 ( g ) 22 t ：+ 1 t h e ngc o n t a i n s 七一1q u a d r i l a t e r a l sa n dn p a t ho fo r d e rls u c ht h a ta l lo jt h e m , a t w , i n d e p e n d e n t r e m a r k b y t h ee x a m p l e i n 6 0 】w ec a ns h o w t h a tt h ec o m i i t i o no n d e g r e e si nt h e o r e m 2 2 2i ss h a r p l e t a n di nb ep o s i t i v ei n t e g e r sa n d1 1 2 十l l e t , g l = ( a ，b ；e 1 ) a n d g 2 = ( x ，y ：e 2 ) b et w oi n d e p e n d e n tc o m p l e t eb i p a r t i t eg r a p h sw i t hj a l = y i = 一la n d i b | = i x l = 7 2 t h e ng k mc o n s i s t so fg 1 g 2a n das e t o fm i n d e p e n d e n te d g e sb e t w e e nb a n dx c t e m l y ，( aux buy ) i sap a r t i t i o no fg * i ti s e a s yt os e et h a te v e r yc y c l ei n g mc o n t a i n sa tl e a s tt w ov e r t i c e si na uy a sl au 1 = 2 ( k 一1 ) g k ld o e sl l o tc o l l t a i n 一1i n d e p e n d e n tq u a d r i l a t e r a l sa n dap a t ho fo r d e r4s u c ht h a tt h ep a t hi s i n d e p e n d e n to f a l lt h ek 一1q u a d r i l a t e r a l s b u td ( 。) + d ( y ) = 2 kf o re a c hp a i ro fn o n d j a e e n tv e r t i c e s 口a n d o f g k ，nw i t hz xa l l t t b 3 i n d e p e n d e n tc y c l e sa n dp a t h si ng r a p h s e r d s sa n df a l t d r e e ( ；l 】l ：o n j e c t l l l e dt h a ti fgi sa g r a p hw i t h g l = 4 a l l ( id ( g ) 2 k t h e ng c o n t a i n s ：i n d e p e n d e n tq u a d r i l a t e r a l s j o h a n s s o np r o x r e dt h ef o l l o w i n gt h e o l e t n ： t h e o r e m2 3 1 1 6 2 j 帮gi s g r a p hw i t hf g = 4 ka n d 烈g ) 2 7 t h p ngh a s 口 s p a n n i n gs u b g r a p hc o n s i s t i n go jk 一1q u a d r i l a t e r a l s ，a n dap a t ho | o r d e r4 s u c ht h a ta l lo f t h e , ma r i n d e p e n d e n t n o ww e g e n e r a l i z et h e o r e n l2 3 ，l a sf o l l o w s b u tt h em e t h o do ft t l ep r o o fo ft h e o r e m 2 3 2i sd i f i e , r e t t tf r o i ut h a to ft h e o r e m2 3 1 t h e o r e m2 3 2 l e tkb enp o s i t i v ei n t e g e ra n dg 3 ( y ，e jag r a p h 吖o r d e r4 k 盯 a 2 ( g ) 4 k 一1 t h e ngc o n t a i n sk 一1i n d e p e n d e n tq u a d r i l a t e r a l sa n dnp a t ho fo r d e r 。4s u c h t h a ta l l 盯t h e mo mi n d e p e n d e n t 4 o ni n d e p e n d e n tc y c l e sa n d2 - f a c t o r sw i t hl a r g ec y l c e s b r a n d te t a 1 f 1 0 p r o v e dt h a ti fg i sag r a p hw i t l ln 4 k a n d 仃2 ( g ) 2 忆，t h e gt l 嬲 a2 f a c t o rw i t he x a c t l ykc y c l e s w a n g 6 6 1c o n s i d e r e dt h eb i p a r t i t eg r a p ha n dp r o r e dt h a t i x 山东大学博士学位论文 i fg = ( k 、k ；f ) i sab i p a r i t cg r a p hw i t h h = 1 = n2 2 ：+ la n dj ( g ) ，。2 1 + 1 ， t 1 1 e ngh a sa2 f a t “) r w i t he x a c t l y 知c y c l e s c h e i le ta 1 , r 6 7 a n dl ie ta 1 6 8 ia l s 。b r a i n e d t l l ed e 譬糟ec o n i t i 0 1 l ss 1 1 c l 】t t l a tg = h ，班；e ) h a sa2 - f a c t o rw i t he x a c t l y 盘c y c l e s w e t ：o n s i d e rt h ed o g r t ，cc o t i t i t i o n so i l2 - f a c t o r sw i t hl a r g ec y c l e si nb i p a r t i t eg r a p h s t h u sw e o b t d nt i l e o l 。e ! n24 1 t h e o r e m2 4 1 l e ts 兰3a n dk lb et w oi n t e g e r sa n dg = ( u ：e ) ob i p a r t i t e a p hw i t hl k i = n j l = h 2s ：玎d ( g ) f ( 1 一；) 扎 + l ，t h e ng h a snz - f a c t o rw i t he z a c t l y c y c l e so fl e n g t h , a tl e a s t2 s w a n g a l s op r o v e dt h ef o l l o w i n gt h e r o e m ： t h e o r e m2 4 2 i 6 9 l e tg = ( k ，硷：e ) hnb i p a r t i t eg r a p h , u f i t h 1 h 1 = 1 12s k h e r es 3o n d 女1a r et w oi n t e g e r s ，t h em i n i m u md e g r e eo f g i sa tl e a s t ( s 1 ) + 1 ， t h c ng ( ：o n t a i n s t l e r t e x d i s j o i n tc y c l e so fl e n g t ha tl e a s t2 s w ea l s og i v et h ef o l l o w i u gr e s u l t ， t h e o r e m2 4 4 l e tn 4a n d 1 阮l m oi ? | d e g e r s l e tg = 1 1 j 1 jp ) k ab i p a 7 t i l e g r a p hw i t h j ；= i 1je h 七+ 1 盯o 1 ，l ( g ) 2 ( 5 一l j 1 十2 t h , e ag “j t ，| t a i n s 七i n d e p e n d e n t e y r 1 e s ) | l e n g t h a tl e a s t 曩 5 i n d e p e n d e n tc y c l e sw i t hs p e c i f i e dl e n g t h si nb i p a r i t eg r a p h s t l l ci n ( t e p e n , h , u tq u a d r i l a t e r a l si nab i p a r t i t eg r a p ha r ec o i l s i d ( ! l ( 、di l l t h i ss e cl i ( u it h a t i sw ep 1 o v et h e o l l ! t l l2 , 5 1 t h e o r e m2 5 1 厶：fm 3 ，n 2a n d 三lb et h r e ei n t e g e r s l e tg = ( n v 2 ；e ) b r ，“b i p a 7 ，t i h ，g r a p h z f t l i = f 坞f = ，。2 + 1 盯t h e m i t ，i m u w d e g r e ej ( g ) 2 + 1 。7 l d r 出f f f ( t )