（应用数学专业论文）一致可分解3平衡设计及其应用.pdf

一致可分解3 一平衡设计及其应用 摘要 摘要 一平衡设计是设计理论中重要的研究对象，在许多方面都有广泛的用 途本文研究一致可分解3 一平衡设计及其应用我们完全确定了区组长度 为4 和6 的一致可分解3 一平衡设计的存在谱，并且应用相关结果来研究 h a r t m a n 和p h e l p s1 2 6 提出的两个研究问题：广义可分解斯坦纳四元系存在 性问题和( 1 ，2 ) 一可分解斯坦纳四元系存在性问题基本解决了广义可分解斯 坦纳四元系的存在性问题，建立了( 1 ，2 ) 一可分解斯坦纳四元系的若干无穷类 的存在结果 在第二章，我们完全确定了区组长度为4 和6 的一致可分解3 一平衡设 计的存在谱 在第三章，我们建立了广义可分解斯坦纳四元系的若干构造方法，特别 是广义可分解烛台型四元系的三倍加权构造和烛台型四元系伴侣构造，基本 解决了广义可分解斯坦纳四元系的存在性问题在第三章的最后我们还给出 解决剩余数值的存在性的一条思路 在第四章，我们建立了( 1 ，2 ) 一可分解斯坦纳四元系的若干构造方法，特 别是( 1 ，2 ) 一可分解烛台型四元系的三倍构造和f r a n c 构造，建立了( 1 ，2 ) 可 分解斯坦纳四元系的若干无穷类的存在结果在第四章的最后我们还给出 解决h a r t m a n 和p h e l p s 的研究问题的一条思路 关键词：一致可分解t 一平衡设计；可分解烛台型t 一系；斯坦纳四元系 作者：孟召平 导师：杜北梁( 教授) 一致可分解3 一平衡设计及其应用 英文摘要 u n i f o r m l yr e s o l v a b l et h r e e - w i s eb a l a n c e dd e s i g n s a n dt h e i ra p p l i c a t i o n s ab s t r a c t t w i s eb a 1 a n c c dd e s i g ni sai r n p o i t a n ts u b j e c ti nc o m b i n a t o r i a ld e s i g nt h e o r ya n d h a sb e e nw i d e l yu s e di nm a n ya r e a s 1 1 ：t h i sd i s s m r a t i o n ，w ed e t e r m i n et h cs p e c t r u mo f u n i f o r m l yr e s o l v a b l et h l 。c o w i s eb a l a n c e dd e s i g n sw i t hb l o c ks i z e sf o u ra n ds i x ，a n d1 - 1 8 ( 2 i tt os t u d yt h eo p e np r o b l e mp o s e db yh a r t m a na n dp h e l p si n 2 6 】：t h ce x i s t e n c eo f a u g m e n t e dr e s o l v a b l es t e i n e rq u a d r u p l es y s t e m sa n d ，t h ee x i s t e n c eo f ( 1 ，2 ) 一r e s o l v a b l e s t e i n e rq u a d r u p l es y s t e m s w ca l m o s t l yd e t e r m i n e dt h ee x i s t e n c eo fa u g m c n t c dr e s o l v a b l es t e i n c rq u a d r u p l es y s t e m sa n d ，g i v es 0 1 t i oi n f i n i t ec l a s s e so f ( 1 ，2 ) 一r e s o l v a b l e s t e i n e rq u a d r u p l es y s t e m s i nc h a p t e r2 w ed e t e r m i n et h es p e c t r u mo fu n i f o r m l yr e s o l v a b l e3 一w i s eb a l a n c e d d e s i g n sw i t hb l o c ks i z e sf o u ra n ds i x i nc h a p t c r3 ，w eg i v es o l r l cc o n s t r u c t i o n so fa u g m e n t e dr e s o l v a b l es t e i n e rq u a d r u p l es y s t e m s ，s p e c i a l l y ，t h et r i p l i n gw e i g h tc o n s t r u c t i o na n dt h ec a n d e l a b r aq u a d r u p l e s y s t e m sp a r t n e rc o n s t r u c t i o no na u g m e n t e dr c s o l v a b l ec a n d e l a b r aq u a d r u p l es y s t e m s w k ；a h n o s t l ) rs o l v et h ep r o b l e m o ft i l ee x i s t e n c eo fa u g m e n t e dr e s o l v a l ? l es t e i n e rq u a d r u - p l es y s t e m s f i n a 1 l y ，w ea l s op r e s e n tap o s s i b l ea p p r o c ht ot h es e t t l e m e n to ft h er e m e a i n i n gv a l u e s i nc h a p t e r4 ，w eg i v es e i n ec o n s t r u c t i o n so f ( 1 ，2 ) 一r e s o l v a b l es t e i n e rq u a d r u p l es y s t e m s ，s p e c i a l l y ，t h et r i p l i n gc o n s t r u c t i o na n d t h ef r a m ec o n s t r u c t i o n0 1 1 ( 1 ，2 ) 一r e s o l v a b l e c a n d e l a b r aq u a d r u p l es y s t e m s w cg i v es o m ei n f i n i t ec l a s s e so f ( 1 ，2 ) 一r e s o l v a b l es t e i n e r q u a d r u p l es y s t e m s f i n a l l y ，w ca l s op r e s e n tap o s s i b l ea p p r o c ht os o l v eh a r t m a na n d p h e l p s o p e np r o b l e m k e y w o r d s ：u n i f o r m l yr e s o l v a b l e 一w i s e s y s t e m ；s t e i n c rq u a d r u p l es y s t e m b a l a n e e dd e s i g n ；r e s o l v a b l ec a n d e l a b r at i i w r i t t e nb yz h a ( ) p i n gm c n g s u p e r v i s e db yp r o f b e i l i a n gd u 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名日期：幼移莎。砂 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导，杀签名：盎兰 搓日 第一章绪论 第一章绪论帚一早弓有了匕 研究背景 本文研究一致可分解3 一平衡设计及其应用具体来说，我们确定了区 组长度为4 和6 的一致可分解3 一平衡设计的存在谱，并且应用相关结果来 研究h a r t m a n 和p h r l p s 【2 6 提出的两个研究问题：广义可分解斯坦纳四元系 的存在性问题和( 1 ，2 ) 一可分解斯坦纳四元系的存在性问题基本解决了广义 可分解斯坦纳四元系的存在性问题，建立了( 1 ，2 ) 一可分解斯坦纳四元系的若 干无穷类的存在结果 1 1 研究背景 ( 一) 一致可分解3 一平衡设计 t 一平衡设计是组合设计理论的重要研究对象，有着广泛的应用背景( 参 见著作 9 】) t 一平衡设计( t - b d ) 是指一个二元组( 义，黟) ，其中x 是点( p o i n t ) 的一个 集合，侈是x 的子集( 称为区组b l o c k ) 的集合，满足，x 的任一t 元子集都 恰包含在惟一的一个区组中2 - b d 通常称为成对平衡设计( p a i r w i s eb a l a n c e d d e s i g n ) 若i x i = u 且召中的区组长度都取自由某些正整数组成的集合k ， 则把该t - b d 记为s ( ，k ，口) 当k = 砖) 时，则以是代替s ( t ，船，u ) 被称为 斯坦纳系( s t e i n e rs y s t e m ) s ( 3 ，4 ，u ) 被称为斯坦纳四元系( s t e i n e rq u a d r u p l e s y s t e m ) 并简记为s q s ( v ) 。 t 一平衡设计的概念最早由h a n a n i 于1 9 6 3 年提出，但他在文 1 8 】中用的 名称是“p a i r w i s cb l a n c c dt - d e s i g n ”本文采用的名称和记号来源于k r a m c rf 3 2 和k r a m c l 和k r c h c r 【3 3 】 设a ( k ，r ) = g c d ( k r ) ( 麻一r 一1 ) ( 忌一t + 1 ) ：七k ) ，k 1 a l l l c rf 3 2 】给出 了s ( t ，k ，u ) 存在的必要条件，具体叙述如下 定理1 】1 【3 2 】若存在s ( t ，k ，u ) ，则对任意0 7 t ，有 第一章 绪论研究背景 ( 秽一r ) ( 一r 一1 ) ( 。一t + 1 ) 三0 ( r o o dq ( k ，r ) ) 关于3 一平衡设计的存在性我们有下面的存在结果 定理1 1 2 ( 1 ) 1 7 】若u 三2 ，4 ( r o o d6 ) 且u 4 ，则存在s q s ( u ) ( 2 ) 1 8 若 三0 ( r o o d2 ) 且秒4 ，则存在s ( 3 ，( 4 ，6 ) ，钉) ( 3 ) f 2 9 ，2 7 】若v 三1 ，2 ，4 ，5 ，8 ，1 0 ( r o o d1 2 ) u 4 且t ，1 3 ，则存在 s ( 3 ， 4 ，5 ) ，v ) ( 4 ) 2 8 】若u 三0 ，1 ，2 ( r o o d4 ) ，u 4 且u 9 ，1 3 ，则存在s ( 3 ， 4 ，5 ，6 ) ，u ) 定理1 】3 ( 1 ) 1 9 ，2 7 】若u 为正整数且u 4 ，则存在s ( 3 7k l ，u ) ，其中k l = 4 ，5 ，6 ，7 ，9 ，1 1 ，1 3 ，1 5 ，1 9 ，2 3 ，2 7 ，3 1 ) ( 2 ) 4 3 若u 为正整数且1 1 5 ，则存在s ( 3 ，k 2 ，u ) ，其中k 2 = 5 ，6 ，7 ，3 9 ， 4 0 1 7 ，2 1 ，2 2 ，2 5 ，2 6 ( 3 ) 4 4 若t j 为正整数且u 6 ，则存在s ( 3 ，k 3 ，v ) ，其中妫= 6 ，7 ，8 ，4 0 ， 4 1 ，4 5 ，4 6 ，4 7 ，5 1 ，5 2 ，5 3 ，8 3 ，8 4 2 2 ，2 6 s ( t ，k ，u ) 被称为是可分解的( r e s o l l l a b l e ) 是指它的区组集能够分解成若干 部分( 称为分解类r e s o l u t i o nc l a s s ) ，其中每一部分都是x 的一个划分我 们把可分解的s ( t ，k ，t ，) 记为r s 他k ，移) r s ( t ，k ，口) 被称为是一致可分解的 ( u n i o 帆r e s o l v a b l e ) ，并记为u r s ( t ，k ，u ) ，是指它的每一个分解类中的区组都 具有相同的长度显然，r s ( t ，k ，移) 是一致可分解的可分解的s q s ( t ，) 简记 为r s q s ( v ) 设3 ( k ) = g c d k ：k ) ，结合定理1 1 1 我们有一致可分解t 一平衡设 计u r s ( t ，k ，口) 存在的必要条件 定理1 1 4 若存在u r s ( t ，k ，u ) ，则对任意0 r 2 时，一致可分 解t 一平衡设计的仅有的结论是建立了r s q s ( v ) 的存在性由定理1 1 4 知， 存在r s q s ( v ) 的必要条件是钉三4 ，8 ( r o o d1 2 ) 经过b o o t h 【7 】，g r e c n w c l l 和 l i n d n e r 1 6 ，h a r t m a n 2 3 ，2 2 ，2 4 】以及j i 和z h u 3 0 的努力，我们已经知道 这个必要条件也是充分的 定理1 1 5 2 4 ，3 0 】存在r s ( 2 x ( v ) 当且仅当u 兰4 ，8 ( 仇州t 2 ) 本文的目标之一是确定u r s ( 3 ， 4 ，6 ) ，口) 的存在谱由定理1 1 4 知，存在 u r s ( 3 ， 4 ，6 ，u ) 的必要条件是u 三0 ( r o o d4 ) 由定理1 1 5 我们只须要考虑剩 余情况v 三0 ( r o o d1 2 ) 即可 ( 二) 广义可分解斯坦纳四元系 广义可分解斯坦纳四元系最初由b o o t h 【7 ，g r e e n w e l l 和l i n d n e r 【1 6 】引 进其在研究可分解斯坦纳四元系时起着重要作用 u 阶广义可分解四元系是一个二元组( x ，日u 占) ，这里( x ，召) 是一个 s q s ( v ) ，为x 的所有二元子集的集合，满足：b u g 能被分解成礼= r ( 秒) = ( u 一1 ) ( u + 4 ) 6 个部分日u = p 1 l bj i r ，使得每一个只都为x 的一个划 分，简记为a r s q s ( v ) 当u 三4 ，8 ( r o o d1 2 ) 时，由定理1 1 5 中的r s q s ( v ) ，加上由其点集形成的 完全图的1 一因子分解，我们可以得到a a s q s ( v ) 于是只剩下t ，三2 ，1 0 ( r o o d 1 2 ) 时的a r s q s ( v ) 的存在问题h a r t m a n 和p h e l p s 提出下面研究问题( 1 2 6 】 中的o p e np r o b l e m1 2 8 5 ) 问题1 1 6 【2 6 】确立当钞三2 ，1 0 ( m o d1 2 ) 时a r s ( 2 s ( v ) 的存在性 3 第一章绪论 主要结果 h u r t m a n 和p h c l p s 【2 6 】同时猜想：对任意的t ，三2 ，1 0 ( r o o d1 2 ) 都存在 a r s q s ( v ) ( 三) ( 1 ，a ) 一可分解斯坦纳四元系 斯坦纳四元系s q s ( v ) ( x ，日) 称为是( ，r t ) 可分解的，如果其区组集8 能 被分解成r 个部分丌1 ，丌2 ，丌t ，使得对于任意i ，x 的任一元子集恰包 含在丌t 的。个区组中显然t = 1 或2 我们把t ，阶( ，o ) 一可分解斯坦纳四 元系记为r s q s ( t ，q ，v ) h a r t m a n 和p h e l p s 【2 6 】证明存在r s q s ( i ，口，u ) 的必要条件是： u 三2 ，4 ( r o o d6 ) ， q u 兰0 ( m o d4 ) ， 业普型三0 ( r o o d 乎) 本文将考虑( 1 d ) 一可分解斯坦纳四元系的存在性由简单的分析可知我 们只需要考虑( 1 ，2 ) 可分解斯坦纳四元系的存在性在必要条件中取o = 2 则可得u 兰2 ，1 0 ( r o o d1 2 ) 引理1 1 7 2 6 若存在r s q s ( 1 ，2 ，u ) ，则 三2 ，1 0 ( r o o d1 2 ) ha 1 t n l a n 和p h e l p s 进一步提出下面研究问题( 【2 6 中的o p e np r o b l e m 1 2 8 4 、 问题1 1 1 ，8 【2 6 】确立当u 三2 ，1 0 ( r o o d1 2 ) 时， r s q s ( 1 ，2 ，u ) 的存在性 对于其中最小值u ：1 0 ，利用b a r r a u 5 】的s q s ( 1 0 ) 在同构意义下的惟 一性，经过计算机的穷尽搜索我们已证明不存在r s q s ( 1 ，2 ，1 0 ) 这一事实 使得上述问题的研究更加困难 1 2 主要结果 本文将致力于研究一致可分解3 一平衡设计的性质和构作方法，区组长 度为4 和6 的一致可分解3 平衡设计的存在性，并且应用相关结果来研究 4 第一章绪论主要结果 广义可分解斯坦纳四元系和( 1 ，2 ) - 可分解斯坦纳四元系 在第二章我们确定了u r s ( 3 ， 4 ，6 ) ，4 ，0 的存在谱 定理2 2 5 对任意正整数n ，存在u a s ( 3 ， 4 ，6 ) ，4 礼) 在第三章中我们建立了广义可分解斯坦纳四元系的若干构造方法，首 先我们引入带广义可分解子系的广义可分解烛台形四元系的概念并建立下 面的构造方法 引理3 2 1 设存在a r c q s ( g ( n 州：s ) 若存在a r s q s ( g + s ：s ) ，则存在 a r s q s ( n g + 5 ：g + s ) 和a r s q s ( n g + s ：m g + 5 ) 其次我们将广义可分解烛台型四元系的概念推广到组长非一致的情况 并由此建立下面的构造方法 引理3 2 3 设存在a r c q s ( g n u l ：8 ) 若存在a r s q s ( g + s ：s ) 和a r s q s ( u + s ： s ) ，贝4 存在a r s q s ( n g 十u + s ：g - - t - s ) 和a r s q s ( n g + u - t - s ：u + s ) 为了应用上面所述的构造方法，我们需要建立更多的带广义可分解子 系的广义可分解烛台型四元系于是我们引入带一致可分解子系的一致可 分解3 一平衡设计的概念并由此建立下面的构造方法 引理3 2 4 设存在u a s ( 3 ，k ；v + l ，u + 1 ) 若对任意的赶a ，存在a r c q s ( 9 s ) 和型为9 七的r g d d ( 3 ，4 ，9 奄) ，则存在a r c q s ( g ( 邺) ：s ) 我们还建立了广义可分解烛台型四元系的三倍加权构造 引理3 3 1 设g 兰s 三0 ( r o o d2 ) 若存在a r c q s ( 9 3 ：s ) ，则存在a r c q s ( ( 3 9 ) 3 ： s ) 最后我们从两个方面对可分解烛台型四元系的概念进行推广首先烛 台型四元系的组长可以是非一致的，其次我们可进一步让区组长度也是非 一致的利用新引入的广义可分解烛台型四元系伴侣的概念建立下面的构 造方法 5 第一章绪论 主要结果 引理3 4 。4 设存在r s q s ( 2 n + 2 ：2 u ，+ 2 ) 。若存在广义可分解烛台型四元系 伴侣p a r a q s ( ( 6 9 ) 3 ：o ) 和p r c q s ( ( 6 9 ) 3 ：s ) ( 或者，p r c q s ( ( 6 9 ) 3 ：o ) 和 p a r c q s ( ( 6 9 ) 3 ：s ) ) ，则存在a r c q s ( ( 1 2 9 ) ”叫( 1 2 9 w ) 1 ：s ) 引理3 4 5 设存在r g ( n ，6 h ，4 ，3 ) 若存在型为( 6 9 ) 6 的r g d o ( 3 ，4 ，3 6 h ，9 ) ，存 在广义可分解烛台型四元系伴侣p a r c q s ( ( 6 9 ) 3 ：0 ) 和p r c q s ( ( 6 9 ) 3 ：5 ) ( 或 者，p r c q s ( ( 6 9 ) 3 ：0 ) 和p a r c q s ( ( 6 9 ) 3 ：s ) ) ，则存在a r c q s ( ( 1 2 9 ) 3 一1 ) ( 6 9 ( 6 h 一2 ) ) 1 ：s ) 利用这些构造，我们得到第三章的主要结论 定理3 6 5 设t j 三2 ，1 0 ( r o o d1 2 ) 若u 1 0 且ugf ，则存在a r s q s ( v ) 这里 f = v 三u ( r o o d1 4 4 0 ) ：让= 1 4 6 ，2 9 0 ，2 9 8 ，5 7 8 ，5 8 6 ，7 2 2 ，8 6 6 ，i 0 1 0 ，11 6 2 ，1 2 9 8 ，1 4 4 2 ， 1 4 5 0 在第三章的最后我们还给出确立当u f 时，a r s q s ( v ) 的存在性的一 条思路 定理3 7 2 若存在a r s q s ( 5 8 ：1 4 ) ，a r s q s ( 6 2 ：1 6 ) 和a r s q 9 ( 8 6 ：1 6 ) ，则当 u f 2 9 8 ，8 6 6 ) 时，存在a r s q s ( v ) 定理3 7 3 若存在a r s q s ( 3 8 ：1 6 ) ，a r s q s ( 5 8 ：1 4 ) 和a r s q s ( 6 2 ：1 6 ) ，则当 u f 时，存在a r s q s ( v ) 在第四章中我们建立了( 1 ，2 ) 一可分解斯坦纳四元系的若干构造方法，特 别是建立了下面的三倍构造方法 引理4 3 5 若9 三s + 6 ( r o o d1 2 ) 且s 兰2 ，1 0 ( r a o d1 2 ) ，贝0 存在( 1 ，2 ) 一r c q s ( 9 3 s ) 利用所建立的构造，我们得到第四章的主要结论 6 第一章绪论 主要结果 定理4 4 5 当t ，三2 6 ，5 8 ，7 4 ( r o o d9 6 ) 或2 j 三6 2 ，1 4 2 ，1 8 2 ( r o o d2 4 0 ) 时，存在 r s q s ( 1 ，2 ，v ) 在第四章的最后我们还引入了( 1 ，；t ，七) 一f l a m e 的概念，并由此建立下面 的构造方法 引理4 5 3 若存在s ( 3 ，k ，u + 1 ) 对任意k k ，若存在( 1 ，2 ) 一r c q s ( 9 ：s ) 和型为9 的( 1 ，2 ；3 ，4 ) - f r a m e ，则存在( 1 ，2 ) n c c 2 s ( 9 ”：8 ) 它为我们提供了确立r s q s ( 1 ，2 ，u ) 的存在性的一条思路，我们只需要对 所有k k 构造( 1 ，2 ) 一r c q s ( 1 2 一1 ：2 ) ，( 1 ，2 ) r c q s ( 1 2 七一1 ：1 0 ) 和型为1 2 的 ( 1 ，2 ；3 ，4 ) 一f r a m e ，其中k = ( 6 ，7 ，8 ，4 0 ，4 1 ，4 5 ，4 6 ，4 7 ，5 1 ，5 2 ，5 3 ，8 3 ，8 4 2 2 ，2 6 ) 7 第二章 一致可分解3 一平衡设计 基本构造 第二章一致可分解3 一平衡设计 本章我们研究一致可分解3 一平衡设计，确定u r s ( 3 4 ，6 ) ，4 ，t ) 的存在 谱由定理1 1 5 下面的分析我们只需考虑u r s ( 3 ， 4 ，6 ) ，1 2 7 7 ) 的存在性 2 1 基本构造 在介绍构作方法之前，我们需要下面的定义 设口是非负整数，t 是正整数，k 是由某些正整数组成的集合我们 把区组长度取自k 的u 阶可分组t 一设计( t - g d d ) 记为g d d ( t ，k ，u ) ，它是一 个三元组( x ，9 ，8 ) ，其中 ( 1 ) x 是一个u 元集( 称为点集( p o i n t s ) ) ； ( 2 ) 9 = g 。，g z ，) 是x 的非空子集的集合( 称为组集( g w u p s ) ) ，并且 满足( x ，乡) 是一个1 一平衡设计； ( 3 ) 召是x 的子集的集合( 称为区组集( b l o c k s ) ) ，其中，每一个子集( 区 组) 的长度都取自k ，而且，每一个区组与任意组至多相交于一个点； ( 4 ) 任意取自t 个不同的组的t 元点集恰包含在惟一的一个区组中 t - g d d 的型( t y p e ) 指多重集 i g i g 9 ) 型为m 七的g d d ( t ，k ，m k ) 称为横截设计，记为t d ( t ，惫，m ) 关于横截设 计的存在性，我们有h a n a n i 2 0 】中引用的由b r o u w c r 得到的下面的结论 引理2 1 1 ( 1 ) 设q 为素数幂，若t q4 - 1 ，则存在t d ( t ，q + i ，q ) ( 2 ) 若q = 2 7 ，则存在t d ( 3 ，q + 2 ，q ) ( 3 ) 若佗= 酊1 q 多2 靠9 ，其中q i 为不同的素数且帆为正整数，1 i s ， 则存在t d ( t ，k ，7 z ) ，其中k = 1 + , m a x t ，m i n q h ) ) g d d ( t ，k ，u ) 称为是( i ，q ) 一可分解的( ( 1 ：口) r e s o l v a b l e ) ，如果它的区组集能 被分解成若干部分( 称为q 一分解类( 口r e s o l u t i o nc l a s s e s ) ) ，使得该设计的每一 8 第二章一致可分解3 一平衡设计 个点恰包含在每一部分的n 个区组中 基本构造 我们把( 1 ：a ) 一可分解的g d d ( t ，k ，u ) 记为( 1 ，a ) 一r g d d ( t ，k ，u ) ，并把( 1 ，1 ) 一r g d d ( t ，k ，u ) 简记为r g d d ( t ，k ，u ) ( 1 ，a ) 一r g d d ( t ，k ，v ) 称为一致可分解的( 慨咖胤r e s o l v a b l e ) ，如果在每一个q 一 分解类中所有区组都具有同样的长度我们简记其为( 1 ，“) 一u r g d d ( t ，k ，v ) ， 当“= 1 时简记为u r g d d ( t ，k ，口) 若取定t d ( 3 ，口+ 1 ，q ) 的一个点，则所有包含此点的区组去掉此点之后恰 形成r t d ( 2 ，q ，q ) 的全部区组显然，去掉一个组的所有点可得到q 个互不相 交的r t d ( 2 ，q ，g ) ，它们形成一个r t d ( 3 ，q ，q ) 因而，我们有下面的结论 引理2 1 2 ( 1 ) 若q 为素数幂，且q 3 ，则存在r t d ( 3 ，q ，g ) ( 2 ) 若几= 疗1 9 芋2 簖一，其中吼为不同的素数且o l t 为正整数，1si s ， 则存在r t d ( 3 ，k ，n ) ，其中k = m a x 3 ，r a i n 盱；) ) 下面的结论来自j i 和z h u 3 0 引理2 1 3 3 0 对于任意正整数g ，存在型为9 4 的r g d d ( 3 ，4 4 夕) 我们还需要构造下而的一些小参数的设计，首先我们需要图论方面的 一些结论图g 的一个1 一因子是g 中边的集合f ，使得g 中的每一点恰在 f 中出现一次若g 的边集恰好构成g 的1 一因子的一个划分，则称g 存在 1 一因子分解本文用到图论方面名词和术语可参考著作 6 】 关于图的1 一因子分解的存在性，我们有下面的结论( 可以参见 2 】) 引理2 】4 ( 1 ) 若佗三0 ( r o o d2 ) ，则完全图存在1 一因子分解 ( 2 ) 若m 扎三0 ( r o o d2 ) ，则完全多部图研存在1 一因子分解。 为方便计，在下面的构造中点( z ，i ) 简记为z i 引理2 】5 存在型为2 6 的u r g d d ( 3 ， 4 ，6 ) ，1 2 ) 9 第二章一致可分解3 一平衡设计基本构造 证明：我们将在z 6xz 2 上构作型为2 6 的u r g d d ( 3 ， 4 ，6 ) ，1 2 ) ，它的组 是 z ) z 2 ，。z 6 设芦= 足，f 2 ，r ) 是z 6 上完全图的1 一因子分解 当1 i 5 且1 js2 时，令p ( i ，j ) = 。o ，b o ，c 1 ，d 1 ) ：hb ) 是只的第m 条边，( c ，d ) 是只的第( m + j ) 条边，1 7 n 3 显然，每一个p ( j ，j ) 都 是z 6xz 2 的一个划分，所有的p ( i ，j ) 以及 磊_ ( i ) ：i z 2 ) 形成型为2 6 的 u r g d d ( 3 ，f 4 ，6 ) ，1 2 ) 的全部分解类 口 引理2 1 6 存在r t d ( 3 ，6 ，5 ) 证明：我们将在z 5 z 6 上构作r t d ( 3 ，6 ，5 ) ，它的组是z 5x ，i z 6 区组集由下面的初始区组在( r o o d5 ，一) 作用下得到 每一个初始区组在( m o d5 ，一) 作用下生成一个分解类由此得到我们所需要 的r t d ( 3 ，6 ，5 ) 的全部分解类 口 为构造型为6 6 的r c d d ( 3 ，4 ，3 6 ) ，我们首先构造下面的( 1 ，2 ) 一r g d d 引理2 1 7 存在型为3 6 的( 1 ，2 ) 一r g d d ( 3 ，4 ，1 8 ) 证明：我们将在z 。8 上构作型为3 6 的( 1 ，2 ) 一r g d d ( 3 ，4 ，1 8 ) ，它的组是 ( 6 i + j ：i 玩) ，j z 6 区组集由下面的初始区组在( + 6r o o d1 8 ) 作用下得 到 a i ： 2 ，3 ，4 ，5 ) ， a 2 2 ，3 ，1 0 ，1 1 ， a a ： 2 ，3 ，1 6 ，1 7 ) ， o ，1 ，2 ，3 ) ； 0 ，1 ，8 ，9 ) ： 0 ，1 ，1 4 ，1 5 ) 、lrj、lrj、lrj、irj、rj、lrj、ir，、l， 5 5 5 5 5 5 5 5 4 2 3 l 2 0 3 4 ， ， ， ， ， ， ， ， 4 4 4 4 4 4 4 4 4 1 2 4 0 2 4 o ， ， ， ， ， ， ， ， 3 3 3 3 3 3 3 3 2 2 o 0 3 3 3 1 ， ， ， ， ， ， ， ， 2 2 2 2 2 2 2 2 2 o 3 1 4 2 0 3 ， ， ， ， ， ， ， ；1 l 0 1 1 2 2 3 4 4 ， ， ， ， ， ， ， ， 0 o 0 o 0 0 0 0 o 0 o 0 o 0 o o r t r t r v r l r t r t r t r t ， ， ， ， j ， ， 1lr，、lr，、lrj、lf、lrj、lrj、lr，、l， 5 5 5 5 5 5 5 5 2 3 1 4 0 3 4 2 ， ， ， ， ， ， ， ， 4 4 4 4 4 4 4 4 2 3 o 2 3 0 1 3 ， ， ， ， ， ， ， ， 3 3 3 3 3 3 3 3 l 4 4 4 2 2 0 o ， ， ， ， ， ， ， ， 2 2 2 2 2 2 2 2 1 4 2 0 3 1 4 2 ， ， ， ， ， ， ， ， ；i 1 】 0 o l 2 2 3 3 4 ， ， ， ， ， ， ， ， 0 o 0 0 0 0 0 0 o o o 0 0 0 0 o r j l 、r j l l r j l l rjlrjl，j1l r j l l r j l ， ， ， ， ， ， ， 、lrj、lr，、，1lrj、lrj、lr，、irj 1，、lr， 5 5 5 5 5 5 5 5 5 0 1 4 0 3 1 2 o 1 ， ， ， ， ， ， ， ， ， 4 4 4 4 4 4 4 4 4 o 1 3 4 l 3 4 1 2 ， ， ， ， ， ， ， ， ， 3 3 3 3 3 3 3 3 3 0 3 3 1 1 1 4 4 2 ， ， ， ， ， ， ， ， ， 2 2 2 2 2 2 2 2 2 o 3 l 4 2 0 3 1 4 ， ， ， ， ， ， ， ， ， ；11 1 o 0 1 1 2 3 3 4 4 ， ， ， ， ， ， ， ， ， 0 o o 0 0 0 0 0 0 0 o 0 0 0 0 0 o 0 rjll，j1rjll rjl、r1l r j l l r j l l r j i rt 、，、irj ，1 l 1 、， ， ， 1 o o ， ， ， o 1 7 ，1 1 u ， ， ，0 6 吐1 1 r t rt rt 第二章一致可分解3 一平衡设计 基本构造 1 ，1 0 ，3 ，1 7 ， 1 ，4 ，9 ，1 1 ， 1 ，1 6 ，1 5 ，5 ) - ， ( 1 ，1 1 ，2 ，1 6 ) ， 1 ，1 7 ，1 4 ，4 ) ， _ 【1 ，5 ，8 ，1 0 ) ， 1 ，9 ，2 ，5 ) ， 1 ，3 ，1 4 ，1 1 ， 1 ，1 5 ，8 ，1 7 ) ， _ ( 1 ，2 ，1 5 ，4 ) ， 1 ，8 ，3 ，1 6 ， 1 ，1 4 ，9 ，1 0 ) ， ( 1 5 ，1 1 ，0 ，2 ) ， 3 ，5 ，0 ，8 ) ， 9 ，1 7 ，0 ，1 4 ) ， 2 ，1 6 ，0 ，9 ) ， 1 4 ，4 ，0 ，3 ) ， 8 ，1 0 ，0 ，1 5 ) ， 2 ，1 7 ，0 ，1 0 ) ， 8 ，1 1 ，0 ，4 ) ， 1 4 ，5 ，0 ，1 6 ) ， 3 ，1 6 ，0 ，1 1 ) ， 1 5 ，4 ，0 ，1 7 ) ， 9 ，1 0 ，0 ，5 ) ， 0 ，2 ，7 ，4 ； o ，8 ，7 ，1 6 ) ； o ，1 4 ，7 ，1 0 ) ； o ，3 ，7 ，1 7 ； o ，1 5 ，7 ，5 ) ； o ，9 ，7 ，1 1 ) ； ( o ，1 0 ，1 3 ，3 ) ； o ，4 ，1 3 ，9 ) ； o ，1 6 ，1 3 ，1 5 o ，5 ，1 3 ，2 ) ； ( o ，1 7 ，1 3 ，8 ) ； o ，1 1 ，1 3 ，1 4 当1 m 1 5 时，p m = 以+ 6 i ：a ，i 历) 为一个2 分解类所有的 p m 形成型为3 6 的( 1 ，2 ) r g d d ( 3 ，4 ，1 8 ) 的全部2 一分解类 口 现在我们可以利用上面的型为3 6 的( 1 ，2 ) 一r g d d ( 3 ，4 ，1 8 ) 构造我们所需 要的r g d d 引理2 1 8 存在型为6 6 的r g d d ( 3 ，4 ，3 6 ) 证明：我们将在z 1 8 易上构造型为6 6 的r g d d ( 3 ，4 ，3 6 ) ，它的组为 6 i + j ：i z 3 z 2 ，j 磊 我们首先在x = 五易上构造型为2 4 的g d d ( 3 ，4 ，8 ) ，它的组为 是) x 历，七五，区组集列在下面 b 1 b 3 b 5 b 7 o o o ( o 2 2 2 2 3 1 3 l 3 0 3 0 b 2 j e 7 4 b 6 b 8 o 0 0 o 2 1 2 0 2 0 2 1 3 0 3 0 3 l 3 1 下面我们将把引理21 7 中型为3 6 的r g d d ( 3 ，4 ，1 8 ) 的点集加权2 ，即填 入型为2 4 的g d d ( 3 ，4 ，8 ) 为了得到分解类，我们在型为3 6 的r g d d ( 3 ，4 ，1 8 ) 的2 一分解类的区组上填入型为2 t 的r o d d ( 3 ，4 ，8 ) 的“半”个分解类( 即一 个区组) ，这要求两者的区组中点的顺序符合一定规律，这些已经在上面作 了限定。 当1s 1 1 5 时，我们把引理21 7 中么m 的第i 个区组记为a 幺a 中 的点按上面的顺序排列不妨设a 毛= y o ，y l , y 2 ，y 3 ) ，令盛( 奄，z ) = ( y 是，。) 为 11 ，争，小f影小如n他”m” 4 4 a 么a 4 4 a 4 4 a 4 第二章一致可分解3 一平衡设计基本构造 五z 2 到a 幺z 2 上的一个一一映射，当ls ! 8 时，令豫( b z ) = 盔。) ： ( k ，。) b f ) 则 1 的情况记n = 酊- 谚z 簖一，q t 5 为素数且q l q 2 1 ) 或n = g 呈2 口? 8 ，吼7 ，2 i 8 对前一种情况，记m = 鳍2 菪s 露一，则n = 5 m 由引理2 1 2 知存在 r t d ( 3 ，k ，m ) ，其中k = m i n q ? t ) 通过删去其中k 一6 个组上的所有的点，我 们得到r t d ( 3 ，6 ，m ) 注意到对引理2 1 6 中的型为5 6 的r g d d ( 3 ，6 ，3 0 ) 的每一 个点加权2 ，应用引理2 1 9 可以得到一个型为1 0 6 的r g d d ( 3 ， 4 ，6 ) ，6 0 ) 所 需的输入设计型为2 6 的u r g d d ( 3 ， 4 ，6 ) ，1 2 ) 可由引理2 1 5 得到我们可对 上述的r t d ( 3 ，6 ，m ) 的每一个点加权1 0 ，应用引理2 1 9 得到一个型为( 2 他) 6 的u r g d d ( 3 ， 4 ，6 ) ，1 2 n ) 所需的输入设计即为我们已得到的1 0 6 的r g d d ( 3 ， 4 ，6 ) ，6 0 ) 对后一种情况，与前一种情况类似应用引理2 1 2 我们可以得到r t d ( 3 ，6 ， 钆) 对该r t d 的每一个点加权2 ，应用引理2 1 9 和型为2 6 的u r g d d ( 3 ， 4 ，6 ) ， 1 2 ) ，我们同样可得到一个型为( 2 n ) 6 的u i r g d d ( 3 ， 4 ，6 ) ，1 2 n ) 最后应用引理2 1 1 0 于我们已得到的型为( 2 n ) 6 的u r g d d