（运筹学与控制论专业论文）循环群zv上（vkk1）不相交差族的构造方法.pdf

北京交通大学硕士学位论文 中文摘要 中文摘要 摘要：差族是一类组合设计，是差集概念的自然推广差族方法是构作b i b 设计 最常用也是最有效的方法之一，关于差族的详细介绍请参考 1 3 1 。设( g ，+ ) 是”阶 的a b e l 群，日是群g 的g 阶子群。又设，= 鼠：l n 是g 的一些七元子集构成 的子集族。对任意b g ，记a b = “一b ：口，b b ，a 6 ，a 2 = 一u j 马， 若，= a ( g h ) ( 其中入( g j ! f ) 表示包含g 日中的任一元素恰好a 次的多重集) ， 则称厂是一个( g ，ek ，a ) 一差族( 或( g ，ek ，a ) - d f ) ，晟称为基区组。当g = 1 时，简 记为( g ，k ，a ) 一d f 。 本文主要考虑的是：g 上的( g ，ek ，a ) 一差族的基区组互不相交的情况( 即g 上 的( g ，h ，k ，a ) 一不相交差族) 。进一步我们要求g 为乙，h = o ) ，a = k l ，此时 为z 付上的( 口，k ，k 一1 ) 一d d f 。我们主要研究在这种情况下( 其中k = 3 ，4 ) 的不相交 差族存在的充分条件。在这种条件下的不相交的差族与许多设计都有密切的关系， 例如：外部差族，w h i s t 竞赛设计，完备基以及循环几乎可分解的循环的d t s 。 本文共分两章。 第一章中综述了本篇文章主要要用的基本概念，不相交的差族与其他设计的 关系，以及前人给出的关于不相交差族的初步结果。 第二章中给出了不相交差族的几种直接构造方法和递归构造方法，最后给出 了一些新的结果。 我们首先利用( k ，1 ) 一c d f 或( t ，k ，k ，1 ) 一c d f 得到乙上一个( 钉，k 一1 ，k 一2 ) 一 d d f 。 然后利用循环的g d d 及半循环的f r a m e ，得到乙上( 钉，g ，k ，k 一1 ) 一d d f 的一个 新构造。 最后给出当p 兰5 ( m o d1 2 ) 为素数时，历，上的( 5 p ，3 ，2 ) 一d d f 的一种特殊构造 方法。 关键词：不相交的差族( d d f ) ；循环差族( c d f ) ；半循环的f r a m e ；循环几乎可 分解；差阵 分类号：0 1 5 7 2 北京交通大学硕士学位论文a b s t r a c t a b s t r a c t a b s t a c t ：d i f f e r e n c ef a m i l yi sak i n do fc o m b i n a t o r i a ld e s i g n a n di t i sa g e n e r a l i z a t i o no fd i f f e r e n c es e t d i f f e r e n c em e t h o di so n eo ft h em o s tu s e f u la n d e f f e c t i v ef o rc o n s t r u c t i n gc o m b i n a t o r i a ld e s i g no fm a n yt y p e s f o rm o r ei n f o r m a r t i o no nd i f f e r e n c ef a m i l y , t h er e a d e ri sr e f e r r e dt o 【1 3 j l 毗( g + ) b e 缸a b e l i a n g r o u po fo r d e r a n dhas u b g r o u po fg 丽t hge l e m e n t a ( g ，ek ，a ) r e l a t i v e d i f f e r e n c ef a m i l y ( o r ( g ，ek ，a ) 一d fi ns h o r t ) i sac o l l e c t i o n ，= 口：t n o fk - s u b s e t s ( c a l l e db a s eb l o c k s ) o fgw i t ht h ep r o p e r t yt h a ti t sl i 8 to fd i f f e r e n c e s 丁= u ja 最i sa t i m e sg hw h e r e 鼠= a b ：口，b 最，口吣i nt h e c 8 8 et h a tg = 1 ，w e s i m p l yc a l li ta ( g ，上la ) 一d f ( o r ( t ，k ，a ) 一d fo v e rg ) i nt h i sa r t i c l e ，w em a i n l yc o n s i d e rt h ef o l l o w i n gc a s e 8 ：t h eb a s eb l o c ko f ( g ，日，七，a ) - d fi nga r ep a i r w i s ed i s j o i n t i np a r t i c u l a rg = 磊，h = o ) ，a = k 一1 ，( g ，h ，七，a ) - d d f i sd e n o t e db y ( t ，k ，k 1 ) 一d d f i n 磊w e m a i n l ys t u d y t h es u f f i c i e n tc o n d i t i o no f ( ”，七，七一1 ) 一d d fi nz ；，f o rk = 3 ，4 d i 8 j o i n td i f f e r e n c e f a m i l i e sa r er e l a t e dw i t hm a n yk i n d so fc o n b i n a t o r i a ld e s i g n ss u c ha se x t e r n a l d i f f e r e n c ef a m i l i e s ，w h i s tt o u r n a m e n t ，c y c l i c a l l ya l m o s tr e s o l v a b l ec y c l i cd i r e c t e d t r i p l es y s t e m sa n dp e r f e c tb a s e s t h e r ea r 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 ri n t r o d u c e st h eb a s i cd e f i n i t i o n ，t h er e l a t i o nb e t w e e nd i s j o i n t d i f f e r e n c ef a m i l i e sa n do t h e rd e s i g n s ，a n ds o m ek n o w nr e s u l t s i nt h es e c o n dc h a p t e r ，w ew i l lp r e s e n ts o m en e wc o n s t r u c t i o n sa n dr e c u r s i v e c o n s t r u c t i o n so fd d f s i nt h el a s tw eg e ts o m en 哪r e s u l t s f i r s t l y , w ec o n s t r u c ta ( 钉，k 一1 ，七一2 ) 一d d fi nz jt h r o u g h ( 口，k ，1 ) 一c d fo r ( k ，k ，1 ) 一c d f s e c o n d l y , w eu s ec y c l i cg d da n ds e m i - c y c l i cf r a m et og e ta0 ，g ，k ，k - 1 ) 一d d f i n 乙 f i n a l l y , w eg i v eas p e c i a lc o n s t r u c t i o no f ( 5 p ，3 ，2 ) 一d d fi nz 岛，w h e np 三 5 ( m o d1 2 ) i sap r i m e k e y w o r d s ：d i s j o i n td i f f e r e n c ef a m i l y ( d d f ) ；c y c l i cr e l a t i v ed i f f e r e n c er a m - i l y ( c d f ) ；s e m i - c y c l i cf r a m e ；c y c l i c a l l ya l m o s tr e s o l v e b l e ；d i f f e r e n c em a t r i x c l a s s n o ：0 1 5 7 2 北京交通大学硕士学位论文第一章绪论 1 基本概念 第一章绪论 设( g ，+ ) 是 阶的a b e l 群，日是群g 的g 阶子群。又设，= 晟：i d 是g 的一 些k 元子集构成的子集族。对任意b g ，记a b = 一b ：n ，b b ，n ”，= u 蚶毋，若，= a ( g 日) ( 其中a ( g 日) 表示包含g 日中的任一元素恰好a 次的 多重集) ，则称，是一个( g ，ek ，a ) 差族( 或( g ，只a ) 一d f ) ，b 称为基区组。当g = 1 时，简记为( g ，ea ) d f ( 或者g 上的( 秽，k ，a ) 一d f ) 。显然( g ，日，七，a ) 一d f 存在的必 要条件为a ( i g i i h i ) 三0 ( * n o d ( k ( k 一1 ) ) ) 。当g 是循环群乙时，日是磊的g 阶 子群，则h = ( v g ) 乙= ( o ，v g ，2 r i g ，0 1 h 9 ) ，这时( 蜀，扣9 ) 乙，靶，”- 差族称为( u ，g ，七，a ) 循环差族，记为( 口，g ，k ，a ) - c d f 。在【2 】中( 口，g ，k ，a ) 一c d f 被称 为( 口，g ，k ，a ) - d f ，在【8 l 中它也被称为g r e g u l a rc y c l i cp a c k i n gc p ( k ，1 ；钉) 。 设( g ，+ ) 是口阶的a b e l 群，日是群g 的g 阶子群设芦一 最：t n 是一 个( g ，h ，奄，a ) 差族，如果它满足下面两个条件：( 1 ) ，里的基区组互不相交；( 2 ) u f 鼠g 日，这时，称为不相交的差族，记为( g ，h ，觅，a ) 一d d f 或( h b e l 群gt = 的( t ，g ，k ，a ) 一d d f ) 。当g = l 或h = o ) 时，记为( g ，k ，a ) 一d d f ( 或g 上的( t ，k a ) 一 d d f ) 。当a = k l 时，不相交的差族芦= 鼠：i n 恰是g 日的一个划分，从 而g 上( 口，g ，k ，k 一1 ) d d f 存在的必要条件是t ，兰g ( r o o d 七) 。 设 五，五，五) 是一个( g ，k ，a ) 一d d f 的集合，其中每一个五( 1 i 8 ) 都 是一个( g ，k ，a ) - d d f ，如果u ：1 ( u 日暖b ) 构成g o ) ，那么称 五，无，) 为 不相交差族的一个完全集，记为( g ，k ，a ) 一c d d f 。显然， 口：b u ：1 五) 组成 一个( g ，k ，s a ) 一d d f ，并且( g ，ta ) 一c d d f 中含( g ，k ，a ) 一d d f 的个数为伪一1 ) a 当8 = 1 ( 即a = k 一1 ) ，一个( g ，k ，a ) 一c d d f 恰为一个( g ，a ) 一d d f 。f u j i - h a r a 等人在 3 】中给出t ( g ，七，a ) 一c d d f 的递归够造方法，从而我们也得到了一些 关于( g ，k ，a ) 一d d f 的一些递归构造方法。这些构造方法我们将在第二章的第二节 介绍。 下面介绍与循环差族和不相交的差族密切相关的两个概念：循环可分组设计 与半循环的f r a m e 。 可分组设计( g d d ) 是一个满足下面条件的三元组( x ，9 ，b ) ： ( 1 ) 9 是集合x ( x 中的元素叫点) 的一个划分，g 中的元素叫做组； ( 2 ) 日是x 的子集的集合( 嚣中的元素叫区组) ，并且每个组和每个区组至多交于一 个点： ( 3 ) 每一对来自不同组的点恰包含在a 个区组中。 北京交通大学硕士学位论文 第一章绪论 常用指数形式来描述一个g d d 的组型：组型t f ，t 静表示在g 中有地个如长 的组，1 i m 区组长度取自集合k 的o d d 记为( k a ) 一g d d 。当k = 七) 时，简 记为( 詹，a ) g d d 。当a = 1 简记为k - g d d 。组型为1 ”的k - o d d 即为参数为( 口，七，1 ) 的 平衡不完全区组设计( b z b d ) ，记为b ( 1 ：秽) 设( x ，多，8 ) 是一个g d d ，盯是x 上的一个置换。对于任意集合s = 。1 ，z 。) x ，定义盯( s ) = 盯0 1 ) ，仃0 k ) ) ，如果有盯( 9 ) = p ( g ) ：g 外= 9 并 i t 盯( b ) = 口( b ) ：b 8 = 层成立，那么盯称为g d d 的一个自同构。任意自同 构盯把8 分成若干个等价类，每个等价类叫层在盯下的轨道。每个轨道取出一个区 组代表叫做此g d d 的基区组。一个g d d 称为是循环的，如果它有一个白同构包含 一个长为 = i 的圈，这时可以把x 看成玩并取盯：i i + 1 ( m o dt ，) 。我们 用( ka ) 一c g d d 来表示轨道都为长轨道的循环的g d d 。 设芦是一个扣，9 ，k ，a ) - c d f ，则，可以产生一个组型为矿扣= 9 n ) 的( ，砷一 c g d d 。其中组集9 = ( 口g ) 磊+ i ：0 i v g ，区组集b = b + t ，：b 兀t ，磊) 。设( x ，9 ，廖) 是一个g d d ，c b ，若存在某个g 9 ，使c 构成x g 的 一个划分，则称c 为此g d d 的一个部分平行类。若组集8 能够划分成一些部分平行 类的并，则此g d d 称为一个细m e 。易见，磊上一个( 夕，七，七一1 ) 一d d f 可以产生 个( t ，g ，七，七一1 ) 一f r a m e 。 假设n 和h 都是正整数，厶= 1 ，2 ，n ，s = 厶磊。如果s 上存在一 个( h n ，h ，惫，k - 1 ) - f r a m e ，它有礼个部分平行类r l ，玩+ 1 ，r t - 1 ) h + 1 ，分别形成j s ( 1 x 磊) ，s ( 2 磊) ，s ( n ) 磊) 的划分，且平行类沈+ j + 1 可通过平行 类i h + 1 中每一个元素的第二个分量模加j 得到，这样的( h n ，h ，七，k - 1 ) 一f r a m e 被称 为半循环的。易知磊上的( h n ，h ，后，七一1 ) d d f 可以产生一个半循环的( 概，h ，七，k - 1 1 丘锄e 。 例子1 1 1 z 1 5 上一个( 1 5 ，3 ，4 ，3 ) 一d d f 的基区组如下： 1 ，2 ，4 ，8 ) ， 3 ，1 1 ，1 2 ，1 4 ， 6 ，7 ，9 ，1 3 。 列出它的五个平行类如下( 分别模加0 ，1 ，2 ，3 ，4 ) ： l ，2 ，4 ，8 ， 3 ，1 1 ，1 2 ，1 4 ， 6 ，7 ，9 ，1 3 ， 2 ，3 ，5 ，9 ) ， 4 ，1 2 ，1 3 ，1 5 ， 7 ，8 ，1 0 ，a 4 ， 3 ，4 ，6 ，l o ， 5 ，1 3 ，1 4 ，1 6 ， 8 ，9 ，1 1 ，1 5 ， 4 ，5 ，7 ，1 1 ) ， 6 ，1 4 ，1 5 ，1 7 ， 9 ，1 0 ，1 2 ，1 6 ， 5 ，6 ，8 ，1 2 ) ， 7 ，1 5 ，1 6 ，1 8 ， l o ，1 1 ，1 3 ，1 7 a 将每一个平行类中的元素分别表示成厶磊的形式，即可得到一个组型为3 5 的 半循环的( 1 5 ，3 ，4 ，3 ) 一d d f ，它的五个初始平行类如下所示： 2 北京交通大学硕士学位论文 第一章绪论 r i ： ( 1 ，o ) ，( 4 ，o ) ，( 2 ，o ) ，( 3 ，1 ) ) ， ( 3 ，o ) ，( 4 ，2 ) ，( 1 ，2 ) ，( 2 ，2 ) ， ( 3 ，2 ) ，( 1 ，1 ) ，( 2 ，1 ) ，( 4 ，1 ) ) ； t 1 4 ： ( 2 ，o ) ，( 0 ，1 ) ，( 3 ，o ) ，( 4 ，1 ) ， ( 4 ，o ) ，( o ，o ) ，( 2 ，2 ) ，( 3 ，2 ) ， ( 4 ，2 ) ，( 2 ，1 ) ，( 3 ，1 ) ，( 4 0 ，2 ) ； 岛：t ( 3 ，o ) ，( 1 ，1 ) ，( 4 ，o ) ，( 0 ，2 ) ) ， ( o ，1 ) ，( 1 ，o ) ，( 3 ，2 ) ，( 4 ，2 ) ， ( o ，o ) ，( 3 ，1 ) ，( 4 ，1 ) ，( 1 ，2 ) ； r i o ： ( 4 ，o ) ，( 2 ，1 ) ，( 0 ，1 ) ，( 1 ，2 ) ， ( 1 ，1 ) ，( 2 ，o ) ，( 4 ，2 ) ，( o ，o ) ) ， ( 1 ，o ) ，( 4 ，1 ) ，( 0 ，2 ) ，( 2 ，2 ) ； 蜀3 ： ( o ，1 ) ，( 3 ，1 ) ，( 1 ，1 ) ，( 2 ，2 ) ) ，t ( 2 ，1 ) ，( 3 ，o ) ，( 0 ，o ) ，( 1 ，o ) ) ， ( 2 ，o ) ，( 0 ，2 ) ，( 1 ，2 ) ，( 3 ，2 ) ) 。 2 不相交差族与其它设计的关系 差族在组合设计里面占有很重要的地位，不相交的差族与很多设计有密切关 系，本节就主要介绍几种与不相交差族有密切关系的设计，以及与他们的关系 2 1 不相交差族与外部差族的关系 在研究外部差族与不相交差族的关系时要用到群环，具体可参考文献 2 0 】，下 面先给出群环的定义： 设r 是一个具有单位1 的可交换环，g 为一个有限a b e l 群，其运算用加法表示。 令剐g 】由所有的形如 ，( z ) = ：a g z * 9 g 的形式和所组成。此处对任意g g 都有r ，而z 则是一个符号。在r 【g 】中定 义加法，数量乘法以及乘法三种运算如下： 则称r 【q 为一个群环。 护+ z ，= ( a 9 + ) 矽 c a g e d = ( 。) 矿 ( 删矿) = ( h 一。) 矿 北京交通大学硕士学位论文第一章绪论 在z 【g 】中的零元和单位元分别为 f o x o ：0 j l _ 一 口g 和 x 0 ：= 1 如果s 是g 的子群，定义z 【q 中的元素 s ( z ) = 护 g e s 设( g ，+ ) 是 阶的a b e l 群，d 是g 的p 个k 元子集的集合。口= d 1 ，d 2 ，上k ) ， 若多重集 u ( 皿一d j ) = a ( g o ) l j ! 舢 其中 ( d 一d j ) = z 一可：z d i ，可d j ) 则称d 是g 上一个( 口，k ，a ；p ) 一外部差族( 或g 上( ，k ，a ；p ) 一e d f ) 。由外部差族的定义 可以看出，它的基区组是互不相交的。 由群环和g 上( 钉，k ，a ；p ) - e d f 的定义，我们有下面的式子是成立的： d , ( x ) d a x 。) = - a + a g ( x ) 1 1 7 ，如果u 丁那么 存在t w a o , ) 。 5 北京交通大学硕士学位论文第一章绪论 2 3 不相交差族与完备基的关系 设g g v = o n + l 阶a b e l 群，完备基p b ( v ) 定义为：集合 s = a l ，x i 2 ，铂) ：1 i t ) x q g ，1 i t ，1 j s3 ，且满足如下性质： ( 1 ) ：= l ：x i j ，1 i s t ，1 j 3 ，互不相同； ( 2 ) ：士( z 2 一i l ) ，士( 甄3 一2 ) ，士( 卜招) ，1 i t ，互不相同。 由p b ( v ) 定义可知： 仕l1 i t ，1 j 3 = g o ； 仕( 2 钇一n ) ，士( 知一记) ，士( 戤1 诌) l1 i t ) = g o 由此可知，p b ( v ) 为g _ i = - - 个( t ，3 ，1 ) 一d d f ，从s i su - s a l j g 上一个( ，3 ，2 ) 一d d f ， 但是反之不一定成立所以我们有下面的定理成立： 定理1 2 6 a b e l 群g 上的p b ( t ，) 为g 上的( 口，3 ，1 ) 一d d f ，进而我们可以得到g 上 的( 口，3 ，2 ) 一d d f 例如：g = 历5 ，s = 1 ，2 ，l o ， 3 ，1 3 ，1 7 ， 4 ，6 ，9 ， 5 ，1 1 1 8 ，则s 为p b ( 2 5 ) 而 s u s = “l ，2 ，l o ， 3 ，1 3 ，1 7 ， 4 ，6 ，9 ， 5 ，1 1 ，i s ， 2 a ，2 3 ，1 0 ) ， 2 2 ，1 2 ，8 ， 2 1 ，1 9 ，7 ) ， 2 0 ，1 4 ，1 5 ) 为一个( 2 5 ，3 ，2 ) - d d f 。 关于p b ( 口) 有一个猜想，即e t z i o n 猜想：对任意的正整数口三1 ( r o o d6 ) ，存 在p b ( 钉) 。 2 4 不相交差族与循环几乎可分解的循环有向三元系的关系 设”，后，a ，g 为任意正整数。集合 h ，n j ) ：1 i j 七 常记为( n 1 ，a 2 ，) ， 称为可迁k 元组。一个组型为旷的有向( 女，a ) g d d 是一个- - 元f l t ( x ，g ，4 ) ，其中x 是 钉g 个点的集合，g 是x 的一个划分，它把x 分成口个长度为g 的组，一4 是x 的一些可 迁元组( 称为区组) 的集合且满足如下性质：每一个区组和每一个组至多相交于一 个点且不同组的任意两个点恰包含在一4 的a 个区组中，一个组型为l ”的有向( k ，a ) g d d 是一个参数为u ，k ，a 的有向平衡不完全区组设计，记为d b ( k ，a ； 】。当k = 3 时，d b ( k ，a ；t ，) 通常称为有向三元系，记作d t s ( v ，a ) 。如果在一个有$ g d d 中存 在一个阶为口g 个x 上的一个置换盯s u m ( x ) ，并且它是保持一4 和g 的，即盯) = 4 和盯够) = 9 ；这里盯( 棚= ( 盯( z 1 ) ，口( 钆) ) ：( z l ，z k ) 4 ) ，盯( 9 ) = 6 北京交通大学硕士学位论文第一章绪论 “盯( 掣) ，盯( ) ) ： 挑，蜘 刃，那么称有扃 g d d 为循环的，这样点集x 可 以定义为z 。也就是模叼的剩余类加群，并且这个设计有一个自同构盯：i i + 1 ( r o o d 叼) 。 对于一个组型为矿的循环有向( k ，a ) 一g d d ，( x ，玩b ) ，假设b = 仇，6 2 ，6 七) 为它的一个区组。包含b 的区组轨道，记作( b ) ，是一个集合，它包含了对于i 乙。的如下不同区组 b + i = ( 6 l + i ，k + ) ( m o d t w ) 如果一个区组轨道包含t ，g 个区组，那么这个区组轨道称为长轨道，否则称为短轨 道。从一个区组轨道中任取一个区组称为基区组。容易证明循环d t s ( v ，a ) 的区 组轨道一定是长轨道。且易知循环d t s ( v ，a ) 存在的必要条件是 ( 1 ) a 三0 ( m o d3 ) 山3 ， ( 2 ) a 毫1 ，2 ( m o d3 ) 且t ，兰0 ，1 ( m o d3 ) 一个组型为矿的有向( 后，a ) 一g d d 的平行类p 是一些区组的集合，且满足x 中的每一 个点恰好包含在p 中的一个区组中。一个组型为g ”的有向( ，a ) 一g d d ( x ，g ，8 ) 称为 可分解的，如果区组集召能被划分成一些平行类r ，只的并。这样，如果一个 有向的g d d 是可分解的，那么必有v g 兰0 ( r o o d 詹) 。另外，冗一 r ，只) 称 为这个设计的一个平行类划分。一个组型为旷的可分解的有向( 七，a ) 一g d d 称为循 环可分解的，如果存在盯：i i + 1 ( r o o dv g ) 作为一个自同构，并且它保持冗的， 即一( 冗) = 冗，这里盯( 冗) = a ( p ) ：p 冗) 。这样的平行类划分冗称为循环的。 一个d b ( k ，九t ，) ( k b ) 称为几乎可分解的，若召可划分成冗l ，冗，的并，其 中忍是x z 的划分( 亿称为几乎可分解平行类) ，这里z 是x 中的某个元素。这 样一个d b ( k ，沁移) 是几乎可分解的，必有秽三1 ( r o o d 后) 。当a = 1 时的循环几乎可 分解的循环d t s ( v ，a ) 简记为循环几乎可分解的循环d t s ( 口) 从上面的定义可以看出从循环几乎可分解的循环d t s ( t ，) 得到磊上的( ，3 ，2 ) d d f 。所以一些关于循环几乎可分解的循环d t s ( 移) 的结果及构造方法都可以用 到d d f 上。 定理1 2 7 循环几乎可分解的循环d t s ( v ) h p 为乙上的( 可，3 ，2 ) d d f 。 3 已知结果 本节列出一些与不相交差族有关的一些已知结果。 我们需要下面的定义： 设g = e f + 1 为奇素数幂，设a 为g f ( q ) 的本原元，c 驴是由酽生成的g f ( 口) 的 子群，即露为g f ( g ) o ，中阶数为，指数为e 的乘法子群。令d 8 = g 分( 1 7 北京交通大学硕士学位论文 第一章绪论 i e 一1 ) 。那么我们称瞎，d “，c 掣1 为g f ( g ) 的e 次分圆类。显然他们恰好 划分g f ( q ) o 。 引理1 3 1 ( 【1 】)设g 一1 = e z 其中g 是奇素数幂，那么口= g ，a 竺1 ) 是g f ( q ) 上一个( q ( 口一1 ) e ，( q 一1 一e ) e ) - d d f 证明：显然c ：；e ) ，碰1 1 是互不相交的，并且他们恰好划分g f ( q ) o ) 。 又眯= 1 ，o l e ，0 l 钯，口( ，d ) 。) ，则 那么 c 驴= c 驴 酽一1 ，a 勉一1 ，口( ，一1 ) 。一1 ， 口= c 护 1 ，o 。，q 知，a ( f 一1 ) 8 ) a 。一1 ，a 2 e 一1 ，a ( 1 1 ) 。一1 ) = 掣，c 曲，d 生 一1 ，o 钯一1 ，a ( i 。1 ) 。一1 ) = g f ( q ) o ， 一1 ，0 1 2 e 一1 ，a ( ，一1 ) 。一1 由于口为本原元，因此对1 ，一1 ，都有a c 一1 0 ，从而 因此得 ( a 证一1 ) ( g f ( q ) o ) ) = g f ( q ) o ，1 i s ，一1 ， a d = g f ( q ) o ) q 。一l ，口知一1 ，d ( 7 1 k 一1 ) = g f ( q ) o ，g f ( q ) o ，g f ( q ) o ) 因此g f ( q ) o 中每一个元素都恰好在口中出现，一1 = ( g 一1 一e ) e 次，即口为 一个徊，( q 一1 ) e ，( q 一1 一e ) e ) 一d d f 。 z j l 理】3 2 ( 【4 j )对于任意的整数竹3 ，p 是模6 余1 的素数的乘积，存在一 个( 4 ”p ，4 ，4 ，1 ) 一c d f 。 引理1 3 3 ( 9 】)若移三l ( r o o d 2 0 ) ，t j 1 0 0 1 并且u 圣 3 2 1 ，5 0 1 ，6 2 1 ，6 8 1 ，8 0 1 ， 0 0 1 ，则存在( t ，5 ，1 ) 一c d f 。 引理1 3 4 ( 【1 】)若钉= p l 庇肼，其中每个a 三1 ( r o o d 6 ) ( i = 1 ，2 ，r ) 是 大于5 的素数，那么磊上存在( t ，3 ，2 ) 一d d f 并且历。上存在( 如，3 ，2 ) 一d d f 。 引理1 3 5 ( 1 】)若口= p 1 仡p r ，其中每仇三1 ( m o d 4 ) 0 = 1 ，2 ，r ) 是 大于等于5 的素数，那么磊上存在( 口，4 ，3 ) 一d d f 。 引理1 3 6 在z 4 上存在( 4 ，3 ，2 ) 一d d f ，在历6 上存在( 1 6 ，3 ，2 ) 一d d f 和( 1 6 ，4 ，3 ， 2 ) 一d d f 。 证明：z 4 上( 4 ，3 ，2 ) 一d d f 的基区组如下： 1 ，2 ，3 8 北京交通大学硕士学位论文 第一章绪论 z 1 6 上( 1 6 ，3 ，2 ) 一d d f 的基区组如下： t 1 ，2 ，4 ) ， 3 ，1 1 ，7 ) ， 5 ，1 2 ，1 0 ， 9 ，6 ，1 5 ) ， 1 4 ，1 3 ，8 z , 8h ( 1 6 ，4 ，3 ，2 ) 一d d f 的基区组如下： 1 ，2 ，7 ) ， 3 ，5 ，1 4 ) ，( 1 3 ，1 1 ，1 0 ) ， 1 5 ，6 ，9 ) 引理1 3 7 若口兰1 0 ( r o o d1 2 ) ，则在历上不存在( t ，3 ，2 ) 一d d f 。 证明：设口= 1 2 k + 1 0 ，若存在( 私，3 ，2 ) 一d d f ，易知每个基区组产生的奇差个 数都是4 的倍数。由于乙 o ) 中的奇数是6 k + 5 个，注意到a = 2 ，从而4 l ( 1 2 七+ 1 0 ) ， 产生矛盾。 9 北京交通大学硕士学位论文第二章关于不相交差族的一些构造方法 第二章关于不相交差族的一些构造方法 本章主要给出一些关于磊上( ，k ，k 1 ) 一d d f 的构造方法，第一节给出直接构 造方法，第二节给出其递归构造方法。最后给出由这些方法所得到对于k = 3 ，4 的 一些新的结果。 1 直接构造 本节给出磊上( t f ，k ，七一1 ) 一d d f 的几种直接构造方法。 首先可以利用循环的b ( k ，l ；v ) ( p c b ( k ，l ；”) ) 来构造磊上的( 口，k 一1 ，k 一2 ) - d d f 。事实上，c b ( k ，1 ；钟) 的存在性完全等价于( t ，k ，1 ) c d f 或者( t ，七，奄，1 ) 一c d f 的 存在性。当c b ( k ，1 ；口) 没有短轨道时，它的基区组构成一个( t ，k ，1 ) 一c d f ；当c b ( k ，1 ；t i ) 只有一个短轨道时，它的长轨道的基区组就构成一个( t ，七，k ，1 ) c d f 。 定理2 1 1 如果存在一个( 奄，1 ) 一c d f 或( t ，k ，k ，1 ) 一c d f ，那么在磊上存在 一个( 移，k 一1 ，k 一2 ) d d f 。 证明：假设，是( 口，k ，1 ) c d f 的基区组集或者( 膏，k ，1 ) c d f 的基区组集并上 区组 o ，v k ，2 v k ，( k 1 ) t ，肛 。任意b = 6 1 ，k ，令d e v b = b + z ： z 乙) = “6 1 + z ，k + $ ) ：z 磊 ，且日= u 日，d e v b ，则( 玩，8 ) 是一 个c b ( k ，1 ；t ，) 。当 兰1 ( r o o dk ( k 一1 ) ) 时c b ( k ，1 ； ) 没有短轨道；当t ，兰k ( r o o d k ( k 一1 ) ) 时c b ( k ，l ； ) 只有一个短轨道并且短轨道的形式为 o ，v k ，2 v k ，( k 一 1 ) v k 。令b ( x ) 为1 3 中包含点z 乙的扣一1 ) ( k 一1 ) 个区组。不失一般性的假 设z = 0 ，b ( o ) = b o ，日。一1 ) 其中m = 扣一1 ) ( k 一1 ) ，下面验证，= b o o ) ，b 1 o ，b 一1 o 即为( t ，奄一l ，k 一2 ) 一d d f 。 情形i t 三1 ( m o d 七( 七一1 ) ) ，此时( 磊，8 ) 没有短轨道。b ( 0 ) 恰包含了每个长 轨道中k 个区组，这样每个非零元作为差恰在b ( o ) 中出现k 次。所以b ( 0 ) 即为磊上 的( 口，七，七) 一差族，从而，= b o o ，b 1 o ) ，骂。一1 o ) ，作成历 o ) 的划 分，弗使得磊 o ) 中的每个元素作为差恰出现了七一2 次，因此，是乙上的( 口，k 一 1 ，七一2 ) - d d f 情形2 ：钉兰k ( m o dk ( k 一1 ) ) ，此时( 磊，b ) 有一个短轨道，不妨设为b o = o ，v k ，2 v k ，( k 一1 ) v l k 。由于每个v k 的倍数作为差在玩中出现k 次，而不 在其他b ( o ) 的区组中出现，因此，仍是一个玩上的( k 一1 ，后一2 ) d d f 。 利用循环的g d d 及半循环的f r a m e ，可以得到五上( 口，g ，k ，k 一1 ) 一d d f 的一个 新构造。 定理2 1 2 假设存在一个组型为矿的k - c g d d ，并且对任意k k 存在一个 半循环的( h k ，h ，k 一1 ) 一f r a m e ，那么在磊肼上存在一个( h g n ，h 9 ，1 4 ，d - 1 ) 一d d f 。 北京交通大学硕士学位论文第二章关于不相交差族的一些构造方法 证明：假设，是组型为9 ，的k - c g d d 的基区组集，b = 6 1 ，b 2 ，k ) 是，中 的任意一个基区组。由假设在bx 磊上存在一个半循环的( h k ，h ，一1 ) 一f r a m e ， 它的部分平行类由忍。( b ) ，风。( b ) ，风。( b ) 生成，其中风。( b ) 做成 玩) ) x 磊的划分。用( 6 霉一6 ) + y g n ( r o o d 弘) 来代替；( b ) 的区组中的元素( k ，y ) ，其 中玩，k b ，! ，磊由此得到区组集a 。( b ) 。当b 取遍尸中的元素并且6 取遍b 中 的元素时，得到区组集a = u 日k 印a 。( b ) 。下面证明a 即为( 咖，h g ，一1 ) 一 d d f 。注意到z 雪n o ，住，( 的一1 ) 礼) 的每个元素z 可以写成z = q g n + r ( o g h 一1 ，1 r q n 一1 ) 的形式。对任意的y z h ，当b 遍历，中的所有区组，b i 遍 历口中的元素时，k 一玩遍历z 矗 o ，n ，0 1 ) 竹) 中的所有元素。当! ，取遍磊中的 所有元素时，4 遍历磊卵 o ，n ，( 的一1 n 且4 是。 o ，( 幻一0 - 的 一个划分。由于黾( b ) ，风。( b ) ，风。( b ) 是半循环的( h k ，h ，一1 ) 一f r a m e 的 平行类，所以对于任意两个元素k 。，6 b b ，它们的混差0 一歹：( k 。， ) ，( k 。，歹) b 是( 一1 ) z h ，即磊中的每个元素恰出现一1 次，于是一4 = ( 一1 ) ( 磊哪 o ，n ，( h g 一1 ) 竹) ) ，即( 磊非 o ，n ，( h g - 1 ) n ) 中的每个元素作为差出现_ j c ，一 1 次。 由于乙上的一个( h n ，h ，k ，k - 1 ) d d f 也是一个半循环的( h n ，h ，k ，k - 1 ) 一f r a m e ，所以有下面的推论。 推论2 1 3 假设存在一个组型为g n 的k - c g d d ，并且对任意的k k 在上 存在一个( h k ，h ，一1 ) d d f ，那么在磊。上存在一个( h g n ，h g ，一1 ) - d d f 当p 兰5 ( r o o d1 2 ) 为素数时，z 品上的( 5 p ，3 ，2 ) 一d d f 有一种特殊的构造方法。 设p 兰5 ( r o o d1 2 ) 是素数，e 是名上的4 次本原单位根，则日= - t - 1 ，士e ) 为召 乘法群的子群。假设厂是一个( 名，h u 0 ，3 ，2 ) 一d d f ，若u b 盯b = z p ( 日u o ) ) ， 且f = 2 ( 名( h u o ，) ) ，则称，为好的不相交差族。 定理2 1 4设p = 1 2 n + 5 是一个大于5 的素数。如果乙上存在一个好的p ，5 ，3 ， 2 ) 一d d f ，那么在z 岛上存在一个( 5 p ，3 ，2 ) 一d d f 。 证明：磊p 竺磊。名，e 是磊上的4 次本原单位根，并且设a = a 1 ，a 。 = 4 n ) 是一个好的( 名，hu o ，3 ，2 ) 一d d f ，其中日= 士1 ，士e ) 对每一个，= l ，m ，设山= o ，a 1 ，唧2 ) ，考虑磊。乙上的区组集：8 = 嘞： i = 0 ，1 ，2 ，3 ；j = 1 ，m ，其中 b = ( 2 ，o ) ，( 岔+ 1 ，q 1 ) ，( 岔+ ，2 ) ) ，i = 0 ，1 ，2 ，3 ；j = 1 ，2 ，m 。 则8 中区组所产生的差 a b = 2 ( 名( 露仕1 ，士e ) ) ) 。 令 c i = ( 1 ，) ，( 1 ，- 1 ) ，( 3 ，o ) ) ，c = ( 4 ，一e ) ，( 4 ，1 ) ，( 2 ，o ) ， 北京交通大学硕士学位论文第二章关于不相交差族的一些构造方法 g = ( 2 ，0 ，( 2 ，1 ) ，( 1 ，o ) ) ，q = ( 3 ，- e ) ，( 3 ，- 1 ) ，( 4 ，o ) ， d l = ( 1 ，1 ) ，( 3 ，1 ) ，( 0 ，+ 1 ) ) ，d 2 = ( 2 ，- x ) ，( 4 ，- 1 ) ，( 0 ，- - e 一1 ) ， d 3 = ( 3 ，) ，( 4 ，0 ，( 0 ，一1 ) ) ，d 4 = ( 1 ，一e ) ，( 2 ，- e ) ，( 0 ，1 一) 令c = a ，g ，伤，q ) ， 口= d l ，d 2 ，d s ，d 4 由予g 是个4 次本原单位根，所以有s 一1 = s ( + 1 ) 。 易验证c 与口中区组产生的差 a c u d = 2 ( ( 召x o ，士1 ，士) ) u ( o ) x 士g + 1 ) ，士e p + 1 ) ) ) ) a 最后考虑彳= a i ，厶) 其中4 = o ) g + 1 ) 如，歹= 1 ，m 。 显然： 爿= 2 ( o ) (