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

北京交通大学硕士学位论文 中文摘要 中文摘要 摘要：差族是一类组合设计，是差集概念的自然推广。差族方法是构作b i b 设计 最常用也是最有效的方法之一，关于差族的详细介绍请参考 1 3 j 。设( g ，+ ) 是t ，阶 的a b e l 群，日是群g 的g 阶子群。又设，= 且： ， 是g 的一些后元子集构成 的子集族。对任意b g ，记b = 口一6 ：n ，6 b ，o 6 ，= u j 鼠， 若，= a ( g 日) ( 其中a ( g 日) 表示包含g 日中的任一元素恰好a 次的多重集) ， 则称，是一个( g ，e 七 a ) 一差族( 或( g ，e 七，a ) 一d f ) ，最称为基区组。当夕= 1 时，简 记为( g ，七，a ) 一d f 。 本文主要考虑的是：g 上的( g ，日，七，”一差族的基区组互不相交的情况( 即g 上 的( g ，e 七，a ) 一不相交差族) 进一步我们要求g 为忍，日= o ) ，a = 蠡一1 ，此时 为乙上的( t ，后，七一1 ) d d f 。我们主要研究在这种情况下( 其中詹= 3 ，4 ) 的不相交 差族存在的充分条件。在这种条件下的不相交的差族与许多设计都有密切的关系， 例如：外部差族，、帕i 8 t 竞赛设计，完备基以及循环几乎可分解的循环的d t s 。 本文共分两章 第一章中综述了本篇文章主要要用的基本概念，不相交的差族与其他设计的 关系，以及前人给出的关于不相交差族的初步结果。 第二章中给出了不相交差族的几种直接构造方法和递归构造方法，最后给出 了一些新的结果。 我们首先利用( 口，后，1 ) c d f 或( 材，七，七，1 ) 一c d f 得到磊上一个( t j ，七一1 ，七一2 ) 一 d d f 。 然后利用循环的g d d 及半循环的f r 锄e ，得到乙上( t ，9 ，七，七一1 ) 一d d f 的一个 新构造。 最后给出当p 兰5 ( m o d1 2 ) 为素数时，z 岛上的( 劬，3 ，2 ) 一d d f 的一种特殊构造 方法。 关键词：不相交的差族( d d f ) ；循环差族( c d f ) ；半循环的矗锄e ；循环几乎可 分解；差阵 分类号：0 1 5 7 2 北京交通大学硕士学位论文 a b s t r a c t a b s t a c t ：d 证e r 凹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 ti 8a g e r d 沱a t i o no fd i 任矗e n c e8 e t d i 丑e r e n c em e t h o di so n eo f 七h em tu 辩f l l l 蚰d 硪t i v ef b rc 伽眦n l c t i n gc o m b i n 删a ld 鹤i g n0 fm 龇l yt y p e 8 r ) rm o r ei n f o m 跏 t i 呲衄删f e r e n c e 胁n i l y ，t h e 溉i d e ri 8r e f e h e dt o 【l3 】l e t ( g ，+ ) b e 锄a b e h 蛐 f o u po fo r d e r t ，蚰d 日a 舳b 伊o u p0 f g w i t h 夕d 印1 e n t a ( g ，e 七，a ) 代缸挽钟 啦如他n 舡m i 细( o r ( g ，日，七，a ) - d fi n8 h o r t ) i 8ac 0 札e c t i o n ，= 最：i j o f 舡s u t 8 ( c a l l e d6 e6 奴妇) o f gw i t ht h ep r o p e r 锣t h a ti t sl 斌o fd i 丘j r e n 啷 ，= u j 晟i 8at i 艄g 日w h e r e 晟= 扣一6 ：d ，6 最，口6 ) ht h e c 够et h a t9 = l ，w e8 i i n p l yc a l li ta ( g ，日，a ) 一d f ( o r ( t ，七，a ) d fo v e rg ) i i lt h j 8a r t i c l e ，w em a i l l l yc 0 璐i d 盱t h ef o 】姗gc 嗍：t h eb a b l o c k0 f ( g ，e a ) - d fi ng 唧p a i 邢i 8 ed 蠲。砒i i l 叫i c u l a rg = 磊，日= o ，a = 七一1 ，( g ，甄七，a ) 一d d fi 8d e n o t e db y ( t ，七，詹一1 ) 一d d fi n 乙w jm a i l 衄8 t u d y t h es u 伍c i e n tc o n d i t i 衄0 f ( 口，七，七一1 ) - d d fi n 磊，五叫七= 3 ，4 d 埘o i n td i 髓聆n c e f a m i l i 凹8 r er e l a t e d 丽t hm 锄yl 【i n d bo fc o n l ) i l l a t o r i a ld 髑i 昏培s u c h 鹪印c t e r n a i d 诳打e n c ef 甜n n i e s ，w l l i s 七t o 啪锄e n t ，c y c h c a l l ya l m o s tr e 量讪l eq ，c h cd i r e c t e d t r i p l es y s t e m s 衄dp e r f 酏tb a s 鹤 i l h e r ea r et w o 出a p t e r si nt h et h 稍i s ： n e 缸s tc h a p t 盯i n t r o d u c e 8t h eb 硒i cd 硪n i t i ，t h er e l a t i o nb e 抑e e nd i 8 j o i n t d i 仃打e n c ef 锄i u e 8 姐do t h e rd e 8 i 目碱a n d8 0 m ek n o w nr 鹤l l l t s i i lt h e8 e o o n dc h a p t e r ，w e 硝np r 圈t8 0 m en e wc o n s t r u c t i o n 8 锄dr e c u r s i v e c o n s t r u c t i o 琳o fd d f s ，i nt h el a 8 七w e 尽e t 跏en e wr 鹤t 1 1 t 8 f i r s t l y ，聊o o 璐t n l c 七a ( 移，詹一1 ，七一2 ) 一d d fi n 磊t h r o u 曲( 口，七，1 ) 一c d f0 r ( 秽，七，七，1 ) 一c d f s e c o n d l y ，w e u c y c l i c g d d 锄d 蚴i - c y c h c 矗锄e t og e t a ( t ，玑七，七一1 ) 一d d f i n 乙 f i n a l l mw e 西v eas p e c i a lo o m t m c t i d no f ( 5 p ，3 ，2 ) 一d d fi ni 碲，w h e np 三 5 ( m o d l 2 ) i 8ap r i m e k e l y 幻r d s ：d 蝎o i n td i 脓e n c e 坶( d d f ) ；c y c l i cr e l a t i v ed i 胁e n c e 缸小 丑y ( c d f ) ；m i - c y c h c 在锄e ；呵c u c 枷ya l h l o s tr e s o l v e b k ；d i f f 矗e n c em a t 】淑 c l a s s n o ：0 1 5 7 2 北京交通大学硕士学位论文 第一章绪论 l 基本概念 第一章绪论 设( g ，+ ) 是钉阶的a b d 群，日是群g 的g 阶子群。又设，= 最：i n 是g 的一 些七元子集构成的子集族。对任意b g ，记b = 口一6 ：n ，6 b ，n 6 ，= u ；，鼠，若，= a ( g 日) ( 其中a ( g 日) 表示包含g 日中的任一元素恰好a 次的 多重集) ，则称乃黾一个( g ，e 七，a ) 一差族( 或( g ，日，七，a ) 一d f ) ，鼠称为基区组。当g = 1 时，简记为( g ，日，”一d f ( 或者g 上的( t ，七，a ) d f ) 。显然( g ，日，七，a ) d f 存在的必 要条件为a ( i gj 1 日i ) 三o ( m o d ( 后伪一1 ) ) ) 。当g 是循环群磊时，日是磊的夕阶 子群，则日一( t ，加) 乙= o ，u 9 ，2 吼，0 一1 ) t ，办，这时( 乙，扣居) 磊，k a ) 差族称为( ，玑七，a ) - 循环差族，记为( t ，吼七，a ) - c d f 在【2 】中( t j ，g ，七，a ) - c d f 被称 为( t ，口，七，a ) 一d f ，在【8 】中它也被称为9 啪r q c 娩妒蜘c p ( 七，1 ；t ，) 。 设( g ，+ ) 是 阶的a b e l 群，日是群g 的g 阶子群。设芦= 最：i n 是一 个( g ，e 七，a ) 差族，如果它满足下面两个条件：( 1 ) 理的基区组互不相交；( 2 ) u j 最冬g 日，这时芦称为不相交的差族，记为( g ，日，七，a ) 一d d f 或( a b e l 群g 上 的( t ，g ，七，a ) - d d f ) 。当9 = l 或日= o 时，记为( g ，a ) d d f ( 或g 上的( t ，七，a ) 一 d d f ) 当a = 七一1 时，不相交的差族，= 恳：l n 恰是g 日的一个划分，从 而g 上( 秽，g ，詹，七一1 ) 一d d f 存在的必要条件是t ，兰9 ( m o d 七) 设 五，死，五 是一个( g ，七，a ) d d f 的集合，其中每一个乃( 1 t 8 ) 都 是一个( g ，七，a ) 一d d f ，如果u ：1 ( u b 矗b ) 构成g o ，那么称 五，焉，兀) 为 不相交差族的一个完全集，记为( g ，七，a ) 一c d d f 。显然， b ：b u ：1 乃) 组成 一个( g ，ks a ) 一d d f ，并且( g ，a ) 一c d d f 中含( g ，后，a ) 一d d f 的个数为( 七一1 ) n 。 当8 = l ( 即a = 七一1 ) ，一个( g ，七，a ) c d d f 恰为一个( g ，七，a ) 一d d f 。刑0 h a r a 等人在 3 】中给出了( g ，七，a ) c d d f 的递归够造方法，从而我们也得到了一些 关于( g ，七，a ) d d f 的一些递归构造方法。这些构造方法我们将在第二章的第二节 介绍。 下面介绍与循环差族和不相交的差族密切相关的两个概念：循环可分组设计 与半循环的丹a l e 。 可分组设计( g d d ) 是一个满足下面条件的三元组( 五9 ，8 ) ： ( 1 ) g 是集合x ( x 中的元素叫点) 的一个划分，9 中的元素叫做组； ( 2 ) 8 是x 的子集的集合( 日中的元素叫区组) ，并且每个组和每个区组至多交于一 个点； ( 3 ) 每一对来自不同组的点恰包含在a 个区组中。 1 北京交遥大学硕士学位论文第一章绪论 常用指数形式来描述一个g d d 的组型：组型t f - t 静表示在9 中有他个如长 的组，1 i m 。区组长度取自集合的g d d 记为( ，a ) g d d 。当k = 砖时，简 记为( 七，a ) 一g d d 。当a = 1 简记为k g d d 。组型为1 ”的肛g d d 即为参数为( 七，1 ) 的 平衡不完全区组设计( b ，b d ) ，记为b ( 七，1 ： ) 。 设( 五g ，舀) 是一个g d d ，盯是x 上的一个置换。对于任意集合s = z l ， x ，定义口( s ) ； 盯( z ) ，盯( z ) ) ，如果有盯( 9 ) = 盯( g ) ：g 9 = 9 并 且盯( 嚣) = p ( 口) ：b b = b 成立，那么盯称为g d d 的一个自同构。任意自同 构盯把召分成若干个等价类，每个等价类叫嚣在盯下的轨道。每个轨道取出一个区 组代表叫做此g d d 的基区组。一个g d d 称为是循环的，如果它有一个自同构包含 一个长为”；i x i 的圈，这时可以把x 看成乙并取口：i t + 1 ( m o dt ，) 。我们 用( ka ) c g d d 来表示轨道都为长轨道的循环的g d d 。 设，- 黾一个( 9 ，七，a ) 一c d f ，则，可以产生一个组型为9 ”0 = 卵) 的( 后，a ) 一 c g d d 。其中组集9 一 ( v 9 ) 乙+ ：osi 1 7 ，如果口丁那么 存在t ( 钉) 。 5 北京交通大学硕士学位论文第一章绪论 2 3 不相交差族与完备基的关系 设g 是t ，= 觎+ 1 阶a b e l 群，完备基p b ( 口) 定义为：集合 s = 戤l ，戤2 ，z t 3 ：1 l t ) g ，1s i t ，1 s 歹3 ，且满足如下性质： ( 1 ) ：士z 巧，1 i t ，l j 3 ，互不相同； ( 2 ) ：士( 戤2 - n ) ，士( 铂一论) ，士( 戤1 一订) ，1 i t ，互不相同。 由p b ( v ) 定义可知： 仕i1 i t ，1s j 3 zg o ) ； 仕( 以2 - 1 ) ，士( 一记) ，士( 戤1 3 ) l1 ist = g o ) 由此可知，p b ( 钉) 为g 上一个( 口，3 ，1 ) 一d d f ，从而su s 即g 上一个( t ，3 ，2 ) 一d d f ， 但是反之不一定成立。所以我们有下面的定理成立： 定理1 2 ba b e l i 弹g 上的p b ( t ，) 为g 上的扣，3 ，1 ) d d f ，进而我们可以得到g 上 的( 口，3 ，2 ) 一d d f 。 例如：g = 历5 ，s = 1 ，2 ，1 0 ， 3 ，1 3 ，1 7 ) ， 4 ，6 ，9 ) ， 5 ，1 1 1 8 ) ) ，则s 为p b ( 2 5 ) 而 s u s = 1 ，2 ，1 0 ) ，t 3 ，1 3 ，1 7 ， 4 ，6 ，9 ， 5 ，1 1 ，1 8 ， 2 4 ，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 ( m o d6 ) ，存 在p b ( 口) 。 2 4 不相交差族与循环几乎可分解的循环有向三元系的关系 设口，屯a ，g 为任意正整数。集合 ( 啦，q ) ：1 i - d d f 逶绢；显然瑶时。，毯笔是嚣零穗交熬，势麓谴翻猞好麓分g f 渤 o 。 又醯一 1 ，矿，o 缸，a ( ，- 1 ) 。 ，贝i j 那么 瞎) 一毋) 一l ，矿一l ，8 ( ，一1 ) 。一l ， 口篇c 1 ，扩，口2 e ，n ( ，一1 ) 6 n 。一1 ，a 2 e 一1 ，a ( ，一1 ) 。一1 ) 一t 醇，e ，c ：2 一l ，a 勉一l ，a ，一1 k l 一g 尹( 霉) o 。 一l ，铲一l ，a ，一蜘一l 由于n 为本原元，因此对1 i ，一l ，都有。缸一l 0 ，从而 因此得 ( 铲一1 ) 搿，鸯、 镑) = g f ( 0 8 ，l l s 歹一l ， 口一g f ( d o t 一l ，铲一l ，a ( ，一1 一l = 秽f ( 鸯 o ，g f ( 藓 o ，g f ( 鼋) 田 因此g f ( 口) o 中每一个元素都恰好在口中出现，一1 = 0 1 一e ) e 次，即移为 一个q ，国一1 ) e ，妇一l e ) e ) - d d f 雩l 璞1 3 2 阖)辩子任意熬熬数托芝3 ，弘楚模6 佘l 静素数静乘积，存撵一 个( 妒p ，4 ，4 ，1 ) - c d f 。 引理1 3 3 ( 9 】)若甜考l ( m o d2 0 ) 。移1 0 0 l 并且”譬 3 2 l ，5 0 1 ，6 2 1 ，6 8 l ，8 0 l ， l ，煲4 蠢在( 蛰，5 ，1 ) 一g d 乳 引理1 3 4 ( 【l 】) 鼋釉= p 1 弛秘，其中每个张章l ( m o d 6 ) 0 = l ，2 ，r ) 是 大于5 的素数，那么蜀上存在( t ，3 ，2 ) 一d d f 并且2 0 上存在( 4 移，3 ，2 ) 一d d f 。 弓l 理l + 3 。5 ( 【l 】)装封= 死纯秘，其中每l 堍兰l ( m o d 4 ) 0 = l ，2 ，r ) 是 大子等予5 豹素数，那么磊主存在讧4 ，3 徊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 1 一d d f 证甓：磊上肇，毒2 ) 一d d f 夔基送缀舞下： l ，2 ，簿， 8 北京交通大学硕士学位论文第一章绪论 五6 上( 1 6 ，3 ，2 ) 一d d f 的基区组如下： 1 ，2 ，4 ) ， 3 ，1 1 ，7 ) ， 5 ，1 2 ，1 0 ) ， 9 ，6 ，1 5 ) ， 1 4 ，1 3 ，8 历8 上( 1 6 ，4 ，3 ，2 ) 一d d f 的基区组如下； 1 ，2 ，7 ) ， 3 ，5 ，1 4 ) ，t 1 3 ，1 1 ，1 0 ， 1 5 ，6 ，9 ) 引理1 3 7 若t ，三1 0 ( m o d1 2 ) ，则在磊上不存在( ，3 ，2 ) d d f 。 证明：设t ，= 1 2 七十1 0 ，若存在( t ，3 ，2 ) 一d d f ，易知每个基区组产生的奇差个 数都是4 的倍数。由于乙 o 中的奇数是6 七+ 5 个，注意到a = 2 ，从而4 i ( 1 2 七+ 1 0 ) ， 产生矛盾。 9 托家交通文学硬士学位论文第= 章关于不籀交菠族的一些擒造方法 第二章关于不相交差族的一些构造方法 本章燕要给出一些必于乙上( 虬概七一1 ) - d df 豹构造方法，第一节给出戴接构 造方法，第二节给出其递归构造方法。最后给出融i 塞些方法所得到对于七= 3 ，4 的 一些耨的结果。 l 直接构造 本帮绘逝瓦上，兢露一1 ) _ d d f 黪尼秘壹接捻适方法。 首先可以利用循环的口( 奄，l ；分) ( 帮c 君( 老，l ；计) ) 来构造氨土豹( 钉，老一l ，奄一2 ) 一 d d f 。事裳上，c 四( 1 ；t ，) 的存在性党全等价于( 口，知，1 ) 一c d f 或者( 甜，屉，七，1 ) 一a d f 的 存在性。当g b ( 七，1 ；t ，) 没有短轨道时，它的基区组构成一个扣，职1 ) - c d f ；当嚣( 蠹，l 潮哭夸一令短辘遘辩，宅懿长孰邀瓣基区缝藏稳姣一令如，瓠1 ) d f 。 定璎2 1 1 如果存在一个( 弘氓1 ) 一c d f 或( 虬觏后，1 ) 一c d f 。那么在磊上存在 一个扣，七一l ，七一2 ) 一d d f 。 证骥；假设绳( 双1 ) c d f 戆熬区维集或者( 暂，蠡，惫，l w d f 懿基区缀集势上 区缝 o ，钉加，勃绛，抟一1 ) 分锺 。经意丑一 6 l ，颤) ，_ ，令d 盼丑= 嚣十z ： z 磊) 一 6 l + 为，k + z ：茹仨z ； ，且心一u b ，d e v 廖，贝0 ( 磊，8 ) 是一 个e b ( 颤l ；静) 当口兰l ( m o d 七( 詹一1 ) ) 时e b ( 1 ；静) 没有短轨邋；当t ，兰蠡( m o d 惫溶一1 ) ) 懿丑魄l ；影) 必毒一个短较遴劳显短筑遴瓣影式兔 8 ，形氟勃必，锤一 l 弘绣 。令b 扛) 为8 中包含点z 氨的0 一1 ) 一1 ) 个区组。不失一般性的假 设z = o ，届( o ) = 岛，b 。一1 ) 其中m = 扣一1 ) 一1 ) ，下面验证，= 糯 o ，b 1 o ，b 。一l o ) 即为( ，惫一l ，七一2 ) 一d d f 情形l ；移兰l ( m 聪露辑一l ；) ，魏瓣磊，艿) 没露短孰遂。露( ) 埝包含了每令长 轨道中奄个区组，这样每个非零元作为差恰在b ( o ) 中出现七次。所以b ( 0 ) 即为磊上 的( 口，詹，格) 一麓族，从而一 玩 o ，脯 o ) ，骗；一t o ) ) ，作成磊 o ) 的划 分，并使得磊 o 中的每个元素 筝鸯差恰出现了奄一2 次，嚣北是磊上的( 是一 l ，是一2 ) 一羚d f 。 情形2 ：钉兰七( m o d 后 一1 ) ) ，此时( 磊，8 ) 有一个短轨邋，不妨设为硒= o ， 后，2 盯惫，佧一1 ) t 肛) 。由于每个u 肛的倍数作为差在风中出现七次，褥不 在其德君( o ) 鸵区维孛爨瑷，因j 迦，爨爨一令磊上戆溉蠢一l ，奄一2 ) d 。 利用循环的g d d 及毕循环的矗a 的特，可以得到氛上( v ，9 ，奄，船一1 ) d d f 酌一个 新构造。 定瑾2 。1 2 假设存在一个组型必扩斡尽c g d d ，著显对任意奄足存在一个 拳簇环豹( 是，矗，影1 ) 一赶砌e ，那么农磊土存农一个( 幻珏，的，一1 ) 一d d 轧 北京交通太学硕士学位论文第二章关于不稿交簇族的一些构逡方法 迸明：假设芦是缎溅为矿的j o a g d d 鲍基区缀集，暑= 颤，颤。，颤 怒芦中 鹃任意一个基区组。赉骰竣在君x 兹上存在一个攀循琢懿潦，矗，一1 ) 浓蝴e ， 它的部分平行类由风。( 廖) ，风：( b ) ，忍。( 司生成，其中黾( 嚣) 做成( b 趣) ) 磊的划分用慨一6 ) 十g ，妒( m o d 坳) 来代替岛。( b ) 的区组中的元素( k ，暑) ，其 中矗 ，露，爹承由鼗褥到区组集氐( 谚。当嚣取速芦申豹元素劳且趣取遮露孛 的元素辩，得蓟区组集一u 口。， 嚣氏( 动。下瑟证弱酃为( 蠢妒，幻，舻，一1 ) 一 d d f 。注意到z 蕊 o ，竹，( 幻一1 ) 礼) 的每个元素厕以写成g q _ 卵+ r ( o q _ j l l ，1 f 一1 ) 的形式。对任意的掣磊，当日遍历刀中的所有区组，如遍 爨君孛熬惩素肄，& 一荻邃蘑z 未 o ，拜。，殛一1 ) 摊 孛豹囊毒元素。墨擎取遍兹孛兹 所有元素时，遍历磊辨 o ，n ，( 的一1 ) 孔) 且是历缈 o ，挑，( 细一1 ) 竹 的 一个划分。由于风。( b ) ，忍。( b ) ，硒。( b ) 是半循环的( 珧，k ，f 一1 ) 椭黼e 的 平行类，所以对于任意蹰个元素蚝，b ，它们的混差0 一j ：( 6 l l ，曲，( 6 ；魄，j ) 至唾是秽一1 ) 磊，帮氙巾夔每令元素埝窭瑗彭一1 次，于是蠢一拶一1 ) f 筋 辨、 o ，椎，( 幻一1 ) n ) ) ，即( 磊。 o ，m ，( 姆一1 ) 扎) 中的每个元素作为差出现矽一 1 次。 由予磊上雏一个( 矗勉惫，奄一1 ) 一d d f 也是一个半循环的( 矗矗，是，露一1 ) _ 趣8 m e ，掰戳有下嚣静箍论。 推论2 1 3 假设存在一个组型为旷的髟，c g d d ，并且对任激的南蜀在玩上 存在一个( j l ，一1 ) 一d d f ，那么在磊。上存程一个( 咖，姆，f ，一1 ) - d d f 。 堂嫩5 ( 氆醒1 2 ) 为素数嚣，走懿( 5 热3 ，2 ) 一d 骞一静将臻戆搀造方法。 设p 赫5 ( m o d1 2 ) 鼹素数，e 是荪上的4 次本原单位根，则脬= 士1 ，士s 为忍 乘法群的予群a 假设，怒一个( z p ，日u o ) ，3 ，2 ) d d f ，若u 且矿嚣一磊( 日u o ) ) ， 且，= 2 ( 磊暇u o ) ) ，剐称芦为好的不相交麓族。 定遴2 1 4 设p 1 2 珏+ 5 是一个太子5 的素数。如果磊上存在一个好的，5 ，3 ， 2 ) 一d d f ，那么在上存在一个( 劬，3 ，2 ) 一d d f 。 证明：蜀审笺z 5 0 磊，e 是名上的4 次本原单饺根，并且设一瘴= a l ，a 。 ( m = 4 嚣) 跫一令磐豹( 磊，露u ，3 ，2 p d f ，其串蟊= 圭l ，觳 。对每一今j = 1 ，m ，设a = n _ m 吩l ，吩2 ) ，考虑z 5 0 磊上的区组集：8 一 嘞： ； o ，1 ，2 ，3 ；歹= l ，m ) ，熊中 = 船，铷) ，( 妒1 ，雩1 ) ，( 伊2 ，2 ) ，一o ，l ，2 ，3 ；歹一l ，2 。，獬 刘牲巾区组所产生豹羞 a 尽= 2 ( 露( 露 士1 ，生s ) ) ) 。 令 q = ( 1 ，) ，( 1 ，一1 ) ，( 3 ，o ) ，e ；一 ( 4 ，一0 ，( 4 ，1 ) ，( 2 ，o 强， 北京交遥犬学硕士学位论义第二鬻关于不相交麓族的一些构造方法 舔= ( 2 ，) ，( 2 ，1 ) ，( 1 ，o ) ，馥一 ( 3 ，一) ，( 3 ，一1 ) ，氍，o ) ， z ) l = ( 1 ，1 ) ，( 3 ，l x 徊，s + 1 ) ，d 2 = ( 2 ，一1 ) ，( 4 ，一1 ) ，( o ，i ) ) ， d 3 = ( 3 ，0 ，( 4 ，s ) ，( o ，e 一1 ) td t = ( 1 ，一g ) ，( 2 ，一苎) ，( o ，1 一) ) 令e = g ，晓，瓯q ，口= 热，逸，现，玖 由予尊是令4 次本灏辇位糇，所黻有一l = + 1 ) 。 易验诫c 与d 中区缀产生的差 a e u d 一2 ( ( 露 o ，士l ，士) ) u ( o 圭每+ 1 ) ，如( + 1 ) ) 最爱考虑= 墨，疋 其巾= o 嵇+ 1 ) 岛，j l ，。，m 。 显然：爿一2 ( o ) ( z 仕0 + 1 ) ，虹忙+ 1 ) ，) ) 所以序u c u d u “? = 2 “旎。名) ( o ，o ) ，因此彳u 召u c u 抄怒一 个( 劫，2 ) 一d 船。 引理2 1 5 对于p 1 7 ，2 9 ，4 1 ，5 3 ，在z 茹上存在( 5 p ，3 ，2 卜d d f 证明：对于p = 1 7 ，2 9 ，4 1 ，5 3 时，存在好的如5 ，3 ，2 ) 一d d f ，其基区组如下# p = 1 7 2 ，5 ，l l ， 3 ，8 ，l o ， l 毛1 2 ，6 ， l 矗，或7 p = = 2 9 2 ，4 ，8 ) ， 1 4 ，1 9 ，9 ， 2 7 ，2 5 ，2 1 ) ， 5 ，1 0 ，2 0 ， 1 6 ，3 2 3 ) ， 1 8 ，7 ，1 5 ， 1 3 ，2 6 ，6 ) ， 1 1 ，2 2 ，1 4 ) ，一毒l 6 ，4 ， ， 2 8 ，5 ，1 7 ， 3 5 ，嚣，l l ， 1 3 ，3 6 ，2 唾 ， 1 6 ，3 2 3 ， 2 0 ，1 4 ，3 9 ， 2 5 ，3 8 ，1 8 ， 2 l ，2 7 ，2 ) ， 1 5 ，1 0 ，7 | ， 2 9 ，3 3 ，1 9 ， 2 6 ，3 1 ，3 4 ， 1 2 ，8 ，2 2 p 一5 3 2 ，4 ，8 ， 7 ，1 4 ，2 8 ， 5 l ，4 9 ，4 5 ， 4 6 ，3 9 ，2 磅， 1 6 ，3 2 ，4 2 ， 3 ，6 ，4 l ， 3 7 ，2 l ，l l ， 5 0 4 7 ，1 2 ， 2 2 ，“，l o ， 2 4 ，4 8 ，3 5 ) ， 3 1 ，9 ，4 3 ， 2 9 ，5 ，1 8 ) ， 1 7 ，3 4 ，2 6 ， 3 6 ，1 9 ，2 7 ， 2 5 ，3 8 ，1 8 ， 2 0 ，4 0 ，1 5 。 垂定理2 1 ，4 得到磊，上麓( 5 弘3 ，2 ) 一d d 款 2 递归构造 先介绣凡个在递鹅孛鼋造中要羯羁静关于循环装族( c d f ) 靛结果： 引理2 2 1 ( 【8 】)如果存在一个( 材，m ，七，1 ) 一c d f 和一个( m ，鼽k1 ) 一c d f ，那么 存在一个( ，幽七，1 ) 一c d f 。 弓l 瑾2 2 。2 霹 壬熬整数嚣3 ，存在一令( 铲，莲，硅，l 曰f 。 就京交通犬学硕士学莅论文第二掌关于不耱交麓族的一些构造方法 证明；由粥，对鼹意整数，l 3 存在一个( 2 州2 - i ，4 ，1 ) 一c i d f ，反复威瘸弓l 理2 。2 1 ，弼褥铲，4 ，4 ，1 ) 一e 。 前面我们给出了d d f 与其它设计的关系以及赢接构造，在本节中我们利用不 完全的差阵给出了a b e l 群g 上( 钞，凫，七一1 ) d d f 的递归构造，下颥我们给出如下的 寒语； 设( 礴+ ) 是一个计的a b e l 群，嚣怒g 的 阶予群，一个( g ，职a ) 一不完全的差 阵( 或者( a 鼠七，a ) - i d m ) 是一个七如一 ) a 的距阵d = ( 奶) ，o is 七一l ， l j a p 一砷( 奶研，使褥对任意的o i d d f ) 则存在( g l og 2 ，皿国g 2 ，知，七一1 ) 一d d f ( 或( g 1 0g 2 ，g 1 0 娲，詹，七一1 ) m d f ) 。 连臻；鬏设鼹谚，嚣l ，蠡，蠢一1 ) 国戆基嚣缀集。由定义我稻毒0 学骞= g 1 嚣1 并且u 丑e ，b 一 一1 ) ( 酝塌) 设d 一( 奶) 是一个( g 2 ，王己，七+ 1 ，1 ) i d m ，其中对于ogi 曼七，lsjs l ( b l l 点岛 蠢电g 2 。我们注意到对予菜行或者莱到的所有元素都加上同一令数 葬雩，差辫瓣性爱祭跨不变，掰墩我稻苓失一般经豹霰设差阵移鹣第一行豹掰露元 素为o 。那么对于1 事j 知，我们得到 如一勘：1 lsl g 2 卜i 飓| = g 2 编， 莠曼 幽：l s l g | g 2 | - l 玩| 一伤玛 设d g l o g 2 且城一凰o g 2 ( 或者巩= g 1 国飓) 由假设( 3 ) ，设c 是( 骗，风 e 愿，毛毫一1 ) i d l ) f ( 或嚣( 玩，噩e 点酝麓奄一1 ) d 豹暇) 。下面我们构造( g ，玩，惫一 1 ) 国d f ( 躐者( g ，玩，蠹一1 ) 一d d f ) ； 对予每一个基区组露= 6 l ，6 2 ，k 我们定义i 岛l 1 日2j 个区组# 易= ( 玩，南) ：l 黑知 其孛歹一l 。，| 锈| 一| 玛| ，运舞怒g 孛戆熬法运算。集合 g = 岛：曰s ，1 j l g 2 i 1 日j i u c 显然，是g 巩( 或者g 既) 的划分。很容易得到基区组襞所产生的箍恰 努是g 辗( 或者g 编) 中每令元豢瓣惫一1 次。 引理2 2 7 ( f 1 】)设钞和仇是正整数，假设磊上存在一个( 幽概詹一1 归d f ，z 矗 上存在一个( m ，七+ 1 ，1 ) 一g d m ，那么猩上存在一个( 铆l ，9 m ，知，麻一1 ) d d f ，进 一步如果上有一个( 秽蠡，蠡一1 ) 一d d f ，那么就露在一个( 管 善，鸯，岛一1 ) 一d d l f 。 证臻：设，是蜀土扣，乳老，垂一1 ) 一d d f 静基送维集。困既窍u 舵芦暑一忍 ( 口夕) 磊和u 日。，曰= ( 船一1 ) ( 磊( u 妒) 磊) 。设d 一( 奶) 是z 。上一个( m ，七十1 ，1 ) 一 c d m ，其中对于o i 詹，l sm 有如z 囊。失一般性的假设差阵d 的第一 孬斡麝有嚣索兔o 。那么黠予lsi 歹蠢，我弱褥羽 呶一而l ：1 蒸z s m = 五。， 并且 妇：l l m = z m t 现在我髓祷造磊聊土麓( 姗，箩m ，蠢，蠢一1 ) 一d d f ，方法如下：j l 垂手每一今基送缀露= 1 4 j 京交适夭攀硕士学位论文第= 章关于不相交麓族的一些擒港方法 6 l ，如，。，k 鼻我们定义m 个嚣缀如下： 马= 瓠+ 锄奶：l i 蠢 其中j 一1 ，m ，邂算是z 赢中的加法运算。熙然集合 = 马：b 只l 歹m 是( 形彩z 赢豹翔分。容易褥捌基嚣组集s 掰产生静差恰好是z ( 静匀) z k 中每个元繁的七一1 次。聪一结论由定理2 2 4 得到。 例子2 2 。8 考虑磊上的( 8 ，2 ，3 ，2 ) - d d f ，其纂医组为，= l ，6 蛩， 2 ，3 5 磊上静一令( 5 ，4 ，l 黔麓，蘩下： 肚蜘| ) 3 奉耄主要结论 利用第一节，第二节提供的构造方法，可以得到尻上的( 3 ，2 ) d d f 与( 4 ，3 ) d d f 新豹存在结果。 定理2 。3 1对于下捌除数管，寇玩上存在和，3 ，2 ) d d f ： ( 1 ) 钉= 4 ”，其中礼兰1 ，是模6 余1 的素数的乘积； ( 2 ) 钉= 4 ”，其中n 是任意的正整数： ( 3 ) 移= 劫，茭孛p = l t 勰，4 l ，5 3 。 证明：( 1 ) 由引理1 3 2 和定理2 1 1 ，可以得到一个( 4 n p ，3 ，2 ) 一d d f 其中馆 3 ，弘是模6 氽1 的素数的乘积。对于n 一2 ，由引理2 2 9 知成立。对于n = l 幽引 理1 3 4 得到。 2 ) 囱弓l 理2 2 2 我翻褥餮一个( 4 矬，4 ，4 ，1 ) 一e d f 国萄，它也怒一个组鍪为4 矗椎。 1 5 就索交通太学硕士学位论文第二牵关于不籀交藏旗的一些构遗方法 的4 o g e l d 。应用推论2 1 3 和互上鲍( 4 ，3 ，2 ) - d d f 卵褥( 铲，3 ，2 d d f 融3 ) 。又 由雩| 理1 3 6 存在磊8 上鹣( 1 6 ，3 ，2 ) d d f 与z 4 上的( 莲，毒萄- d d f 。 ( 3 ) 由碍i 理2 1 5 得到。 定理2 3 2 若移慧l ( m o d 2 0 ) ，秽竖l o o l 并且钞 3 2 l ，5 0 l ，6 2 l ，鹤l ，8 0 l ，9 0 l ， 箨么忍上存在一今和，4 ，3 ) 国乙 证明：这个结论可由引理1 3 3 和定理2 1 1 推出。 注本文给出了氖上的( 3 ，2 ) d d f 与扣，4 ，3 ) 一d d f 存在的一些结果。下丽对 予牡赞l 绘出下嚣豹薅令说臻： ( 1 ) 在玩上存在( 3 ，2 ) 一d d f ，其中口三l ( m o d3 ) ，1 s 口2 0 0 ，影1 0 ( m o d 1 2 ) ，可能的例外值是甜一8 8 ，1 2 l ，1 3 6 ，1 6 0 ，1 8 4 。 对于静= 魏纯务，其中魏差l ( m o d6 ) 盼素数，可由萼l 理l 。3 4 缮戮；对 手t | = 驴弘其中芦是搂6 佘l 煞素数豹巢积霉弘= l ，抖l ，胃自窳理2 3 1 霉爨；对 于t ，= 2 5 ，5 5 参考m ；对于t ，= 8 5 ，1 4 5 构造方法可由引理2 1 5 得到；对于t ，一1 7 5 可以用引理2 2 7 ；最后对于t ，= 如，1 0 0 ，在【4 1 中存在( 4 0 ，4 ，1 ) 一c b i b d 和( 1 0 0 ，4 ，1 ) 一 e b l b d ，滋定理2 1 。l 移在4 0 ，s ，2 ) 一d d f 秘l ，3 2 ) 一d r ( 2 ) 禚磊上存在( q 4 ，3 ) 一d d f ，其中移兰l m o d4 ) ，1 s 譬2 0 l ，且移9 ，可 能的例外值是 = 1 5 3 ，1 7 7 当钞一执纯拜其巾鼽三l ( b l o d4 ) 的素数孵，构造方法可由引理1 3 5 得到。 在鞠可潋褥翻管 2 l ，3 3 ，4 5 ，5 7 ，固，嚣，8 l ，弱，l 衢，1 1 7 ，1 2 l ，1 2 筑1 8 9 熬褥造秀法， 对于口= 1 4 l ，2 0 1 可用定理2 3 2 ，对予 = 1 6 5 可用弓l 理2 2 7 引理2 3 3 当n 豢3 ( m o d4 ) 时，在忍n 上存穰一个( 2 ”，8 ，3 ，2 ) ，d d f 。 证明：反复应用零l 瑗2 2 1 和弓l 攥2 2 。2 我粕褥潮一夸( 扩，8 ，莲，1 ) e p f 辆瓣3 ( m o d4 ) ) ，应用推论2 1 3 和磊上鹃( 4 ，3 ，2 ) - d d f 帮得结论。 引理2 3 4 如果口麓1 ( m o d2 0 ) 付s1 0 0 1 并麒簪t 3 2 1 ，5 0 1 ，6 2 l ，6 8 1 ，8 0 l ，9 0 1 ) ， 那么在忍。上存在一个( 黝，3 ，4 ，3 ) 一d d f 。 证明；由弓| 理1 3 。3 阿得一个( q 瓤1 ) - e b i b d 其中移三l ( 毪静d2 0 ) 掣sl o o l 并 且口重 3 2 l ，5 0 1 ，6 2 1 ，6 8 1 ，8 0 1 ，9 0 1 ，也就是一个缀型为1 ”的孓g d d 。由磊5 上一 个( 1 5 ，3 ，4 ，3 ) d d f 和推论2 1 3 即得结论。 ；l 建2 。3 。5 羞在魄；5 ( 糯丽国豹素数) 童存在一令( 轫，3 ，2 ) - d 嚣，邸 么z 拂上存在一个( 2 ，i 鼽3 ，2 ) 一d d f m 黛3 ( m o d4 ) ) 。 证明 由定理2 1 2 榭一个( 妒，8 ，3 ，2 ) 一d d f 警3 ( m o d4 ) ) 。威用引理2 2 7 得 至4 一个( 2 坳，勋，3 ，2 ) d d f 。如果存在一个( 印，3 ，2 ) 一d d f ，那么就襻在一个( 2 ”热3 ，2 ) 一 d d f 沸兰3 ( 硒o d4 ) ) 。 1 6 j 京交通火学硕士学位论文第二章关于不穗交麓族鲍一些构德方法 孳l 避2 3 6 在士存在一个( 3 嘞3 热4 ，3 卜d d f 其中静一l ( m o d2 譬墨 l l 并飘钉譬 3 2 l ，弱l ，6 2 l ，鼹l ，鞠i ，l p 三5 ( m o d6 ) 瓣素数 证明：由磊5 上的( 1 5 ，3 ，4 ，3 ) 一d d f 存在，利用推论2 1 3 及引理2 2 7 即可得刻。 1 7 蔻京交遥大学硕士学霞论文 参考文献 参考文献 l l vc i m g8 姐g d i n 鞯侥哪细：c 】妇n 可e z 缸m d 蝴黔他，l 如”磁汹觏d 巍啪诹f 威鼢懈缸 如打麟鹪d e 8 i g 卫8 ，d 艄a n d 嗍抽p 奴如( 吣) ，1 6 7 - 1 髓 f 2 】m b l l r 蚺t i ，冗e c _ 唧懈甜舢t 他c 洳肿加r 成脾作竹m 耐r 如瞄们d 武黪懈懈如m 施，j c o m - b m d 镳+ ，8 1 9 髂) ，1 6 秘1 8