（应用数学专业论文）平衡t叶三元系的存在性.pdf

上海交通大学 学位论文原创性声明 舡人郑重声1 1 月：所牟交的学位论文，足本人在甘师f 0 指导i - ， 进行研究r 辑! 所取得的成累。涂文一已经汴昵i j | 用的内容外， 文不含仆何其他个人或集体已经发表或撰写过钧f 1 ：讯成裂： 文的研究做出虫要负献的个人知失体均l 存史中以j ：确方式 。本人完仝意识到本声i 删的法律结果i i 木人乐川。 学伉论文作者签名： l = 期：勿uq - z 月叮h 上海交通大学 学位论文版权使用授权书 奉学位论文作者完个，解学校有关保留、使用学位隆文的姚定 同意! 誊校倪瞰并旬国家青关部门或扪构送交论文的丝耳弘一幕i i 乜r 版，允计沦文被台暖和借陡= 本人授权上海交通凡学可以将本学付 论文的令部或部分i 工j 棒编入九父数据j i 进行检索九j 以采川影e j 、 缩叫或扛拓i 等复制手段保存和j 1 ：编本学伶沦文。 保密l 1 ，存一年解密后适用小授权书。 小喾停沦文属于， 小保密留 ( 请， ! 以i 方框内 j + “”) 学位论文f 1 1 者签名： 癣蕞扦导教师签名：c 儿j 羟 h 划：咖d 年2 月卟h 1 2 期：2 一c ，年2jj 引i 上海交通大学硕士学位论文 - - 平衡 t叶三元系的存在性 摘 要 组合设计是离散数学的一个重要的分支, 特别是由于组合设计的理论和方法 在数理统计, 运筹学, 信息论和计算机科学中的重要应用, 组合设计的研究进入了 一个飞速发展的时期. 区组设计是组合设计中一个关键的部分. 设x = 1 , 2 , , v ,b= b 1, b2, , bb 是x 的k - 子集的集合, r 为包含x 的任意一 个元素的k - 子集数, 假若对任意的i , j x ( i j ) ,b中有个区组同时包含他们, 则称( x ,b) 为平衡不完全区组设计, 简称 b i b d , 记做 b ( k , , v ) , 其中 v叫做阶, k 叫做区组容量( 或区组长度) , 叫做相遇数. 当 k = 3 时, 我们称之为三元系, 三元系是区组设计中一个重要的研究方向. 设( v ,b) 是一个 b ( 3 , , v ) , 其中若干个区组 b1, b 2, , btb, 若存在 s v , 使 得对任意 1 j , k t , b jbk= s , 将每个区组看成三角形状的叶子, 叶子的三个 角上元素即为区组中三个元素, 则 t个区组所代表的 t个叶子就可以 s为中心拼 成一个 t 叶相交于中心一点的结构. 显然, 除中心 s 外, t 叶上其他点两两不同, 我 们称这个结构为 t叶三元组. 如果b中所有区组恰能划分为若干个 t叶三元组, 且 v 中每个点作为 t叶三元组中心的次数相等, 称这个设计为 v上平衡的 t叶三 元系( b a l a n c e d t - f o i l t r i p l e s y s t e m ) , 记作 b f t s ( t , , v ) . 关于平衡t 叶三元系的存在性问题, u s h i o 5 在2 0 0 1 年研究了 t = 2 时的情形, 并且证明了: 定理 1 . 3 . 平衡 2 叶三元系存在的充要条件是 ( v - 1 ) 0 ( m o d 1 2 ) , v 5 . 本文对 t 3的情形研究了平衡 t叶三元系的存在性问题, 首先给出 b f t s ( t , , v ) 存在的必要条件: 定理 1 . 4 . 若 b f t s ( t , , v ) 存在, 则有 ( v - 1 ) 0 ( m o d 6 t ) , v 1 + 2 t . 然后, 我们利用循环设计和可分解横截设计, 依次得到如下的结果: 定理 2 . 1 . b f t s ( 3 , , v ) 存在的充要条件为 ( v - 1 ) 0 ( m o d 1 8 ) , v 7 . 定理 3 . 1 . b f t s ( 4 , , v ) 存在的充要条件为 ( v - 1 ) 0 ( m o d 2 4 ) , v 9 . 由此解决了 t = 3 和4 的平衡t 叶三元系的存在性问题, 并且对任意的 t , 我们得到 如下的结论: 上海交通大学硕士学位论文 - - 定理 4 . 1 . 当 v 4 t 时, b f t s ( t , , v ) 存在的充要条件为 ( v - 1 ) 0 ( m o d 6 t ) 关键词:三元系, 平衡 t 叶三元系, 循环设计, 可分解横截设计. 上海交通大学硕士学位论文 - - e x i s t e n c e o f b a l a n c e d t - f o i l t r i p l e s y s t e m a b s t r a c t c o m b i n a t o r i a l d e s i g n i s a n i m p o r t a n t b r a n c h o f d i s c r e t e m a t h . w i t h t h e w i d e l y u s e o f t h e t h e o r e t i c s a n d t e c h n i q u e s o n s t a t i s t i c , o p e r a t i o n a l r e s e a r c h , c o m p u t e r s c i e n c e a n d s o o n , c o m b i n a t o r i a l d e s i g n d e v e l o p e s q u i c k l y . b l o c k d e s i g n i s a k e y p a r t o f c o m b i n a t o r i a l d e s i g n . t h e d e f i n a t i o n o f b l o c k d e s i g n i s s h o w e d a s f o l l o w i n g : l e t x = 1 , 2 , , v ,b= b 1, b2, , bb i s t h e s e t o f k - s e t s ( d e n o t e d a s b l o c k ) o f x , r i s t h e n u m b e r o f t h e s e t s i n c l u d i n g s o m e e l e m e n t o f x , i f f o r a n y i , j x ( i j ) , t h e r e a r e b l o c k s o n b c o n t a i n i n g b o t h o f t h e m a t t h e s a m e t i m e , w e c a l l ( x ,b) a s a b a l a n c e d i m c o m p l e t e b l o c k d e s i g n ( b i b d ) , d e n o t e d a s b ( k , , v ) . v i s t h e d i m e m s i o i n , k i s t h e v o l u m n o f b l o c k , i s t h e n u m b e r o f i n t e r s e c t . w h e n k = 3 , w e c a l l t h e d e s i g n a s t r i p l e s y s t e m w h i c h i s a n i m p o r t a n t p a r t o n b l o c k d e s i g n . l e t ( v ,b) b e a b ( 3 , , v ) , i f t h e r e a r e t b l o c k s s u c h a s b 1, b2, , bt b, a n d t h e r e i s a n e l e m e n t s u c h a s s v s o t h a t f o r 1 j , k t , b j bk= s . w e r e g a r d e v e r y b l o c k a s a t r a i n g l e f o i l , t h e t h r e e p o i n t s o n t h e f o i l a r e j u s t t h e e l e m e n t s o n t h e b l o c k , t h e n t h e t f o i l s r e p r e s e n t e d b y t h e t b l o c k s a b o v e f o r m a s t r u c t u r e t h a t i n t e r s e c t o n t h e c e n t e r e l e m e n t s . o b v i o u s l y , a n y t w o e l e m e n t s o n t h e s t r u c t u r e a r e d i f f e r e n t e x c e p t s , w e c a l l i t a t - f o i l t r i p l e b l o c k . i f t h e b l o c k s o f b c a n b e d i v i d e d i n t o s o m e t - f o i l t r i p l e b l o c k s , a n d t h e t i m e s t h a t t h e e l e m e n t o f v b e i n g t h e c e n t e r a r e e q u a l , w e c a l l i t f o r m s a b a l a n c e d t - f o i l t r i p l e s y s t e m o n v , d e n o t e d a s b f t s ( t , , v ) . a b o u t b a l a n c e d t - f o i l t r i p l e s y s t e m , u s h i o s t u d i e d t h e c a s e o f t = 2 o n 2 0 0 1 a n d s h o w e d t h a t : t h e o r e m . 1 . 3 . t h e n e c e s s a r y a n d s u f f i c i e n t c o n d i t i o n s o f e x i s t e n c e o f b a l a n c e d 2 - f o i l t r i p l e s y s t e m i s ( v - 1 ) 0 ( m o d 1 2 ) , v 5 . w e m a k e s o m e r e s e a r c h o n t h e e x i s t e n c e o f b a l a n c e d t - f o i l t r i p l e s y s t e m f o r t 3 a n d f i r s t p r o v e : 上海交通大学硕士学位论文 - - t h e o r e m 1 . 4 . i f b f t s ( t , , v ) e x i s t s , w e h a v e ( v - 1 ) 0 ( m o d 6 t ) , v 1 + 2 t . t h e n w e g e t t h e f o l l o w i n g r e s u l t s b y u s i n g c y c l i c b l o c k d e s i g n a n d r e s o l v a b l e t r a v e r s e d e s i g n : t h e o r e m 2 . 1 . t h e n e c e s s a r y a n d s u f f i c i e n t c o n d i t i o n s o f e x i s t e n c e o f b f t s ( 3 , , v ) i s ( v - 1 ) 0 ( m o d 1 8 ) , v 7 . t h e o r e m 3 . 1 . t h e n e c e s s a r y a n d s u f f i c i e n t c o n d i t i o n s o f e x i s t e n c e o f b f t s ( 4 , , v ) i s ( v - 1 ) 0 ( m o d 2 4 ) , v 9 . t h e o r e m 4 . 1 . w h e n v4 t , t h e n e c e s s a r y a n d s u f f i c i e n t c o n d i t i o n s o f e x i s t e n c e o f b f t s ( t , , v ) i s ( v - 1 ) 0 ( m o d 6 t ) . k e y w o r d s :t r i p l e s y s t e m , b a l a n c e d t - f o i l t r i p l e s y s t e m , c y c l i c b l o c k d e s i g n ,r e s o l v a b l e t r a v e r s e d e s i g n . 上海交通大学硕士学位论文 - - 一. 引言 组合设计是离散数学的一个重要的分支, 对于组合设计的系统研究, 是从 2 0 世纪 3 0 年代 r . c . b o s e 等人的工作开始的. 特别是由于组合设计的理论和方法在 数理统计, 运筹学, 信息论和计算机科学中的重要应用, 组合设计的研究进入了一 个飞速发展的时期. 在组合设计中, 我们经常要从一个给定的集合中选定一组子 集, 使其满足某些特定的性质, 与之相关的问题是这样的子集的存在性, 计数问题 与构造问题. 这些问题是区组设计所研究的基本问题. 我们首先给出区组设计的概念: 定义. 1 设 x = 1 , 2 , , v ,b= b1, b 2, , bb 是 x的 k - 子集( 称为区组) 的集合, r 为包含 x的任意一个元素的 k - 子集数, 假若对任意的 i , j x ( i j ) ,b中有个 区组同时包含他们, 则称( x ,b) 为平衡不完全区组设计. 简称 b i b设计, 记做 b ( k , , v ) . v 叫做阶, r 叫做重复度, k 叫做区组容量( 或区组长度) , 叫做相遇数. 关于不完全区组设计, 有如下定理: 定理 1 . 1 2 . 设 k 2 , ( v ,b) 为一个 b ( k , , v ) , 则 ( i ) v 中任意一点 p 的重复度 r = ( v 1 ) ( k 1 ) , ( i i ) b中所包含的区组个数 b = |b| = v ( v 1 ) / k ( k 1 ) . 当 k = 3时是区组设计中第一个需要研究的情形. 英国的 w o o l h o u s e在 1 8 4 4 年首先提出 k = 3 的区组设计问题, 三年后k i r k m a n 给出了 b ( 3 , 1 , v ) 存在的充要条 件. 1 8 5 3年 s t e i n e r在研究四次曲线的二重切线问题时也遇到了 k = 3 , = 1的区 组设计问题, 他猜测了六年前 k i r k m a n已证明了的结果, 1 8 5 9年 r e i s s证明了 s t e i n e r的猜测. 从此 k = 3 , = 1的区组设计就被称为 s t e i n e r三元系( t r i p l e s y s t e m ) . 定义. k = 3 时的 b i b 设计叫三元系, b ( 3 , , v ) 叫做 v 阶重三元系. 关于三元系的存在性问题已经解决: 定理 1 . 2 3 4 . b ( 3 , , v ) 存在的充要条件是 v 1 , 3 ( m o d 6 ) , 若1 , 5 ( m o d 6 ) v 0 , 1 ( m o d 3 ) , 若2 , 4 ( m o d 6 ) v 1 ( m o d 2 ) , 若3 ( m o d 6 ) v 2 , 若0 ( m o d 6 ) 设( v ,b) 是一个 b ( 3 , , v ) , 其中若干个区组 b1, b 2, , btb, 若存在 s v , 使 得对任意 1 j , k t , b jbk= s , 将每个区组看成三角形状的叶子, 叶子的三个 上海交通大学硕士学位论文 - - 角上元素即为区组中三个元素, 则这 t个区组所代表的 t个叶子就可以 s为中心 拼成一个t 叶相交于中心一点的结构, 显然, 除中心外, t 叶上其他点两两不同. 我 们称这种结构为 t叶三元组. 如果b中所有区组恰能划分为若干个 t叶三元组, 且 v 中每个点作为 t叶三元组中心的次数相等, 则称这个设计为构作在 v上平衡 的 t 叶三元系( b a l a n c e d t - f o i l t r i p l e s y s t e m ) , 简记作b f t s ( t , , v ) . 这个问 题首先由 u s h i o 在 2 0 0 1 年提出, 他得到如下结果: 定理 1 . 3 5 - 7 . 平衡 2 叶三元系存在的充要条件是 ( v - 1 ) 0 ( m o d 1 2 ) , v 5 . 本文对任意的 t , 研究平衡 t叶三元系的存在性问题. 首先, 我们给出下述必 要条件: 定理 1 . 4 . 若 b f t s ( t , , v ) 存在, 则有 ( v - 1 ) 0 ( m o d 6 t ) 且 v 1 + 2 t . 证明: 设( v ,b) 是一个b f t s ( t , , v ) , 由定理1 . 1 可知|b| = v ( v - 1 ) / 6 , v 中每个点 作为中心的次数是相等的, 故|b| 0 ( m o d v t ) , 所以( v - 1 ) 0 ( m o d 6 t ) , 从平衡 t叶三元系的定义可知任意一个 t叶三元组中除了中心之外的点两两不同, 故 v 中至少有2 t + 1 个不同的点, 从而有v 1 + 2 t . 我们需要利用循环设计来构造平衡 t 叶三元系, 先引入循环三元系的概念: 定义. 设 v = z v, ( v ,b) 为一个 b ( 3 , , v ) . 如果对于任一区组 b = a1, a2, a3b, 都有 b + 1 = a 1+ 1 , a2+ 1 , a3+ 1 b( 此处加法在 zv中进行) , 则称( v ,b) 为 zv上的一个循环 三元系, 并记做 c b ( 3 , , v ) . 设( v ,b) 为zv上的一个c b ( 3 , , v ) , 把加法循环群z v看作一个自同构群. v 和 b在zv的作用下都保持不变.b中的区组在z v的作用下划分成若干个轨道, 每个轨 道所包含的区组的个数必定是 v的一个因数. 从而为了确定循环设计, 只要在每 个轨道中确定一个区组即可, 这个区组称其为初始区组. 循环三元系的存在性已经完全解决, 如下: 定理 1 . 5 8 . 令 c b ( 3 , ) = v | c b ( 3 , , v ) 存在 , v c b ( 3 , ) 的充要条件为: ( v , ) ( 9 , 1 ) , ( 9 , 2 ) 且 ( i ) v 1 , 3 ( m o d 6 ) , 若1 , 5 , 7 , 1 1 ( m o d 1 2 ) ( i i ) v 0 , 1 , 3 , 4 , 7 , 9 ( m o d 1 2 ) , 若2 , 1 0 ( m o d 1 2 ) ( i i i ) v 1 ( m o d 2 ) , 若3 , 9 ( m o d 1 2 ) ( i v ) v 0 , 1 ( m o d 3 ) , 若4 , 8 ( m o d 1 2 ) ( v ) v 0 , 1 , 3 ( m o d 4 ) , 若6 ( m o d 1 2 ) ( v i ) v 3 , 若0 ( m o d 1 2 ) 上海交通大学硕士学位论文 - - 利用循环三元系, 我们可以找到一种构作平衡 t 叶三元系的方便的方法: 定理 1 . 6 . 如果 c b ( 3 , , v ) 存在, ( v - 1 ) 0 ( m o d 6 t ) 且 v 1 + 2 t , 同时该循环设 计的初始区组恰好可以划分成若干个 t叶三元组( 称这些 t叶三元组为初始叶) , 则 b f t s ( t , , v ) 存在. 证明: 设( z v,b) 是一个 c b ( 3 , , v ) , 因为初始区组恰好可以划分成若干个初始叶, 将初始叶中每个区组 b = a , b , c 在 z v上作 b + i = a + i , b + i , c + i | i zv 便可得到 v 个 t叶三元组, 从而保证了 zv中每个点作为中心的次数相同, 这样即得到 b f t s ( t , , v ) . 推论 1 . 1 . 设 v 1 ( m o d 6 t ) 且 v 2 t + 1 , 则 b f t s ( t , 1 , v ) 存在. 证明: 易知 c b ( 3 , 1 , v ) 存在, 设( z v,b) 是一个 c b ( 3 , 1 , v ) , 其构造方法可参考文献 1 1 - 1 8 , 不妨令 c b ( 3 , 1 , v ) 的每个轨道中含0 的区组作为初始区组, 因为= 1 , 故 每 t个初始区组只有 0一个公共点, 将它们以 0为中心构成一个初始叶, 由定理 1 . 6 可知 b f t s ( t , 1 , v ) 存在. 推论 1 . 2 . 设 v 1 ( m o d 2 t ) 且 v 2 t + 1 , 则 b f t s ( t , 3 , v ) 存在. 证明: 易知 c b ( 3 , 1 , v ) 存在, 设( z v,b) 是一个 c b ( 3 , 3 , v ) , 因为 v 2 t + 1 , 所以可令 初始区组为 v - 1 , 0 , 1 v - 2 , 0 , 2 ( v + 1 ) / 2 , 0 , ( v - 1 ) / 2 . 依次从初始区组中抽 取 t 个初始区组以 0为中心作一个初始叶, 可知这 t个初始区组只有 0一个公共 点, 由定理 1 . 6 可知 b f t s ( t , 3 , v ) 存在. 除了循环设计之外, 我们还要利用可分解横截设计来构造平衡 t叶三元系. 有关可分解横截设计概念如下: 定义. 设集合 v大小为 v = 3 k , 设 g = a i( 称 ai为组) | i z3且| ai| = k 且 g构成对 v 的一个划分. v的 3元子集( 称为区组) 的集合构成一个集合b, 如果对任意区组 b b, | b a i| = 1 , i z3, 且v 中任意两个属于不同组的元素恰好在1 个区组中, 称这 个设计为 g上的横截设计, 记作 t d ( 3 , 1 , k ) . 设( v ,b) 是一个 t d ( 3 , 1 , k ) ,b可以划 分成若干部分, 使得 v中任意元素恰好在每部分中出现一次, 则称每个部分为一 个平行类, 此时称( v ,b) 为 g 上的可分解的横截设计, 记为 r t d ( 3 , 1 , k ) . 为了后面叙述方便, 我们将要用到如下两个引理: 引理 1 . 1 . 设 b f t s ( t , 6 t , s ) 存在, 则 b f t s ( t , 6 t , 3 s ) 也存在. 证 明 : 设 a = a i| izs , b = bi| izs , c = ci| izs , 先 分 别 作 a , b , c 上 b f t s ( t , 6 t , s ) . 然后构造2 t 个相同的t d ( 3 , 1 , s ) = ai, b i + j - 1, cj | i , j zs . 对任意 的i z s, 从t d ( 3 , 1 , s ) 中抽取t 个含有ai的不同区组以ai为中心合为t 叶三元组, 上海交通大学硕士学位论文 - - 这样总共可以得到 2 s个以 ai为中心的 t叶三元组. 最后再构造 4 t个同样的 t d ( 3 , 1 , s ) , 用类似方法可得 2 s个以 b i为中心的 t叶三元组和 2 s个以 ci为中心 的 t叶三元组. 综上所述, 我们就得到了一个 a b c上的 b f t s ( t , 6 t , 3 s ) . 引理 1 . 2 . 设 s n , r t d ( 3 , 1 , 2 s + 1 ) 存在. 证明: 设 v = a b c , g = a , b , c , a = a i| i z2 s + 1 , b = bi| i z2 s + 1 , c = ci| i z2 s + 1 , 构造 r t d ( 3 , 1 , 2 s + 1 ) 如下: b= b j a , bj a= ( 1 , d1 j+ a ) , ( 2 , d2 j+ a ) , ( 3 , d3 j+ a ) , a z2 s + 1, 其中( 1 , i ) 代表 ai, ( 2 , i ) 代 表 bi, ( 3 , i ) 代表 ci, di j代表下面矩阵中第 i 行第 j 列的值 + 12.5312.420 2.321.210 0.0000.000 ss sssss 下面的 3节将给出平衡 3叶三元系和平衡 4叶三元系存在的充要条件, 以及当 v 4 t 时平衡 t 叶三元系存在的充要条件. 上海交通大学硕士学位论文 - - 二. 平衡 3叶三元系的存在性 本节讨论平衡 3 叶三元系的存在性. 定理 2 . 1 . b f t s ( 3 , , v ) 存在的充要条件为 ( v - 1 ) 0 ( m o d 1 8 ) , v 7 . 证明: 必要性由定理 1 . 4 可知. 充分性可分成下列几种情形考虑: 情形 1 . ( , 1 8 ) = 1 且 v 1 ( m o d 1 8 ) , v 1 9 . 由推论 1 . 1 可知 b f t s ( 3 , 1 , v ) 存在, 取次即得到 b f t s ( 3 , , v ) . 情形 2 . ( , 1 8 ) = 2 且 v 1 ( m o d 9 ) , v 1 0 . 若 v 1或 1 9 ( m o d 3 6 ) , 由推论 1 . 1可知 b f t s ( 3 , 1 , v ) 存在, 取 2次即得 b f t s ( 3 , 2 , v ) . 若 v 1 0 ( m o d 3 6 ) , 设 v = 3 6 m + 1 0 , 令 v = a b c , 其中 a = ai| i z1 2 m + 3 ; b = bi| i z1 2 m + 3 ; c = ci| i z1 2 m + 3 . 设( z1 2 m + 4, b ) 是一个 c b ( 3 , 2 , 1 2 m + 4 ) , 对 b 中区组的元素作下列映射: 令fa( i ) = a i, i z1 2 m + 4/ 1 2 m + 3 , fa( 1 2 m + 3 ) = , 即得到a 上b ( 3 , 2 , 1 2 m + 4 ) 记为( a ,a) 令fb( i ) = b i, i z1 2 m + 4/ 1 2 m + 3 , fb( 1 2 m + 3 ) = , 即得到b 上b ( 3 , 2 , 1 2 m + 4 ) 记为( b ,b) 令fc( i ) = c i, i z1 2 m + 4/ 1 2 m + 3 , fc( 1 2 m + 3 ) = , 即得到c 上b ( 3 , 2 , 1 2 m + 4 ) 记为( c ,c) 将区组集a,b,c加上 2 个相同的 t d ( 3 , 1 , 1 2 m + 3 ) = ai, b i + j - 1, cj | i , j z1 2 m + 3 即可构成 v 上 b ( 3 , 2 , 3 6 m + 1 0 ) . 现在说明如何由上述 b ( 3 , 2 , 3 6 m + 1 0 ) 构作出一个 b f t s ( 3 , 2 , 3 6 m + 1 0 ) . 设( z 1 2 m + 4, b ) 中每个轨道的某一含 0区组为初始区组, 设某轨道的初始区组为 0 , m , n , 对任意i z 1 2 m + 4/ 1 2 m + 3 ,a中必含有形如 ai, am + i, an + i| am + i或an + i可能为 的区组, 称其为 a i代表组, 同时a中必有区组 , am - 1, an - 1 , 称其为一个代表组. 同样地, 可以在b , c中确定 bi代表组, ci代表组和代表组, 下同. 从a , b , c中各抽取一个代表组可以构成一个以为中心的 3叶三元组. 因 为( z 1 2 m + 4, b ) 有4 m + 1 个初始区组, 故a , b , c中所有代表组抽取出来可以构成4 m + 1 个为中心的 3 叶三元组. 选 定 一 个t d ( 3 , 1 , 1 2 m + 3 ) ,对 每 个iz 1 2 m + 3,抽 取 区 组 a i, bi + j - 1, cj| j = i , , i + 8 m + 1 , 记这8 m + 2 个区组构成集合为si.a中抽取一个 ai代 表组, 加上 s i中抽取2 个含ai的区组可以构成一个3 叶三元组. 因为( z1 2 m + 4, b ) 中有 上海交通大学硕士学位论文 - - 4 m + 1个初始区组, 故 312+ m zi i s 与a可以构成 4 m + 1个以 a i( i z1 2 m + 3) 为中心的 3叶三 元组. 对每个 j z1 2 m + 3, 上述 t d ( 3 , 1 , 1 2 m + 3 ) 中剩余的包含 cj的区组, 加上另一个 t d ( 3 , 1 , 1 2 m + 3 ) 中区组 a i, bi + j - 1, cj| i = 0 , , 4 m , 再从c中取出 4 m + 1个 cj代表组, 和前面类似作法, 可以构成 4 m + 1个以 cj为中心的 3叶三元组. 需要注意的是, 为 保证只有 ci一个公共点, 第一个 t d ( 3 , 1 , k ) 中以 a i代表组与第二个 t d ( 3 , 1 , k ) 中 a4 - i代表组在同一叶即可, i = 1 , 2 , 3 , 4 . 最后b加上第二个 t d ( 3 , 1 , 1 2 m + 3 ) 余下区组, 用类似方法可以构成4 m + 1 个以 bi为 中 心 的 3 叶 三 元 组 ( iz1 2 m + 3) . 综 上 所 述 ,这 样 就 形 成 了 一 个 b f t s ( 3 , 2 , 3 6 m + 1 0 ) . 若 v2 8 ( m o d 3 6 ) ,设 v = 1 2 m43 6 t2 8 ( m3 t2 ) , t0 , 作 c b ( 3 , 2 , 1 2 m + 4 ) , 令其初始区组为: 0 , 2 r 2 , 3 m r 2 r = 0 m 1 ; 0 , 2 m 2 r 1 , 6 m r 1 r = 0 m 1 ; 0 , 2 r 2 , 3 m r 2 r = 0 m 1 ; 0 , 2 m 2 r 1 , 6 m r 1 r = 0 m 1 ; 0 , 3 m 1 , 6 m 2 . 按照初始区组的顺序, 依次每3 个初始区组只有0 一个公共点, 故可以构成一 个初始叶. 由定理 1 . 6 可知 b f t s ( 3 , 2 , 3 6 t + 2 8 ) 存在. 最后将上述得到的 b f t s ( 3 , 2 , v ) 取/ 2 次即得到 b f t s ( 3 , , v ) . 情形 3 : ( , 1 8 ) = 3 且 v 1 ( m o d 6 ) , v 7 . 由推论 1 . 2 可知 b f t s ( 3 , 3 , v ) 存在, 取/ 3 次即得到 b f t s ( 3 , , v ) . 情形 4 : ( , 1 8 ) = 6 且 v 1 ( m o d 3 ) , v 7 . 若 v 1或 7 ( m o d 1 2 ) , 由推论 1 . 2可知 b f t s ( 3 , 3 , v ) 存在, 取 2次即得 b f t s ( 3 , 6 , v ) 若 v 1 0 ( m o d 1 2 ) , 设 v = 1 2 m + 1 0 , 令 v = a b c , 其中 a = ai| i z4 m + 3 b = bi| i z4 m + 3 c = ci| i z4 m + 3 设( z4 m + 4, b ) 是一个 c b ( 3 , 6 , 4 m + 4 ) , 对 b 的区组中元素作下面映射: 上海交通大学硕士学位论文 - - 令 fa( i ) = ai, i z4 m + 4/ 4 m + 3 , fa( 4 m + 3 ) = , 即得到 a 上 b ( 3 , 2 , 1 2 m + 4 ) 记为( a ,a) 令 fb( i ) = bi, i z4 m + 4/ 4 m + 3 , fb( 4 m + 3 ) = , 即得到 b 上 b ( 3 , 2 , 1 2 m + 4 ) 记为( b ,b) 令 fc( i ) = ci, i z4 m + 4/ 4 m + 3 , fc( 4 m + 3 ) = , 即得到 c 上 b ( 3 , 2 , 1 2 m + 4 ) 记为( c ,c) 将区组集a , b , c加上6 个t d ( 3 , 1 , 4 m + 3 ) = a i, bi + j - 1, cj | i z4 m + 3, j z4 m + 3 即可 构成 v 上 b ( 3 , 6 , 1 2 m + 1 0 ) . 现在说明如何由上述 b ( 3 , 6 , 3 6 m + 1 0 ) 得到 b f t s ( 3 , 6 , 3 6 m + 1 0 ) . 与情形 2中 v 1 0 ( m o d 3 6 ) 类似,a , b , c中所有代表组可以构成 4 m + 3 个以为中心的 3 叶三 元组.a中剩余区组加上 2个 t d ( 3 , 1 , 4 m + 3 ) , 对每个 i z 4 m + 3, 抽取 a中 4 m + 3 个 ai 代表组( 记作a i j, j z4 m + 3) , 这样ai j, ai, bi + j - 1, cj , ai, bi + j, cj + 1 构成以ai为中心的3 叶三元组, 共构成 4 m + 3 个以a i为中心的3 叶三元组. 以bi和ci为中心的3 叶三元 组的作法与 ai类似. 这样就构造了一个 b f t s ( 3 , 6 , 1 2 m + 1 0 ) . 若 v 4 ( m o d 1 2 ) , 可设 v 1 2 m 4 , m 1 , 循环设计的初始区组如下: 0 , 3 m r , 3 m r 2 r = 0 m 1 ; 0 , 4 m r 2 , 6 m r 1 r = 0 m 1 ; 0 , 3 m r , 3 m r 2 r = 0 m 1 ; 0 , 4 m r 2 , 6 m r 1 r = 0 m 1 ; 0 , 3 m 1 , 6 m 2 . 将初始区组取 3次得到 c b ( 3 , 6 , v ) , 与情形 2 中 v 2 8 ( m o d 3 6 ) 类似的, 按照 顺序每 3 个不同初始区组可以构成一个初始叶. 由定理1 . 6 可知 b f t s ( 3 , 6 , 1 2 m + 4 ) 存在. 最后将上述 b f t s ( 3 , 6 , v ) 取/ 6 次即得到 b f t s ( 3 , , v ) . 情形 5 : ( , 1 8 ) = 9 且 v 1 ( m o d 2 ) , v 7 由推论 1 . 2 可知 b f t s ( 3 , 3 , v ) 存在, 取/ 3 次即得到 b f t s ( 3 , , v ) . 情形 6 : ( , 1 8 ) = 1 8 , v 7 若 v 1 ( m o d 3 ) , 此时 b f t s ( 3 , 6 , v ) 存在, 取 3 次即为 b f t s ( 3 , 1 8 , v ) . 若 v 5 ( m o d 6 ) , 此时 b f t s ( 3 , 9 , v ) 存在, 取 2 次即为 b f t s ( 3 , 1 8 , v ) . 若 v 2 ( m o d 6 ) , 则 若 v 8 ( m o d 1 2 ) , 设 v = 4 m , m 4 , c b ( 3 , 1 8 , 4 m ) 存在, 初始区组按下列顺序排 列: 0 , 1 , 3 0 , 3 , 7 0 , 2 m - 1 , 4 m - 1 取 6 次; 上海交通大学硕士学位论文 - - 0 , 1 , 2 0 , 2 , 4 0 , 2 m - 1 , 4 m - 2 取 3 次. 按顺序每 3个初始区组合为一初始叶, 若三个初始区组中有两个区组除 0外有公 共点, 将其中一个轨道中另外一个含 0区组作为初始区组. 由定理 1 . 6可知 b f t s ( 3 , 1 8 , 4 m ) 存在. 若 v 2 ( m o d 1 2 ) , 设v = 1 2 t + 2 , t n , 若t = 1 , v = 1 4 , 如下构作b f t s ( 3 , 1 8 , 1 4 ) 的初始叶( 括号内区组构成一初始叶, 下同) : 0 , 1 , 2 0 , 3 , 6 0 , 4 , 8 取 3 次; 0 , 2 , 4 0 , 5 , 1 0 0 , 6 , 1 2 取 3 次; 0 , 1 0 , 1 1 0 , 2 , 6 0 , 1 , 取 3 次; 0 , 4 , 1 2 0 , 3 , 9 0 , 2 , 取 3 次; 0 , 5 , 2 0 , 8 , 1 0 0 , 3 , 1 1 ; 0 , 3 , 1 , 4 , 2 , 5 , . 各轨道在 z1 3作加法, 且( x , y , ) + i = ( x + i , y + i , ) , i z1 3 若 t 1 , 设 v = a b c d , 其中 a = ai| i z4 t - 1 , b = bi| i z4 t - 1 , c = ci| i z4 t - 1 , d = i| i z5 . 构作 v 上的 b ( 3 , 1 8 , 1 2 t + 2 ) , 它由如下 4 个部分组成: ( ) : 由情形 5 可知 b f t s ( 3 , 1 8 , 4 t - 1 ) 存在, 作 a , b , c 上的 b f t s ( 3 , 1 8 , 4 t - 1 ) . ( ) : 作 z 5上的 c b ( 3 , 1 8 , 5 ) , 对区组中元素作映射 f ( i ) =j( i z5) 即得 d上的 b ( 3 , 1 8 , 5 ) . ( ) : 由引理1 . 2 可知r t d ( 3 , 1 , 4 t - 1 ) 存在, 故以 a , b , c 为组作一r t d ( 3 , 1 , 4 t - 1 ) 设计, 因为 4 t - 1 6 , 故可以从中抽取 5个平行类 p i, i z5, 将 pi与i结合, pi中每 个区组 a m, bn, cl 替换成 4个区组 am, bn,i am,i, cl i, bn, cl am, bn, cl