（运筹学与控制论专业论文）关于图中相互独立的圈和2因子的新结果.pdf

山东大学硕士学位论文 关于图中相互独立的圈和2 因子的新结果 子潇 山东大学数学与系统科学学院 运筹学与控制论 山东济南2 5 0 1 0 0 中文摘要 本文考虑的图若无特殊声明均为简单、无向有限图，对于个图g = g ( y ( g ) ， e ( g ) ) ，我们用v ( g ) 和e ( g ) 分别表示图的顶点集合和边集合对任意的t ， y ( g ) ，我们用如( t ，) 表示顶点t ，在g 中的度数( g ) 和6 ( g ) 分别表示图g 的最大度和最小度，在不引起混淆的情况下简记为和j 对于图g ，我们用 i g i = i y ( g ) i 表示g 的阶数，即g 的顶点数，并定义图g 中两个不相邻的顶点 的最小度和为； a r 2 ( g ) = m i n d a ( z ) + d c ( u ) l = ，y y ( g ) ，z y ，x yge ( g ) ) ( 若g 是个完全图，则令c r 2 ( g ) = ) 对图g 中任意点缸，u 的邻域定义如下：小，g m ) = z v ( g ) i 伽e ( g ) ) 完全二部图k x 3 称为一个爪，如果g 不含同构于k t ，3 的生成子图，则 称g 是无爪图对于图g 中的一条路p 和个圈c 。定义路和圈的长度分别 为：l ( p ) = l y ( p ) i 一1 ，t ( c ) = i v ( c ) 1 g 的个哈密顿圈是g 的包含g 中所有顶点的个圈g 的一个1 因子 是g 的个1 正则支撑子图，通常我们称1 因子为完美对集或完美匹配显然 g 的一个1 因子是覆盖g 的所有顶点的个边集合g 的个2 因子是g 的 个2 - 正则支撑子图，易见2 因子的每一个连通分支为一个圈图的k 个独立 圈是指g 中k 个顶点不相交的圈 图的独立圈、2 因子问题是图的因子理论中非常重要的一部分，也是图的哈 密顿圈理论的推广和延伸它是图论中非常有趣的一类问题，其理论研究日益成 熟和完善，而且它在计算机科学、通信网络设计等中都有重要应用关于图的独 立圈、2 一因子的研究主要集中在以下几个方面：图中含指定个数的独立圈和2 - 因子，含指定长度的独立圈和2 因子和图中具有指定性质的独立圈和2 一因子等 等 全文共分三章第一章简单介绍了图论的基本概念，圈和因子的历史和发展 状况及一些已有的相关结论这一章是第二章和第三章的基础 山东大学硕士学位论文 在本文的第二章中，我们研究了图中含指定长度的相互独立的圈问题，颜谨 1 7 】证明了下面的的结论：如果g 是个简单图，s ，k 是两个正整数并且s k ， 其中g 的顶点个数n 3 sq - a ( k 一8 ) + 3 如果砚( g ) n + s ，那么g 包含 k 个顶点不相交的圈g ，仉并且i g i = 3 其中1 i 8 ，i g i = 4 其中 8 i k 在第二章中我们则有以下结论： 定理2 1 1 如果g 是个简单图，8 ，k 是两个正整数并且s k ，其中g 的顶 点个数佗3 s + a ( k s ) + 3 如果c r 2 ( g ) 佗+ 2 k 一生笋，那么g 包含k 个顶 点不相交的圈a ，晚并且i g i = 3 其中1 i s ，i q i = 4 ，i e ( g ) l 5 其 中8 i k 第三章我们则讨论了图中含指定边和指定长度的图的2 因子的问题其主 要结果如下， 定理3 1 1 设g 是一个有n l + 他+ 1 个顶点的简单图，其中n 1 3 ，n 2 3 若占( g ) 孕1 + f 孕1 + l ，那么g 包含两个顶点不相交的圈o ，岛，其中 i c x i = 啦+ 1 ，i q i = n j ( i ，j = 1 ，2 ) ，并且v e g 我们有e e ( c t ) 或e e ( q ) 关键词t 独立圈，无爪图，2 一因子，哈密顿圈，哈密顿图 山东大学硕士学位论文 s o m en e wr e s u l t so ni n d e p e n d e n tc y c l e sa n d2 - f a c t o ri ng r a p h s y ux i a o 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 n2 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 e ag r a p h ，w h e r ev ( g ) a n de ( c ) 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 e 如( 口) t os t a n df o rt h ed e g r e eo f 可i ng l e ta ( c ) a n d 6 ( c ) d e n o t et h em 扣面丑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 ) ji st h eo r d e ro fg ，a n d d 2 ( g ) = r a i n r i g ( 功+ d g ( 可) l z ，可y ( g ) ，z y ，x y 窖e ( g ) ) i st h em i n i l n m nd e g r e es u i no fn o n a d j a c e n tv e r t i c e s ( 、h 印gi sac o m p l e t e g r a p h ，w ed e f i n e ( g ) = o o ) f o rav e r t e xuo fg ，t h en e i g h b o r h o o do f 让a r ed e n o t e db yn g ( u ) = z y ( g ) l z t l e ( g ) ，i kc o m p l e t eb i p a r t i t eg r a p hk 1 ，3i sc a l l e dac l a w ，a n dg i s s 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 ok i 3 l e tpb ea p a t ha n dc ac 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 yl ( p ) a n d z ( c ) ，r e s p e c t i v e l y t h a ti 8 ，l ( p ) = i y ( p ) i l ，z ( c ) = i v ( c ) 1 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 yv e r t e xo fg a1 - 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 d 骶c a l la 1 - f a c t o ra p 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 ta 1 - 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 t h et h e o r yo fi n d e p e n d e n tc y c l e sa n d2 - f a c t o ro fg r a p h si st h ee x t e n d i n g o fh a m i l t o nc y c l et 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 f u r - t h e r m o r ei th a si m p o r t a n ta 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 s t h e s t u d yo fi n d e p e n d e n tc y c l e sa n d2 - f a c t o rt h e o r ym o s t l yf o c u s e so nt h ef o l l o w i n g ： a s p e c t sg 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 rc o n t a i n i n gs p e c i f i e dl e n g t h ，a n dg r a p hc o n t a i n i n g i 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 es p e c i f i e dp r o p e r t i e s ，e t c i i i 山东大学硕士学位论文 t h ep a p e ri sd i v i d e di n t ot h r e ec h a p t e r s i nc h a p t e r1 w ei n t r o d u c e8 0 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 y t b j 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 c o n c e r n i n gi n d e p e n d e n tc y c l e sc o n t a i n i n gs p e c i f i e dl e n g t h ，y a aj i n 【1 7 】p r o v e d t h en e x tr e s u l t l e t3a n d 后b et w op o s i t i v ei n t e g e r sw i t hs 七，a n dl e tgb ea g r a p ho f o r d e rn 3 s + 4 ( 一s ) + 3 i fc r 2 ( g ) n + s ，t h e ngc o n t a i n s 七d i s j o i n t c y c l e 8c 1 ，gs a t i s f y i n gi g l = 3f o r1 i sa n di a i = 4f o rs i 七i a c h a p t e r2 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 2 1 1 l e tsa n d 七b et w op o s i t i v ei n t e g e r sw i t hs5 七，a n dl e tg b eag r a p ho fo r d e rn 3 s + 4 ( k s ) + 3 i fc r 2 ( g ) 佗+ 2 k 一半，t h e ng c o n t a i n s 七d i s j o i n tc y c l e sc 1 ，仇s a t i s f y i l a gl g i = 3f o r1si sa n di g i - m4 ， i e ( g ) i 5f o rs i 七 i l ac 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 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 de d g e s i nt h i sc h a p t e r ，t h em a i nr e s u l ti sr t qt h ef o l l o w i n gt h e o r e m t h e o r e m 3 1 1 l e t g b e a s i m p l e g r a p h o f o r d e r n l + 砌+ l ，a n d n l 3 ，n 2 芝3 i f6 ( g ) 孕 + 孕1 + 1 ，t h e ng c o n t a i n st w od i s j o i n tc y c l e sq ，qs a t i s f y i n g i g i = 啦+ 1 ，1 6 2 i = n j ( i ，j = 1 ，2 ) ，a a dv e g w eh a v ee e ( q ) o re e ( 岛) k e yw o r d s ：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 ，h a m i l t o nc y c l e ，h a m i l - t o ng r a p h i v 山东大学硕士学位论文 v ( g ) i g l e ( g ) 万( g ) ( g ) 如( t ) 观( g ) m h 符号说明 g 的顶点集合 图g 的阶 g 的边集合 g 的最小度 g 的最大度 t 7 在图g 中的度 g 中两个不相邻的顶点的最小度和 s 导出的g 的子图 不小于z 的最小整数 不大于z 的最大整数 v 原创性声明 本人郑重声明s 所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果对本文的研 究作出重要贡献的个人和集体，均已在本文中以明确方式标明本声 明的法律责任由本人承担 论文作者签名 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他手段保存 论文和汇编本学位论文 ( 保密论文在解密后应遵守此规定) 论文作者签名：三e 缸导师签名：啦日期：2 鲤墨：s ，萝 第一章引言 本章第一节首先介绍一些在本文中要用到的图论定义及术语，未说明的图论 术语在其他章节中必要时再给予阐述；第二节主要介绍圈理论及因子理论的历史 背景和进展状况；第三节简单介绍一些已有的相关结论以及本文的主要结果 1 1 基本概念 我们首先介绍一些常用的图论术语，其他未说明的定义和术语请参见文献 【1 】我们通常称二元集合g = g ( y ( g ) ，e ( g ) ) 为一个图，其中v ( g ) 0 称为 顶点集合，v ( g ) 中的元素称为图g 的顶点；e ( g ) 为边集合，e ( g ) 中的元素 称为图g 的边当i y ( g ) i + i e ( g ) l i u l ，则称u 为g 的最大独立集g 的 独立数是指它的最大集中的顶点个数，记为q ( g ) 设a 、b 是v ( g ) 的两个不相 交的子集，a 和b 之间的边集我们记为e g ( a ，b ) = 【z y e ( g ) i x a ，y b ， 且e ( a ，b ) = e g ( a ，b ) 设日是g 的一个子图，对任意z v ( g ) 一y ( 日) ，有 ( z ) = n g ( z ) ny ( 日) g 的一个哈密顿圈是g 的包含g 中所有顶点的一个 圈若g 包含个哈密顿圈，则称g 是一个哈密顿图g 的个1 - 因子是g 的个1 正则支撑子图，通常我们称l 一因子为完美对集或完美匹配显然g 的 一个1 一因子是覆盖g 的所有顶点的个边集合g 的一个2 因子是g 的一个 2 - 正则支撑子图，易见2 一因子的每一个连通分支为个圈g 的一个子图集合 称为相互独立的或顶点不相交的，如果它们中的任何元素在g 中没有公共顶点 若存在v ( g ) 的两个不交子集x 、y ，使得v ( g ) = xuy ，且g 的所有边均有 山东大学硕士学位论文 一个端点在x 内，另个端点在y 内，则称g 为二部图，也称为二分图记为 g = ( x ，k e ( g ) ) ，简记为g = ( x ，y ) 如果f x i = i y l ，则称g 为均衡二部图 完全二部图k t ，3 称为个爪如果g 不含同构于蜀3 的生成子图，则称g 是无爪图 1 2 问题产生的背景 一、哈密顿圈的基本定理 哈密顿圈是有个圈的2 - 因子关于哈密顿圈度条件的结果有很多，其中 最经典的两个结果是由d i r a c 和o r e 给出的 定理1 2 1 ( d i i 批f 2 】) 设g 是一个图，其顶点数疗3 如果j ( g ) 詈，则g 有 一个哈密顿圈 推论1 2 2 设a , b 是图g 的一条哈密顿路的两个端点，如果d ( a ，g ) + d ( b ，g ) i g i ，那么图g 是哈密顿图 定理1 2 3 ( o r e 3 ) 设g 是一个顶点数佗3 的图，并且c r 2 ( g ) n ，则g 有 一个哈密顿圈 对于二分图g = ( ，e ) ，m o o n 和m o s e r 给出了个图g 含个哈密顿 圈的度条件 定理1 2 4 ( 【4 】) 设g = ( k ，e ) 是一个二分图使得i l = i k i = n 并且 0 1 ，i ( g ) n + 1 ，则g 有一个哈密顿圈 二、图中含独立圈和2 - 因子问题 图的独立圈理论和2 - 因子理论是图的哈密顿圈理论的推广和延伸图的独 立圈理论和2 _ 因子理论是图论中非常有趣的一类问题，也足国内外研究的热门 课题其理论研究日益成熟和完善，而且它在计算机科学、通信网络设计等中都 有重要应用关于图的独立圈理论和2 一因子理论的研究主要集中在以下几个方 面：图中含指定个数的独立圈和2 因子；含指定长度的独立圈和2 因子；图中 具有指定性质的独立圈和2 一因子等等 2 山东大学硕士学位论文 1 9 6 3 年，c o r r d 和h a j n a l 在 5 】中给出了个图g 含k 个独立圈的最小度 条件j u s t e s e n 6 】把此最小度条件推广到更般的情况 定理1 2 5 ( 5 】) 设g 是一个顶点数为仃的图如果n 之3 k 并且6 ( g ) 2 k ，那 么g 含k 个顶点不相交的圈 定理1 2 6 ( 【6 】) 设g 是一个顶点数为n 的图如果7 l 3 k 并且观( g ) 4 k ， 那么g 含k 个顶点不相交的圈 e n o m o t o 7 】和w a n g 8 】各自独立地把上述度条件砚( g ) 4 k 改进为c r 2 ( g ) 之 4 南一1 b r a n d t 等利用上述结果进一步证明了t 定理1 2 7 ( 【9 】) 设g 是一个顶点数为n 的图如果佗4 k 并且a 2 ( a ) n ，那 么g 有一个2 因子恰含k 个顶点不相交的圈 果t 三、图中含指定长度的独立圈和参因子问题 1 9 8 4 年，z a h a r 考虑了图中含指定长度圈的度条件问题，证明了下面的结 定理1 2 8 ( 1 0 】) 设g 是- - 4 $ 1 其顶点数l y ( g ) i = n l + n 2 ，其中n l 3 ，n 2 3 为两个整数如果j ( g ) 之警1 + 警1 ，那么g 有两个独立圈口和岛，其长分 别为仃l 和砌 z a h a r 同时给出了一个著名的猜想： 猜想1 2 9 ( 【1 0 】) 设g 是一个图其顶点数礼= n l + n 2 + + n k ( m 3 ) ，如果 j ( g ) f 等1 + f 等1 + + f 警1 ，那么g 有k 个独立圈q ，c 2 ，仉，其长分别 为n l ，仃2 ，佗七 此猜想至今尚未得到解决c a t l i n 证明了以下结果： 定理1 2 1 0 ( 【1 1 】) 设g 是- 4 $ i 其顶点数几= n l + 他+ + n k ( m23 ) ， 如果占( g ) 警+ d ( 佗) ，那么g 有k 个独立圈q ，岛，g ，其长分别为 n l ，砌，n k 3 山东大学硕士学位论文 a i g e r 和b r a n d t 改进了以上结果，得到下面的定理： 定理1 2 1 1 ( 【1 2 】) 设g 是一个图其顶点敷铊= n l + n 2 + + 佗七仇3 ) ，如 果6 ( g ) 学，那么g 有k 个独立圈c 1 ，岛，g ，其长分别为n l ，n 2 ，仃七 对所有啦= 3 的情况，w a n g 证明了如下结果： 定理1 2 1 2 ( 【1 3 】) 设g 是一个顶点数为佗的图假设佗3 k + 3 ，6 ( g ) 下n + k ， 那么g 有一个参因子含k + 1 个独立圈c 1 ，岛，q + 1 使得对所有1 i k 都有i a l = 3 e n o m o t o 用观代替6 ，得到以下结果： 定理1 2 1 3 ( 1 4 1 ) 设g 是一个顶点数为n 的图假设n 3 k + 3 ，a r 2 ( g ) m + 后) ，那么g 有一个参因子含k + 1 个独立圈q ，岛，q + 1 使得对所有 1 i k 都有i g i = 3 对于g 中含两个指定长度的圈问题，w a n g 给出了如下结果； 定理1 2 1 4 ( 【1 5 】) 设g 是一个顶点数为n 6 的图，使得6 ( g ) 之学 ，那么 对任意两个整数s 3 ，t 3 ，s + t n ，g 含两个独立圈g 和岛，其长分别 为s 和t ，除非n ，s ，t 皆为奇数并且g 鲁甄舾1 ) 2 ，( n - 1 ) 2 + 凰 显然，对任意奇数n 3 ，g 兰甄n 一1 ) 2 ，( 加1 ) 2 + 蜀不含两个独立奇圈；若 n 为偶数，则k 临n 2 不含奇圈w a n g 还考虑了下列情况： 定理1 2 1 5 ( 【1 5 】) 设g 是一个顶点数为亿6 的图，其中7 l 为偶数如果 6 ( g ) 詈，那么对任意两个偶数8 4 ，t 4 ，8 + t n ，g 含两个独立圈c 1 和 q ，其长分别为s 和t 对于图g 中含若干个譬圈的度条件，d i r a c 给出了如下结果： 定理1 2 1 6 ( 1 6 d 设g 是一个顶点数为n 3 k 的图如果6 ( g ) 学，那么 g 含k 个独立乒圈 4 山东大学硕士学位论文 对于图g 中含若干个3 圈和垂圈，b r a n d t 等给出了以下结果： 定理1 2 1 7 ( 【9 】) 如果g 是一个简单图，s , k 是两个正整数并且s5 七。其中g 的顶点个数仃3 s + 4 ( k 一8 ) + 3 如果a 2 ( g ) n + 5 ，那么g 包含k 个顶点 不相交的圈a ，q 并且i g l = 3 其中1 i s ，i c t f 4 其中8 i k 而颜谨在此基础上又给出了以下结果： 定理1 2 1 8 ( 1 7 j ) 如果g 是一个简单图，s , k 是两个正整数并且8 居，其中g 的顶点个数n 3 s + 4 ( 七一8 ) + 3 如果晚( g ) 芝n + s ，那么g 包含蠡个顶点 不相交的圈a ，仇并且i g l = 3 其中1 i s ，l g i = 4 其中8 i k 本文则给出了下面的结论s 定理2 1 1 如果g 是一个简单图，s , k 是两个正整数并且8s 七，其中g 的顶 点个数n 3 s + 4 ( 七一8 ) + 3 如果c r 2 ( g ) n + 2 后一曼笋，那么g 包含后个顶 点不相交的圈q ，g 并且i g i = 3 其中15is8 ，i a i = 4 ，i e ( a ) i 5 其 中8 t 七 四、二分图中含指定长度的独立圈和二因子问题 对于二部图g = ( ，e ) ，w a n g 证明了下列结果： 定理1 2 1 9 ( 【1 8 】) 设g = ( h ，k ，e ) 是一个二部图，使得i i = i l 亍n 2 ， 并且6 ( g ) 量1 + 1 如果七0 ，t 3 并且n = 2 k + t ，那么g 有一个2 - 因 子含七+ 1 个独立圈c 1 ，岛，戗+ l 使得对所有1 i 詹都有i g i = 4 同时w a n g 1 9 又给出了这样一个结果：设g = ( ，e ) 是一个二分图， 且i v x i = i k i = 3 k 如果6 ( g ) 2 k + l ，那么g 包含詹个独立的6 圈，且每个 6 圈至少含2 条弦 对于二部图g = ( ，k ，e ) ，a m a r 提出了下面的猜想，并证明了其当七= 2 时成立 猜想1 2 2 0 ( 【2 0 】) 设g = ( ，e ) 是一个二部图，使得i i = i i = n = 死l + 砚+ + 仇( 啦2 ) 如果6 l ，l n + k ，那么g 有七个独立圈a ，岛，仉， 其长分别为2 礼l ，2 n 2 ，2 辄 5 山东大学硕士学位论文 w a n g 还证明了下面的结果， 定理1 2 2 1 ( 【2 1 】) 设g = ( ，k ，e ) 是一个二部图，使得l i = i k i = n l + n 2 + + 7 l k ，其中n l n 2 死七2 ，若j ( g ) 丑堡2 产，则g 有k 个 独立圈q ，岛，g ，其长分别为2 n 1 ，2 他，2 n k 定理1 2 2 2 ( 【2 2 】) 设g = ( v l ，k ，e ) 是一个二部图，使得i i = i k l = n 4 如果对所有z 和y k 都有d ( z ) + d ( y ) 礼+ 2 ，那么对任意两个整数 8 2 ，t 之2 ，8 + t 7 l ，g 含两个独立圈g 和q 。其长分别为2 s 和2 五、图中含指定边或指定点的独立圈和2 - 因子问题 对于过指定边或指定顶点的独立圈和2 因子问题，w a n g 在 2 3 】中给出了 下面的猜想： 猜想1 2 2 3 ( 【2 3 ) 如果k 之2 ，与t l 相比k 足够大，并且观( g ) n + 2 k 一2 ， 那么对g 中任意k 条相互独立的边e l ，e 2 ，铅，g 有一个2 - 因子含七个独立 圈q ，c 2 ，仉，使得e i e ( g ) 此猜想已被e g a w a 2 4 】等解决 定理1 2 2 4 ( 2 4 1 ) 设詹2 ，i g i = n 3 k ，如果 c r 2 ( g ) 僦 n + 2 k 一2 ，【刳+ 4 七一2 ) 或 6 ( g ) 懈 詈1 + k l ，坐学1 1 ) ， 那么对任意给定的k 条独立边e l ，e 2 ，e k ，g 可分为矗个圈日1 ，日2 ，风使得 e t e ( 皿) 本文则给出了下面的这个结论： 定理3 1 1 设g 是个有i l l + l i 2 + 1 个顶点的简单图，其中佗l 3 ，n 2 3 若石( g ) 之f 纽41 + f 墨丝2 41 + l ，那么g 包含两个顶点不相交的圈g ，c 2 ，其中 i c i i = 啦+ 1 ，i q i = 码( i ，j = 1 ，2 ) ，并且v e g 我们有e e ( a ) 或e e ( c 2 ) 在二分图中w a n g 2 5 】证明了：设g = ( k ，k ，e ) 是一个二分图使得i m i = k i = n 3 k ，其中k 2 是个整数假设对0 1 ，l ( g ) n + k ，则对g 中任 6 山东大学硕士学位论文 意给定的七条独立的边e 1 ，e k ，g 包含k 个顶点不相交的圈q ，仅使得 e e ( g ) 并且l ( q ) 6 ，其中i 1 ，后刘桂真和颜谨在 2 6 】和 2 7 】中给 出了下面两个定理； 定理1 2 2 5 ( 【2 6 】) 设g = ( ，k ，e ) 是一个二分图满足l i = l k l = n 2 k + 1 ， 其中k 1 是一个整数假设对o 1 ，1 ( g ) 4 n + 3 2 k - - i ，则对g 中任意给定的k 条独立的边e l ，e k ，g 有一个参因子含k + 12 , - r 点不相交的彳圈使得 岛e ( c ；f ) ，其中i 1 ，詹 定理1 2 2 6 ( 【2 7 ) 设g = ( k ，k ，e ) 是一个二分图满足i k i = i k i = 2 k ，其中 七1 是一个整数假设对0 1 ，1 ( g ) 3 k + 1 ，则对g 中任意给定的七条独立 的边e l ，g 有一个参因子含七个顶点不相交的名一圈使得e i e ( q ) ，其 中i 1 ，k 对于图中含指定顶点的独立圈和2 一因子问题刘桂真和颜谨在【2 剐和【2 9 】中 给出了下面两个定理： 定理1 2 2 7 ( 2 8 】) 设g = ( ，k ，e ) 是一个二分图满足i i = i i = n 2 k + 1 ， x - 中k 1 是一个整数假设对0 1 ，i ( g ) 芝竽 ，则对g 中任意给定的后个互 不相同的点t ，l ，抛，仇，g 包含七个顶点不相交的名圈使得钝y ( q ) ，其中 i 1 ，七 定理1 2 2 8 ( 【2 9 】) 设g = ( ，e ) 是一个二分图满足i i = i i = 仃2 k + 1 ， 其中k l 是一个整数假设对盯l ，1 ( g ) 3 k + f 4 n 3 + k 。，则对g 中任意给定的k 个互不相同的点移1 ，他，仇，g 有一个参因子含k 个顶点不相交的圈使得它 们中的k 一1 个为彳一圈并且仇y ( a ) ，其中i 1 ，k 耿建艳在【3 0 】中给出了下面两个结论- 定理1 2 2 9 ( 3 0 】) 设k 2 ，1sssk ，佗22 k + 1 如果c r l ，l ( g ) 2 僦z f 学1 ，n + 七 ，那么对任给的k 个顶点v l ，咙，鲰，g 包含k 个独立圈q ，q ，g 使 得t 仇y ( c t ) ，i c t i 6 ，且q ，q ，仉中至少有8 个j ，圈 定理1 2 3 0 ( 3 0 】) 设后2 ，0s8 后，n 2 k 如果s ( g ) m 凹 照等世1 ，f 纽垃4 咀1 ，气铲1 ) ，那么对任给的k 个顶点v l ，耽，仇，g 包含七个独立圈c l ，岛， ，q 使得：仇y ( c ：) ，i c , i = 4 0 iss ) ，i c ；l 6 ( 8 + 1 i 七) 山东大学硕士学位论文 1 3本文的主要结果 本文主要考虑了关于图中相互独立的圈和2 一因子的若干结果，在第二章和 第三章中分别给出了一个定理： 定理2 1 1 如果g 是一个简单图，s , k 是两个正整数并且8 k ，其中g 的顶 点个数n 3 s + 4 ( k s ) + 3 如果a 2 ( g ) n + 2 k 一字，那么g 包含k 个顶 点不相交的圈a ，q 并且i g i = 3 其中1 i s ，i g i = 4 ，i e ( c i ) i 5 其 中s l k 定理3 1 1 设g 是个有n l + 彻+ 1 个顶点的简单图，其中n 1 3 ，n 2 3 若6 ( g ) 孕1 + 垃41 + 1 ，那么g 包含两个顶点不相交的圈g ，c 2 ，其中 i c t i = 啦+ 1 ，i 岛i = n j ( i ，j = 1 ，2 ) ，并且y e g 我们有e e ( c 1 ) 或e e ( c 2 ) 另外，本文在每章的最后还提出了一些问题，以待进一步研究 8 第二章图中含指定长度的独立圈 本章主要研究图中含指定长度的独立圈如无特殊说明，本章中的图g 均 是指一般简单图本章分为三节，第一节给出了相关的结果，第二节则证明了本 章的主要定理第三节给出了可以进一步研究的问题 2 1相关结果及本章结论 关于含指定长度的独立圈问题b r a n d t 等在【9 】中给出了这样一个结果t 如 果g 是一个简单图，s , k 是两个正整数并且8 k ，其中g 的顶点个数n 3 s + 4 ( k 一8 ) + 3 如果观( g ) n + 8 ，那么g 包含k 个顶点不相交的圈 o ，g 并且ic ；f i = 3 其中l i 3 ，i g i 4 其中3 i k 颜谨在 1 7 】 中又给出了这样个结果；如果g 是个简单图，s , k 是两个正整数并且s k ， 其中g 的顶点个数n 3 s + 4 ( k s ) + 3 如果砚( g ) 7 l + 8 ，那么g 包 含k 个顶点不相交的圈q ，瓯并且i g l = 3 其中1si s ，i q i = 4 其中 8 l k 在【1 9 1 中w a n g 给出了这样个结果设g = ( h ，k ，e ) 是一个均衡 二分图，i i = i k i = 3 k 如果6 ( g ) 22 k + 1 ，那么g 包含k 个独立的6 圈，且 每个6 圈至少含两条弦 本章主要的结果就是下面的定理； 定理2 1 1 如果g 是一个简单图，s , k 是两个正整数并且8 k ，其中g 的顶 点个数n 3 s + 4 ( 七一s ) + 3 如果c r 2 ( g ) n + 2 k 一学，那么g 包含k 个顶 点不相交的圈q ，g 并且i q i = 3 其中1si 善，i g i = 4 ，i e ( c i ) i 5 其 中8 i k 2 2定理证明 在定理2 1 1 的证明过程中我们需要用到下面的引理： 引理2 1 1 设c = n l a 2 a 3 ( 1 4 a l 是一个4 圈，v e - v ( c ) ，如果e ( t ，c ) 之3 ，则 c v ( c ) u u 】- ) 包含一个4 圈c 且i e ( c ，) i 5 证明：不妨设( t 7 ) = a l ，a 2 ，n 3 ) ，则c = ? 3 a l a 2 a 3 v ，且i e ( c ，) i 5 引理得 证 口 9 山东大学硕士学位论文 引理2 1 2 设a 是个3 圈，q = a l a 2 a 3 a 4 a 1 是个4 圈，且q ，仍顶点不 相交，若e ( a ，c 2 ) 1 0 ，则g ( y ( a ) uy ( q ) ) 包含一个3 圈q 和一个4 圈 q ，且i e ( q ) i 5 证明：假设引理不成立设g = f l ：l x 2 x 3 x l ，因为e ( a ，岛) 1 0 ，所以存在 口c 1 ，使得d ( v ，c 2 ) = 4 ，不妨设为x l ，即d ( x t ，c 2 ) = 4 ，则g ( y ( q ) ut , 1 ) 一定包含个4 圈q ，使得l e ( q ) i 5 从而 ，c 2 ( 现) nn c 2 ( x 3 ) = 毋，否则存 在一个3 圈，故d ( x 2 ，c 2 ) + d ( x 3 ，q ) s4 ，即 1 0 e ( c 1 ，c 2 ) d ( x l ，c 2 ) + d ( x 2 ，c 2 ) + d ( x 3 ，q ) 4 + 4 = 8 从而得出矛盾，故引理成立 口 引理2 1 3 设a ，q 是两个点不相交的4 圈，若e ( g ，q ) 之1 3 ，则g ( v ( c 1 ) u y ( q ) ) 包含两个点不相交的4 圈q ，q ，且i e ( q ) i 5 ，i = 1 ，2 证明t 假设引理不成立不妨设c 1 = x l x 2 x 3 x 4 x l ，g = n l a 2 a 3 a 4 a t ，因为 e ( q ，岛) 1 3 ，所以存在一点v q ，使得d ( 可，岛) = 4 ，不妨设为z l ，即 d ( x l ，c 2 ) = 4 ，则g ( v ( c 2 ) ux 1 ) 一定包含一个4 圈q 使得l e ( q ) i 5 因 此n v 。( x 2 ) nn c 2 ( x 3 ) n ( z 4 ) = d ，即讹q ，d ( u ， z 2 ，z 3 ，z 4 ) ) 2 。从而 e ( 岛，q z 1 ) 8 我们有 1 3 e ( q ，c 2 ) d ( x l ，伤) + e ( 岛，q t , 1 ) 4 + 8 = 1 2 从而得出矛盾，故引理成立 口 定理2 1 1 证明t 设s ，七，亿是三个正整数，使得8 七令g 是一个有n 3 s + 4 ( k s ) + 3 个顶点且满足c r 2 ( g ) n + 2 k 一曼軎墨的图，根据定理1 2 1 8 ，我 们得到g 含奄个点不相交的圈，且满足l q l = 3 ，其中ls is8 ，l q l = 4 其中 8 i 七 为了证明定理2 1 1 ，我们取k 个点不相交的圈，且满足i g i = 3 ，其中 1 i 占，l g i = 4 其中8 i k 使得i g i =