（运筹学与控制论专业论文）循环几乎可分解的循环有向三元系.pdf

目录 摘要 设u ，k ，a 为任意正整数个平衡不完全区组设计是一个二元组( vb ) 其中y 为u 个元素的集合，8 为v 中k 元子集( 称为区组) 的集合，且 满足如下性质：y 中任意两个不同的点恰包含在廖的a 个区组中我们 把它简记作( ，k ，a ) 一b i b d 或b ( k ，a ； ) 当a = l 时，( u ，a ) 一b i b d 称为s t e i n e r2 一设计若舀是y 中循环三元组的集合且满足v 中每个 有序对恰出现在8 的a 个区组中，则称此设计为一个m e n d e l s o h n 三元 系，记做m t s ( v ， ) 若8 是v 中可迁三元组的集合，且满足v 中的任 意两个点恰包含在8 的 个区组中，则称此设计为一个有向三元系，记 做d t s ( v ，a ) 对于循环可分解的循环s t e i n e r2 - 设计和循环可分解的( 或几乎可分 解的) 循环m t s ( v ，砘前人给出了它们的直接构造和递归构造，但其平 行类轨道和区组轨道都要满足一些限定条件本文在综述前人已有结果的 基础上，在对平行类轨道和区组轨道没有限定条件的情况下给出了a = 1 时循环几乎可分解的循环有向三元系的直接构造和递归构造 本文共分两章 第一章中综述了文献1 6 7 和 1 1 】中利用差族和分圆类给出的循 环可分解的循环s t e i n e r2 一设计和循环可分解的( 或几乎可分解的) 循环 m t s ( v ，a ) 的直接构造和递归构造 第二章中具体给出了循环几乎可分解的循环有向三元系的直接构造 和递归构造 目录 2 当v ；1 ( m o d6 ) 且为素数时，利用磊 o ) 中的一个6 阶子群的生 成元n 给出了循环几乎可分解的循环d t s ( v ) 的直接构造 当u = 4 t 3 ) 时，在构造循环几乎可分解的循环有向三元系的过 程中，我们利用了完备的( v g ，g ， ) 循环有向差族以及半循环的d l r a y n e 两个概念，并且利用了循环几乎可分解的循环有向三元系和循环有向差 族的关系 另外，当v = 2 5 p 时，其中pi5 ( r o o d6 ) ，8 ；1 ( r o o d4 ) 且 s 5 ，我们还利用差阵和完备的循环有向差族构造了循环几乎可分解的 循环d t s ( v ) 在本文的最后，我们还利用差阵给出了循环几乎可分解的循环有向 三元系的一个递归构造 关键词有向三元系；s t e i n e r2 一设计；m e n d e l s o h n 三元系；循环 几乎可分解；循环差族；半循环的d f r a m e ；差阵 目录 a b s t r a c t 3 l e tu ，ab ei n t e g e r s l e tvb ea 一s e ta n d 舀b eac o l l e c t i o no fk - s u b s e t s o fvt h ee l e m e n t so fv a n d8a r ec a l l e dp o i n t sa n d b l o c k s r e s p e c t i v e l y a p a l l ( k 召) i sc a l l e dab a l a n c e di n c o m p l e t eb l o c kd e s i g n ( d e n o t e db y ( ，k ， ) b i b do rs ( k ， ；”) ) ，i fe v e r yp a i ro fd i s t i n c te l e m e n t so fvi s c o n t a i n e di np r e c i s e l yab l o c k so f 日a ( ，k ，a ) - b i b dw i t ha=ii s c a l l e da s t e i n e 7 2 - d e s i g n am e n d e l s o h n t r i p l es y s t e m ，m t s ( v a ) ，i sa p a i r ( k8 ) ；vi sas e to f p o i n t sa n d 3i sac o l l e c t i o no fc y c l i ct r i p l e sw i t h t h ep r o p e r t yt h a te v e r yo r d e r e dp a i ro fe l e m e n t so fv o c c u r si ne x a c t l ya b l o c k so f 嚣ad t s ( v ，a ) i sap a i r ( k 3 ) w h e r evi sav - s e ta n d 3i sa c o l l e c t i o no ft r a n s i t i v e l yo r d e r e d3 - t u p l e so fv ，s ot h a te a c ho r d e r e dp a i r o fd i s t i n c te l e m e n t so fv u p p e u r si ne x a c t l y b l o c k so f 召 t h ee x i s t e n c ep r o b l e m so f c y c l i c a l l yr e s o l v a b l ec y c l i cs t e i n e r2 - d e s i g n s a n dc y c l i cm t s ( v 、a 1 sw i t hac y c l i cr e s o l u t i o no rac y c l i ca l m o s tr e s o l r t i o nh a v eb e e np r e v i o u s l ys t u d i e d ，b u tt h e i rb l o c ko r b i ta n dr e s o l u t i o n c l a s s e so r b i tm u s ts a t i s f yc e r t a i nc o n d i t i o n s i nt h i sa r t i c l e ，d i r e c ta n d r e e u r s i v ec o n s t r u c t i o n sf o rac y c l i cd i r e c t e dt r i p l e s y s t e mw i t hac y c l i c a l m o s tr e s o l u t i o na r ep r e s e n t e dw h e na = 1 t h e r e8 x et w oc h a p t e r si nt h et h e s i s ： t h ef i r s tc h a p t e rs u m m a r i e st h ek n o w nr e s u l t so n c y c l i c a l l yr e s o l v a b l e c y c l i cs t e i n e r2 - d e s i g n sa n dc y c l i c a l l yr e s o l v a b l e ( o ra l m o s tr e s o l v a b l e ) c y c l i cm t s ( v ，a ) sb yu s i n gd i f f e r e n c ef a m i l ya n dc y c l o t o m i cc l a s s e si n s l ， 【7 a n d 【1 1 1 目录4 i nt h es e c o n dc h a p t e r ，w eg a v et h ed i r e c ta n dr e c u r s i v ec o n s t r u c t i o n s o fc y c l i cd t s ( v ) w i t hac y c l i ca l m o s tr e s o l u t i o nw h e nuil ( m o d6 ) ， v = 4 ( 3 ) a n du = 2 8 p ，w h e r epi5 ( m o d6 ) ，s ；1 ( m o d4 ) a n d s 5 k e y w o r d s d i r e c t e dt r i p l es y s t e m ；s t e i n e r2 - d e s i g n ；m e n d e l s o h n d e s i g n ；c y c l i c a l l ya h n o s tr e s o l v a b l e ；c y c l i cd i f f e r e n c ef a _ i n i l y ( c d f ) ；s e m i c y c l i cd i r e c t e df r a m e ；d i f f e r e n c em a t r i x 第一章综述 1 1 基本概念和记号 设t ，k ，a 为任意正整数一个平衡不完全区组设计是一个二元组 ( k 舀) ，其中y 为 个元素的集合，尽为y 中k 元子集( 称为区组) 的集合，且满足如下性质；v 中任意两个不同的点恰包含在8 的a 个 区组中我们把它筒记作( ，k ，a ) 一b i b d 或b ( k ，a ；u ) 当a = 1 时， ( t ，a ) 一b i b d 称为s t e i n e r2 一设计k = 3 时，( ，a ) 一b i b d 称为三 元系 如果在一个( v ，k ， ) 一b i b d 中存在一个阶数为u 的y 上的置换d s g m ( 矿) ，并且它是保持b 的，即口( 8 ) = 1 3 ；这里( 8 ) = ( 口( z 1 ) 、口( z a ) ) 。1 ，x k 舀 ，那么称这个( u ，k ，a ) 一b i b d 为循环的这样的点集 y 可以定义为乙，也就是模w 的剩余类加群，且这个设计有一个自同构 口：i h + 1 ( m o du ) 对一个循环的s t e i n e r2 设计( k b ) ，设b = b l ，b k 为它的一个 区组包含b 的区组轨道，记做徊) ，是一个集合，它包含了对于i 蜀 的如下不同区组：b + i = b l + i ，6 k + ) ( m o d 口) 如果一个区组 轨道包含”个区组，就把它称为长轨道，否则称为短轨道从一个区组轨 道中任取一个区组称为基区组包含区组 o ，u 肚，( k 一1 ) v k 的x _ e 2 。 轨道称为正则短轨道 容易验证，一个循环的( 口，k ，a ) - b i b d 的区组轨道一定是长轨道或 正则短轨道且易知循环( ，k ，a ) b i b d 存在的必要条件是 。i 1 ，k ( m o dk ( k 一1 ) ) 当u ；1 ( m o dk ( k 一1 ) ) 时，一个循环的( t ，k ，a ) 一b i b d 没有短轨道；当 5 第一章综述 6 vik ( r o o dk ( k 1 ) ) 时，这个循环设计除了长轨道外，只有一个, t n 短 轨道 一个( v ，k ，a ) 一b i b d 的平行类p 是一些区组的集合，且满足v 中 的每一个点恰好包含在p 中的一个区组中一个( t ，a ) 一b i b d 称为可 分解的，如果它的区组集8 能划分成一些甲行类p l ，砟的并我们把 冗= p l ，r ) 称为这个设计的一个平行类划分如果一个( u ，a ) 一 b i b d 是可分解的，那么必有 i0 ( r o o d ) p 所在的一个平行类轨 道，记作( p ) ，如下定义： p 十y ：y 磊 ，其中p + y = 日+ y ： b p ，从一个平行类轨道中任取一个_ 甲行类称为基平行类一个可分 解的( v ，k ， ) - b i b d 称为循环可分解的，如果存在一个阶数为 的矿上 的置换口：i i + 1 ( r o o du ) ，并且它是保持兄的，即口( 冗) = 亿，这里 口( 冗) = a ( p ) ：p r e 这时我们把该平行类划分冗称为循环的对一 个阶数为v 的1 ，上的置换口：i i + 1 ( m o d ”) ，一个( v ，k ，a ) b i b d 是 循环的并且是循环可分解的，则称这个设计为循环可分解的循环的 易得一个可分解的循环( u ，a ) - b i b d 存在的必要条件为 w ；k ( r o o d ( k 1 ) ) 这样可知循环可分解的循环( ，k ，a ) b i b d 有一个正则短轨道d = d + i ：i = 0 ，1 ，v l ，其中d = o ，v k ，2 v k ，一，( k 一1 ) ) 一个m e n d e l s o h n 三元系，记做m t s ( v ，a ) ，是一个二元组( v 8 ) 其中y 是u 个点的集合，嚣是y 中循环三元组( 称为区组) 的集合 且满足如下性质：y 中的每一个有序对恰出现在目的a 个区组中为 和( ，3 ， ) 一b i b d 中的区组 n ，b ，c ) 相区别，把m t s ( v ，a ) 的区组记做 ( a ，b ，c ) 可知区组( a ，b ，c ) 中的有序对为 ( 。，6 ) ，( b ，c ) ，( c ，n ) ) 且它产生的 差为 6 一a ，c b ，o c ) 且易知( a ，b ，c ) = ( b ，c ，a ) = ( c ，a ，b ) 一个m e n d e l s o h n 三元系是一类特殊的三元系事实上，如果忽略一 第一章综述 个l l ，i t s ( v ，a ) 的方向，就可以得到一个( u ，3 ，2 a ) 一b i b d 参照前面所定 义的关于( ，k ，a ) 一b i b d 的基本概念，可以类似的定义m t s ( v ，a ) 的 区组轨道，平行类轨道以及循环可分解的循环m t s ( v ，a ) 等概念 一个m t s 扣， ) 的几乎平行类p 是一些区组的集合，且满足y ) 中的每一个点恰包含在p 中的一个区组中( 其中z 为v 中的某个元素) 一个m t s ( v ，a ) ( k1 3 ) 称为几乎可分解的，如果区组集8 能被划分成一 些几乎平行类p ：，谚的并，这样对于一个几乎可分解的m t s ( v ，a ) ， 必有 ；1 ( m o d ) 定理1 1 1 7 】一个循环的m t s ( v ，a ) 存在的充要条件为 ( 1 ) ai1 ，5 ( m o d6 ) 且v i 1 ，3 ( r o o d6 ) ， ( i i ) a ；2 ，4 ( m o d6 ) 且 i0 ，1 ( r o o d6 ) ， ( i i i ) a ；3 ( m o d6 ) 且 i 1 ( m o d2 ) ，或 ( i v ) a ；0 ( m o d6 ) 且3 ， 除去：( v ， ) = ( 9 ，1 ) ，( 6 ，2 ) 和( 9 ，2 ) 1 2 直接构造的已知结果 本节将对前人关于循环可分解的循环s t e i n e r2 - 设计和循环可分解的 ( 或几乎可分解的) 循环m t s ( v ，a ) 的直接构造进行简单介绍 关于循环可分解的循环s t e i n e r2 一设计，文献( 6 和【1 1 中给出的直 接构造均需满足条件( p 1 ) 和( p 2 ) ，其中 ( p 1 ) d 为正则短轨道d 中的基区组一个平行类若包含区组d ，则 它不再包含口中的任何其他区组； ( p 2 ) 冗为一个平行类且不包含正则短轨道d 中的任何区组这时 满足冗+ t = 冗的最小正整数t 为k 第一章综述 8 首先介绍一下文献 6 中满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环 s t e i n e r2 设计的直接构造，其中k 为奇数 引理1 2 1 【6 v 是一个素数如果一个循环可分解的循环( k v ，k ，1 ) - b i b d 存在，则有“i1 ( r o o dk ( k 一1 ) ) 为了介绍s t e i n e r2 一设计的直接构造，我们还需引入以下定义 一个基区组族，= b i ：i n 称为磊上的一个( t ，k ，1 ) 一差族( 简 记做( ，k ，1 ) 一d f ) ，如果满足u 。，b 。= 毛令k 为一个奇数，v ；1 ( m o dk ( k 一1 ) ) 为一个素数一个( ，k ，1 ) 一d f ，= b ；：i ) ，称为根 差族( 简记做( ，k ，1 ) 一r d f ) ，如果每个基区组都是玩中的k 次单位根 的陪集 定理1 2 2 ( 6 当 为素数且k 为奇数时，如果存在一个( v ，1 ) 一r d f ， 则存在一个循环可分解的循环( k v ，1 ) b i b d 作为定理1 2 2 的补充，以下定理解决了( v ，k ，1 ) 一r d f 的存在性问 题它是w i l s o n 定理 见 1 2 】的改进形式： 定理1 2 3 【9 令口= n k ( k 一1 ) 十1 是一个素数，k = 2 m + l ，e 是z ， 中的一个k 次单位根，且s = 一1 ，一l ，“一1 ，磊中的一个 ( u ，k ，1 ) r d f 存在的充分条件是m n 的因子有如下形式的分解链； d o = 1ld l ld 2 ，1d 2 tld 2 t + l = m n 使得 n = 兀o t ( d 2 r + l d 2 t ) 妒( s ) cu 0 t t ( h d 2 t - 1 h 。7 ) u 1 ， 其中妒( s ) = z y _ 1 ：z ，y 田并且4 是磊中由d 次幂生成的群 上述设计中k 必须为奇数，丽文献 1 1 中给出的循环可分解的循环 s t e i n e r2 一设计的直接构造却无需考虑k 的奇偶性 同样，由引理1 21 对于一个满足条件( p 1 ) 和( p 2 ) 的循环可分解的 第一章综述 9 循环( k p ，k ，1 ) 一b i b d ，有pil ( r o o dk ( k 1 ) ) 故对非负整数t ，可令 p = k ( k1 ) t + 1 由g c d ( ，p ) = 1 知玩p 兰磊乙在文献【1 l 】中，令 v = z k 乙，以口：( i ，j ) 一( i ，j ) + ( 1 ，1 ) ( r o o d ( k ，p ) ) 作为一个自同构 下面介绍文献【儿 中给出的一个满足条件( p 1 ) 和( p 2 ) 的循环可分 解的循环( 坳，k ，1 ) 一b i b d 的直接构造 令w 为a f ( k ( k 一1 ) t + 1 ) = 邑中的一个本原元构造如下( 地+ 1 ) 个区组： d = ( o ，o ) ，( 1 ，o ) ，( 2 ，0 ) ，( k 一1 ，o ) ) ， a ；= ( 1 ，u ( k - 1 ) ) ( o ，a o ) ，- ，( 0 ，a k - 1 ) ) ，0 i t ， 马= ( 1 ，u 幻) ( ( o ，b o ) ，一，( k 一1 ，6 b1 ) ) ，0 j ( k 一1 ) t 把马( 0 冬j ( 一1 ) ) 划分成如下k 一1 个子族： b ? = ( 1 ，u 。( k - 1 ”) - ( o ，6 0 ) ，一，( k 一1 ，b k1 ) ) ，0 j t ， b = ( 1 ，u 2 ( k - 1 b + ) ( o ，b o ) ，- 一，一1 ，b k 一1 ) ，0 j t ， 骘一2 = ( 1 ，u 一1 + ( k - 2 ) ) ( o ，b o ) ，( k 一1 ，b k - , ) ) ，0 j t 如果2 - 维向量( a o ，a l ，a k “b o ，b l ，b k 一1 ) 满足某些充分条件， 就可以得到一个满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环( k ( k ( k 一1 ) t + 1 ) ，k ，1 ) 一b i b d ，其中 v = 玩磊忙一1 ) ”1 ， 廖= d ( m o d ( - ，k ( k 一1 ) t + 1 ) ) ) u a i ( m o d ( k ，k ( k 一1 弦+ 1 ) ) ：0 i ) u 马( m o d ( k ，k ( k 一1 ) t + 1 ) ) ：0 茎j ( k 一1 ) ) 并且，模( 一，k ( k 一1 ) t + 1 ) 的一个平行类轨道中的基平行类为 d ) u a i ( m o d ( k ，一) ) ：0 i t ) u 目( r a o d ( k ，一) ) ：0 j t ，0 兰l k 一2 ) 第一章综述 1 0 同时模( k ，一) 的一个平行类轨道中的基平行类为 磷一2 ( r o o d ( 一，k ( k 一1 ) t + 1 ) ) ) ，0 j t 这里，记号m o d ( k ，一) 表示第一分量模k ，而第二分量不变， 我们还需再给出一些新的定义。 q = m t + 1 为一个素数幂，c o 为g f ( q ) 1 0 中阶数为t ，指数 为m 的乘法子群令这个子群的陪集为0 2 ，c 易，c 鬻一，我们称之为 g f ( q ) 中指数为m 的分圆类显然它们恰好划分g f ( q ) ( o ) 分圆类 嚷，姥，馏。1 ) 记做岛 如果在g f ( q ) 中存在一个m 元集合，满足其中的元素互不相同且分 别属于m 个不同的分圆类c o ，c ，c 鬻，则称这个m 元集合为分圆 类。的一个相异代表元系，记做s d r c ( 。) 一个循环有序k 元组( c o ，c 一，c k 一1 ) 的分差就是集合 c 0 一 c 。，c 1 一c 。+ ，c k 一1 一c s + k 1 ) ，其中下标是模k 的 以上提到的2 女一维向量( a o ，n l 、，a 女“b o ，b 1 ，b k 一1 ) 需满足以下 条件； 定理1 2 4 1 1 】令u 为g f ( p ) 中的一个本原元，其中p = k ( k 一1 ) + 1 是 一个素数，t 是一个非负整数如果存在g f ( p ) 中的元素，a o ，a - ，“ b o ，b l ，b k 一1 满足如下条件，则存在一个满足条件( p 1 ) 和( p 2 ) 的循环 可分解的循环( k p ，k ，1 ) 一b i b d ( c 1 ) 集合 o ，a l ，- 一，a k 一1 ) 中元素彤成的k ( k 一1 ) 个差形成一个 s d r c ( k ( k 1 ) ) i ( c 2 ) 循环有序的k 元组( b o ，b l ，一，b k 一1 ) 的t 一分差形成一个s d r c ( 反) ，其中0 t k 一1 i ( c 3 ) o o ，a l ，- 一，a k 1 ) u u 幻：0 j k 一2 ) b o ，b t ，“1 ) 形 成一个s d r c ( 氏陋1 1 ) ， 第一章综述 当= 4 时，文献【1 1 中还给出了使得满足条件( p 1 ) 和( p 2 ) 的 循环可分解的循环( 卸，4 ，1 ) 一b i b d 存在的p 的上界p o ，即当p p o = 2 2 5 8 1 5 0 7 时，存在一个满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环( 4 p ，4 ，1 ) b i b d 以上讨论的都是关于满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环 s t e i l l e r2 - 设计的直接构造接下来我们再介绍一下文献f 7 1 中给出的满 足条件( m i ) 一( m 4 ) 的循环可分解的( 或几乎可分解的) 循环m e n d e l s o h n 三元系的直接构造，其中： ( m 1 ) 恰有2 a 个短轨道； ( m 2 ) 其中仅包含一个短轨道的平行类的个数为a ； ( m 3 ) 如果一个平行类中包含某一短轨道中的区组，则它不包含其余 短轨道中的区组； ( m 4 ) 若一平行类中不包含短轨道中的任意区组，则其所在的平行类 轨道长度和区组长度相同，即为3 引理1 2 5 7 循环可分解的循环m t s ( v ，a ) 存在的必要条件为 ( i ) a ；l ( m o d2 ) 且u i 3 ( m o d 6 ) ，或 ( i i ) a 三0 ( m o d2 ) 且 i0 ( m o d3 ) ， 除去：( ， ) = ( 9 ，1 ) ，( 6 ，2 ) 和( 9 ，2 ) 引理1 2 6 7 循环几乎可分解的循环m t s ( v ， ) 存在的必要条件为 ( i ) a ；1 ( m o d2 ) 且v ；i ( m o d6 ) ，或 ( j j ) a 差0 ( r o o d2 ) 且口ii ( r o o d3 ) 在介绍文献【7 中设计的直接构造时，需用到以下定义： g 为 阶阿贝尔群，令，= 只：i ，) 为g 中元组( 称为区 组) 的族，其中只= k o ，k i ，五，一1 ) 如果对任意的t i ，z # ，0 z ，y 一1 ，g 中的每个非零元都恰出现在差凫一厶中a 次，则称， 第一章综述 1 2 为一个( ”，k ，a ) 一差族( 简记做( u ，a ) 一d f ) 一个( u ， ) 一m e n d e l s o h n 差族( 简记做( ，a ) - m d f ) 与( ，k ，a ) 一 d f 的不同之处在于g 中的不同二元组都是连续且循环有序的，即 岛 加1 o 为和( v ，k ，a ) - d f 中的区组相区别，把( u ，k ，a ) m d f 中的区组记做( 厶， 1 ，一， 卜1 ) 易知，由一个( ，k ，a ) 一m d f 可 以得到一个循环的m t s ( v ，a ) 如果在一个( ，a ) 一m d f 中，基区组r 被分成大小相同的卢类，且在同一类中的区组都是完全不相交的，则称f 为p p 哂不相交的当然，卢和a 没有直接联系但文献 7 】是在p = a 的情况下给出m t s ( v ，a ) 的直接构造 定理1 2 7 7 】u 是正整数且ve1 ( m o d3 ) 如果存在一个a p l y 不相 交的( v ，3 ，a ) 一m d f ，则存在一个满足条件( m 1 ) 一( m 4 ) 的循环可分解的循 环m t s ( 3 v ，a ) 类似，关于循环几乎可分解的循环m t s ( v ，a ) 有如下定理： 定理1 2 8 7 】 是正整数且 i1 ( m o d3 ) 如果存在- 4 a p l y 不相 交的( v ，3 ，a ) 一m d f ，则存在一个循环几乎可分解的循环m t s ( v ，a ) 关于定理12 7 和定理1 2 8 中提到的a p l y 不相交的( v ，3 ，a ) 一m d f 的存在性问题，可参见文献 7 在此不一一赘述 1 3 差阵及递归构造的已知结果 利用差阵给出一个设计的递归构造是组合设计中一种比较常用的方 法下面我们先介绍一些有关差阵的基本概念 设( g ，) 是一个 阶有限群g 上的( v ，k ，a ) 差阵是一个k ( a ) 矩阵d = ( 屯) ，它的元素取自g ，并且满足对于任意的1 i j 、都 有 第一章综述 1 3 d “蛎11 2 曼 a ) 恰包含g 中的元素a 次当g 是阿贝尔群时，运用加法运算，从而得到 差d ：! 一d “通常把五上的( u ，k ，a ) 差阵记作( u ，k ，a ) 一d m a = 1 时， ( ，k ，1 ) 一d m 简记作( v ，) 一d m 目前差阵已经被广泛研究，下面是其中 的一个结论 引理1 3 1 1 3 设 和k 是正整数且9 c d ( v ，( k 一1 ) ! ) = 1 对于i = 0 ，1 ，k l ，j = 0 ，1 ，一，v l ，令啦；i j ( m o d ) ，那么d = ( d 。) 就是一个磊上的( ，) - d m 特殊地，如果 是一个奇素数，那么对任 意的整数k ，2 k ，存在一个磊上的( v ，) 一d m 当k 为奇数时，关于满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环 s t e i n e r2 - 设计的递归构造，有如下定理： 定理1 3 2 6 】如果存在 ( 1 ) 一个满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环( k v ，k ，1 ) 一b i b d ( 2 ) 一个满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环( k u ：k ，1 ) 一b i b d ( 3 ) 一个( “，k4 - 1 ) 一d m 那么存在一个满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环( k u v ，k ，1 ) 一 b i b d 利用差阵也可以给出不考虑k 的奇偶性时，满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环( k p ，k ，1 ) - b ，b d 的递归构造 定理1 3 3 1 1 如果存在 ( 1 ) 一个满足条件( p 1 ) 和( e 2 ) 的循环可分解的循环( k v ，1 ) b i b d ( 2 ) 一个满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环( k u ，k ，1 ) b i b d ( 3 ) 一个( “，+ 1 ) 一d m ， 那么存在一个满足条件( p 1 ) 和( p 2 ) 的循环可分解的循环( k u v ，女，1 ) 日r 疗j ) 第一章综述 关于循环可分解的( 或几乎可分解的) 循环m t s ( v ，a ) 有 定理1 3 4 7 】“，v 为正整数且“，v ；1 ( r o o d ) 如果存在一个a p l y 不相交的( ，k ，a ) 一m d f ，一个a p l y 不相交的( u ，k ， ) 一m d f 和一个 ( “，k + 1 ) 一d m ，则存在一个a p l y 不相交的( 1 t v ，k ，a ) 一m d f 第二章循环几乎可分解的循环有向三元系 2 1 基本概念和记号 设 ，k ，a ，g 为任意正整数集合 ( o 。，a j ) ：1 i j ) 通常 记为( a l ，a 2 ，a k ) ，称作可迁元组一个组型为g ”的有向( ：，a ) 一 g d d 是一个三元组( x ，g ，4 ) ，其中x 是”9 个点的集合，9 是x 的 一个划分，它把x 分成u 个长度为g 的组，且是x 的一些可迁k 元 组( 称为区组) 的集合且满足如下性质：每一个区组和每一个组至多相 交于一个点且不同组的任意两个点恰包含在4 的a 个区组中一个组 型为1 ”的有向( k ，a ) 一g d d 是一个参数为v ，k ，a 的有向平衡不完全区 组设计，记为d b ( k ，a ；v ) 当k = 3 时，d b ( k ，a ；v ) 通常称为有向 三元糸，记作d t s ( v ， ) 如果在一个有向g d d 中存在一个阶为 g 的 x 上的置换口s y m ( x ) ，并且它是保持4 和g 的，即d ( 4 ) = a 和 a ( g ) = 9 ；这里口( 4 ) = ( a ( 。1 ) ，一，口( z k ) ) ：( x l ，x k ) 一4 ) ，o ( g ) = 口( 玑) ，d ( 蜘) ) ： y i ，9 ) ，那么称这个有向g d d 为循环的 这样点集x 可以定义为磊。，也就是模”9 的剩余类加群，且这个设计有 一个自同构口：i i 十1 ( r o o dv g ) 对一个组型为g ”的循环有向( k ，a ) 一g d d ，( x ，孚，层) ，假设b = ( b l ，b 2 ， ，b k ) 为它的一个区组包含b 的区组轨道，记作徊) ，是一个集合它 包含了对于i 玩。的如下不同区组 b + i = ( b l + i ，- ，k + i ) ( r o o du 雪) 如果一个区组轨道包含叼个区组，那么这个区组轨道称为长轨道，否则 称为短轨道从一个区组轨道中任取一个区组称为基区组容易证明循 环d t s ( v ，a ) 的区组轨道一定是长轨道且易知循环d t s ( v ，a ) 存在的 1 5 第二章循环几乎可分解的循环有向三元系 1 6 必要条件是 ( i ) a 0 ( m o d3 ) 且t ，3 ( i i ) a11 ，2 ( m o d3 ) 且v ；0 ，1 ( m o d3 ) 一个组型为g “的有向( k ，a ) - g d d 的平行类p 是一些区组的集合， 且满足x 中的每一个点恰好包含在p 中的一个区组中一个组型为g ”的 有向( 女，a ) 一g d d ( x ，蛋，1 3 ) 称为可分解的，如果区组集8 能被划分成一些 平行类r ，一，砟的并这样，如果一个有向g d d 是可分解的，那么必 有v g i0 ( m o d ) 另外，冗= p l ，砟) 称为这个设计的一个平行类 划分p 所在的一个平行类轨道，记作( p ) ，如下定义： p + ：y 磊。) ， 其中7 ) 十y = b + y ：b p 从一个平行类轨道中任取一个平行类称 为基平行类一个组型为g 。的可分解的有向( k ， ) 一g d d 称为循环可分 解的、如果存在口：i i + 1 ( r o o dv g ) 作为一个自同构，并且它是保持 冗的，即o ( n ) = 冗，这里口( 冗) = a 伊) ：p 冗) 这样的平行类划分 冗称为循环的 一个组型为9 ”的有向( k ，a ) 一g d d ( x ，9 ，b ) 的带洞平行类是一些 可迁k 元组的集合p ，它对某个g g 形成x g 的一个划分，组g 称作相对于p 的洞p 所在的一个带洞平行类轨道，记作( p ) ，如下定 义： p + y ：y 毛9 ) ，其中p + y = b + y ：b _ p ) 从一个带洞平行 类轨道中任取一个带洞平行类称为基带洞平行类一个组型为g ”的有向 ( k ，a ) 一g d d ( x ，g8 ) 称为组型为g ”的d f r a m e ( 或d f r a m e ( g ”) ) 如果区 组集8 能被划分成一些带洞平行类q 1 ，q ”一，q ，的并一个组型为矿 的d f r a m e 称为循环带洞可分解的，如果存在口：i i + 1 ( m o dv g ) 作 为一个自同构，并且它是保持冗= q 1 ，q 。，q r ) 的这样的带洞平 行类划分冗称为循环的 关于组型为g ”的d f r a m e ，我们可以举一个例子来说明一下 第二章循环几乎可分解的循环有向三元系 1 7 例子2 1 1 一个组型为4 4 的甜r a w 。e , 它的四个组分别为 0 ，4 ，8 ，1 2 ， 1 ，5 ，9 ，1 3 ， 2 ，6 ，1 0 ，1 4 ， f 3 ，7 ，1 1 ，i s 带洞平行类分别为 ( 1 ，2 ，7 ) ，( 3 ，5 ，1 4 ) ，( 1 3 ，1 1 ，1 0 ) ，( 1 5 ，6 ，9 ) ) ， 1 2 ，3 ，8 ) ，( 4 ，6 ，1 5 ) ，( 1 4 ，1 2 ，1 1 ) ，( 0 ，7 ，1 0 ) ) ， “3 ，4 ，9 ) ，( 5 ，7 ，0 ) ，( 1 5 ，1 3 ，1 2 ) ，( 1 ，8 ，1 1 ) 1 ， ( 4 ，5 ，1 0 ) ，( 6 ，8 ，1 ) ，( 0 ，1 4 ，1 3 ) ，( 2 ，9 ，1 2 ) ) 一个d b ( k ，a ； ) ( v 舀) 称为几乎可分解的，若8 可划分成冗 ，咒。 的并，其中亿，是x 扛) 的划分( 冗 称为几乎可分解平行类) ，这里3 7 , 是x 中的某个元素循环几乎可分解的循环d b ( k ，a ；u ) 实际上是一个 组型为1 。的循环带洞可分解的d f r n m e 这祥，如果一个d b ( k ，a ， ) 是 几乎可分解的，必有 1 ( m o dk ) 前人的工作中，不管是循环可分解的循环s t e i n e r2 设计，还是循环 可分解的( 或几乎可分解的) 循环m e n d e l s o h n 三元系的直接构造和递归 构造，其平行类轨道和区组轨道都要满足一些限定条件本部分在对平行 类轨道和区组轨道没有限定条件的情况下给出丁当a = 1 时循环几乎可 分解的循环有向三元系的直接构造和递归构造 2 2 直接构造 引理2 2 1 循环几乎可分解的循环d t s ( v 】只含有一个几乎可分解平行 第二章循环几乎可分解的循环有向三元系 1 8 类轨道，且轨道长为u ， 证明设( _ p ) 为循环几乎可分解的循环d t s ( v ) 中任一几乎可分解平行 类轨道且轨道长为n 因p 中区组个数为( 一1 ) a ，从而】p 】= 扣一1 ) 3 任取一个区组b _ p 设 ( b ) n pj = b 对于p l ，7 2 ( p ) ，由循环几乎可分解的定义，易知i ( b ) np l i = i 徊) np 2 i = i b 又已知此设计为循环的，故i ( b ) i = v ，且有”= n1 b 从而，l ( b ) n p i = 加且不依赖于b 的选取所以有( v n ) l ( 一1 ) 3 故n=”t2 定理2 2 2 当 是素数且 i1 ( r o o d6 ) 时，存在循环几乎可分解的循 环d t s ( v ) 证明设。是乙 o ) ( = z ) 中的一个6 阶子群的生成元这样有= 1 从而舻= - 1 令z l ，。( 。一1 ) 6 为z 的全体代表元系，这里 为露中的由n 生成的6 阶子群 设区组集尽由如下沁一1 ) a 个有向基区组构成： a 。= - ( 1 ，0 = 。，0 4 ) ， b t = z l ( n 3 ，。5 ，n _ ) ， 其中i = 1 ，2 ，扣一1 ) 6 下面将证明刃中的每一个元素恰出现在 u 瘩1 ) 6 ( a a 。ua b 。) e e - o ( 由a 。和b i 生成的有向差的集合为娥( c 户一 1 ) 1 ，n ，d 2 ，0 3 ，4 ，d 5 ) ( m o d ) ，其中i = 1 ，2 ，r ，( 一1 ) 6 这样z ：中 的每一个元素恰在u ( v - t ) 6 ( a ；ua b e ) 中出现一次。因此，由基区组a ， 和鼠生成一个循环的d t s ( v ) ，( 乙，8 ) 下面要证明这个设计是循环几乎可分解的令 冗o = a ，最：i = 1 ，2 ，t 一，( 一1 ) 6 包含在冗。中的区组个数为( 扣一1 ) 6 ) 2 = ( v 一1 ) a a 。na ，= o ，a n b ，= 0 和bn 马= d 显然成立，且a ，及鼠中都不包含0 从而 第二章循环几乎可分解的循环有向三元系 1 9 有u 生1 ) 6 ( a 。ub 。) = 磊 o ) 模加0 ，1 ， 一1 到7 上，可以得到 v 个几乎可分解平行类： 码一亿。十，( m o du ) ， 其中j = 0 ，1 ，”一1 这些几乎可分解平行类7 恰好覆盖设计( 五，廖) 的所有区组的集合n 为给出当u = 4 。时循环几乎可分解的循环有向三元系的一个构造方 法，先描述一些更进一步的定义， 一个( v g ，9 ，a ) 循环差族( 记为( v 9 ，g ，k ，a ) 一c d f ) f 是z 。中一 些k 元子集( 也称为基区组) 的集合，且满足蜀。一”五。中的元素在 芦= u b e ，a b 中恰出现a 次，其中对于b = 。o ，。l t ，双一i ) ，a b = z ，一i i ：0 t ，j k 一1 ；i ， 如果一个( v g ，9 ，k ，a ) 循环差族中 的基区组都是可迁k 元组，定义a b = 叻一x i ：0 i j5k 一 1 ) ，其中b = ( x o ，x l ，x k 1 ) ，那么这个循环差族称为