（运筹学与控制论专业论文）图中独立4圈与独立6圈的相关结论.pdf

山东大学硕士学位论文 图中独立4 圈与独立昏圈的相关结论 刘东 山东大学数学与系统科学学院 运筹学与控制论 山东济南2 5 0 1 0 0 中文摘要 本文考虑的图若无特殊声明均为简单、无向有限图，对于一个图g = g ( y ( g ) ， e ( g ) ) ，我们用v ( g ) 和e ( g ) 分别表示图的顶点集合和边集合对任意的u v ( g ) ，我们用d a ( v ) 表示顶点u 在g 中的度数a ( g ) 和6 ( c ) 分别表示图g 的最大度和最小度，在不引起混淆的情况下简记为和6 对于图g ，我们用 i g i = i y ( g ) i 表示g 的阶数，即g 的顶点数，并定义图g 中两个不相邻的顶点 的最小度和为： a 2 ( c ) = m i n d g ( x ) + d c ( y ) l z ，y y ( g ) ，z y ，x y 名e ( g ) ) ( 若g 是个完全图，则令a 2 ( g ) = o o ) 对于二部图g ，令g 的两个部分的顶点集合分别为k 和k 若l i = 1 i ， 则称g 为均衡二部图定义 6 1 ，l ( c ) = m i n d g ( z ) + d g ( y ) l x y l ，y v 2 ， 盯1 ，l ( a ) = m i n d g ( x ) + d g ( 可) i z ，y ，x y e ( g ) ) ( 若g 是个完全二部图，则令仃l ，1 = o o ) 图的个路因子就是指每一个分支都是一条路的一个生成子图给定个正 整数k ，p 因子就是指每个分支都至少含k 个顶点的一个路因子 对于图g 中的一条路p 和一个圈c ，定义路和圈的长度分别为：l ( e ) = i y ( p ) i 一1 ，t ( c ) = i v ( c ) 1 g 的一个哈密顿圈是g 的包含g 中所有顶点的一个圈g 的一个l 一因子 是g 的一个1 正则支撑子图，通常我们称1 因子为完美对集或完美匹配显然 g 的一个1 因子是覆盖g 的所有顶点的一个边集合g 的一个2 因子是g 的 一个2 正则支撑子图，易见2 因子的每一个连通分支为一个圈图的k 个独立 圈是指g 中k 个顶点不相交的圈 图的独立圈、2 一因子和路因子问题是图的因子理论中非常重要的一部分，也 是图的哈密顿圈理论的推广和延伸它是图论中非常有趣的一类问题，也是国内 山东大学硕士学位论文 外研究的热门课题其理论研究日益成熟和完善，而且它在计算机科学、通信网 络设计等中都有重要应用关于图的独立圈、2 一因子和路因子理论的研究主要集 中在以下几个方面：图中含指定个数的独立圈和2 - 因子；含指定长度的独立圈和 2 一因子；图中具有指定性质的独立圈和2 因子；具有指定性质的路因子等等 全文共分四章第一章简单介绍了图论的基本概念，圈和路因子理论的历史 和发展状况及一些已有的相关结论这一章是第二章和第三章的基础 第二章讨论了含4 k 个顶点的简单图的结构和度条件的部分结果其主要结 果如下： 定理2 1 1 设g 是一个有4 k 个顶点的简单图，其中k 是一个正整数，如果 c r 2 ( g ) 4 k 一2 ，则g 包含k - 1 个点不相交的4 圈g ，i = 1 ，2 ，k 一1 ，并且 e ( ( g y ( u 等g ) ) ) 2 本文第三章中我们考虑了含6 七个顶点的二部图的结构和度条件，提出了用 6 一圈与1 2 圈去划分二部图，还有用6 圈去划分二部图主要证明了如下几个 结论 定理3 1 1 设k 2 是一个正整数，g 是有6 七个顶点的均衡二部图，i kl = i i = 3 k ，6 l ，l ( g ) 4 k 一1 ，则g 包含k 1 个点不相交的6 一圈 定理3 1 2 设g 是有6 k ( k 5 ) 个顶点的均衡二部图，i i = l k l = 3 k ，d l ，1 ( g ) 4 k 一1 ，则g 可以划分为k 一2 个6 一圈和个1 2 一圈，并且这k 一1 圈点不相 交 定理3 2 1 设g 为二部图，i i = i k i = 3 k ，6 1 1 ( g ) 4 k + 1 ，则g 包含k 个 6 一圈。 本文第四章主要给出了关于满足一定度条件的图不含指定点的独立圈问题 的注释 另外，本文的第二章和第三章最后还提出了一些问题，以待进一步研究 关键词；独立圈，二部图，均衡二部图，哈密顿圈，路 i i 山东大学硕士学位论文 s o m er e s u l t so i ld i s j o i n t4 - c y c l e sa n d6 - c y c l e s l i ud o n g s c h o o lo fm a t h s y s s c i 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 01 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 x 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 ( c ) 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 g ( v ) t os t a n df o rt h ed e g r e eo ft ，i ng l e ta ( g ) a n d a ( c ) 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 ，l g i = f y ( g ) li st h eo r d e ro f g ，a n d 既( g ) = r n i n d c ( x ) + d g ( y ) i z ，y y ( g ) ，z y ，z yge ( 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 e ( 7 2 ( g ) = 。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 ，l ( g )= , n i n d g ( z ) + d a ( y ) x ，可) 盯1 ，l ( a ) = r a i n r i g ( z ) + 4 g ( v ) l z k ，v k ，x y 簪e ( 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 nm l = i k l ，w ec a l lg ab a l a n c eb i p a r t i t eg r a p h l e tpb eap a t ha n dcac 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 f cb yl ( p ) a n d2 ( c ) ，r e s p e c t i v e l y t h a ti s ，l ( p ) = l y ( p ) l 一1 ，2 ( c ) = i v ( c ) 1 a p a t hf a c t o ri sas p a n n i n gs u b g r a p hw h o s ec o m p o n e n t sa r ep a t h s f o ra p o s i t i v ei n t e g e rk ，p k f a c t o rm e a n sap a t hf a c t o rs u c ht h a te a c hc o m p o n e n th a s a tl e a s tkv e r t i c e s ah a m i l t o nc y c l eo fgi sac y c l eo fgw h i c hc o n t a i n se v e r y v e r t e xo fg ai - f a c t o ro fag r a p hgi sa1 - 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 la 1 - 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 n o fi n d e p e n d e n te d g e st h a tc 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 r s 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 k i n d e p e n d e n tc y c l e so fga r ekc y c l e sw h i c hh a v en oc o m m o nv e r t e x i i 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 i ti sa ni n t e r e s t i n gp r o b l e mi ng r a p ht h e o r y t h ed i s c u s s i o ni sm a t u r e a n dp e r f e c ti n c r e a s i n g l y a n di th a si m p o r t a n ta p p l i c a t i o n si nc o m p u t e rs c i e n c e a n dn e t w o r k s 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 y m o s t l yf o c u so nt h ef o l l o w i n gs e v e r a lt o p i c s ：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 r 6 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 r i d2 - f a c t o rc o n t a i n i n g s 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 rw h i c hh a v e s 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 ep a p e ri sd i v i d e di n t of o u rc h a p t e r s i nc h a p t e rl ，w ei n t r o d u c es o m e b a s i cn o t a t i o n s ，t h eh i s t o r yo ft h ec y c l et h e o r ya n dt h ep a t h - f a c t o r ，a n dt h e p r o g r e s so nt h ec y c l ea n dt h ep a t h - f a c t o rt h e o r y t h i sc h a p t e ri st h eb a s eo ft h e n e x tt w oc 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 s i nt h i sc h a p t e r ：t h em a i nr e s u l ti sa st h ef o l l o w i n g t h e o r e m t h e o r e m2 1 1 s u p p o s egi sas i m p l eg r a p hw i t h4 kv e r t i c e s w h e r e 七i sa p o s i t i v ei n t e g e r i fa r 2 ( g ) 4 k 一2 ，t h e ng c o n t a i n s 七一1v e r t e x - d i s j o i n t4 - c y c l e s w h e r ei = l ，2 ，k 一1 , a n de ( ( g v ( u , g - ：g ) ) ) 2 i nc h a p t e r3 ，w eh a v et h ef o l l o w i n gr e s u l t s t h e o r e m3 1 1 l e t 后2b eap o s i t i v ei n t e g e ra n dgb eab a l a n c eb i p a r t i t e g r a p hw i t h6 kv e r t i c e s i fl i = i k l = 3 ka n d 占l ，l ( c ) 4 k 一1 ，t h e ng c o n t a i n s k lv e r t e x - d i s j o i n t6 - c y c l e s t h e o r e m3 1 2 l e t 后5b eap o s i t i v ei n t e g e ra n dgb eab a l a n c eb i p a r t i t e g r a p hw i t h6 kv e r t i c e s i fi h l = i l = 3 ka n d6 1 ，l ( a ) 之4 k 一1 ，t h e ng c o n t a i n s k 一26 - c y c l e sa n da1 2 一c y c l es u c ht h a ta l lo ft h e ma r ev e r t e x - d i s j o i n t t h e o r e m3 2 1 l e tgb eab a l a n c eb i p a r t i t eg r a p h i fi i = i k l = 3 ka n d 6 1 1 ( a ) 4 k + 1 , t h e ng c o n t a i n sk6 - c y c l e s i nc h a p t e r4 w eg i v et w oc o u n t e r e x a m p l e sf o rag r a p hs a t i s f y i n gs o m ec o n d i t i o n st oc o n t a i ni 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 dv e r t i c e s f u r t h e r m o r e ，i nc h a p t e r2 ，c 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 s f o rf u t u r er e s e a r c h i v 山东大学硕士学位论文 k e yw o r d s ：i n d e p e n d e n tc y c l e ，b i p a r t i t eg r a p h ，b a l a n c eb i p a r t i t eg r a p h ， h a m i l t o nc y c l e ，p a t h v 山东大学硕士学位论文 v ( a ) l g l e ( g ) j ( g ) a ( c ) c l a ( v ) a r 2 ( g ) 符号说明 g 的顶点集合 图g 的阶 g 的边集合 g 的最小度 g 的最大度 在图g 中的度 s 导出的g 的子图 g 中两个不相邻的顶点的最小度和 不小于z 的最小整数 【z j不大于z 的最大整数 v i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 盖! j 庄 e t 期：三幽丞占， 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件 和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 副歪 导师签名： 瑶忽型坠日期：2 匾。支矿 ，1j -伤， - 书 第一章引言 本章第一节首先介绍一些在本文中要用到的图论定义及术语，未说明的图论 术语在其他章节中必要时再给予阐述；第二节主要介绍圈理论及因子理论的历史 背景和进展状况；第三节简单介绍一些已有的相关结论以及本文的主要结果 1 1 基本概念 我们首先介绍一些常用的图论术语，其他未说明的定义和术语请参见文献 1 】我们通常称二元集合g = g ( y ( g ) ，e ( g ) ) 为一个图，其中w ( c ) d 称 为顶点集合，y ( g ) 中的元素称为图g 的顶点；e ( g ) 为边集合，e ( c ) 中的元 素称为图g 的边当l v ( g ) i + i e ( g ) i i u i ， 则称u 为g 的最大独立集g 的独立数是指它的最大集中的顶点个数，记为 q ( g ) 设a 、b 是v ( c ) 的两个不相交的子集，a 和j e i 之间的边集我们记为 e g ( a ? b ) = z y e ( g ) l x a ，y b ) ，且e ( a ，b ) = e c ( a ，b ) 设日是g 的 个子图，对任意z v ( g ) 一y ( 日) ，有j 】、( z ) = j 】、b ( z ) n y ( ) g 的一个哈 密顿圈是g 的包含g 中所有顶点的一个圈若g 包含个哈密顿圈，则称g 是个哈密顿图g 的个1 因子是g 的个1 正则支撑子图，通常我们称1 一 因子为完美对集或完美匹配显然g 的一个l 一因子是覆盖g 的所有顶点的一个 边集合g 的一个2 因子是g 的个2 一正则支撑子图，易见2 因子的每一个 连通分支为一个圈g 的一个子图集合称为相互独立的或顶点不相交的，如果它 们中的任何元素在g 中没有公共顶点若存在v ( g ) 的两个不交子集x 、y ，使 山东大学硕士学位论文 得v ( c ) = xuy ，且g 的所有边均有一个端点在x 内，另一个端点在y 内， 则称g 为二部图，也称为二分图记为g = ( x ：y ；e ( g ) ) ，简记为g = ( x ，y ) 如果i x i = i y i ，则称g 为均衡二部图我们用d ( x ，y ) 表示g 中从z 到y 的 距离如果图g = g ( y ( g ) ，e ( g ) ，妒g ) 和图h = 日( y ( 日) ，e ( 日) ，砂h ) 之间存在一 个双方单值的映射偶( 目，) ，满足口：v ( v ) 一y ( 日) ，及：e ( g ) 一e ( 日) ，且 此= u u 铮砂日( 砂( e ) ) = 口( ) 占( t ，) ) 则称图g 和图h 同构，记为g 兰h 长为4 的圈称为4 一圈，长为6 的圈称为6 一圈，长为1 2 的圈称为1 2 - 圈 1 2 问题产生的背景及其进展状况 哈密顿圈是有一个圈的2 因子关于哈密顿圈度条件的结果有很多，其中 最经典的两个结果是由d i r a c 和o r e 给出的 定理1 2 1 ( d i r a c 2 ) 设g 是一个图，其顶点数n 3 如果6 ( g ) 号，则g 有 一个哈密顿圈 定理1 2 2 ( o r e 3 ) 设g 是一个顶点数n23 的图，并且a 2 ( g ) n ，则g 有 一个哈密顿圈 对于二分图g = ( ，k ；e ) ，m o o n 和m o s e r 给出了一个图g 含一个哈密顿 圈的度条件 定理1 2 3 ( 【4 】) 设g = ( ，v 2 ；e ) 是一个二分图使得i i = i k i = n 并且 o 1 ，l ( g ) n + 1 ，则g 有一个哈密顿圈 图的独立圈理论和2 一因子理论是图的哈密顿圈理论的推广和延伸图的路 因子理论又是图的独立圈理论的推广和延伸图的独立圈理论和2 一因子理论是 图论中非常有趣的一类问题其理论研究日益成熟和完善，而且它在计算机科 学、通信网络设计等中都有重要应用关于图的独立圈理论和2 一因子理论的研 究主要集中在以下几个方面：图中含指定个数的独立圈和2 一因子；含指定长度 的独立圈和2 因子；图中具有指定性质的独立圈和2 一因子等等 1 9 6 3 年，c o r r d d i 和h a j n a l 在【5 】中给出了一个图g 含k 个独立圈的最小 度条件j u s t e s e n 6 】把此最小度条件推广到更一般的情况 2 山东大学硕士学位论文 定理1 2 4 ( 5 ) 设g 是一个顶点数为n 的图如果n 3 k 并且j ( g ) 2 k ，那 么g 含k 个顶点不相交的圈 定理1 2 5 ( 6 】) 设g 是一个顶点数为n 的图如果n 3 k 并且观( g ) 4 k ， 那么g 含k 个顶点不相交的圈 e n o m o t o 7 】和w a n g 8 各自独立地把上述度条件c r 2 ( g ) 24 k 改进为c r 2 ( g ) 2 4 后一1 b r a n d t 等利用上述结果进一步证明了： 定理1 2 6 ( 【9 】) 设g 是一个顶点数为n 的图如果n 4 k 并且叻( g ) n ，那 么g 有一个2 因子恰含k 个顶点不相交的圈 果： 1 9 8 4 年，z a h a r 考虑了图中含指定长度圈的度条件问题，证明了下面的结 定理1 2 7 ( 【1 0 】) 设g 是一个图其顶点数i y ( g ) l = n l + n 2 ，其中n 1 3 ，n 2 之3 为两个整数如果6 ( g ) 等1 + 等1 ，那么g 有两个独立圈c t 和岛，其长分 别为n l 和? 2 2 z a h a r 同时给出了一个著名的猜想： 猜想1 2 8 ( 【1 0 】) 设g 是一个图其顶点数礼= n 1 + n 2 + + n 七( m 3 ) ，如果 6 ( g ) 等 + 等 + + 警 ，那么g 有k 个独立圈c t ，q ，g ，其长分别 为7 2 1 ，n 2 ，凡 此猜想至今尚未得到解决c a t l i n 证明了以下结果： 定理1 2 9 ( 【1 1 】) 设g 是一个图其顶点数n = n l + n 2 + + n k ( 3 ) ， 如果6 ( g ) 警+ d ( n ) ，那么g 有k 个独立圈c l ，岛，g ，其长分别为 n 1 ，n 2 ，几k a i g e r 和b r a n d t 改进了以上结果，得到下面的定理： 定理1 2 1 0 ( 1 2 】) 设g 是一个图其顶点数n = n l + 他+ + 佗( 仡3 ) ，如 果6 ( g ) 学，那么g 有后个独立圈a ，q ，g ，其长分别为礼1 ，? 2 2 ，n 七 3 山东大学硕士学位论文 对所有7 , i = 3 的情况，w a n g 证明了如下结果： 定理1 2 1 1 ( 【1 3 】) 设g 是一个顶点数为n 的图假设n 3 k + 3 ，占( g ) 之下n + k ， 那么g 有一个2 一因子含k + 1 个独立圈c 1 ，c 2 ，c k + l 使得对所有1 is k 都有i g i = 3 e n o m o t o 用c r 2 代替6 ，得到以下结果： 定理1 2 1 2 ( 1 4 1 ) 设g 是一个顶点数为n 的图假设n 3 k + 3 ，c r 2 ( g ) ( 几+ 七) ，那么g 有一个2 因子含k + 1 个独立圈c 1 ，6 2 ，c k + 1 使得对所有 1 i k 都有i g i = 3 对于二部图g = ( ，v 2 ，e ) ，w a n g 证明了下列结果： 定理1 2 1 3 ( 1 5 1 ) 设g = ( k ，v 2 ，e ) 是一个二部图，使得i k l = f k l = 凡2 ， 并且6 ( g ) 号1 + 1 如果k 之0 ，t23 并且n = 2 k + t ，那么g 有一个2 一因 子含七十1 个独立圈c 1 ，c 2 ，c k + 1 使得对所有ls is 惫都有i q i = 4 对于图g 中含若干个3 - 圈的度条件，d i r a c 给出了如下结果： 定理1 2 1 4 ( 1 6 d 设g 是一个顶点数为n 3 k 的图如果j ( g ) t n + k ，那么 g 含k 个独立争圈 对于g 中含两个指定长度的圈问题，w a n g 给出了如下结果： 定理1 2 1 5 ( 1 7 d 设g 是一个顶点数为n 6 的图，使得6 ( g ) 学 ，那么 对任意两个整数s 3 ，t 3 ，s + t n ，g 含两个独立圈g 和岛，其长分别 为s 和t ，除非n ，8 ，t 皆为奇数并且g 笺k 。一1 ) 2 ，( 。一1 ) 2 + k 1 显然，对任意奇数n 3 ，g 竺k ( 。一1 ) 2 ，( 。一1 ) 2 + k 1 不含两个独立奇圈；若 n 为偶数，则j 厶2 ，。2 不含奇圈w a n g 还考虑了下列情况： 定理1 2 1 6 ( 1 7 0 设g 是一个顶点数为n 之6 的图，其中扎为偶数如果 6 ( g ) 詈，那么对任意两个偶数s 4 ，t 4 ，s + t n ，g 含两个独立圈c t 和 q ，其长分别为s 和t 4 山东大学硬士学位论文 对于二部图g = ( ? k ，e ) ，a i l l a r 提出了下面的猜想，并证明了其当k = 2 时成立 猜想1 2 1 7 ( 1 8 】) 设g = ( ，k ，e ) 是一个二部图，使得l i = i k l = n = n 1 + n 2 + + n k ( n i 2 ) 如果6 1 1 佗+ k ，那么g 有k 个独立圈c 1 ，岛，c k ， 其长分别为2 n l ，2 n 2 ，2 n k w a n g 还证明了下面的结果： 定理1 2 1 8 ( 【1 9 】) 设g = ( k ，e ) 是一个二部图，使得i k l = i k i = 礼1 + n 2 + + n 七，其中n l2n 2 n 七2 ，若6 ( g ) r t l + r t 2 虿4 - - 一k r t k ，只- lg 有七个 独立1 tg ：岛，仉，其长分别为2 n 1 ，2 n 2 ，2 n k 定理1 2 1 9 ( 2 0 】) 设g = ( ，k ，e ) 是一个二部图，使得ik l = l k i = n 4 如果对所有z 和y 比都有d ( x ) + d ( y ) n4 - 2 ，那么对任意两个整数 8 2 ，t 2 ，8 + t n ，g 含两个独立圈g 和q ，其长分别为2 s 和2 t 对于过指定边或指定顶点的独立圈和2 - 因子问题，w a n g 在( 2 l 】中给出了 下面的猜想： 猜想1 2 2 0 ( 2 1 】) 如果k 2 ，与n 相比k 足够大，并且a 2 ( g ) n + 2 后一2 ， 那么对g 中任意七条相互独立的边e l ，e 2 ，g 有一个2 因子含k 个独立 圈q ，q ，g ，使得岛e ( g ) 此猜想已被e g a w a 2 2 】等解决 定理1 2 2 1 ( 2 2 】) 设七2 ，l g i = n 3 k ，如果 或 c r 2 ( g ) r y l _ a x ( d , + 2 k 一2 ，【罟j + 4 七一2 6 ( g ) m o z 号 + 七一l ，f 2 产 1 】， 那么对任意给定的k 条独立边e l ：e 2 ，e k ，g 可分为岛个圈日1 ，凰，日k 使得 e t e ( 凰) 5 山东大学硕七学位论文 1 3 已有结论及本文的主要结果 设g 是个简单图，长为4 的圈称为垂圈，长为6 的圈称为6 - 圈对于图 中的4 圈和6 圈的结论主要如下： 定理1 3 1 ( 5 ) 设l g l = n 3 k ，并且6 ( 6 ) 2 k ，则g 包含k 个点不相交的 圈 而j u s t e s e n 通过改进定理1 的度条件，得到了一下更好的结果 定理1 3 2 ( 【6 】) 设l g l = n 3 k ，并且a 2 ( g ) 4 k ，则g 包含k 个点不相交的 圈 r o b e r tj o h a n s s o n 在 2 3 】的定理2 7 中给出了g 包含k - 1 个点不相交的4 - 圈的度条件 定理1 3 3 ( 【2 3 】) 设l g i = 4 k ，并且6 ( 6 ) 2 k ，则g 包含k 1 个点不相交的4 - 圈和一条独立的缸路 d a n h o n gz h a n g 和h o n gw a n g 则在中的引理2 1 2 中将定理3 的度条件改 为6 ( g ) 2 k 1 定理1 3 4 ( 2 4 】) 设i g i = 4 k ，并且6 ( 6 ) 2 k l ，则g 包含k 1 个点不相交 的4 圈 定理1 3 5 ( 2 5 】) 设l g i = 4 k ，其中k 是个正整数，如果c r 2 ( g ) 4 k 一2 ，则 g 包含k - 1 个点不相交的4 圈 设g 是个一个均衡二部图，长为6 的圈称为6 - 圈，长为1 2 的圈称为1 2 圈对于二分图中的6 圈的结论主要如下： 定理1 3 6 ( 【2 6 】) 设l g l = ( k ，；e ) 是个二部图，且l l = i k l = n 2 k + l ， 其中k 是一个正整数如果6 ( a ) f n 2 + 1 ，则g 包含一个2 一因子，这个2 因子恰好有k 个分支 定理1 3 7 ( 2 7 】) 设i g i = ( ，v s ；e ) 是一个二部图，且i k l = k i = 3 k ，如果 6 ( g ) 22 k + l ，则g 包含k 个独立的6 - 圈 6 山东大学硕士学位论文 定理l 3 8 ( 2 8 】) 设i g f = ( ，k ；e ) 是一个二部图，且i m f = i k f = 3 k ，其中 k 是个正整数如果6 ( g ) 2 k 一1 ，则g 包含至少k - 1 个相互独立的6 一圈并 且使每一个昏圈至少包含两条弦 定理1 , 3 9 ( 2 9 】) 设i g f = ( m ，k ；e ) 是一个二部图，且f i = i k i = n 3 k ， 其中k 2 是一个正整数如果o t ，l ( g ) 礼+ k ，那么对g 中的任意k 条 独立边e l ，e 2 ，e 七，g 中一定存在k 个相互独立的圈白，岛，_ ，g ，并且使 岛e ( g ) ，j g i 6 ，对任一i 1 ，2 ，后) 定理1 3 1 0 ( 2 9 p 设l g l = ( ，k ；e ) 是一个二部图，且1 i = i i = n 3 k ， 其中k 2 是一个正整数如果f f l 1 ( g ) 凡+ k ，那么对g 中的任意k 条 独立边e l ，e 2 ，g 中一定存在k 个相互独立的圈a ，q ，伉，并且使 e t e ( g ) ，对任一i 1 ，2 ，七) ，且y ( a uc 2 u u 仉) = y ( g ) 定理1 3 1 1 c h e ne ta 1 1 3 0 ，w a n g 3 1 】设i g l = n 2 k 如果 “g ) ( 仃“莩1 + 2 k 或 们) 蚴_ 【半 7r 2 礼+ 。4 k 1 ， 那么对任意给定的k 条独立边e l ，e 2 ，e k ，g 含k 个独立圈g ，q ，g 使得 e i e ( g ) ，i c i i 6 h a j i m em a t s u m u r a 在 3 2 】中分别考虑了用o 1 ，1 ( g ) 和6 ( g ) 来限制度条件 并给出了以下几个结果 定理1 3 1 2 ( 【3 2 】) 设k l ，1s8 k ，n 2 k 如果 吼。( g ) m 州半1 l f 莩1 + 2 k ， 那么对任意给定的k 条独立边e l ，e 2 ，e k ，g 含k 个独立圈c 1 ，岛，仅使得 e e ( c d ，f g f 6 且 a ：q ，g ) 中至少含有8 个4 - 圈 定理1 3 1 3 ( 3 2 】) 设k 1 ，0 s 七，n 2 k 如果 郧) 半1 r 2 n + 。4 k l ， 山东大学硕士学位论文 那么对任意给定的k 条独立边e l ，e2 ，e ，g 有含k 个独立圈c 1 ，q ，g 使 得e t e ( g ) ，i g i = 4 ( 1 iss ) ，i g i 6 ( s + 1 i 七) 由定理1 3 2 和定理1 3 3 又可以推出下面的结论： 定理1 3 1 4 ( 3 2 】) 设k 之l ，t t22 k 如果 o 1 ，l ( g ) 下4 n + 2 k - 1 1 或 占( g ) 2 n + 。3 k 1 ， 那么对任意给定的k 条独立边e l ，e 2 ，仇，g 含k 个独立缸圈g ，q ，g 使 得e t e ( g ) 本文第二章中我们考虑了定理1 3 5 给出的简单图剩余部分的结构和度条 件，主要证明了下面这个结论 定理2 1 1 设g 是一个有4 k 个顶点的简单图，其中k 是一个正整数，如果 a 2 ( c ) 4 k 一2 ，则g 包含k 一1 个点不相交的垂圈g ，i = 1 ，2 ，k 一1 ，并且 e ( ( g y ( u 等g ) ) ) 2 本文第三章中我们考虑了含6 七个顶点的二部图的结构和度条件，主要证明 了如下几个结论 定理3 1 1 设k 2 是一个正整数，g 是有6 七个顶点的均衡二部图，l k l = l k i = 3 k ，6 1 ，1 ( g ) 之4 k l ，则g 包含k 一1 个点不相交的6 一圈 定理3 1 2 设g 是有6 k ( k 5 ) 个顶点的均衡二部图，f kl = i l = 3 k ，6 1 1 ( g ) 4 七一1 ，则g 可以划分为k 一2 个6 一圈和个1 2 一圈，并且这七一1 圈点不相 交 定理3 2 1 设g 为二部图，l l = 1 i = 3 k ，6 1 ，l ( g ) 4 k + 1 ，则g 包含k 个 6 一圈 本文第四章主要给出了关于满足一定度条件的图不含指定点的独立圈问题 的注释 另外，本文的第二章和第三章最后还提出了一些问题，以待进一步研究 8 第二章简单图的结构和度条件 这一章我们主要讨论含4 k 个顶点的简单图的结构如无特殊说明，本章中 的图g 均是指简单图本章共分两节第一节给出了含4 k 个顶点的简单图的结 构第二节给出了可以进一步讨论的问题 2 1 简单图的结构和度条件 在这一章中我们主要研究的是含4 七个顶点的简单图的结构的问题，这一问 题已有的主要结果有： 定理1 3 5 ( 【2 5 】) 设l g i = 4 k ，其中k 是个正整数，如果a 2 ( g ) 4 k 一2 则 g 包含k 一1 个点不相交的垂圈 本章主要证明了以下定理 定理2 1 1 设g 是一个有4 l 【个顶点的简单图，其中k 是一个正整数，如果 a 2 ( g ) 24 k 一2 ，则g 包含k - 1 个点不相交的4 一圈g ，i = 1 ，2 ，k 一1 ，并且 e ( ( g y ( u 譬c ：) ) ) 芝2 证明定理2 1 1 之前我们先给出下面的引理： 引理2 1 1 ( ( 2 5 】) 设e 是一个4 圈并且z ，y 是图g 中独立于c 的两个不同 的点如果d ( x ，c ) + d ( y ，c ) 5 ，那么包含一个4 圈c 7 和一条与其点不想交 的边e ，并且e 恰好只与x ，y 中的一个点相邻 定理2 1 1 的证明：设g 是满足定理2 1 1 条件的简单图，根据定理1 3 5 ，我 们可以知道图