（应用数学专业论文）有向图的圈分解.pdf

上毒交通太学博士学位论文 有向图的圈分解 摘要 图的圈分解问题是图论和设计理论研究中的重要课题自1 8 4 7 年，k k 一- 确定了凰的3 圈分解及1 8 9 2 年l u c 勰确认w a e c k i 解决了k ，。的n 圈分解以来， 国内外许多学者对完全图的圈分解问题作了大量的研究，并取得了许多优 美的结果，也有一些文献1 2 0 ，6 3 ，5 4 ，5 6 ，5 7 ，5 8 5 9 6 0 ，6 1 ，6 2 6 3 6 4 ，6 5 ，删涉及到完 全有向图的圈分解问题 本文的第二章主要研究了最大填充m e n d d s o h n 三元系在i2 4 中，推广了 c o l b o u r n 和r o 6 8 ，7 0 1 的定理，主要研究了d 一p 和d 。u p 的有向3 圈( m e n d e j s o h n 三元系) 分解，它不仅具有理论意义，而且在计算机网络设计中有一定的现 实意义通过利用差，i 一曲r d 序列，h o o k e dl a n g f o r d 序列等组合论工具，证 ，明了当n 1 3 d 。为n 阶完全有向图，p 为d 。中顶点不相交的有向圈的并 时，风一p 或d 。u p 可分解为有向3 圈( 即m e n d e l ”h n 三元系) 的充分必要条件 为d n p 或d 。u p 的边数可被3 整除在d 。不考虑方向时即成为2 ，作为 以上内容的直接推论可得以下定理：当n 1 3 时，2 一p 或2 k u p 可分船 为3 圈的充分必要条件为2 碥一p 或2 k u p 的边数可被3 整除 如果图g 不存在3 圈分解，我们可考虑其子图日如果子图f 存在3 圈分 解，则称g 可被3 圈填充，g h 称为该填充的剩余在g 的所有可能剩余 ，中，边数最少的剩余称为是最小剩余，最小剩余所对应的填充称为最大填 充如果图。不存在3 圈分解，我们也可以通过多次使用某些边，而得到图 的3 圈分解图g 的3 圈覆盖为三角形( 亦称3 圈) 的集合p ，使得g 中的每 条边至少出现在p 的一个三角形中，因此可构造多图g ( 尸) ，使得g ( p 】中的点 u 和”之间有z 条边联接的充分必要条件是p 中有z 个三角形包含点u 和“ 显然，g ( p ) 存在3 圈分解o c p ) 一g 称为该覆盖的冗余在g 的所有可能的 冗余中，边数最少的冗余，称为最小冗余最小冗余所对应的覆盖称为最小 覆盖在s2 5 中，推广了2 4 中的结论，研究了d 。一尸和风u p 的最大填充 中文摘要 m e n d 小0 h n 三元系证明了当n 1 3 ，p 为巩中顶点不相交的有向圈的并时， 巩一p 或d 。u p 可分解为向3 圈( 或m e n d e l s o h n 三元系) 和剩余厶的充分必要 条件是o 。一户或d 。u p 的边数为模3 余l ，其中 = 0 1 2 ；, o 为空集，“为有 向4 圈( 或顶点不相交的两个有向2 圈的并) 工2 为有向2 圈2 4 中的结论 即为t = 0 的情况 本文的第三章利用数学归纳法和直接构造法，研究了d 。一p 和仉u p 的 有向4 圈分解证明了当n 8 ，p 为d 。中顶点不相交的有向圈的并时，仇一p 或d 。u p 可分解为有向4 圈的充分必要条件是d 。一，或d 。u 户边数可被4 整 除 集合? 的元素为图g 中边不相交的r a m i l t o n 圈，r 称为最大h a m 蜘n 圈 集，简称最大集，如果r 中所有h a m i l t o n 圈满足g f ( 丁) 不含h a m i l t o n 圈，e 为r 中所有h a m l l t n a 圈的边所组成的集合图g 的谱为整数的范围本文 的第四章研究了完全有向图d 的最大h a m i l t o n 圈集证明了口。中存在含有 m 个有向h a m i l t o n 圈的最大集r 的充分必要条件为：嘲冬m ! n 一1 本文的第五章研究d 。+ p 的有向m 圈分解，证明了当m 为偶数，“为 奇数且4 ms2 n 。p 为d 。中n 个顶点不相交的有向二圈的并，即p = ”邑 时，存在风。+ p 的有向m 圈分解的充分必要条件是m 整除2 一+ 2 n 关键词：完全有向图t 完全二部图，圈分解，填充，覆盖，最大h a m i l t c e 。 圈集，h a m i l t o n 圈、： a o s r r a c t c y c l ed e c o m p o s i t i o n so fd i r e c t e dg r a p h s a b s t r a c t c y c l ed e c o m p o s i t i n so fg r a p h si so n eo ft h ei n t e r e s t i n gp r o b l e m si nb o t hg r a p h t h e o r ya n dc o m b i n a t o r i a lt h e o r y m a n yb e a u t i f u lr e s u l t sh a v eb e e ng o tw h e nk i r k m a n 8 0 l w d3 - c y c l ed e c o m p o s i t i o n so f c o m p l e t eg r a p hk 。i n1 8 4 7a n dl u c a si n1 8 9 2c r e d i t e d w a l e c l dw i t hs e t t l i n gt h es p e c t r u mp r o b l e mf o rn - c y c l es y s t e m so f t h e r ea r es o r t i e p a p e r 8 2 0 ，5 3 ，5 4 ，5 6 ，5 7 , 5 8 ，5 9 ，6 0 ，6 1 ，6 2 ，6 3 ，6 4 ，6 5 ，6 6 w h i c hc o n s i d e rd i r e c t e d c y c l ed e c o m p o s i t i o n so f d i r e c t e dg r a p h i nt h i sd i s s e r t a t i o n ，w em a i n l ys t u d yd i r e c t e d c y d ed e c o m p o s i t i o n so f d i r e c t e dg r a p h i n 2 4 ，w ee x t e n dt h er e s u l t so fc o l b o u r na n dr o s a 【6 8 ，7 0 1t od i r e c t e dv e r s i o n a n dg i v et h ef o l l o w i n gt w ot h e o r e m s t h ef i r s to n ei s ：l e tf lb ea ni n t e g e r ，n 1 3 l e td nb eac o m p l e t ed i r e c t e dg r a p hw i t h o u tl o o p sa n di t so r d e ri sn ，l e tpb ea v e r t e x - d i s j o i n tu n i o no f d i r e c t e dc y c l e s i n ka n dj e ( p ) jb e t h en u m b e r o f e d g e so f p t h e nc al d 。一p ( o rc si d 。t 9 p ) i fa n do n l yi f n 印一1 ) 一i e ( p ) l 毒0 ( m u d3 ) ( o r n ( n 一1 ) + j e ( p ) i 兰0 ( m u d3 ) ) t h es e c o n do n e i s ：l e t 仃b ea n i n t e g e r ，n 1 3 l e t pb eav e r t e x - d i s j o i n tu n i o no f c y c l e si n2 a n df e ( j d ) fb et h en m t l b e ro f e d g e so fp t h e n g i2 虬一p ( o r gj2 以up ) i f a n do n l y i f n ( n 一1 ) 一i f ( 刑0 ( m u d3 ) ( o r n 一1 ) + i e ( p ) i 0 ( m o d3 ) ) a p a c k i n go fag r a p hg w i t ht r i a n g l e si sap a r t i t i o no ft i l ee d g es e to fas u b g r a p h 日o fg ，e a c he l e m e n to fw h i c hi n d u c e sat r i a n g l e ；t h er e m a i n d e rg r a p ho ft h i sp a c k i n g ， a l s ok n o w na st h el e a v e ，i st h es u b g r a p hg hf o r m e df r m ng b yr e m o v i n gt h ee d g e s i n 日i ft h er e m a i n d e rg r a p hi sm i n i m u mi ns i z e ( t h a ti s ，h a st h el e a s tn u m b e ro f e d g e sa m o n ga l lp o s s i b l el e a v e so fg ) ，t h e nt h ep a c k i n gi sc a l l e dan l a x i m u mp a c k i n g a c o v e t i n go fag r a p hg w i t ht r i a n g l e si sac o l l e c t i o no ft r i a n g l e s ，p ，s u c ht h a te a c h e d g eo fg o c c u r si na tl e a s to n et r i a n g l ei np s o ，i fc ( v ) i st h em u l t i g r a p hf o r m e d b yj o i n i n ge a c hp a i ro fv e r t i c e s “a n d 口w i t hze d g e si fa n do n l yi fp c o n t a i n szt r i p l e s t h a tc o n t a i nb o t hua n d 口，t h e nc l e a r l yg fg ( p ) t h em u l t i g r a p hg ( 尹) 一gi sc a l l e d t h e “c e s sg r a p ho fg ac o v e r i n gw i t hs m a l l e s te x c e s sg r a p h i ns i z e ) i sc a l l e da i i m i n i m u mc o v e r i n g i n 2 5 ，w ef u r t h e re x t e n dt h ew o r ko f 2 4 m a i n l y , w eo h t a l n t h em a x i m u mp a c k i n g so fd r pa n dd 。upw i t hm e n d e l s o h nt r i p l e sr e s p e c t i v e l y w es h o w ：f o re a c hd i r e c t e d2 - r e g u l a re n b g r a p hp o fd na n da ni n t e g e rn ，r i21 3 ， 一p ( o r d 。u p ) e b bb ep a c k e dw i t h l e a v e 厶i f a n do n l y i f n ( n 一1 ) 一i e ( p ) f 三i ( m o d3 ) ( o rn ( n 一1 ) + | f ( p ) i i ( m o d3 ) ) w h e r e i = 0 ，1 ，2 h e r e ，l o = d ，厶；g ( o r2 c 2 ) a n d 如= c 2 i nd l a p t e r3 w eu s ei n d u c t i o nm e t h o da n dd i r e c tc o n s t r u c t i o nt op r o v ed i r e c t e d 4 - c y c l ed e c o m p o s i t i o n so fd 。一pa n dd n up w ep r o v et h ef o l l o w i n gr e s u l t ，l e t nb ea ni n t e g e r ，n 8a n dpb eav e r t e x - d i s j o i n tu n i o no fd i r e c t e dc y c l e si n 巩 t h e n ( hj d 。_ p ( o rc 4l z k u 户) i f a n do n l yi f n 一1 ) 一i e ( j p ) l 兰0 ( r o o d4 ) ( o r m 一1 ) + l f ( p ) i 毒0 ( r o o d4 ) ) ah a m i l t o n c y c l e i n a g r a p h g i sas p a n n i n g c y c l e o f g i f t i sa s e t o f e d g e - d 浏o i n t h a m i l t o nc y c l e si nga n di fe ( t ) i st h es e to fe d g e so c c u r r i n gi nt h eh a m i l t o nc y c l e s i nt ，t h e nti ss a i dt ob em a x i m a li fg e ( t ) h a sn oh a m i l t o nc y c l e i nc h a p t h4 ， w es t u d yam a x i m 甜s e th a m i l t o nc y c l e si nt h ec o m p l e t ed i r e c t e dg r a p h 风w e 吕h o w ： f o rt w op o s i t i v ei n t e g e r sm ，n ，t h e r ee x i s t sam a x i m a ls e to fmh a m i l t o nc y c l e si nd t i i fa n do n l y i f f ；15 仇sn 一1 f o rn 27 i nc h a p t e r5 ，w es h o wf o rp o s i t i v ee v e ni n t e g e rm ，o d di n t e g e rna n d4 冬m 2 n ， t h e r ee x i s t sm c y e l es y s t e mo f 巩n + pi fa n do n l yi f2 n 2 + 2 n 薹0 ( r o o dm ) ，w h e r e pi snv e r t e x - d i s j o i n tu n i o no fd i r e c t e d2 - c y c l e si nb k e yw o r d s ：c o m p l e t ed i r e c t e dg r a p h tb i p a r t i t eg r a p h ，c y c l e d e c o m p o s i t i o n ，p a c k i n g ，c o v e r i n g ，m a x i m a ls e t s ，h a m i l t o nc y c l e 符号说明 图； 晶表示n 阶加法群； 表示t l 阶完全图； 风表示n 阶完全有向图，即对任意口4 - ，d e g + ( 口) = d e g 一( ”) 2n i ； d m 。表示顶点集为uu k ，l h i = m ，l k i = n 且含2 r a n 条边的完全有向二部 v c g ) 表示图g 的顶点集，i v ( g ) i 表示图g 的顶点集中含元素的个数 e ( c ) 表示图g 的边集。l z c a ) l 表示图g 的边集中含元素的个数； a 表示长为l 的圈； a 。表示长为j 的有向圈t p 为d 。中顶点不相交的有向圈的并； p l s 表示完美l a n g f o r d 序列； h l s 表示勾状l 8 n g f o r d 序列 附件四 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担a 学位论文作者签名：荡。午1 名手 日期： 西年亏月l 咱 附件五 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定。 同意学校保留并向国家有关部门或机构送交论文的复印件和电予 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“”) 学位论文作者签名：蒲争i 磊午 指导教师签名：；兜埒磊 j 日期：蝣弓月i 咱日期：罂。年乡月， 口 第一章绪论 圈的分解问题包含很多类型其中与组合设计理论联系紧密的同题之一为将图分 解为因子或将图分懈为圈d u 和w g 1 ，2 ，3 ，4 ，5 6 ，7 l 研究了将图分解为因子， 关于将图分解为因子。感兴趣的读者还可参看文献【8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，15 11 6 ，1 7 ， 1 8 ，1 9 ，2 0 】将囝分解为圈将在5 1 1 介绍本文主要用组合设计中的方法研究与有向图 有关的围分解问题具体研究以下五个问题t ( 1 ) 占k 为n 阶完全有向图尸为d f 中 顶点不相交的有向圈的并。三k 一尸或口。u p 的有向3 圈分解的存在性问题i ( 2 ) p 为d 。中顶点不相交的有向圈的并，z k p 或矾u 尸的最大填充m e n d e b o h n 兰元 系的存在性问题；( 3 ) p 为风中顶点不相交的有向圈的并。 n p 或口，u p 的 有向4 圈分解的存在性向题( 4 ) k 的最大h a m i l t o n 圈集的存在性问题；( s ) p 为 d 。中n 个顶点不相交的有向二围的并。d 。+ p 的有向m 圈分解的存在性问题 1 1 研究背景 n 阶s t e i n e r 三元系，记为s t s ( n ) ，为一有序点对( s t ) ，其中s 为n 元点集， 而t 是s 的三元子集的集合使得s 中的任一点对都出现在丁中唯一的一个元素( 三 元子集) 中 s t e i n e r 兰元系存在的充分必要条件为。 n il 或3 ( r o o d6 ) 三角形也 可看作3 圈因此，从图论的观点来看s t s ( n ) 可看做托边的一个三角形翅i 分， 使得每边都出现在个三角形岛中，我们记该分解为g l 易知，如果( s t ) 为 n 阶s t s ( n ) ，则i r l = 晦m 自从1 8 4 7 年，r e v t p k i r k m a n 2 1 解决了s t s ( ) 的存在性问题以来，至 少有一千篇文章f 2 2 】与s t s ( n ) 有关 m a t hr e v i e w 有关于s t s ( n ) 单独的一个单 元s t s ( n ) 的研究已经较为完善，详细内容可参阅c j c o l b o u r n 与a r o s a 2 2 】 的专著 拓展三元系的概念。我们可得到n 阶m 圈分解的概念n 阶m 圈分鹪为一有序 点对( s ，即，其中s 为n 元点集，而t 是s 的边不相交的m 圈的并，使得s 中的任 l 一点对都出现在丁中的唯一的一个m 圈中从图论的观点来看，令的顶点为s ， 组成 厶的所有m 圈可形成集合t 图j 0 可表示为丁中m 圈的并这些m 圈划分 玩的边大约三十年前，最初关于m 圈分解的存在性问题，已经拓展到更为广阔的 领域，如，嵌人卜完戋各种类型的可分解性等详细参看文献 2 3 ，2 4 ，2 5 ，2 6 ，2 7 ， 2 8 ，2 9 ，3 0 ，3 1 ，3 2 ，3 3 ，3 4 ，3 5 ，3 6 ，3 7 ，勰，3 9 ，4 0 ，4 1 ，4 2 1 - n 阶3 圈分解的存在性问题已经完全解决，人们着手研究当m 4 时，m 圈分 解的存在性同题n 阶m 暖分解存在的必要条件为；( 1 ) n m l ；( 2 ) n 为奇 数；( 3 ) ! 穹学为整数b a l s p a c h 和h g n v a l a s 【4 3 j 于2 0 0 1 年m a j 8 f 4 4 j 于 2 0 0 2 年，分别证明了这些条件也是充分的 定理l 1 1 1 4 3 j 当m ，n 为正奇敷。3sm n ，完全图墨。可分解为m 圈的充 分必要条件是以的边敷为竹l 的倍数 定理1 1 2 1 4 4 】当m 为正偶数，n 为正奇数。3sm m 完全图心可分解 为竹l 圈的充分必要条件是以的边数为m 的倍数 当然。在获取以上两个较为完美的结果之前，以下几个阶段性的成果需要我们去 纪念1 8 4 7 年，k i r k m a n 解决了n 阶3 圈分解的存在性问题1 8 9 2 年，l u c a s 【4 5 】解决了甄的n 圈分解的存在性问题i1 9 6 5 年，k o t z i g1 4 6 解决了当m 笠0 ( m o d4 ) 时，耳n 的m 圈分解的存在性间题；1 9 6 6 年，l t o 乩【4 7 】解决了当m 警2 ( m o d4 ) 时“的m 圈分解的存在性问题；之后。r o s a 进一步证明了当m 为奇数 且n i i ( m o d2 m ) 或n 为奇数且n 量m ( m o d2 m ) 时。j “可分解为长为m 的闭迹 ( c l o s e d t r a i l so f l e n g t hm ) 当m = 5 或7 时r o s a 指出这些闭速成为m 圈1 9 8 0 年，a l s p a c h 和v a r m a 4 8 l 证明了m 为一个质数幂的2 倍时，岛的m 圈分解存在 的必要条件也是充分条件1 9 8 8 年，j a c k s o nf 4 9 】解决丁对所有的奇数m 和所有满 足一n i i 或m ( m o d2 m ) 的整数m 和t l ，的m 圈分解的存在性问题 在考虑瓜的m 圈分解存在性问题的同时，a 五、的m 圈分解的存在性问题也 被列入数学家的考虑范畴 1 9 6 1 年。h a n a n i 【5 0 l 解决了当a = 1 ，m = 3 时， 蜀。 2 圭查茎堡盔堂堕圭堂垒堡塞 的m 圈分解的存在性问题；h u a n g 和r o s af 5 1 ，5 2 先后于t 9 7 3 年和1 9 7 5 年，解决 了当4 冬m 1 6 时，a 瞄的m 圈分解的存在性问题；1 9 7 8 年，b e r m o n d ，h u a n g 和s o t t e a u ( 5 3 l 解决了当m 为偶数且8 m 1 6 时，a 的m 圈分麓的存在性i 可 题；同年，b e r m o n d ，和s o t t e a u 5 4 l 解决了当m 为奇数，5 m 1 3 时，a 峨的 m 翻分解的存在性问题；1 9 9 1 年，e b e l l 5 5 j 解决了当m 5 0 时，a 的7 7 l 圈 分解的存在性问题 k 为n 阶完全有向图， 上k 为定义子n 个顶点。且每对顶点被2 a 条有向边联接 的完全有向多图。同样可以考虑 n 圈分解的存在性问题1 9 7 5 年，j s c h 6 n h e i n1 5 6 解决了当 = l ，傅= 4 时，a d 的有向m 圃分解的存在性问题；b e r m o a d ，h u a n g 和s o t t e a uf 5 3 】及b e r m o n d 和f a b r e 2 0 解决了当r t z 为偶数。4 m 兰1 0 时， a 三k 的有向m 圈分解的存在性网题；b e r m o n d 和s o t l ；e a u f 5 4 】解决了当m 为奇数， 5 ms1 3 时。a k 的有向m 圈分解的存在性问蹶 2 0 0 3 年，b a l s p a c h ，h g a v l a s ，m a j n a 和h 、，e 玎a l 】f 5 7 1 解决了k 的r t 圈分解的存在性同题。他们证明 了当m ，n 为整数2 m sn ，z k 可分解为m 圈的充分必要条件为k 的边数可被 m 整除关于有向图的圈分解还可参看文献 5 8 ，5 9 ，6 0 ，6 1 ，6 2 ，6 3 6 4 ，6 5 6 6 】， 前面我们提到了3 t s ( n ) 存在的充分必要条件为tn ；1 或3 ( m o d6 ) 对有些 珏值。s y s ( ) 不存在，文献中给出了通过忽略一些边，用三元系划分其余的边图 g 舶三角形填充是将g 的子图目的边划分为边不相交的三角形( 3 圈) 的并。子图 g 一日即将g 中所有在日中的边减去，g 一日称为对应填充的剩余在g 的所有 可能的剩余中，边效最少的剩余称为最小剩余最小剩余对应的填充称为最大填充 1 9 7 5 年，h a | l j f 6 7 】研究了剩余为1 因子，边数为2 + 1 的生成森林4 圈或空图 时，k 。的晟大3 圈填充；1 9 8 6 年，c o l b o u m 和r _ o s a 6 8 】研究了n 为奇数，剩余 日为j 毛的2 正则子图时，j 厶的最大3 圄填充；2 0 0 1 年，f u 和r o d g e r 6 9 研究 了剩余为的2 正则子图时，和2 j 厶的最大4 圈填充 当盯s ( n ) 不存在时我们也可通过多次使用圈g 的某些边，而将图g 以及多 3 节一章绪论 用的边分解为三角形的并图g 的三角形覆盖是一些三角形的集合尹，使得g 中的 每一条边至少出现在p 的个三角形中，因此，多图g ( p ) 中的两点t 和口被# 条 边联接的充分必要条件是p 包含个三角形均含有两点“和 ，显然岛lg ( p i 图 g ( r ) 一g 称为g 的冗余g 的所有可能的冗余中。舍边数最小的冗佘称为最小冗 余最小冗余对应的覆盖称为最小覆盖1 9 7 5 年，h a n a n i 6 7 研究了冗余为l 因子， 边数为+ 1 的生成森林，2 圈或空图时。碥的最小3 圈覆盖；1 9 8 7 午，c o l b o u m 和r o s a 7 0 研究了n 为奇数，冗余日为k 。的2 正则子图时。蜀。的最小3 圈覆盖 b ，a l s p a c h 和h g a v a _ 1 a s 4 3 于2 0 0 1 年，m a j m1 4 4 于2 0 0 2 年分别讨论了剩 余为厩的l 因子时，的m 圈填充 定理1 1 3 f 4 3 l 当m ，l 为正偶数。4 ms 竹，i 为完全图j 矗的1 因子时。 k 一，可分解为m 圈的充分蕾要条件是j 厶一，的边数为t i 的倍数 定理1 1 4 【4 4 】当m 为正奇数。n 为正偶数。3 s m s 珥i 为完全因疋的1 因子盱。局。一，可分解为m 圈的充分必要条件是蚝一j 的边敷为m 的倍数 2 0 0 3 年m a j n a 7 1 l 讨论了冗余为墨。的一因子时，的m 圈覆盖 定理1 1 5 f 7 1 l 当n 为偶数。m 为整数，3smsn ，i 为完全图蜀。的一因 干时，。+ ，存在m 圈分解的充分必要条件为五+ ，的边数为竹l 的倍数 关于无向图的覆盖和冗余，感兴趣的读者还可参看文献【7 2 ，7 3 ，7 4 ，7 5 。7 7 ，7 7 7 8 ， 7 9 ，8 0 ，8 l ，8 2 ，8 3 ，8 4 ，8 5 ，8 6 ，8 7 ，8 8 ，8 9 】 本文我们将研究当剩余和冗余为特定图时，完全有向圉的填充和覆盖 1 2 主要结果 在2 + 4 中推广了c o l b o u r n 和r o s a 6 8 ，7 0 l 的定理，主要研究了完全图d r 。一p 和d nup 的有向3 圈分解，它不仅具有理论意义，而且在计算机网络设计中有一定 的现实意义通过利用差，l a n g f o r d 序列，h o o k e dl a n g f ：o r d 序列等组合理论中的工 具，证明了下面定理 4 上海交通大学博士学位论文 定理2 l5 当n 1 3 ，口为n 阶完全有向图，p 为口。中顶点不相交的有向圈 的并时，口。一p 或口。up 可分解为有向3 圈( m e n d e l s o h n 三元系) 的充分必要条 件为k 一尸或风l j p 边数可被3 整除 当口。不考虑方向时即成为2 k ，作为以上内容的直接推论可得下面定理 定理2 1 6 当n 1 3 ，2 ，n p 或2 u p 可分解为3 圈的充分必要条件是 2 瞄一p 或2 k u p 的边数可被3 整除 如果图g 不存在3 圈分解，我们可考虑最大填充和最小覆盖在2 5 中，推广 了2 4 中的结论，研究了玩一p 或c k u 尸的最大填充m e n d e l s o h n 兰元系。得到 以下定理 、 定理2 1 7 当n 1 3 ，p 为z k 中顶点不相交的有向圈的并时，k p 或日。u p 可分解为向3 圈【或m e n d e l s o l m 三元系) 和剩余厶的充分必要条件为三k p 或 z ) n u p 的边数为模3 余i ，其中= o 1 ，2 岛为空集，厶为有向4 圈( 或2 个顶点 不相交的有向2 圈的并) ，如为有向2 圈 定理2 1 5 即为f = 0 的情况 n 和r 。d g e r 【6 9 | 研究了噩。一，和2 k 一f 的4 圈分解，证明了如果f 为以 的2 正则子图，n 为正奇数，凰一f 可分解为4 圈的充分必要条件为 _ 一，的 边数可被4 整除同时他们证明了如果，为2 以的2 正则子图，2 置。一，可分解 为4 圈的充分必要条件为2 碥一f 的边效可被4 整除本文的第三章推广了凡和 r o d g e r 6 9 1 的定理，利用数学归纳法和直接构造法，研究了d 。一p 和d nup 的有向 4 圈分解的存在性问题，证明了以下定理 定理3 5 1 当f l 8 ，p 为d 。中顶点不相交的有向圈的并时，n ，一户或风u p 可分解为有向4 圈的充分必要条件为口一p 或三) n u 尸边效可被4 整除。 集合丁的元素为图g 中边不相交的h a m i l t o n 圈，? 称为最大h a m i l t o n 圈集或 简称为最大集，如果? 中所有h a m i l t o n 圈满足g e ( t ) 不含h a m i l t o n 圈，e ( t ) 为t 中所有h a m i t o n 圈的边图g 的谱为整数 ? i 的范围本文的第四章研究了完 5 全有向图d ，。的最大h a m i l t o n 圈集证明了以下定理 定理4 2 5 - m ，n 为整数。n 7 。d n 中存在古有m 个有向h a m i l t o n 圈的最大集 的充分必要条件为- 郭m sn 1 本文的第五章研究与有向二部图有关的圈分解证明丁下面定理 定理5 3 1 当m 为偶数。n 为奇数且4 m 2 n ，p 为仉，。中r 1 个顶点不相交 的有向= 圈的并时z ) 忭。+ p 存在有向m 圈分解的充分必要条件是m 整除2 舻+ 2 n 6 第二章d 。一p 和d 。up 的最大填充m e n d e l s o h n 三元系 在本章中我们主要研究当p 为d 。中顶点不相交的有向圈的并时，n 。一p 和 kup 的最大填充m e n d e l s o h n 三元系作为该问题的特殊情况，我们首先在2 3 中 研究k p 和b 。u p 的有向3 圈分解的存在性问题 2 1 引言 n 阶s t e i n e r 三元系，记为汀s ( n ) ，是一有序点对( s ，? ) ，其中s 为n 元点集， t 是s 的三元子集的集合，t 中的元素称为区组，使得s 中任一点对都出现在唯一 的个区组中众所周知，s t e i n e r 三元系存在的充分必要条件为t n 1o r3 ( r o o d 6 ) 从图论的观点来看，s t s ( n ) 可看做j 矗边的一个三角形划分，使得每一边都出 现在唯一的一个三角形岛中( 该三角形也称区组) 如果可分解为三角形的并，也 称j 矗存在三角形分解，简记为，岛f 西。 图g 的子图日的边的一个兰角形划分称为图g 的一个三角形填充该填充的剩 余( 1 e a v e ) 为g 一日，即从图g 中减去子图中的所有边在图g 的所有可能的剩余 ( 1 e a v e ) 中，含有边数最少的剩余l e a v e ) ，称为最小剩余( 1 e a v e ) 最小剩余( 1 e a v e ) 所对 应的填充，称为最大填充关于最大填充，下面的定理广为人知 定理2 1 1 【6 7 q 为完全国，j 厶的最大三角彤填充所砷应的剩余p 为 in ( m o d6 ) ol23 4f 5 l l pfa f0eq f 为1 因子。日为合奇数( g + 1 ) 条边的生成森林也称为f n 即f e ，g 是长为 4 的朋 人们自然会想到，当完全图j f n 的子图日具有什么特点时。g l 一- 当n 为奇数，日为的2 正则子图时，c o l b o u r n 和r a 【6 8 】证明了以下定理 7 第二幸d 。一p 和d 。u p 的最大填充m e n d e l s o h n 三元系 定理2 1 2 【6 8 ln 为正奇数，日为完全图k 。的2 正则于图，当n = 9 时，子 图日满足h c j u g ，则c j 一日的充分必要条件为j 厶一日的边数可被3 整 除 图g 的三角形覆盖是一些三角形的集合只使得口中的每一条边至少出现在p 的一个三角形中，因此。多图g ( p ) 中的任意两点“和p 被条边联接的充分必要条 件是g ( p ) 中包含的个三角形均舍有点和显然g i g p ) 图g 沪) 一g 称为 g 的冗余在图g 所有可能的冗余中畲有边数最少的冗余，称为最小冗余。最小冗余 所对应的覆盖称为最小覆盖关于最小覆盖，有以下定理 定理2 1 3 【6 7 l 完全图k 。的最小三角形覆盖的置小冗余p 为 i n ( m o d6 ) 0 1 234 5 i p 0 ， 0 晶 0 五凸 ，是1 因子，日含有奇教g + 1 条边的生成蠢林。只也称为t r i p o l e ，伤为长 为2 的圈 关于覆盖c o l b o u r n 和咖1 7 0 得到了定理2 1 4 ，c m f u ，h l f u 和ca r o d g e r 9 0 1 用不同的方法也证明了定理2 1 4 定理2 1 4 【7 0 i n 为正奇数，日为j 的2 正则子圈向：一定是生成函 则 g i u 日的充分盟要条件为甄u h 的边敷为3 的倍数 对于有向图可以考虑相应的填充和覆盖问题 n 阶m e n d e l s o h n 三元系简记为m t s ( n ) ，是一有序点对丁) ，其中s 为n 元点 集，r 为s 中三元子集的集合r 中的元素 也称为区组，是循环的，即若( 口，6 ，c ) l 则循环( o ，6 。c ) 台有边曲，b c ，s 中任何一有序点对恰好出现在t 的个三元区组 中从图论的观点肴，m t s ( n ) 可看作将完全有向图d 。的有向边进行划分使得每一 条边恰好含在一个有向三角形孑3 中，我们记该种划分( 分解) 为，赢i z k ， 打1 s ( 竹) 1 9 1 ) 存在的充分必要条件为n 暑0 ，l ( r o o d3 ) ，n 6 关于m e n d e l s o h n 三元系感兴趣 的读者可参看文献1 9 2 ，9 3 ，9 4 ，9 5 ，9 6 ，9 7 ，9 8 ，9 9 ，1 0 0 ，l o l l 3 上海交通大学博士学位论文 我们将对定理212 和定理21 4 进行拓展，研究d 。的填充m e n d e l s o h n 三元 系，从而证明以下定理 定理2 1 5 为整数。疗21 3 ，日。为n 阶无繇有向因，p 由d 。中顶点不相支 的有向田并组成，1 _ e ( p ) i 为p 的边敷，则g 3ld ，一p ( 或c 3i 上) n u p ) 的充分皿要 条件为tn m 一1 ) 一l e ( p ) l 羞0 ( r o o d3 ) ( 或n ( n 一1 ) + i e ( p ) 1 暑0 ( m o d3 ) ) 如果我们忽略不记d f 。中边的方向，则得到2 k 图2 墨是每一对顶点由2 条边 相联。因此我们可得定理2 1 6 需要指出的是c m n ，h ，l n i 和c a r o d g e r 9 0 用差的方法证明了岛i 蚝up 定理2 1 b 行为整敷。忭2 1 3 ，尸由中顶点不相交的圈并组成。皿( p ) l 为p 的边敷，则c 纠2 j 0 一p ( 或gj2 u p ) 的充分必要条件为tn 1 ) 一】e ( p ) l i 0 ( m o d3 ) ( 或仡一1 ) + i f ( 尸) i 暑0 ( m o d3 ) ) 进步推广定理2 1 1 ，定理2 1 3 和定理2 1 5 ，我们研究了d f 。一p 和d n u p 的 最大填充m e n d e l s o h n 三元系，得到以下定理 定理2 1 7 n 为整敷。p 由上k 中顶点不相交的有向圈并组成。n 1 3 ，d n 一尸( 或工k u p ) 可被有向3 圈填充且剩余为厶的充分必要条件为n ( n 一1 ) 一f e ( p j f 三 ( r o o d3 ) ( 或n b 一1 ) + j e ( p ) 三( m o d3 ) ) ，其中i = o 1 ，2 j l o = 西，厶= e t 或 j- 2 c 2 ，l 2 = c k 2 2 预备知识 给n 阶完全图的边赋予方向得簖 任意竹阶完全无环有向图d f 。中的点 有一 d 。= k ：+ k 二 逆转j 口中每一边的方向得对 d e g + 一) = d e g 一( ) = n 一1 显然， 吼为长h 的圈，p 由坼。中顶点不相交的圈的并组成，y ( a 。) 为圈瓯中的所 有点组成的集合，如果n = 壹k v f g ) n y ( ) k 。“j ) ，则令r ；u 基，吼按 照反转边的方向的规定，可得；c 0 ，尉，c i 和靠 g 苎三兰旦：= 塑! 生茎盔基壅型些! 塑三垂墨 为了方便，我们记 o 为t 个顶点不相交的有向圈c i 的并 a 为m 元集合，日为n 元集合且a n b = 口有向二部图d a 。日( i k 。) 台2 r a n 条有向边如，d 3 , 2 含1 2 条边。其中边口i 吗不同于b d 为方便，我们称有向边为边 易得，蜀n “= j o + + ，。d t 帅。尊d n + 玩+ d f m ，d 肿+ l = k + 。1 图g l 和岛的并图记为g 1 v g 2 ，满足e ( g v g 2 ) = e (