（应用数学专业论文）kirkman带洞填充和覆盖.pdf

k i r k m a n 带洞填充和覆盖 摘要 填充和覆盖是组合设计理论的重要研究对象，有着广泛的应用背景本 文研究具有可分解性质的最优填充和最优覆盖的性质、构作方法和存在性 在第二章中，我们引入了两种重要的辅助设计，即r m g d d 和r h g d d ， 并且系统地研究了它们的构作方法特别地，我们把r s r e e s 构作。r g d d 的方法推广到构作r h g d d 另外，我们还建立了一个关于r h g d d 的有效的 复合构作在此基础上，我们在第三章中彻底解决了3 - r m g d d 和3 二r h g d d 的存在性问题 第四章分析了k h p d 和k h c d 的基本结构，较为系统地研究了它们的 构作方法特别地，我们给出了由f d g d d 和i r h g d d 来构作这两类设计鲍 方法 。 当g u 兰0 ( r o o d3 ) 且9 ( u 一1 ) 兰0 ( m o d2 ) 时，k h p d ( 9 让) ( k h c d ( g u ) ) 就 是型为扩的3 - r g d d ，其存在性由r s r e e 8 ( 1 9 9 3 ) 最终确定我们在第五 章中基本解决了当g u 兰0 ( m o d3 ) 且g ( - 一1 ) 三1 ( m o d2 ) 时，k h p d ( g u ) 和k h c d ( g u ) 的存在性问题从而我们基本确立了当g u 三0 ( r o o d3 ) 时， k h p d ( g u ) 和k h c d ( g 乜) 的存在性进一步地，第六章讨论了当g u 0 ( m o d 3 ) 时，k h c d ( g ) 的存在性问题：我们证明了当g 是偶数时，对任意的整数 6 ，除了一类可能的例外，存在一个k h c d ( g u ) 第七章列出了一些有待进一步研究的问题 关键词：k i r k m a n 带洞填充；k i r k m a n 带洞覆盖；可分组设计；f r a m e ；存在 性 作者：王成敏 导师：殷剑兴( 教授) k i r k m a n 带洞填充和覆盖英文摘要 k i r k m a nh o l e yp a c k i n g sa n dc o v e r i n g s a b s t r a c t p a c k i n g sa n dc o v e r i n g sa r ei m p o r t a n ts u b j e c t si nt h ec o m b i n a t o r i a ld e s i g nt h e o r y a n dh a v eb e e nw i d e l yu s e di nm a n ya r e a s i nt h i sd i s s e r t a t i o n ，w ei n v e s t i g a t et h e p r o p e r t i e s ，s t r u c t u r ea n de x i s t e n c eo fo p t i m a lr e s o l v a b l ep a c k i n g sa n dc o v e r i n g s i nc h a p t e r2 ，w ei n t r o d u c et w oe s s e n t i a la u x i l i a r yd e s i g n s ，r m g d da n dr h g d d ， a n ds t u d yt h e i rr e c u r s i v ec o n s t r u c t i o n ss y s t e m a t i c a l l y e s p e c i a l l y , t h em e t h o d su s e db y r s r e e st oc o n s t r u c tr g d da r eg e n e r a l i z e dt oc o n s t r u c tr h g d d b e s i d e s ，w eg i v e ap o w e r f u lc o m p o s i t i o nc o n s t r u c t i o nf o rr h g d d b yt h ec o n s t r u c t i o n se s t a b l i s h e d a b o v e ，w ec o m p l e t e l ys o l v et h ee x i s t e n c ep r o b l e m so f3 - r m g d da n d3 - r h g d di n c h a p t e r3 i nc h a p t e r4 ，w ea n a l y z et h es t r u c t u r ea n ds t u d yt h ec o n s t r u c t i o no fk h p da n dj k h c d i ns p e c i a l ，w em a k eu s eo ff d g d da n di r h g d dt oc o n s t r u c tt h e s et w ok i n d s o fd e s i g n s w h e ng u 三0 ( r o o d3 ) a n d9 ( t 一1 ) 兰0 ( r o o d2 ) ，ak h p d ( g u ) o rak h c d ( g 缸) i s j u s ta3 - r g d do ft y p eg 让，w h o s ee x i s t e n c eh a sb e e nc o m p l e t e l yd e t e r m i n e db yr s r e e s ( 1 9 9 3 ) i nc h a p t e r5 ，w ea l m o s ts o l v e dt h e e x i s t e n c ep r o b l e m so fk h p d ( g u ) sa n d k h c d ( g u ) sw h e ng u 兰0 ( m o d3 ) a n dg ( 牡- i ) 墨1 ( r o o d2 ) s o ，w h e ng u 兰0 ( r o o d3 ) ， t h ee x i s t e n c eo fk h p d ( g u ) sa n dk h c d ( g u ) sa r ea l m o s te s t a b l i s h e d f u r t h d r m o r e ，w e c o n s i d e rt h ee x i s t e n c eo fk h c d ( g q ) 7 sw h e ng u 0 ( r o o d3 ) i nc h a p t e r6 i ti sp r o v e d t h a tf o ra n ye v e nga n dp o s i t i v ei n t e g e r 让6 ，t h e r ee x i s t sa k h c d ( g 仙) e x c e p tf o ra c l a s so fp o s s i b l ee x c e p t i o n s i nc h a p t e r7 ，s e v e r a lf u r t h e rs t u d yp r o b l e m sa r ep r e s e n t e d k e y w o r d s ：k i r k m a nh o l e yp a c k i n g ；k i r k l n a nh o l e yc o v e r i n g ；g r o u pd i v i s i b l ed e s i g n ； f r a m e ；e x i s t e n c e i i w r i t t e nb yw a n gc h e n g m i n s u p e r v i s e db yp r o f y i nj i a n x i n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：；臣粒日期：( 超荆9 归 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名 导师签名锄勃? 、 涉 州r 、一 ) j e l 期：出蛐7 d 日期：塑擞c c 目 第一章绪论研究背景 第一章绪论 1 1 研究背景 填充和覆盖是组合设计理论的重要研究对象，有着广泛的应用背景本 文研究具有可分解性质的最优填充和最优覆盖的性质、构作方法和存在性 早在十九世纪五十年代，k i r k m a n 【3 1 】提出了下面问题： 问题1 5 个女学生每天3 人一组分成5 组出去散步，能否在一周内使得任意 2 人恰好同组一次 同一年，k i r k m a n 3 2 】和c a y l e y 【1 3 1 分别给出了这个问题的解后来这 个问题被推广为任意t ，三3 ( r o o d6 ) 个女生每天3 人一组出去散步，是不是 可以在( v - i ) 2 天里使得任意2 人恰好同组一次这就是缉合设计理论中著 名的k i r k m a n 女生问题，亦即k i k m a n 三元系的存在性问题 定义1 1 1 个阶数为t ，的k i r k m a n 三元系( k t s ( v ) ) 是一个对子似，b ) ，其 中x 是一个t ，元集合，b 是x 的某些三元子集的集合，召的元素称作区 组( b l o c k ) ，满足： ( 1 ) 任意两点恰同时出现在一个区组中； ( 2 ) 区组集可以划分为一些子集只( i n 每个只是点集x 的一个划分( 称 只为平行类( p a r a l l e lc l a s s ) ) 在经历了一个多世纪的沉寂之后，这个问题于1 9 7 2 年被r a y ：c h a u d h u r i 和w i l s o nf 3 9 1 解决 定理1 1 2 ( 【3 9 】) k t s ( v ) 存在当且仅当钐三3 ( r o o d6 ) 这个问题的解决大大推动了组合设计理论的发展，与之相关的大量问 题也随之被提了出来( 例如见 1 6 】和【2 0 】) 作为k i r k m a n 女生问题的推广，填 充和覆盖问题引起了人们大量的关注下面我们给出填充和覆盖的定义 1 第一章绪论研究背景 定义1 1 3 设k 是由一些正整数组成的集合一个填充( 覆盖) 是一个对子 ( x ，召) ，其中x 是一个移元集合，召是x 的大小属于k 的一簇子集，其元素 称为区组，满足x 的任意点对至多( 至少) 出现在一个区组中 填充( p a c k i n g ) 亦称为填充设计( p a c k i n gd e s i g n ) ，覆盖( c o v e r i n g ) 亦称为覆 盖设计( c o v e t i n gd e s i g n ) 一个阶数为 ，区组大小取自于集合k 的填充( 覆盖) 被记作p d ( v ，k ) ( c d ( v ，k ) ) 设( x ，召) 为一个p d ( v ，k ) ( c d ( v ，k ) ) 对x 中的任意点对e - - - z ，y ) ，记 m ( e ) 为召中包含点对e 的区组个数则p d ( v ，k ) 的边剩余( 1 e a v e ) ( c d ( v ，k ) 的边重复( e x c e s s ) ) 是指由所有1 一m ( e ) ( m ( e ) 一1 ) 重边e 张成的图，其中e 取 遍x 中的所有点对当一个填充( 覆盖) 的边剩余( 边重复) 为空集时，该填 充( 覆盖) 成为一个恰当设计本文讨论的填充( 覆盖) 是包含恰当设计作为 特殊情形的填充( 覆盖) 若一个填充( 覆盖) 的区组个数达到最多( 最少) ，则该填充( 覆盖) 称为 最优的( o p t i m a l ) 如果没有特别地说明，那么下面讨论的填充和覆盖都是指 最优的关于填充和覆盖问题的研究有着久远的历史，具体细节读者可参阅 综述文章【2 0 】 若一个p d ( v ，k ) ( c d ( v ，k ) ) 的区组集可以划分成一些平行类，则称该设 计是可分解的( r e s o l v a b l e ) ，记为r p d ( v ，k ) ( r c d ( v ，k ) ) 特别地，如果k = 3 ， 那么称其为k i r k m a n 填充( 覆盖) ，记为k p d ( v ) ( k c d ( t ，) ) - 而当移三3 ( r o o d6 ) 时，一个k p d ( v ) ( k c d ( v ) ) 就是一个k t s ( v ) 在1 9 7 4 年，k o t z i g 和r o s a 【3 3 】最先考虑了当t ，三0 ( r o o d6 ) 时k p d ( v ) 的存在性作为k t s 的推广，该填充称为一个阶数u 的拟k i r k m m a 三元系 ( n k t s ) 后来b a k e r 和w i l s o n 【6 】，b r o u w e r 【7 】等也对这个问题进行了深入地研 究，并由r e e s 和s t i n s o n 4 3 】最终确定了n k t s 的存在性谱 定理1 1 4 ( 3 3 ，6 ，7 ，4 3 】) 设口三0 ( r o o d6 ) ，则n k t s ( v ) 存在当且仅当t i 1 8 随后，a s s a f , m e n d e l s o h n 和s t i n s o n 【4 】研究了当t ，三0 ( r o o d6 ) 时，k c d ( v ) 的存在性，并由l a m k e n 和m i l l s 3 4 1 最终解决了这个问题 2 第一章 绪论 研究背景 定理1 1 5 ( 【4 ，3 4 1 ) 设钉兰0 ( r o o d6 ) ，则k c d ( v ) 存在当且仅当t ，1 8 e e m 夕，h o r 矗k 和w a l e s 【1 4 】对上述问题作了进一步地推广，考虑当可0 ( m o d3 ) 时，k p d ( v ) ( k c d ( v ) ) 的存在性为了满足可分解的性质，他们要求 当t ，- - l - 1 ( m o d3 ) 时，k p d ( v ) ( k c d ( v ) ) 的每一个平行类恰有一个长度为4 的 区组，其余区组长度均为3 ，而当t ，兰2 ( r o o d3 ) 时，k p d ( v ) ( k c d ( v ) ) 的每一 个平行类恰有一个长度为2 的区组，其余区组长度均为3 作为上述推广的一个应用，文 9 】证明了k p d ( v ) 可以用来构作密钥分 享方案中的门限方案 定理1 1 6 ( 【9 】) 如果存在一个r p d ( v ， t ，s ) ) ( s 伽) ，那么存在一个完美的 ( 2 ，叫) 门限方案，其可选密钥个数为m ( 口) 后来诸多文献讨论了当t ，0 ( r o o d3 ) 时，k p d ( v ) 和k c d ( v ) 的存在性 以及进一步的相关问题，主要有c a o 和t a n g 1 1 1 】，c a o 和z h u 【1 2 ，c a o 和d u 【1 0 】，c o l b o u m 和l i n g 【1 7 】以及p h i l l i p s ，w a l e s 和如【3 8 】等已知的一堑存在 结果列举如下 定理1 1 7 设正整数t ，兰2 ( m o d3 ) 且钐1 7 ，则存在k p d ( v ) 和k c d ( v ) 定理1 1 8 设正整数口兰1 ( r o o d3 ) 如果t ，三4 ( r o o d6 ) ( 秒1 6 ) 或t ，三1 ( m o d 6 ) 2 5 ) ，那么存在k p d ( 口) 定理1 1 9 设正整数口三1 ( r o o d3 ) 如果t ，1 9 且钐6 7 ，那么存在k c d ( t ，) 更进一步地，y i n 【5 1 】推广了k p d ( k c d ) 的概念，定义了k i r k m a n 带洞 填充( 覆盖) ，记为k h p d ( k h c d ) 下面我们先介绍h p d 和h c d 的概念，进 而给出k h p d ( k h c d ) 的定义 定义1 1 1 0 设t i ，9 ，k 为正整数且满足t k 3 一个洞大小一致的带洞填 充( 覆盖) 是一个三元组伍，9 ，b ) ，其中x 是一个g u 元集，乡是x 的u 个大 小为g 的子集( 称为洞或组) 且形成x 的一个划分，b 是一簇k 元子集( 称 为区组) ，满足不在同一个组上的点对至多( 至少) 出现在一个区组中 3 第一章绪论研究背景 该设计记作型为g u 的k - h p d ( k - h c d ) 一个型为9 u 的k - h p d 的存在性 与一个码长为t ，重量为k 的( g + 1 ) 一元常重码的存在性等价( 见【2 1 ，4 8 ，5 0 】) 文【4 9 】和【3 0 】分别确立了3 - h p d 和3 - h c d 的存在性 定理1 1 1 1 ( p 9 ) 对任意正整数g 和t 3 ，如果g ，让满足： ( 1 ) 夕三1 ，5 ( r o o d6 ) ，锰兰5 ( m o d6 ) ， ( 2 ) g 兰2 ，4 ( r o o d6 ) ，t 三2 ( r o o d3 ) ， 那么存在一个型为g “的3 - h p d ，其包含1 警【旦学j j 一1 个区组否则，存在 _ 个型为g u 的3 - h p d ，其包含【警【哆产j j 个区组 定理1 1 1 2 ( 【3 0 】) 对任意正整数g 和u 3 ，存在一个型为g u 的3 - h c d ，其包 含f 警旦【! ! 产1 1 个区组 如果一个h p d ( h c d ) 的区组集可以划分成一些平行类，那么该h p d 2 时，没有任何关于 k h p d ( 9 “) 和k h c d ( g u ) 存在性的结果 定理1 1 1 3 ( 【5 1 】) 设牡为正整数，则 ( 1 ) 如果t 27 且牡8 ，那么存在一个k h p d ( 2 u ) ； ( 2 ) 如果t 4 且t | 6 ，那么存在个k h c d ( 2 ) 1 2 主要结果 本文主要研究k h p d ( k h c d ) 的性质、构作方法和存在性 第二章定义了两类辅助设计，即具有可分解性质的m g d d 和h g d d ( 记 为r m g d d 和r h g d d ) 它们不但在本文研究某些可分解填充( 覆盖) 时起着 关键作用，而且本身也是两类广受关注的设计，在其他方面有着诸多的应用 ( 例如见【2 2 】) 随后我们系统地研究了这两类设计的构作方法特别地，我 们将r e e s 【4 0 】构作r g d d 两个非常有力的方法推广到构作r h g d d ，建立了 如下两个构作 定理2 3 3 设存在一个t d ( m ，q ) 和一个型为( m ，h n ) 的k - h g d d ，且该h g d d 的区组集包含s 个互不相交的区组大小为k ( k k ) 的m 平行类，则存在一 个型为( m ，( a h ) n ) 的k - h g d d ，其包含s 舻个区组大小为k 的互不相交的平 行类 定理2 3 5 如果以下条件均成立： ( 1 ) 一个型为沏，g n ) 的r - 可分解k - h g d d 存在，且对应每一个叱r ，该 5 第一幸 绪论 主要结果 h g d d 存在心个啦平行类； ( 2 ) 一个t d ( m ，z ) 存在，且c 是一个自同构群强可迁地作用在该t d 的每一 个组上； ( 3 ) 设 岛：j = 1 ，2 ，in ) 是c 的一簇子集，满足q = 易奉6 ：6 c ， j = 1 ，2 ，ir ) 在c 上是可分解的，且对每一个啦f ，在这一簇子集中有 r 个大小为的集合； 那么存在一个型为，( 1 9 ) n ) 的k - r h g d d 在第二章中，我们还建立了一个复合构作r h g d d 的方法 定理2 4 3 设m 和t 为正整数假设存在一个r t d ( m + l ，t ) 和一个型为 ( m ，h n e l ) 的( k ，a ) 一i r h g d d ，并且对每一个i ( 2 i t ) ，存在一个型为( 概+ e i ，e i ) m 的( k ，a ) i r g d d ，则存在一个型为( m ，胪e ) 的( k ，a ) i r h g d d ，这里e = 笔l 岛进一步地，如果hie 且一个型为( 仇，胪 ) 的( k ，a ) r h g d d 存在，那 么一个型为( m ，舻件m ) 的( k ，a ) 一r h g d d 也存在 作为3 - r h g d d 的一种特殊情形，3 - r m g d d 的存在性在第三章中被完 全确立 定理3 3 4 设正整数仇3 ，n 3 一个型为( m ，1 n ) 的3 - r m g d d 存在的必要 条件m n 三0 ( r o o d3 ) 和( m 一1 ) ( n 一1 ) 兰0 ( r o o d2 ) ，除了两个例外( m ，n ) 一( 3 ，6 ) 或( 6 ，3 ) 也是充分的 随后我们彻底解决了3 - r h g d d 的存在性问题 定理3 5 1 0 设正整数h 1 ，仇3 ，n 3 一个型为( m ，h 住) 的3 - r - i g d d 存 在的必要条件h m n 三0 ( r o o d3 ) 和h ( m 一1 ) m 一1 ) 兰0 ( m o d2 ) ，除了两个例外 ( ，仇，n ) = ( 1 ，3 ，6 ) 或( 1 ，6 ，3 ) 也是充分的 在第四章中，我们主要讨论了k h p d 和k h c d 的构作方法，除了一些 基本构作方法外，我们还通过f d g d d 和i r h g d d 来构作k h p d 和k h c d 6 第一章绪论 主要结果 定理4 3 5 如果存在一个型为( 让，夕i 1 谚始) 的3 - f d g d d ，且对每一个i ( 1 t n ) ，存在一个i k h p d ( ( 鲰+ t u ，铷) b ) ( i k n c i ) ( ( 9 , + t u ，t t ，) u ) ) ，涝足u ( ( 9 + 铷) u ) 一 u ( 叫u ) = 照哇丑( l ( ( 肌+ 叫) ) 一i ( w u ) = 匹幽2、j ，那么存在一个k h p o ( ( 9 + 叫) 乜) ( k h c d ( ( g + 伽) u ) ) ，这里9 = 叁1 吼如 定理4 3 8 设h m 三0 ( m o d3 ) 且g m 兰0 ( r o o d3 ) 如果一个型为，驴9 ) 的 3 - i r h g d d ，一个k h p d ( h m ) ( k h c d ( h m ) ) 和一个k h p d ( g m ) ( k h c d ( g m ) ) 都存 在，那么一个i h p d ( ( h n + 夕) m ) ( k h c d ( ( h n + 9 ) m ) ) 也存在 由定理4 3 8 ，我们有下面两个重要的推论 推论4 3 9 设h m 三0 ( m o d3 ) 如果存在_ 个型为，驴) 的3 - r h g d d 和一个 k i t p d ( h n ) ( k h c d ( h m ) ) ，那么也存在个i h p d ( ( h n ) 价) ( k h c d ( ( 概) m ) ) 推论4 3 1 0 设m 兰0 ( m o d3 ) 如果存在个型为( m ，1 n ) 的3 r m g d ，d 和一个 k p d ( m ) ( k c d ( m ) ) ，那么也存在一个k t t p d ( n m ) ( k h c d ( 扩) ) 第五章研究了当9 u 兰0 ( m o d3 ) ，夕( t 一1 ) 兰1 ( r o o d2 ) 且夕2 时，k h p d ( g ) 和k h c o ( g u ) 的存在性结合定理1 1 4 ，定理1 1 5 和引理3 1 3 ，我们基本确 立了当g u 兰0 ( r o o d3 ) 时，i h e i ) ( g 口) 和k h c d ( g ) 的存在性 定理5 4 3 对任意的正整数9 ，t 满足9 u 兰0 ( r o o d3 ) ，u 3 ，除了6 个例外和3 7 个可能的例外，一个k h p d ( 9 u ) 存在6 个例外为( 9 ，牡) ( 2 ，3 ) ，( 2 ，6 ) ，( 6 ，3 ) ， ( i ，6 ) ，( 1 ，1 2 ) ，( 3 ，4 ) ) ，3 7 个可能的例外为( 夕，t ) ( 九，6 ) lh e ) u ( 3 九，4 ) ，( h ，1 2 ) f h f 这里e = 1 1 ，1 3 ，1 7 ，1 9 ，2 3 ，2 9 ，3 1 ，3 7 ，4 1 ，4 3 ，6 7 ，7 9 ，8 9 ，9 7 ，1 1 3 ，1 2 7 ，t 3 t ，f = i x ，1 3 ，1 7 ，1 9 ，2 3 ，2 9 ，3 1 ，4 1 ，4 3 ，6 7 定理5 4 4 对任意的正整数夕，u 满足g u 三0 ( m o d3 ) ，u 3 ，除了6 个例外 和1 7 个可能的例外，一个i n c d ( g ) 存在6 个例外为( g ，t ) ( 2 ，3 ) ，( 2 ，6 ) ， ( 6 ，3 ) ，( 1 ，6 ) ，( 1 ，1 2 ) ，( 3 ，4 ) ) ，1 7 个可能的例外为( 夕，t ) ( 9 ，6 ) i9 e ) 。这里 e = 1 1 ，1 3 ，1 7 ，1 9 ，2 3 ，2 9 ，3 1 ，3 7 ，4 1 ，4 3 ，6 7 ，7 9 ，8 9 ，9 7 ，1 1 3 ，1 2 7 ，1 3 1 7 第一章绪论主要结果 进一步地，我们讨论了更一般的情况，即g u 0 ( r o o d3 ) 此时一个 k h p d ( g ) ( k h c d ( g “) ) 的每一个平行类中含有个非3 长区组在第六章中， 我们研究了g 为偶数的情形，基本解决了此时k h c d ( g ) 的存在性问题 定理6 3 9 设9 ，t 为正整数如果g 为偶数且t 6 ，那么除了一个例外和一 类可能的例外，存在一个k h c d ( g u ) ，其中例外为( g ，u ) = ( 2 ，6 ) ，一类可能的 例外为g 三1 0 ( r o o d1 2 ) 且t 兰2 ( m o d3 ) 8 第二章辅助设计及其构作方法定义及记号 第二章辅助设计及其构作方法 本章我们引入两种辅助设计，即r m g d d 和r h g d d ，并且讨论它们的 各种构作方法这两种设计不但在本文研究可分解填充( 覆盖) 时起着关键 作用，而且本身也是两类广受关注的设计( 例如见【2 2 】) 2 1 定义及记号 首先我们给出一些相关的定义和常用的记号 定义2 1 1 设t ，为非负整数，k 是某些正整数的集合一个阶数为t ，的可 分组设计( g d d ) 是一个三元组( x ，乡，召) 它满足以下四个条件： ( 1 ) x 是一个秒元集，它的元素称作点( p o i n t ) ； ( 2 ) 9 = g - ，g 2 ，) 是x 的某些子集的集合，且形成x 的一个划分多的 元素称作组( g r o u p ) ； ( 3 ) b 是x 的一些子集构成的集合，召的元素称作区组( b l o c k ) 对任意b 扫， 有i b ；k ，并且对任意g g ，有l bng 1s1 ； ( 4 ) x 中任意取自不同组上的点对，恰包含于召的a 个区组中 重集t = i a l ：g 乡) 称为该设计的型，这种设计简记为型为t 的( ka ) g d d 若9 包含地个大小为g i 的组( 1 t 仃) ，则用指数记号贫- 鲮h 鳄n 表 示该设计的型当k = 七) 时，简记k 为k 型为1 钞的( k ，入) g d d 通常被 称为成对平衡设计( p b d ) ，记作b ( k ，a ；口) 特别地，b ( k ，a ；u ) 被称为平衡不 完全区组设计( b i b d ) 型为扩的k - g d d 被称为横截设计( t d ) ，记作t d ( k ，n ) 众所周知，存在 一个t d ( k ，讫) 与存在k 一2 个n 阶互相正交的拉丁方( m o l s ) 等价 在一个g d d ( x ，9 ，艿) 中，如果存在一个子集acb 使得x 中的每一点 恰出现在4 的口个区组中，那么4 称为该g d d 的一个酗平行类若q = 1 ， 则4 为一个平行类 9 第二章辅助设计及其构作方法定义及记号 进一步地，如果一个g d d ( x ，乡，b ) 的区组集能够划分成子集4 1 ，4 2 ， 4 ，并且对每一个江1 ，2 ，r ，存在一个f 使得任意一个点z x 恰在 a 的啦个区组中出现，那么我们称这个g d d 是r 可分解的若r - - - q ) ，则 称该设计是q 一可分解的当f = 1 ) 时，简称为可分解的通常我们用( k ，入) r g d d 来表示可分解的( k ，a ) 一g d d ；用r b ( k ，入； ) 来表示可分解的b ( 七，入；t j ) ； 用r t d ( k ，n ) 来表示可分解的t d ( k ，n ) 定义2 1 2 一个双可分组设计( d g d d ) 是一个四元组( x ，多，兜，召) ，其中x 称 为点集；乡= g 。，g 2 ，g m 和咒= 日l ，h 2 ，玩 都是x 的个划分，乡 和咒中的元素分别称为组和洞；召是x 的一簇子集，b 的元素称为区组 这个四元组满足如下条件： ( 1 ) 对任意的区组b b ，有l b l k 对任意的区组b b ，任意的组g 9 和任意的洞h 咒，有i b ng l 1 且l bn h l 1 ； ( 2 ) x 中任意不在同一组上且不在同一洞中的点对恰出现在a 个区组中 该设计记为( k ，a ) d g d d 如果a = 1 ，那么进一步简记为k - d g d d 一 个型为( m ，h l l h 2 , z h 。n ) 的( ka ) 一d g d d 是指该d g d d 有m 个组，n = n l + 他+ + 嘞个洞，并且对每一个蓄( 1 l s ) ，存在啦个洞，使得其中的 每一个洞与每一个组都相交于个点需要指出的是，并不是所有的d g d d 都可以表示成这种形式，但本文主要考虑这种类型的d g d d d g d d 最早由 z h u 【5 2 】定义，后来被诸多学者广泛研究关于d g d d 的一般讨论可参阅文 f 1 5 】 型为( m ，1 n ) 的( k ，a ) d g d d 就是通常所说的网格可分组设计( m g d d ) i 记作型为( m ，1 n ) 的( k ，入) m g d d a s s a f 【1 】1 明确定义了m g d d ，并且证明了 ( 3 ，入) m g d d 存在的必要条件也是充分的随后，在文 2 】中m g d d 作为一个 有力的工具，在构作填充和覆盖中有着重要的应用进一步地，文【5 ，3 5 ，2 8 证明除了两个例外，( 4 ，a ) 一m g d d 存在的必要条件也是充分的文 2 8 】还讨 论了m g d d 在样本设计中的应用 1 0 第二章辅助设计及其构作方法 基本构作方法 型为( 仇，h n ) 的( k ，a ) 一d g d d 通常称为带洞可分组设计( h g d d ) ，记作型为 ( 仇，驴) 的( k ，a ) h g d d w e i 【4 6 最早对h g d d 进行研究，证明了( 3 ，入) 一h g d d 存在的必要条件也是充分的文【2 9 】进一步讨论了( 4 ，入) h g d d 的存在性问 题，证明了除了两个例外和4 个可能的例外，( 4 ，a ) 一h g d d 存在的必要条件 也是充分的 如果一个m g d d ( h g d d ) 的区组集能够划分成若干个平行类，那么称该 m g d d ( h g d d ) 是可分解的，记为r m g d d ( r h g d d ) 注：当h = 1 时，一个型为m ，h n ) 的( k ，入) r h g d d 就是一个型为( m ，1 n ) 的 ( k ，a ) r m g d d ，即r m g d d 是r h g d d 的一种特殊形式因此本章关于r h g d d 的构作方法同样适用r m g d d 正如上面提到的，m g d d 有着诸多方面的应 用，为了突出它的特殊性，我们仍然保留r m g d d 的记号 2 2 基本构作方法 在介绍构作方法之前，我们需要下面的定义 型为( m ，h g ) 的( k ，a ) d g d d ( x ，乡，咒，召) 称作型为，驴夕) 的( k ，a ) i h g d d 设咒= 日l ，日2 ，风+ 。 为洞的集合，为了区别唯一的一个与其余大小不一 样的洞( 不妨记为日n + 1 ) ，称该洞为奇异洞( d i s t i n g u i s h e dh o l e ) 特别地，一个 型为，h h ) 的( k ，a ) 一i h g d d 就是一个型为，护+ 1 ) 的( k ，a ) h g d d 如果一个型为( m ，h g ) 的( k ，a ) i h g d d 的区组可以划分为若干个平行类 和部分平行类，其中每一个部分平行类是x 玩+ ，的一个划分，那么称该 i h g d d 是可分解的，记作型为( 仇，h g ) 的( k ，a ) i r h g d d ， 简单计算知一个型为，h g ) 的( 七，入) 一i r h g d d 有a ( g - - 下h ) 丁( m - - 一1 ) 个部分平行 类，因此若一个i r h g d d 存在，则必有g h 特别地，如果g = h ，那么一个 型为( 仇，h g ) 的( k ，a ) 一i r h g d d 就是一个型为( m ，扩+ 1 ) 的( k ，a ) r h g d d 下面的两个引理就是通常所说的“填洞构作” 引理2 2 1 设正整数g ，h 满足hlg 若存在一个型为( m ，g n ) 的( k ，a ) 一i h t i g d d 和一个型为( 仇，舻 ) 的( k ，a ) 一r h g d d ，则存在一个型为( m ，h g l ) 的( k ，a ) 第二章辅助设计及其构作方法 基本构作方法 r h g d d 引理2 2 2 设正整数9 ，h 满足hig 若存在个型为( 仇，胪9 ) 的( k ，入) 一i r h g d d 和一个型为( m ，h g ) 的( k ，a ) 一r h g d d ，则存在一个型为( m ，h n + g ) 的( k ，a ) 一 r h g d d 在递推构作g d d 和p b d 时，经常使用加权方法和“w i l s o n 基本构作法 ( 见【4 7 】) 下面的引理是从一个r g d d 出发，用一些r h g d d 作为输入设计来 获得新的r h g d d 引理2 2 3 设存在一个型为g m 的( z ，a 1 ) r g d d 和一个型为( z ，h n ) 的( k ，a 2 ) r h g d d ，则存在一个型为( m ，( h g ) n ) 的( k ，a 1 a 2 ) r h g d d 进一步地，如果一 个型为( m ，舻) 的( k ，a 1 a 2 ) r h g d d 存在，那么一个型为( 仇，九叼) 的( k ，a 1 入2 ) 一 r h g d d 也存在 个型为l m 的( z ，入1 ) r g d d 就是一个r b ( i ，入1 ；m ) ，作为上面引理的一个 推论，我们有下面的结论 推论2 2 4 设存在r b ( i ，a l ；仇) 和一个型为( z ，驴) 的( k ，a 2 ) r h g d d ，则存在一 个型为( m ，胪) 的( k ，a l a 2 ) 一r h g d d 下面的引理是从一个r h g d d 出发，用一些r g d d 作为输入设计来得到 r h g d d 引理2 2 5 假设存在一个型为( 仇，h n ) 的( z ，a 1 ) r h g d d 和一个型为g 的( k ，a 2 ) r g d d ，则存在一个型为，( h g ) n ) 的( k ，入1 入2 ) 一r h g d d 一个型为矿的k - r g d d 就是一个r t d ( k ，9 ) ，从而我们有下面的结论 推论2 2 6 假设存在一个型为( m ，h n ) 的( k ，入) r h g d d 和一个r t d ( k ，9 ) ，则存 在一个型为( m ，( h a ) n ) 的( k ，a ) 一r h g d d 1 2 第二章辅助设计及其构作方法 r e e s 方法的变着 2 3 r e e s 方法的变着 在文【4 0 】中，r e e s 创造性地建立了两个构作r g d d 的方法，并以此成 功地解决了六个组的3 - r g d d 的存在性，从而完成了3 - r g d d 的存在性谱 后来这些方法在【4 1 ，4 2 ，2 3 】中被大量使用，充分显示了这两个构作的强大威 力在这一节中，我们将这两个构作方法推广到构作r h g d d 下面先给出几个有关的概念 定义2 3 1 设g 为作用在有限集x 上的置换群，若对任意的z ，y x ，都存 在一个g 使得( z ) - - - - y ，则称g 在集合x 上可迁，或称g 是x 上的一 个可迁群 定义2 3 2 设g 为作用在有限集x 上的置换群令z x ，g ，若( z ) - - z ， 则称z 为的固定点若g 中只有恒等置换才在x 中有固定点，则称g 在 x 上半正则若g 在x 上可迁且半正则，则称g 在x 上正则或强可迁j 定理2 3 3 设存在个t d ( m ，q ) 和一个型为( m ，扩) 的k h g d d ，且该h g d d 的区组集包含8 个互不相交的区组大小为k ( k k ) 的平行类，则存在一 个型为，( a h ) n ) 的k - h g d d ，其包含s a 2 个区组大小为k 的互不相交的平 行类 证明：设( x ，乡，咒，同是一个满足条件的型为( m ，h n ) 的k - h g d d 我们将 在点集x 磊上构作一个所需的h g d d ，其组集为 gx 磊lg 多，洞的 集合为 凰z 口l 噩咒) 设p 是一个包含区组大小为k ( k k ) 的戈上的q - 平行类，是一个 从p 中包含点z 的所有区组到磊上的双射下面根据p 中的区组构作点 集x z o 上的k 长向量的集合p ，： p ，= 【( z 1 ，。( b ) ) ，( x 2 ，：( b ) ) ，( x k ，七( b ) ) ) ：b = x l ，2 ；2 ，x k p ) 易见p ，是点集x 玩上的一个平行类令b p ，不妨记t d ( m ，q ) 的点集 为k 磊根据该t d ( m ，口) 的任一区组 ( 1 ，九。) ，( 2 ，h 2 ) ，( 仇，k ) ) ，构作一个 对应的区组 】3 第二幸 辅助设计及其构作方法 r e e s 方法的变着 ( z l ，仇。( b ) + h g ( z ，)