（运筹学与控制论专业论文）图的独立圈和独立团理论的若干结果.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均已在文中以明确方式标 明。本声明的法律责任由本人承担。 论文作者签名：邀盔盘 e t 期：丝垒垒兰盟星堕 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：熬盔歪导师签名：秀复i 呈日 期：型旦釜翘壁旦论文作者签名：拯焦垡导师签名：岔复1 星日期：型旦釜翘壁旦 目录 中文摘要i 英文摘要i i i 符号说明v i i 第一章引言1 1 1 基本概念1 1 2 问题产生的背景及其进展情况2 1 3 已有的结论及本文的主要结果1 2 第二章图中含指定长度的独立圈1 4 2 1 预备知识及引理1 4 2 2 定理2 1 1 的证明1 5 第三章图中含指定长度的独立团1 7 2 1 预备知识及引理1 7 2 2 定理3 1 1 的证明1 9 2 3 可进步讨论的问题2 8 第四章无爪图中的独立团问题2 9 3 1 预备知识及引理2 9 3 2 定理4 1 1 的证明2 9 3 2 可进步讨论的问题3 3 参考文献3 4 致谢3 7 个人简介i 0 3 8 c o n t e n t s c h i n e s ea b s t r a c t i e n g l i s ha b s t r a c t i i i l i s to fs y m b o l s v i i c h a p t e r1i n t r o d u c t i o n 1 1 1b a s i cd e f i n i t i o n sa n dn o t a t i o n s 1 1 2t h eh i s t o r ya n dp r o g r e s so fc y c l e sa n dp a t h - f a c t o r st h e o r y 2 1 3t h ek n o w nr e s u l t sa n dt h en e wr e s u l t s 1 2 c h a p t e r2i 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 ng r a p h s 1 4 2 1p r e l i m i n a r i e sa n dl e m m a s 1 4 2 2p r o o fo ft h e o r e m2 1 1 1 5 c h a p t e r3i n d e p e n d e n tc l i q u e sw i t hs p e c i f i e dl e n g t h s i ng r a p h s 1 7 2 1p r e l i m i n a r i e sa n dl e m m a s 1 7 2 2p r o o fo ft h e o r e m3 1 1 1 9 2 3s o m ep r o b l e m st od i s c u s s 2 8 c h a p t e r4i n d e p e n d e n tc l i q u e si nc l a w - f r e eg r a p h s 2 9 3 1p r e l i m i n a r i e sa n dl e m m a s 2 9 3 2p r o o f o f t h e o r e m4 1 1 2 9 3 2s o m ep r o b l e m st od i s c u s s j 3 3 r e f e r e n c e s 3 4 a c k n o w l e d g m e n t 3 7 c u r r i c u l u mv i t a e 3 8 山东大学硕士学位论文 图的独立圈和独立团理论的若干结果 张蓓蓓 山东大学数学学院 运筹学与控制论 山东济南2 5 0 1 0 0 中文摘要 本文考虑的图若无特殊声明均为简单、无向有限图，对于一个图g = g ( y ( g ) ， e ( g ) ) ，我们用v ( a ) 和e ( g ) 分别表示图的顶点集合和边集合对任意的v y ( g ) ，我们用d g ( 钉) 表示顶点 在g 中的度数( g ) 和6 ( g ) 分别表示图g 的最大度和最小度，在不引起混淆的情况下简记为和6 对于图g ，我们用 i g l = l y ( g ) i 表示g 的阶数，即g 的顶点数，并定义图g 中两个不相邻的顶点 的最小度和为： a 2 ( a ) = r a i n d a ( z ) + d a ( y ) l x ，y y ( g ) ，z y ，x yge ( g ) ( 若g 是一个完全图，则令a 2 ( a ) = c o ) 对于二部图g ，令g 的两个部分的顶点集合分别为和k 若i i = i i ， 则称g 为均衡二部图定义 6 l ，l ( g ) = m i n d a ( z ) + d a ( ! ，) i z k ，y k ) ， f f l ，1 ( g ) = m i n d a ( x ) + d a ( y ) l x ，y ，x yge ( g ) ) ( 若g 是个完全二部图，则令仃1 ，l = 。o ) 完全二部图k 1 3 称为一个爪，如果g 不含同构于k 1 ，3 的生成子图，则 称g 是无爪图对于图g 中的一条路p 和一个圈c ，定义路和圈的长度分别 为：l ( p ) = i y ( p ) i 一1 ，z ( c ) = l v ( c ) 1 g 的一个哈密顿圈是g 的包含g 中所有顶点的一个圈g 的一个l 一因子 是g 的个1 ，正则支撑子图，通常我们称1 因子为完美对集或完美匹配显然 g 的一个1 一因子是覆盖g 的所有顶点的一个边集合g 的一个2 因子是g 的 个二正则支撑子图，易见2 因子的每一个连通分支为一个圈图的k 个独立 圈是指g 中k 个顶点不相交的圈 图的独立圈、2 因子和路因子问题是图的因子理论中非常重要的一部分，也 是图的哈密顿圈理论的推广和延伸其理论研究日益成熟和完善，而且它在计算 机科学、通信网络设计等中都有重要应用关于图的独立圈、2 因子和路因子理 山东大学硕士学位论文 论的研究主要集中在以下几个方面：图中含指定个数的独立圈和二因子；含指 定长度的独立圈和2 因子；图中具有指定性质的独立圈和2 一因子；具有指定性 质的路因子等等 本文的创新之处在于讨论了图中包含指定个数的阶为3 和4 的独立团问题 全文共分四章第一章简单介绍了图论的基本概念，圈因子理论的历史和发展状 况及一些已有的相关结论，这一章是其余三章的基础 第二章讨论了图中包含指定长度的独立圈问题，证明了如下结论： 定理2 1 1 设k 和s 是两个非负整数，且k s 简单图g 满足礼= i g i 3 s + 4 ( k s ) + 7 如果a 2 ( g ) 2 佗+ s ，那么g 中包含一个由k + 1 个圈 g ，伉+ 1 所组成的2 因子，满足l ( g ) = 3 其中1 i s 一1 ，z ( g ) = 4 其 中3 i k 一3 ，z ( g ) 4 其中k 一2si k l ，且有l ( c k ) 3 ，4 ，7 ，8 ) 第三章讨论了图中包含指定长度的独立团的问题其主要结果如下： 定理3 1 1 设k 和8 是两个非负整数，且k s ，简单图g 满足t t = i g i 3 s + 4 ( a s ) 如果c r 2 ( g ) 堑产+ k l ，那么g 包含互不相交的s 个3 _ 团 和k 一8 个垂团的并，即g s k 3 十( k s ) k 4 在第四章中我们考虑了非空无爪图中含指定长度的独立团的问题，并证明了 如下定理： 定理4 1 1 设k 和s 是两个非负整数，且k s ，设简单图g 是一个非空的 无爪图，且满足n = l g i 3 s + a ( k s ) 如果图中任意相邻两点的度数和 卢( g ) 下3 n - s - 1 ，那么g 包含互不相交的s 个3 - 团和k 一8 个4 - 团的并，即 g2s k 3 + ( k s ) 甄 另外，本文的第三章和第四章中还提出了一些问题，以待进一步研究 关键词：独立团；独立圈；无爪图；2 因子 i i 一 山东大学硕士学位论文 s o m er e s u l t so ni n d e p e n d e n tc y c l e sa n di n d e p e n d e n t c l i q u e si ng r a p h s z h a n gb e i b e i s c h o o lo fm a t h e m a t i c s ，s h a n d o n gu n i v e r s i t y s h a n d o n gj i n a n 2 5 0 1 0 0 a b s t r a c t a l lg r a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t es i m p l eg r a p h s l e tg = ( y ( g ) ， e ( g ) ) b eag r a p h ，w h e r ev ( g ) a n de ( g ) d e n o t et h ev e r t e xs e ta n de d g es e to f g ，r e s p e c t i v e l y w eu s ed ev ) t os t a n df o rt h ed e g r e eo f 口i ng l e ta ( g ) a n d 6 ( g ) d e n o t et h em a x i m u ma n dt h em i n i m u mv e r t e xd e g r e eo fg ，r e s p e c t i v e l y f o rag r a p hg ，i g i = i y ( g ) ii st h eo r d e ro fg ，a n d 观( g ) = r a i n d e ( z ) + d e ( 可) l z ，y y ( g ) ，z y ，x y 掣e ( g ) i st h em i n i m u md e g r e es u mo fn o n a d j a c e n tv e r t i c e s ( w h e ngi sac o m p l e t e g r a p h ，w ed e f i n ec r 2 ( g ) = o o ) f o rab i p a r t i t eg r a p hgw i t hp a r t i t es e t s 巧a n d 巧，d e f i n e 6 1 ，1 ( g ) = m i n d a ( x ) + d e ( y ) l x ，y ) ， 盯l ，l ( g ) = m i n d g ( x ) + d e ( 可) l z v x ，可，x yge ( g ) ) ( w h e ng i sac o m p l e t eb i p a r t i t eg r a p h ，w ed e f i n eo 1 ，1 = o 。) w h e ni i = 1 i ，w ec a l lgab a l a n c eb i p a r t i t eg r a p h t h ec o m p l e t eb i p a r t i t eg r a p h 甄3i sc a l l e dac l a w ，a n dgi ss a i dt ob ec l a w - f r e ei fgh a sn oi n d u c e ds u b g r a p hi s o m o r p h i ct o 3 l e tpb eap a t ha n d cac y c l e w ed e n o t et h el e n g t ho fpa n dt h el e n g t ho fcb yi ( p ) a n df ( c ) ， r e s p e c t i v e l y t h a ti s ，l ( p ) = l y ( p ) i 一1 ，l ( c ) = i v ( c ) 1 ah a m i l t o nc y c l eo f gi sac y c l eo fgw h i c hc o n t a i n se v e r yv e r t e xo fg a1 - f a c t o ro fag r a p hg i s a1 - r e g u l a rs p a n n i n gs u b g r a p ho fg ，a n dw ec a l la1 - f a c t o rap e r f e c tm a t c h i n g i ti sr e a d i l ys e e nt h a ta1 - f a c t o ro fgi sac o l l e c t i o no fi n d e p e n d e n te d g e st h a t c o v e r sa l lv e r t i c e so fg a2 - f a c t o ro fgi sa2 - r e g u l a rs p a n n i n gs u b g r a p ho fg c l e a r l y , e a c hc o m p o n e n to fa2 - f a c t o ro fg i sac y c l e ki n d e p e n d e n tc y c l e so fg a r ekc y c l e sw h i c hh a v e1 1 0c o m m o nv e r t e x i 山东大学硕士学位论文 t h ei n d e p e n d e n tc y c l e s 2 - f a c t o ra n dp a t h - f a c t o rt h e o r yi nga r ei m p o r t a n t p r o b l e m si ng r a p hf a c t o r i a lt h e o r y , a l s ot h e ya r et h ee x t e n d i n go fh a m i l t o nc y c l e t h e o r y t h ed i s c u s s i o ni sm a t u r ea n dp e r f e c ti n c r e a s i n g l y a n di ti si m p o r t a n t a p p l i c a t i o n st oc o m p u t e rs c i e n c ea n dn e t w o r k t h es t u d yo fi n d e p e n d e n tc y c l e s ， 2 - f a c t o ra n dp a t h - f a c t o rt h e o r ym o s t l yf o c u so nf o l l o w i n g ：g r a p hc o n t a i n i n gs p e c - i f i e dn u m b e ro fi n d e p e n d e n tc y c l e sa n d2 一f a c t o r ，i n d e p e n d e n tc y c l e sa n d2 - f a c t o r c o n t a i n i n gs p e c i f i e dl e n g t h ，g r a p hc o n t a i n i n gi n d e p e n d e n tc y c l e sa n d2 - f a c t o r w h i c hh a v es p e c i f i e dp r o p e r t i e s ，a n dp a t h - f a c t o rw h i c hh a v es p e c i f i e dp r o p e r t i e s ， e t c t h ei n n o v a t i o no f t h i sp a p e ri s d i s c u s s i n gt h eg r a p hc o n t a i n i n gs p e c i f i e d n u m b e ro fi n d e p e n d e n t3 - c l i q u e sa n d4 - c l i q u e s t h ep a p e ri sd i v i d e di n t of o u r c h a p t e r s i nc h a p t e r1 ，w ei n t r o d u c es o m eb a s i cn o t a t i o n sa n dg i v eac o n c i s e s u r v e yo nt h eh i s t o r ya n dt h ep r o g r e s so nt h ec y c l et h e o r y , a n ds o m ep r i m a r y r e s u l t sa b o u tt h ep a p e r t h i sc h a p t e ri st h eb a s eo ft h en e x tt h r e ec h a p t e r s i nc h a p t e r2 ，w ei n v e s t i g a t et h eg r a p hc o n t a i n i n gi n d e p e n d e n tc y c l e sw h i c h h a v es p e c i f i e dp r o p e r t i e sa n dp r o v et h ef o l l o w i n gr e s u l t t h e o r e m 2 1 1l e tsa n dkb et w op o s i t i v ei n t e g e r sw i t hs ka n dl e tgb ea g r a p ho fo r d e r 佗i f 礼3 s + 4 ( 七一8 ) + 7 ，t h e ng h a sa2 - f a c t o rw i t h 七十1c y c l e s g c k + 1s u c ht h a tz ( g ) = 3f o r1 i s 一1 ，z ( g ) = 4f o rs i k 一3 ， l ( g ) 4f o rk 一2si k la n dt ( c k ) 3 ，4 ，7 ，8 ) i nc h a p t e r3 ，w ei n v e s t i g a t et h eg r a p hc o n t a i n i n gs p e c i f i e dl e n g t ho fi n d e - p e n d e n tc l i q u e s i nt h i sc h a p t e r ，w eh a v et h ef o l l o w i n gr e s u l t t h e o r e m 3 1 1l e tsa n dkb et w oi n t e g e r sw i t h0 s ka n dl e tgb eag r a p h o f o r d e r 礼i f 礼3 s + 4 ( k s ) a n dc r 2 ( g ) 3 ( n s ) 2 + k 一1 ，t h e ng c o n t a i n s sd i s j o i n t3 - c l i q u e sa n dk 一5d i s j o i n t4 - c l i q u e ss u c ht h a ta l lo ft h e ma r ed i s j o i n t i e ，g s 9 3 + ( k s ) 心 i nc h a p t e r4 ，w ei n v e s t i g a t et h ec l a w - f r e eg r a p hc o n t a i n i n gi n d e p e n d e n t c l i q u e sw h i c hh a v es p e c i f i e dp r o p e r t i e sa n dp r o v et h ef o l l o w i n gr e s u l t t h e o r e m 4 1 1s u p p o s egi san o n - e m p t yc l a w - f r e eg r a p h l e tsa n dkb et w o i n t e g e r sw i t h0 s 七i f n 3 s + 4 ( k s ) a n dp ( g ) 3 ( n s 一1 ) 2 ，t h e ng c o n t a i n ssd i s j o i n t3 - c l i q u e sa n d 七一sd i s j o i n t4 - c l i q u e ss u c ht h a ta l lo ft h e ma r e d i s j o i n t ，i e ，g2s k 3 + ( k s ) 比 i v f u r t h e r m o r e ，i nc h a p t e r3a n dc h a p t e r4 ，w el i s ts o m ep r o b l e m sf o rf u t u r e k e yw o r d s ：i n d e p e n d e n tc l i q u e ；i n d e p e n d e n tc y c l e ；c l a w - f r e eg r a p h ；2 - f a c t o r v 山东大学硕士学位论文 v ( a ) i g i e ( g ) 6 ( g ) a ( a ) 如( 可) a 2 ( g ) n ( g ) m 【z j e ( a ，b ) e ( a ，b ) g ( u ) g 旧 符号说明 g 的顶点集合 图g 的阶 g 的边集合 g 的最小度 g 的最大度 r v 在图g 中的度 g 中两个不相邻的顶点的最小度和 g 的独立数 不小于x 的最小整数 不大于x 的最大整数 连接a 与b 的边集合 连接a 与b 的边数 v 在图g 中的邻集 由s 导出的g 的子图 i 山东大学硕士学位论文 。 l ( c ) i ( p ) 划分为m 与1 0 , 个顶点的完全二都图 圈c 的长度 路p 的长度 第一章引言 本章第一节首先介绍一些在本文中要用到的图论定义及术语，未说明的图论 术语在其他章节中必要时再给予阐述；第二节主要介绍圈理论及路一因子理论的 历史背景和进展状况；第三节简单介绍一些已有的相关结论以及本文的主要结 果 1 1 基本概念 我们首先介绍一些常用的图论术语，其他未说明的定义和术语请参见文献 【1 1 我们通常称二元集合g = g ( y ( g ) ，e ( g ) ) 为个图，其中v ( u ) d 称为顶 点集合，v ( u ) 中的元素称为图g 的顶点；e ( g ) 为边集合，e ( g ) 中的元素称为 图g 的边当i y ( g ) i 十i e ( g ) i i u i ，则称v 为g 的最大独立集g 的独立数是指它的最大集中的顶点个数，记为q ( g ) 设 日是g 的一个子图，对任意x v ( u ) 一y ( 日) ，有蜥( z ) = r g ( z ) n 矿( h ) 设v 和日分别是g 中一个顶点和一个子图，用n ( v ，h ) 代表日中和秽相邻的 点的集合，记d ( v ，h ) = l n ( v ，h ) 1 我们用g 一日表示u v ( u ) 一v ( h ) i 对于 山东大学硕士学位论文 g 中两个不相交的子集a 和b ，令e ( a ，b ) = 【伽l a ， b ，u 口e ) 代 表连接a 和b 的边集合，同时令e ( a ，b ) = i e ( a ，b ) l 代表连接a 和b 的边 数若子集a 和b 相交，我们令e ( a ，b ) = d ( x ，b ) 若g 中包含m 个独 z a 立子图集合 g l ，g 2 ，g 。) ，使得g 与图皿同构，i = 1 ，m ，那么我们记 g2 研+ 如+ + 若这m 个独立子图都同构于图日，我们记g m h g 的一个哈密顿圈是g 的包含g 中所有顶点的一个圈g 的一个1 一因子是g 的 一个1 正则支撑子图，通常我们称1 一因子为完美对集或完美匹配显然g 的 一个1 因子是覆盖g 的所有顶点的一个边集合g 的一个2 因子是g 的个 2 正则支撑子图，易见二因子的每一个连通分支为一个圈g 的一个子图集合 称为相互独立的或顶点不相交的，如果它们中的任何元素在g 中没有公共顶点 若存在v ( c ) 的两个不交子集x 、y ，使得v ( c ) = x uy ，且g 的所有边均有 一个端点在x 内，另一个端点在y 内，则称g 为二部图，也称为二分图记为 g = ( x ，y ；e ( g ) ) ，简记为g = ( x ，y ) 如果l x i = i y i ，则称g 为均衡二部图 对二部图定义 6 1 1 ( a ) = m i n d v ( x ) + d a ( y ) l x ，y ， o 1 ，l ( a ) = m i n d v ( x ) + d a ( y ) l x ，y ，x y 隹e ( g ) 完全二部图甄，3 称为一个爪如果g 不含同构于k l ，3 的生成子图，则称g 是 无爪图 1 2 问题产生的背景及其进展状况 哈密顿圈是有一个圈的2 因子关于哈密顿圈度条件的结果有很多，其中 最经典的两个结果是由d i r a c 和o r e 给出的 定理1 2 1 俐设g 是一个图，其顶点数n 3 如果6 ( g ) 詈，则g 中包含 一个哈密顿圈 推论1 2 2 俐设a ，b 是图g 的一条哈密顿路的两个端点，如果d ( a ，g ) + d ( a ，g ) i g l ，那么图g 是哈密顿图 定理1 2 3 俐设g 是一个顶点数n 3 的图，并且a 2 ( a ) 扎，则g 有一个 哈密顿圈 2 山东大学硕士学位论文 x 于：j ：- - 分图g = ( ，；e ) ，m o o n 和m o s e r 给出了一个图g 中包含哈密顿 圈的度条件 定理1 2 4 例设g = ( ，v 2 ；e ) 是一个二分图使得l i = i v 2 l = n 并且 o r l ，i ( g ) 礼+ 1 ，则g 中包含一个哈密顿圈 图的独立圈理论和2 - 因子理论是图的哈密顿圈理论的推广和延伸图的路 因子理论又是图的独立圈理论的推广和延伸图的独立圈理论和2 - 因子理论是 图论中非常有趣的一类问题，也是国内外研究的热门课题其理论研究日益成熟 和完善，而且它在计算机科学、通信网络设计等中都有重要应用关于图的独立 圈理论和2 因子理论的研究主要集中在以下几个方面：图中含指定个数的独立 圈和2 因子；含指定长度的独立圈和二因子；图中具有指定性质的独立圈和2 - 因子等等 1 9 6 3 年，c o r r 5 和h a j n a l 在【5 】中给出了一个图g 含k 个独立圈的最小度 条件j u s t e s e n 6 】把此最小度条件推广到更一般的情况 定理1 2 5 俐设g 是一个顶点数为礼的图如果n 3 k 并且6 ( g ) 2 k ，那 么g 中含k 个独立圈 定理1 2 6 俐设g 是一个顶点数为竹的图如果n 3 k 并且a 2 ( g ) 4 k ， 那么g 中含k 个独- 孟j 1 e n o m o t o 7 】和w a n g 8 】各自独立的把上述定理中的度条件a r 2 ( g ) 4 k 改进 为a 2 ( g ) 4 k 一1 定理1 2 7 俐设g 是一个顶点数为n 的图如果礼3 k 并且u 2 ( g ) 之 4 k 一1 ，那么g 中包含k 个独立圈 b r a n d t 等利用上述结果证明了， 定理1 2 8 例设g 是一个顶点数为n 的图如果佗4 k 并且a 2 ( g ) n ，那 么g 中有一个恰含k 个圈的2 一因子 关于二部图中指定个数的独立圈，w a n g 1 0 】给出了以下结论： 3 山东大学硕士学位论文 定理1 2 1 5 似剐设g 是一个顶点数为n 的图假设礼3 k + 3 ，6 ( g ) 学， 那么g 中有一个2 因子含k + 1 个独立圈c 1 ，q ，g + 1 使得对所有1 i k 都有i a i = 3 e n o m o t o 用c r 2 代替6 ，得到以下结果： 定理1 2 1 6 似劬设g 是一个顶点数为n 的图假设礼3 k + 3 ，a 2 ( g ) m + 尼) ，那么g 中有一个2 一因子含k + 1 个独立圈g ，q ，c k + l 使得对所 有1 i k 都有i g i = 3 对于图g 中含若干个3 - 圈的度条件，d i r a c 给出了如下结果： 定理1 - 2 1 7 似例设g 是一个顶点数为n 3 k 的图如果6 ( g ) 丁n + k ，那么 g 中包含k 个独立3 一圈 对于g 中含两个指定长度的圈问题，w a n g 给出了如下结果： 定理1 2 1 8 价剐设g 是一个顶点数为n 6 的图，使得6 ( g ) 学 ，那么 对任意两个整数8 3 ，t 3 ，s + t 礼，g 中包含两个独立圈q 和q ，其长 分别为s 和t ，除非n ，8 ，t 皆为奇数并且g 兰甄。一1 ) 2 ，伽一1 ) 2 + 硒 显然，对任意奇数n 3 ，g 笺k ( 。一1 ) 2 ，( 。一1 ) 2 + k 不含两个独立奇圈；若 n 为偶数，则2 ，。2 不含奇圈w a n g 还考虑了下列情况： 定理1 2 1 9 伊剐设g 是一个顶点数为n 6 的图，其中n 为偶数如果 6 ( g ) 詈，那么对任意两个偶数s 4 ，t 4 ，s + t n ，g 中包含两个独立圈 q 和q ，其长分别为8 和t 对于二部图g = ( ，e ) ，a m a r 提出了下面的猜想，并证明了其当k = 2 时成立 猜想1 2 2 0 似劝设g = ( v l ，e ) 是一个二部图，使得i m l = l k i = n = n l + 礼2 + + 讯( 啦2 ) 如果6 1 1 n + k ，那么g 中包含k 个独立圈 q ，q ，伉，其长分别为2 n x ，2 n ：，2 n k 5 山东大学硕士学位论文 w a n g 还证明了下面的结果： 定理1 2 2 1 似刚设g = ( ，e ) 是一个二部图，使得i i = i i = n l + 礼2 + + n 七，其中n l n 2 n 七2 如果6 ( g ) 丑坐产，那么g 中 包含k 个独立圈g ，岛，g ，其长分别为2 n ，2 n 2 ，2 n k 定理1 2 2 2 伯_ f 设g = ( ，e ) 是一个二部图，使得l k f = i k f = 扎4 如果对所有z v x 和y k 都有d ( x ) + d ( y ) n + 2 ，那么对任意两个整数 8 2 ，t 2 ，s + tsn ，g 含两个独立圈a 和q ，其长分别为2 s 和2 t 果： 对于二部图g = ( k ，e ) 中包含独立4 - 圈的问题，w a n g 证明了下列结 定理1 2 2 3 伊o ) 设g = ( ，k ；e ) 是一个二部图，k 是一个正整数，且i l = i k i = 2 k 如果6 l ，1 ( g ) 后+ 1 ，那么g 中含k 一1 个独立4 一圈a ，g ，c k 一1 和一条4 一路p ，且路p 和所有4 圈相互独立 定理1 2 2 4 俾别设g = ( ，k ，e ) 是一个二部图，使得l l = l k i = 竹2 ， 并且6 ( g ) 兰 + 1 如果k 0 ，t 3 并且n = 2 k + t ，那么g 有一个恰含k + 1 个独立圈c i ，c 2 ，g + l 的参因子，使得对所有1si 七都有i g i = 4 颜谨证明了以下结论： 定理1 2 2 5 俾圳假设m 3 ，n 2 ，k 之1 是三个整数，设g = ( ，k ，e ) 是 - - 4 二- 部图，使得l i = i i = 佗2 k + 1 如果6 ( g ) k + l 且对于g 中任意 一个长为2 m 的圈c 都有d ( x ) m + 1 ) ，那么g 中包含k 个独立4 - 圈 e 对于图中含若干独立4 - 圈的问题，r o b e r tj o h a n s s o n 在【2 4 】中给出了g 包 含k 一1 个独立缸圈的度条件 定理1 2 2 6 设i g l = 4 k ，且6 ( g ) 2 k ，则g 包含相互独立的k 一1 个 4 一圈和一条4 一路 颜谨将结论改进为以下结果： 6 山东大学硕士学位论文 定理1 2 2 7 设i g i = 4 k ，且晚( g ) 4 k 一1 ，则g 中存在一个支撑子图 由相互独立的k 一1 个4 圈和一条4 路组成 d a n h o n gz h a n g 和h o n gw a n g 则在【2 6 1 中将定理1 2 2 6 的度条件改为 6 ( a ) 2 k 一1 ，得到如下结论： 定理1 2 2 8 他钏设i g i = 4 k ，且6 ( a ) 2 k 一1 ，则g 中包含k 一1 个独立的 4 一圈 定理1 2 2 9 伯例设i g i = 4 k ，其中k 是一个正整数如果c r 2 ( g ) 4 k 一2 ，则 g 中包含k 一1 个独立的4 - 圈 对于图g 中含若干个相互独立的3 - 圈和垂圈的问题，b r a n d t 等证明了如 下结果： 定理1 2 3 0 例设k 和s 是两个正整数，且k s ，简单图g 满足佗( g ) 3 s + 4 ( k s ) + 3 如果a 2 ( g ) n + 8 ，那么g 中含k 个顶点不相交的圈 a ，q ，g ，使得i g i = 3 ，其中1 i s ，i g i 4 ，其中8 t k 颜谨将定理1 2 3 0 中圈的长度做了更明确的限定： 定理1 2 3 1 设k 和8 是两个正整数，且k 8 ，简单图g 满足n ( a ) 3 s + a ( k 一8 ) + 3 如果锄( g ) 佗+ 8 ，那么g 中包含k 个顶点不相交的圈 c 1 ，g ，仇，使得l g i = 3 ，其中1 i 8 ，i g i = 4 ，其中8 i k 高云澍又进一步把以上定理改进为如下两个定理； 定理1 2 3 2 伯圳设k 和s 是两个正整数，且k 8 ，简单图g 满足n ( a ) 3 s + a ( k 一8 ) + 1 如果a 2 ( a ) 礼+ k ，那么g 包含k 个顶点不相交的圈 a ，岛，g ，使得i a i = 3 ，其中1 is8 ，i gj = 4 ，其中s i k 定理1 2 3 3 似例设k 和8 是两个正整数，k s ，简单图g 满足n ( a ) 3 s + 4 ( k s ) ，且图中不包含z ，其中z 是不含4 一圈的顶点数和边数均为4 的 图如果仃2 ( g ) n + 8 ，那么g 包含k 个顶点不相交的圈g ，g ，仉，使 得l g i = 3 ，其中1 i 8 ，i g i = 4 ，其中s i k 7 山东大学硕士学位论文 w a n gh o n g 在【3 1 】中证明了： 定理1 2 3 4 伯圳设佗，s 和t 是整数，且8 1 ，t 芝0 ，佗= 3 s + 4 t ，阶为佗的 简单图g 满足6 ( g ) ( n + s ) 2 ，那么g 中有一个2 一因子由互不相交的s 个三 角形和t 个4 圈组成 关于弦圈的结论，高云澍证明了： 定理1 2 3 5 伊剀设r 和s 是两个非负整数，且k s ，简单图g 满足钆( g ) 3 7 + 4 s 如果6 ( g ) 2 r + 3 s ，那么g 中包含互不相交的r 个圈和8 个弦圈 于潇在( 【3 3 】) 中考虑了定理1 2 3 l 中的所有垂圈都至少含_ 条弦的情况并 证明了： 定理1 2 3 6 设k 和8 是两个正整数，且k s ，简单图g 满足n ( a ) 3 s + 4 ( 七一8 ) + 3 如果a 2 ( a ) 亿+ 2 k 一字，那么g 包含k 个顶点不相交的 圈a ，岛，瓯，使得i g l = 3 ，其中1s iss ，i g i = 4 ，i e ( g ) l 5 ，其中 s i k 本人在此基础上考虑了图中含若干个互不相交的孓团和垂团的问题，又做 出了以下结论： 定理1 2 3 7 仍锄设k 和8 是两个非负整数，且k s ，简单图g 满足n = l a l 3 s + 4 ( 七一s ) + 3 如果晚( g ) 业掣2 + k ，那么g 包含互不相交的s 个3 一团和k 一8 个4 一团的并，即g2s 蚝+ ( k s ) k 4 对于过指定边或指定顶点的独立圈和2 - 因子问题，w a n g 在【3 5 】中给出了 下面的猜想： 猜想1 2 3 8 似圳如果k 2 ，与n 相比k 足够大，并且a 2 ( c ) 礼+ 2 七一2 ， 那么对g 中任意k 条相互独立的边e l ，e 2 ，e 七，g 中有一个2 一因子恰含k 个 独立圈g ，c 2 ，仇，使