（运筹学与控制论专业论文）二部图中的独立圈.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 摘要：在研究图的相关性质及应用的很多文章中都是关于图的独立圈( 顶点不交 的圈) 方面的，尤其是特定长度的独立圈如何求出图的最大独立圈的个数，并由 此来讨论图的圈分解已成为近些年来图论中的重要课题 该文是本人于研究生阶段在图的特定长度的独立圈，独立有向圈等方面得到 的结果的总结 本文共分为四章：下面无特殊说明七均为正整数 第一章综述本文所研究课题的背景、发展现况及原有结论，阐述本人所做工 作 第二章讨论了二部图的独立垂圈；对二部图g = ( k ，；e ) ，l k i = i k i = 2 忙2 ) 进行了讨论，得到结论： 若6 ( g ) 后，且g 满足条件( + ) ( 见3 页注记【1 】) ，则g 有后一1 个独立垂圈，或一2 个 独立4 - 圈和一个与它们独立的其它长度的圈 第三章讨论了二部图的独立6 - 圈，对二部图g = ( ，k ；e ) ，l l = l k i = 3 七 进行了讨论，得到g 有后一1 个独立良圈的一个充分条件，即： 若6 ( g ) 2 一1 ，则g 有七一1 个独立6 - 圈 第四章给出了有向二部图的一个圈分解；通过应用第二章、第三章讨论的结 果，对有向二部图进行了讨论，得到下列结论： ( 1 ) 对d = m ，k ；a ) ，i h l = i l = 2 七 2 ) ，若d 满足( + ，) ( 见1 9 页注记【2 】) 且6 ( d ) 3 七，则d 有七个独立的有向垂圈，或d 竺d ，此时七为奇数 ( 2 ) 对d = ( m ，；a ) ，i i = i i = 3 后，若d ( d ) 5 七，则d 有七个独立的有 向6 - 圈 关键词：二部图；垂圈；6 - 圈；有向二部图；有向4 圈；有向6 - 圈 分类号：0 1 5 7 5 北京交通大学硕士学位论文 a b s t r a c t a b s t r a c t a b s l r a c i ： i nt h en t e r a t l l r e ，m a n yp a p e r so fd i s j o i n tc y c l 鹤a s s o c i a t e dt o 口a p l l s ，e s p e c i a u yf o rt h eq 7 c l 器o fc e r t a i ns i z e s ，h o wt oo b t a i nt h em 戚m a l 肌m b e 瑁o ft h e d 坷o i n tc ”l 髑a n dd i s c u s st h ed e c o m p o s i t i o 璐o fc y c l e sf o rg r 印h 8h a _ v eb e o o m e s i g n i & a n ti ng r 印ht h e 0 珥 t h j sp a p 盯m 曲以yc o m p 订s 鹤o fw h a tih a v eo b t a i n e di nt h e 五e 1 凼0 fd 两o i n t 呵d 鹤o fc e r t a j n8 i z 鹤a n dd i s j o i n td i r e c t e dc y c l 鹤d u r i n g 如ys t u d yi n 戗呛r e c e n t t h r e ey e a r s c h a p t e r0 n et o t a u yd 郫c r i b 船t h eb a c k 鲫n d ，t h ed e v e l o p m e n ts i “l a t i o na n d t h eo b t 8 i n e d 咖c l 璐i o i l sj l lt h e 矗e l d si n v 档t i g a t e di nt h i sp a p e r ，觚dt h e | ls i m p l y m 髓t i o n sw h a tih a v ed o n e h c h a p t e r 怕1 7 0 ，w ed i s c u s 8t h ed i s j o i n t4 c y c l e 8 ( q u a d r i l a t e r a l s ) i nb i p a r t i t e 口印h s f b r t h eg i v b i p a r t i t e f a p h g = ( ，k ；f ) ，i hj = i i = 2 ，w h e r e 七i 8 ap o s i t i v ei n t e g 盯w l l i c hi 8a tl e 船t2 ，w eo b t a i nt h ef b l l a w i n gr 圈l l l t ： s u p p 0 8 et h a tt h em i n i 皿l md e 口0 fgi sa tl e a s t 七驵dg8 a t i s 矗e st h e c o n d i t i o n ( 幸) 7 i h e ngc o n t a 主n s 七一1d 捌0 i n tq l 埝d r i l a t e r a l s0 r 詹一2q u a d r i l a t e r 如 缸d 锄o t h e rc y c l eo fd i 丘矗e n tl 锄g t hs u c ht h a t 啦lo ft h 咖缸ed i 8 j o i n t i n d m p t e r t h r e e ，w ed i ；c l l 8 s t h e d 坷。毗6 - c y d e s i nb i p a r t i t e f a p l l s f o r t h e 百v e nb i p a r t i t ef a p hg = ( k ，k ；e ) 砸t hi h i = i k i = 3 七，w h e r eki sap 耐t i v e i n t e g e r ，w eo b t a i nas u 佑c i e n tc o n d i t i o nt h a tgc o n t m 璐七一1d 蠲o i n t6 - c y c l e s ，i e s u p p o s e t h a t t h e m i i l i m u md e g r e eo f g i 8a t l e a s t2 七一1 t l l e n gc 0 i n t a i l l 8 七一ld 两o i n t6 _ c y d 鹤 hc h 印t e rf o l l r ，t h ed e o o m p 0 8 i t i o n so fd i r e c t e dq u a d m a t e r a l sf o rd i r e c t e d b i p a r t i t ef a p h s 舡e 舀v e n f b rt h ed i r e c t e db i p a r t i t eg r a p hw eo b t a i nt h ef b u a 耐n g r e s u l t 8 ： ( 1 ) l e td = ( k ，k ；棚w i t hi kj = j kj = 2 七，w h e r e 七i 8ap o s i t i v ei n t e g e r a t l e 鹤t2 s u p p o s e t h a t ds a t i 砸e s ( 奉7 ) a n d t h e m i n i m l l md e f e eo f d i sa t l e 鹪t 3 七t h e nd c o n t 越璐七d i s j o i n td i r e c t e dq u a d r i l a t e r a l 8 ，o re l s e 七i so d da n dd i s i s o m o r p l l i ct od ( 2 ) i 威d = ( k ，k ；a ) w i t hi k i = i k i = 3 后，w h e r e 七i 8ap o s i t i v ei n t e g e r i ft h en l i n i m 眦d e g r e eo fdi sa tk 蠲t3 七t h e nd c o n t a i l l s 后d 两o i n td i r e c t e d a u a d r i l a t e r a k k e y w o r d s ：b i p a r t i t ef a p h ；q u a d f i l a t e r a l ；昏c y c l e ； d i r e c t e db i p a r t i t e 北京交通大学硕士学位论文 a b s t r a c t f a p h ； d 打e c t e dq u a d r i l a t e r a i ； d i r e c t e d 每c y c l e c l a s s n o ：0 1 5 7 5 致谢 首先感谢我的导师郝荣霞教授，本论文的各项工作都是在郝老师的悉心指导 和亲切关怀下顺利完成的无论是在每学期的研究生基础课学习过程中，还是在 毕业论文的选题、研究以及成文的过程中郝老师自始至终都给了我大量的支持 和帮助郝老师以渊博宽广的知识系统、严谨务实的治学态度和平易近人的师者风 范，使我受益匪浅，并将受惠终生，在此特向郝老师表示深深的敬意和感激 感谢关心我们成长的学校、学院领导，感谢给我以传道授业解惑的所有老师 们感谢所有帮助过我的同学和朋友，感谢我同门的师兄妹们，谢谢你们给了我一 个愉快的学习环境让我的人生又多了一段美好的回忆 感谢我的家人及所有的亲人们所给予我的一切，他们对我的关心、援助和期 望都是我前进的最大源泉和动力 最后，诚谢各位专家和学者在百忙中审阅我的论文。诚恳接受您的宝贵意见 和建议，并期待您的批评和指导 北京交通大学硕士学位论文第1 章绪论 第1 章绪论 近些年来对图的独立圈的的研究很活跃，尤其是对特定长度的独立圈的研究 关于这方面的最早研究是k c o r 刚i 和a h a j n a l 3 】在1 9 6 3 年提出的，他们证明了对 阶至少为3 枷q 图g 中，若节点的最小度6 ( g ) 22 则g 有七个独立圈；j l l s t e s e n 在1 9 8 9 年改进了他们的结果，给出了对g 中的任意一对不相邻顶点z ，暑，若d ( z ) + d ( ”) 船，则g 有詹个独立圈；之后h w g 【4 】强化了他们的结论，将条件弱化为d 扛) + d ( ! ，) 4 七一1 ，则g 有七个独立圈 此后，h w a l l g 等人又发表了一系列关于独立4 - 圈的文章1 9 9 6 年，h ，w 抽g 在 文献【5 j 中对二部图g = ( m ，k ；e ) ，f k f = f k f = n 2 后进行了讨论，给出了 若j ( g ) 矗+ 1 ，l 2 ，则g 有七个独立圈，并证明了当n = 2 时，g 有七一1 个独 立4 - 圈和一条与它们独立的阶为4 的路1 9 9 9 年，b e r ti h n d e r a t h 等人在文献f 6 1 中 又证明了对阶为4 女的图g ，若6 ( g ) 2 七，则g 有七一1 个独立4 一圈和一个阶为4 的至 少有四条边的子图与它们独立 受前人的启发，本文在第二章考虑了最小度至少为七的二部图的独立4 圈，证 明了对g = ( ，k ；e ) ，i k i = i k i = 2 2 ) ，若6 ( g ) 七，且g 满足条件( ) ， 则g 有七一1 个独立4 - 圈，或膏一2 个独立4 圈和一个其它长度的圈与它们独立并 在第三章进一步讨论了二部图的独立昏圈，得到对二部图g = ( k ，；a ) ，i i = l k i = 3 七，若6 ( g ) 2 七一1 ，则g 有七一1 个独立6 - 圈 这几年来此类问题又延伸到对有向图的讨论2 0 0 0 年，h w a n g 在文献7 1 中证 明了对阶大于等于3 的有向图d ，若6 ( d ) ( 3 n 一3 ) 2 ，则d 有h 3 j 个有向3 圈 2 0 0 4 年，d a i l h o n gz h a n g 和h w a n g 在文献中【8 】又研究了阶为3 的有向图d ，证明 了若6 ( d ) 6 七一2 ，则d 有七个有向4 圈，除非d 垒d + ，此时七为偶数文章第四章 受文献【8 】的影响，分别讨论了有向二部图的有向垂圈和有向良圈，并得到它们的一 个圈分解 独立圈作为图论的一个重要部分，应用广泛目前已有一些结果是研究图的独 立圈的最大个数，但如何通过寻找晟大个数来找图的圈分解，这方面的工作有待进 一步完善 本文第二章，第三章讨论的图皆为有限的，无向简单图，凡未声明的记号和 术语均参见文献 1 】- 第二章介绍的定义、结果均适合于第三章、第四章，第四章 讨论的有向图皆为严格有向图凡在第四章中未提到的术语和名词均参见g a r y 和l i n d a 的著作| 2 1 北京交通大学硕士学位论文 第2 章二部图中的独立4 _ 圈 2 1相关定义 第2 章二部图中的独立4 - 圈 所谓二部图是指一个图它的顶点集可以分解为两个非空子集x 和y ，使得每 条边都有一个端点在x 中，另一个端点在y 中；这样一种分类( x ，y ) 称为图的一个 二分类边的端点称为与这条边关联，反之亦然与同一条边关联的两个顶点称为 相邻的，与同一个顶点关联的两条边也称为相邻的 给定二部图g = ( ，；e ) ，( ，k ) 为顶点分类，e 为边集对顶点z y ( g ) ， 令b ( z ) = b y ( g ) ：硼e ( g ) 如果g 是g 的一个子图，令d ( 马c ) = i b ( z ) ny ( g ) | 记路p 的长度为f ( p ) 假设是y 的一个非空子集，以为顶点 集，以两端点均在y ，中的边的全体为边集所组成的子图，称为g 的由矿导出的子图， 记为g 【吲一个图的集合称为独立的，如果这个集合中任两个图之间没有公共顶 点设x 和y 是图g 的两个独立的子图或y ( g ) 的两个不相交的子集，用e ( x ，y ) 表 示g 中x ，y 之间的边数 2 2主要引理 下面无特殊说明，g = ( ，；e ) 为给定的二部图 引理2 2 1 设e 为一个4 一圈，z ，可是g 的不在c 上的两个相异顶点，血，暑属于不同 的分类若d ( z ，g ) + d ( ，c ) 3 ，则g ( e ) u 如，”) 】中有一个4 一圈和一条与它 独立的边e ，其中e 与z ，中之一关联 证明由于g 是二部图，所以d ( z ，e ) 2 ，d ( 可，c ) 2 不妨设d ( z ，e ) = 2 ， d ( 可，e ) 1 ，其中z k 设e = n l 啦n 3 n 4 8 1 ，舀( z ) ny ( c ) = 现，4 ) ，则不 管是取= z 2 0 3 0 4 z ，n 1 可e ，还是= z n 2 8 1 毗z ，n 3 1 ，e ，引理都成立 口 引理2 2 2 f 5 】设d 为一个4 一圈，z 玑u 是与c 独立的两条独立边若d ( z ，e ) + d ( ，c ) + d ( u ，c ) + d ( u ，e ) 5 ，则g ( c ) u p ，! ，t ，口 包含一个4 一圈争一条与它独立 的阶为4 的路p 引理2 2 3 设p 1 和恳是g 的两条独立路，且z ( 只) 1 ，f ( 恳) = 3 若e ( p l ，岛) 2 ，则g ( 只up 2 ) 】包含一个4 一圈，除非j ( p 1 ) = 1 ，f ( 易) = 3 ，今日= 删，岛= o l n 2 0 3 0 4 ( u ，l 属于不同的分类) ，则e ( r ，恳) = 伽4 ，t ，0 1 ) ， 证明 设b = t l 口，b = n 1 0 2 n 3 n t 显然，对某个顶点n y ( b ) ，如果d ( o ，岛) 2 ， 则g ( p 1 u 易) 】包含一个4 - 圈又因为e ( 马，马) 2 ，所以d ( “，b ) = 1 ，d ( 钉，尼) ； 1 若p 2 上有点6 ，使幻e ，则6 不能与恳上属于( “，恳) 的点相邻否则g ( 只u 2 北京交通大学硕士学位论文 第2 章二部图中的独立4 - 圈 恳) 】中就会有一个垂圈这表明t | 与b 的端点相邻，也就是说4 e 则我们有6 = n 1 口 注记【l 】：若路只= “t ，岛= o l 眈啦n 4 ( 钍，a 1 属于不同的分类) 是图g 的两个导出子 图，且e ( 只，恳) = u 啦， n 1 ) ，则将g ( p 1 u 马) 】记为p ，若图g 中不包含这样的 一个导出子图与t + 同构，则称g 满足( ) 引理2 2 4 设g 的两条独立路p 1 和b ，且f ( p 1 ) ；2 ，f ( b ) = 3 若g 满足( 十) 且e ( 只， b ) 3 ，则g ( 只u 岛) 】包含一个4 一圈 证明 设r = 牡l t 2 t 3 ，岛= n 1 0 2 0 3 n 4 ，不妨设 “1 ，n 1 ) k ( 反证) 假设g ( 只u b ) 1 不包含4 - 圈，则d ，马) 1 ，i 1 ，2 ，3 ) 由于g 满足( + ) ，由引理2 2 3 ，e ( t 1 t 1 2 ， 恳) l ，e ( 地u 3 ，岛) s 1 所以e ( b ，岛) 2 ，矛盾 口 引理2 2 5 设g 的两条独立路b 和岛，且 ( 只) = l ( b ) = 3 若g 满足( t ) 且e ( b ，b ) 3 ，则g ( p 1u b ) 】包含一个4 一圈 证明 假设g 【y ( 只u 易) 】不包含垂圈设只= t 1 她u 3 地，马= 口1 n 2 钧m ，不妨 设 t 1 ，0 1 ) h 由引理2 2 3 ，e 1 钍2 ，恳) 1 ，e ( 地蛳，b ) 1 ，所以e ( 且，昆) 2 ， 矛盾 口 引理2 2 6 【6 l 设4 一圈e 和阶为4 的路p ，p 与强立，且。y ( p ) d ( 茁，c ) 6 则g ( g u p ) 】包含两个独立的4 一圈，除非p 有一个端点，不妨设为。，有d ( z ，g ) = o 引理2 2 7 设g 的4 一圈g ，路只和忍，且z ( b ) = 2 ( 恳) = 3 若它们相互独立，且g 满 足( + ) ，e ( a 只u 恳) 9 ，则g 够u bu 马) 1 包含两个独立的4 一圈 证明( 反证) 假设g ( g u 只u 恳) 】不包含两个独立的4 - 圈设只= t 1 1 抛3 嘶，b = m n 2 啦，e = z 1 勋茁3 她z l ，且 t 1 ，n 1 ，z 1 ) k 我们可设d ( 瓤，只u b ) d 协，p l u b ) ，i 2 ，3 ，4 ) 则d ( z 1 ，马u 尼) 2 9 4 1 = 3 ，不失一般性，设d ( z 1 ，只) = 2 ， 则只+ z l 中有一个4 - 圈而g ( g u p l u b ) 】不包含两个独立的4 圈，故由引理2 2 4 ， e ( z 2 黝z 4 ，b ) 2( 2 2 1 ) 我们有下面结论成立 d ( 。i ，b ) l ， l ，2 ，3 ，4 )( 2 2 2 ) ( 2 2 2 ) 的证明如下因为g 够u 且ub ) 】不包含两个独立的4 - 圈，所以对 所有的i 2 ，3 ，4 ，有d ，b ) 1 若d ( z 1 ，p 2 ) = 2 ，则e ( z 2 2 3 姐，且) 2 从 而4 = d ( z l ，p lu 尼) 9 一( 2 + 2 ) = 5 ，矛盾，所以( 2 2 2 ) 成立 由( 2 2 1 ) ，( 2 2 2 ) ， e ( e ，马) 9 一d o l ，易) 一e ( z 2 2 3 瓤，b ) 9 1 2 = 6( 2 ，2 ，3 ) 3 北京交通大学硕士学位论文第2 章二部图中的独立4 - 圈 由引理2 2 6 ， e ( g ，p 1 ) = d ( z ，c ) = 6 ( 2 2 4 ) y ( p 1 ) 且d ( h l ，c ) = o ，d ( 蛳，c ) = o 中必有一个成立又d ( z l ，马) = 2 ，扛1 u 2 ，z l t l 4 e ， 所以d ( 蛳，c ) o ，从而 d ( “1 ，回= 0 且 $ l 地，茁1 乱4 ，现均，如地，z 3 毗，瓤3 ) e 由( 2 2 1 ) ( 2 2 4 ) 得，e ( z l ，b ) = 1 ，e ( 勋黝z 4 ，马) = 2 分为两种情况讨论： ( 1 ) z 1 0 2 e 由于g ( e up l u 岛) 】不包含两个独立的4 - 圈，z l m 甓e ，z 2 n l 岳 e ，z 2 n 3 隹e ，铂n 1 隹e ，轧0 3 岳e 而e ( 现奶z 4 ，b ) = 2 ，所以只有z 3 2 e ， z 3 n 4 e ，与( 2 2 2 ) 矛盾 ( 2 ) z l n 4 e 则l 眈垡e ，z 2 0 3 簪e ，瓤n 3 聋e 且z 2 n 1 隹e ，瓤n 1 隹e 否 则g z 1 ，z 2 ) uy ( b ) 】笺r ，g 【 z 1 ，瓤) uy ( 恳) 】兰p ，与g 满足( ) 矛盾所以只 有黝0 2 e ，z 3 d 4 e ，与( 2 2 2 ) 矛盾 综上d ( z l ，马) = 1 ，且根据对称性d ( z l ，易) = 1 ，从而d ( z 1 ，只ub ) = 2 由 于d ( z 1 ，只u 马) 的最大性，d ( 戤，p 1u 局) 2 ， 2 ，3 ，4 ) ，所以e ( gp 1u 恳) = ：1 d ( 戤，只u 马) 8 ：d ( t l ，丑) 4 七一4 8 = 4 ( 七一3 ) y ( 而) 6 北京交通大学硕士学位论文第2 章二部图中的独立4 圈 若存在日中的某个q ，使。y ( 而，d 扣，q ) 25 由引理2 2 2 ，g ( q u 岛) 】中 有一个4 _ 圈q ，和一条与它独立的阶为4 的路，矛盾 所以对日中的所有q ，均有。y ( f 2 ) d ( t l ，q ) = 4 则d ( 9 3 ，f 1 ) = 1 ，d 恤，日) = 1 ，d ( z 3 ，f 1 ) + d ( 瓤，b ) = 2 且蚰，驰必须相邻到f 1 中同一个顶点( 否则f 中就有两条 独立的阶分别为3 和4 的路) ，不妨设为z l ，则黝玑ge ，钆1 簪e ，所以只有。3 抛 e ，钆抛e 则f 中就有两条路。l 玑z 2 和蜘$ 3 抛姐，矛盾所以最中有一条阶为4 的 路 现证明只中也有一条4 路否则，e ( 只) = 2 ，。y ( n ) d ，f 1 ) = 4 因为g ( p uf 1 u f 2 ) 】不包含4 - 圈，所以d ，足) 1 ，d ，p ) 1 ，其中加y ( f 1 ) 则 d ( 锄，p u 兄) 4 + 4 = 8 t 蚝y ( f 1 ) 所以 d ( 叫，日) 4 七一4 8 = 4 ( 七一3 ) 埘e y ( 且) 若存在日中的某个q ，使。y ( n ) d ( ，n ) 5 由引理2 2 2 ，g ( q u f l ) 】中 有一个4 - 圈q ，和一条与它独立的阶为4 的路 所以对日中的所有o ，均有。，( f 1 ) d ，q ) = 4 所以d ，只) = 1 ，其中叫 y ( f 1 ) 对z l ，玑应用引理2 2 3 ，则g ( p 1 ) u z l f l ) 】皇p ，矛盾 所以不管哪种情况f 中都有两条阶为4 的路现证明g 中有七一2 个独立的4 - 圈 现g 日中有三条阶为4 的路，记为p ，p 1 和恳令p = z l 。2 铂乳，r = “l t 2 呦t 1 4 ，b = 0 1 0 2 0 3 n 4 ( 设 z l ，u 1 ，口1 ) ) 由于g ( pu 只up 2 ) 】不包含4 - 圈，故e ( p ) = 3 ， e ( 只) = e ( 尼) = 3 由引理2 2 5 ，e ( p b ) 2 ，e ( 只b ) s2 ，e ( b ，恳) 2 所以 d ( t l ，p u 只u b ) 6 + 6 + 2 + 2 + 2 2 = 2 0 y u 岛) 所以 d ( 叫，胃) 8 七一2 0 = 8 ( 一3 ) + 4 埘y ( p 1 u 尼) 则存在日中的一个q ，使。y ( p l 。恳) d ，q i ) 9 由引理2 2 7 ，g ( q u p l u p 2 ) 1 中有两个独立的垂圈矛盾所以定理成立口 定理2 3 2 给定二部图g = ( ，k ；e ) ，l k i = i k i = 2 膏，其中七为不小于2 的正 整数如果g 满足( ) ，且最小度至少为k ，则g 中要么有一1 个独立的4 一圈，要么 有七一2 个4 一圈和一个其它长度的圈与它独立 证明 ( 反证法) 若= 2 ，假设g 中没有4 - 圈由于6 ( g ) 2 ，故g 中至少有一条 边，不妨设为z 1 口1 ( 其中。1 k ) 则存在两个顶点z 2 ，抛，使耽z l 可1 钯为一条4 路 7 北京交通大学硕士学位论文第2 章二部图中的独立4 - 圈 因为g 不包含4 - 圈，所以! j 2 2 2 聋e ，故存在两个点设为z 3 ，蜘，使z 3 搬z 1 1 ，1 2 2 铀为一 条6 路则剩余两个点乳，驰，不妨设铂m ，驰由于6 ( g ) 2 ，若船舶e ， 则g 中有一个6 - 圈z 1 暑，l z 2 钧如抛z 1 故可设。3 船隹e ，则z 3 舶e 且锄船e 若钆玑e ，则g 中有一个8 - 圈否则，由于g 中不含4 - 圈，必有瓤抛e ，驰z 2 e ， 则g 有6 - 圈z 1 耽z 3 驰z 2 们z 1 或o l 暑，1 勋船如耽z 1 所以当七= 2 时，定理成立 现在考虑女3 时假设g 不包含七一1 个独立的4 - 圈由定理2 3 1 ，g 中有七一 2 个独立的4 - 圈，记为q l ，q 2 ，q 一2 令日= u 旨q ，f = g 日与定理2 3 1 类 似的过程，可推出f 中有两条独立的阶为4 的路p l 和恳下证g 中有后一2 个独立的垂 圈和另一个其它长度的圈与它们独立 设y ( f ) = z 1 ，现，勋，她，耽，耽，珈，驰) ， z l ，暑n ) k 且b = 。l 勘，岛= 可l 抛船驰因为g ( 只u 岛) 】中没有垂圈，所以e ( 只) = e ( b ) = 3 由引理2 2 5 ， e ( 只，易) 2 所以 d ( t u ，只u b ) 6 + 6 + 2 2 = 1 6 椰y ( p 1 u 危) 所以 d ( t l ，日) 8 后一1 6 = 8 一2 ) y ( p 1 u 尼) 若存在日中的某个q ，使。y ( 危u 危) d ( ，q ) 9 由引理2 2 7 ，g 【矿( qu 只ub ) 1 包含两个独立的垂圈，矛盾 所以对所有的q ，均有。y ( p | 。尸2 ) d ，酝) = 8 ，则e ( b ，马) = 2 由于g ( 日 u 马) 1 不包含4 - 圈，日，恳之间的这两条边不能关联到同一顶点，也就是说它们要相 互独立分为两种情况讨论： ( 1 ) 这两条边在同一条路上关联的两个顶点属于相同的分类，即 z 1 驰，如讥) e 或 z l 驰，勋钝 e ，则g ( p 1ub ) 】包含一个昏圈 ( 2 ) 这两条边在同一条路上关联的两个顶点属于不同的分类若 z 1 驰，勋f 1 ) e ，则g ( 马) u z l ，沈) l 兰p ，矛盾同理对 乩轨，铂f 1 ) e ，所以只有扛l 驰，黝1 ) e ，则g ( 只u 马) 1 中有一个8 _ 圈所以g 包含七一2 个独立圈和另一个其它长度 的圈定理得证 口 8 北京交通大学硕士学位论文 第3 章二部图中的独立6 _ 圈 3 1相关引理 第3 章二部图中的独立6 - 圈 本文主要沿用第二章的相关概念下面无特殊说明，g = ( ，；e ) 为给定的 二部图 引理3 1 1 设c 为g 的一个6 一圈，z ，是不在g 上的两个相异顶点，血，属于不同 的分类若d ( 。，c ) + d ( ，e ) 5 ，则g ( c ) u 扛，可 】包含一个6 一圈和一条与它 独立的边e ，其中e 与z ，中之一关联 证明 因为g 为二部图，所以d ( z ，c ) 3 ，d ( ，g ) s3 不失一般性，设z u 且d ( z ，回= 3 ，d ( 玑e ) 2 令d = n l 啦m n 6 口1 ，( z ，c ) = n 2 ，d 4 ，n 6 ) 若n l ”e ，则6 圈z 眈0 3 如哪a p 与它独立若o l 掣岳e ，则0 3 暑，e 和z d 2 n l n 6 如n 4 z 或者是口叫e 和z 0 4 0 3 n 2 n l n 6 z 均满足要求 口 引理3 1 2 设g 的两条相互独立的路r 和马，z ( p 1 ) l ，z ( 岛) = 5 若e ( p l ，马) 3 ，则g ( 只u 最) j 包含一个6 一圈，除非f ( 最) = 1 ，e ( n ，恳) = 3 且关联到只的三个 点形成一条阶为3 的路 证明 若存在某个 y ( 最) ，有d ，b ) 3 ，则g ( 县u 马) 】包含一个6 - 圈 故可设日= 删，d ( t ，岛) = 2 且d ( ，恳) 1 ( 由于e ( 只，b ) 3 ) 设马= n l n 2 啦口4 如n 6 ，扣，n 1 ) m 若n 相邻到的恳的两个顶点，它们在马上形成长度大 于2 的子路，则g ( p lu 尼) 】包含一个昏圈所以如果g ( p 1u 岛) 】中不含6 - 圈，则 有 “n 2 ，m 4 ) e 或 “，t 1 0 6 ) e 若前者成立，则只能3 e 若后者成立， 则”e 不管哪种情况，关联到r 的三个顶点形成一条阶为3 的路 口 引理3 1 3 设g 的四条相互独立的路为只，b ，b 和p 且f ( 只) = l ( 尼) = f ( 岛) = 1 ，z ( p ) = 5 若e ( 片u b u b ，p ) 9 ，则g 【y ( p 1 u 恳u b u p ) 】包含一个6 一固 证明( 反证) 假设g ( p 1 u 岛u 忍u p ) 】不包含6 - 圈令p 1 = “。u 2 ，马= z l z 2 ，马= 玑抛，p = 0 1 n 2 船口4 n 5 0 6 ，不妨设 “1 ，z 1 ，玑，n 1 ) 由引理3 1 2 ，e ( b ，p ) 3 ， e ( 马，p ) 3 ，e ( b ，p ) 3 由于e ( 只u 马u 马，p ) 9 ，所以e ( 只，p ) = e ( 岛，p ) = e ( 马，p ) = 3 对p l ，不妨设d ( l ，p ) = 2 ，由引理3 1 2 ，分为两种情况： ( 1 ) u l a 2 ，u l 吼，坳n 3 ) e 则对马，由于g 【y ( p lubu 马up ) 】中不含6 - 圈， 必有伽1 0 4 ，z 1 0 6 ，钇n 5 f 而e ( 岛，p ) = 3 ，所以d ( 可l ，尸) = 2 和d 渤，p ) = 2 中 只能有一个成立但不管哪种情况，g ( 只u 恳u 忍up ) 】中都有一个6 - 圈，矛盾 ( 2 ) “1 n 4 ，“1 d 6 ，地n 5 ) e 则 z 1 2 ，z 1 啦，z 2 3 ) e ，与( 1 ) 类似，我们仍然 可以得到矛盾 口 引理3 1 4 设g 的6 一圈c ，三条路只，马和b ，z ( p 1 ) = f ( 马) = f ( 岛) = 1 假 9 北京交通大学硕士学位论文第3 章二部图中的独立6 - 圈 设g 只，b ，尼相互独立，且e ( g 只u b u b ) 1 3 ，则g ( c u 只u b u 马) 】包 含一个6 一圈和一条与它独立的阶为6 的路p 证明假设g ( g u p l u 马u b ) 】中没有这样的两个子图设r = t l 忱，恳= z l z 2 ， 恳= 玑耽，c = 口l 眈n 3 m n 5 0 6 l ，不妨设 “l ，1 ，秽1 ，口1 ) m 因为e ( a 马ub u b ) 1 3 ，故可设e ( e 只) 5 则存在g 中的一条4 路设为d l 眈如舶，使e ( n l 2 0 3 0 4 ，p 1 ) = 4 则g 【 n 1 ，n 2 ，幻，毗) u y ( r ) 】中有一个6 - 圈由于g 够u 只u 马u 岛) l 不包 含题设中的两个子图，我们有 e ( 奶0 6 ，局u b ) 2( 3 1 1 ) 显然，e ( a 最) 6 ，又由于e ( g ，p 1 ) 5 ，分为两种情况讨论： ( i ) e ( gb ) = 6 则有两个6 _ 圈t l 抛n 3 n 4 5 船“l 和札1 “2 n 5 n 6 d l n 2 u 1 ，所以e ( 口1 n 2 马u 马) 2 ，e ( 砸口4 ，马u 马) 2 ，否则引理就成立由( 3 1 1 ) ，e ( c ，b u b ) 6 所以e ( g ，只u 恳u 恳) 6 + 6 = 1 2 ，矛盾 ( i i )e ( c ，p 1 ) = 5 ，不妨设地0 5 e 则有6 - 圈“l 坳口5 n l n 2 u 1 ，所以e ( 船帆，尼 u 岛) 2 ，由( 3 1 1 ) ， e ( d l 眈，尼u b ) 2e ( c ，只u b u 马) 一e ( c ，只) 一2 2 1 3 5 2 2 = 4 事实上e ( 口1 n 2 ，bu 尼) = 4 ，则所有的等号均成立，即 e ( 船0 4 ，恳u b ) = e 口6 ，恳u 岛) = 2( 3 1 2 ) 则d ，b u b ) = o 若d ，恳u b ) 0 ，不妨设4 2 1 e ，则有6 - 圈z l 勋n 1 n 5 n 4 z l 和阶为6 的路0 3 t 1 2 u 1 0 2 可1 驰，矛盾所以d ( n 3 ，马u 马) = 2 0 = 2 且船z 2 e ， 抛e 由( 3 1 2 ) ，可分为两种情况： ( a ) d ( 弼，岛u 马) o ，不失一般性，设n 5 2 2 e 则g 【y ( c u bu 岛u 忍) 】 中有一个6 圈。l n 2 0 1 0 6 0 5 观。l 和阶为6 的路t 1 2 “1 0 4 啦暑1 2 玑，矛盾 ( b ) d ，另u b ) o ，不失一般性，设0 6 2 1 e 则g 够up 1u 局ub ) 】 中有一个良圈o l 勘叫0 6 2 1 和路“2 1 1 1 啦0 1 耽鲰，仍然矛盾所以d ( n 5 ，马ub ) = d ( a 6 ，岛u 忍) = o ，与( 3 1 2 ) 矛盾所以引理成立 口 引理3 1 5 设g 的两条相互独立的路只，b 且z ( p 1 ) = 3 ，f ( b ) = 5 若e ( 只，岛) 5 ，则g ( 只u 马) 】包含一个6 一圈， 证明假设g ( bub ) 】不包含6 - 圈设p 1 = z l 娩z 3 乳，b = 1 抛9 3 乳讹9 6 ，不妨 设 z 1 ，”1 ) m 则由引理3 1 2 d ，马) 2 ，i l ，2 ，3 ，4 因为e ( b ，b ) 5 ， 故存在两个点z l ，勉，使e ( z 1 勋，b ) 23 由引理3 1 2 ，e ( z l z 2 ，马) = 3 ，分为下列四 种情况： 1 0 北京交通大学硕士学位论文第3 章= 部图中的独立6 _ 圈 ( a ) z 1 1 1 2 ，z 1 驰，勋珈) e 由于g 【y ( 只u 易) 】中没有6 - 圈，所以d ( 如，b ) = d ( 9 4 ，b ) = o ，从而e ( 只，恳) = 3 5 ，矛盾 ( b ) 1 玑，z 1 珈，z 2 拈 e 则d ( 如，b ) = o 且乩蜘簪e ，瓤蜘簪e ，所以e ( p 1 ，马) 3 + 1 5 ，矛盾 ( c ) 扛l 珈，娩玑，z 2 始 e 则d ( 瓤，岛) = o 且z 3 驰e ，$ 3 珊譬e ，所以e ( 只，马) s3 + 1 5 ，矛盾 ( d ) 扣1 驰，z 2 蜘，勋舶 j - 则d ( 勘，b ) = o ，茁3 伽岳e ，z 3 蜘隹e ，所以e ( 且，恳) 3 + 1 5 ，矛盾所以引理成立 口 引理3 1 6 设g 的两条相互独立的路r 扣恳且z ( p i ) = f ( 尼) = 5 若e ( b ，b ) 6 ，则g ( 只u 易) 1 包含一个6 一圈，除非e ( 只，马) = 6 且g ( ru 岛) 】与下列某个 图同构： 滕慧飚 ( n )( 6 )( c ) 证明( 反证法) 假设g ( 马u 恳) 】中没有6 - 圈设p l = z 1 勋z 3 钆，尼= 玑耽抛驰拈蛳 不妨设 z 1 ，掣1 ) k 由引理3 1 5 和3 1 2 ，e ( z l z 2 如乳，b ) 4 ，e ( 如茁6 ，恳) 3 因 为e ( p 1 ，马) 6 ，所以 3 e ( z l z 2 z 4 ，恳) 4 且2 e ( z 5 ，尼) 3 ( 3 1 3 ) 由引理3 1 2 ，e ( z l z 2 ，马) 3 所以2 e ( z l 勋，b ) 3 ( 若e ( z 1 $ 2 ，易) 1 ， 则e ( z 3 铂z 5 ，b ) 6 1 = 5 由引理3 1 5 ，g ( p lu 足) 1 包含一个6 - 圈) 故 可分为下列两种情况讨论： 情形1 e ( z l z 2 ，马) = 3 由引理3 1 2 ，分为下列四种情况： 情形1 1 扛1 耽，z 1 驰，现蜘) e 由于g ( 只u 岛) 】不包含6 - 圈，所以d ( z 3 ，马) = d ( 她，易) = o ，且z 5 抛簪 e ，霉5 驰簪e ，船簪e 而e ( 马，马) 6 ，故必有 z 5 拈，如玑，粕蜘) e 则有6 - 圈粕1 耽珈玑蜘z 6 ，矛盾 情影1 2 扛l 驰，z 1 蜘，现舶 e 则d ( z 3 ，马) = o ，? 4 船譬e ，勘舶隹e ，z 5 蛐隹 e ，z 5 蜘垡e ，z 6 佻e 分两种情况讨论： 情形1 2 1 轧1 e 则由于g ( p l u r ) 】不包含6 _ 圈，z 6 珈隹e 而e ( p l ，b ) 6 ， 故必有 z 5 1 j 2 ，如1 ) e 则e ( 只，恳) = 6 且g ( 只u 恳) 】竺( a ) 情形1 2 2z 4 帅聋e 由于e ( b ，岛) 6 ，所以 z 5 耽，z 6 肌，z 6 蜘) e 6 且g ( 只u 易) l 垒( b ) 则e ( p l ，b ) = 北京交通大学硕士学位论文第3 章二部图中的独立6 圈 情形1 3 z 1 1 1 2 ，沈玑，勋蜘) e 则d ( 她，恳) = o 且z 3 弧譬e ，奶佻隹e ，如抛譬e ，z 5 玑隹e ，粕玑隹e ，钠崔 e 由于e ( p 1 ，恳) 6 ，故必有 如抛，船舶，z 6 蜘) e 则e ( 日，b ) = 6 且g 【y ( ru p 2 ) 】皇( c ) 情形1 4 z 1 驰，勋舶，勋蜘) e 则z 3 沈隹e ，z 3 舶聋e ，蜘隹e ，z 6 雏譬e 且d ( 瓤，忍) = d ( 如，马) = o 所 以e ( r ，马) 3 + 1 + 1 6 ，矛盾 情形2e ( 1 勋，岛) = 2 分为下列三种情况： 情形2 1d ( z 1 ，恳) = 2 且d ( z 2 ，岛) = o 由于g ( 只u 尼) 】不包含6 - 圈，分为两种 情况： 情形2 1 1 z 1 弛，z l 驰) e