（应用数学专业论文）强度为3的四元系覆盖.pdf

强度为3 的四元系覆盖摘要 摘要 t - ( v ，尼，a ) 覆盖设计是一个二元组( x ，召) ，x 是u 元集合，层是x 上k 元 子集的多重集合，召的元素称作区组这个二元组满足：对于x 上的任意t 元子集，至少有a 个区组b b 包含该t 元子集，其中t 称为强度t - ( v ，k ，a ) 覆盖是斯坦纳系的推广，是组合设计中一类重要的设计使t - ( v ，k ，a ) 覆盖设 计存在的最小区组数称为覆盖数，记为g ( u ，k ，t ) 当t = 2 时，覆盖数已被 广泛研究”相比之下，对于t 2 覆盖数的研究不是很多，m i l l s 2 和季 利均 3 】等人基本确定了c ( v ，4 ，3 ) 本文利用g d d 设计，s f a n 设计和关于3 设计的基本构作，构作了一 些烛台形四元系进而，从指标为入的烛台形四元系或指标为入的烛台形四 元系覆盖设计出发，通过填洞构作获得四元系覆盖设计，从而基本确定了强 度为3 的四元系覆盖数，即： 设u ，a 是正整数，则c 2 ( 7 ，4 ，3 ) = i c 2 ( 6 ，3 ，2 ) + 2 ；除一些可能例外，其 余情形均成立 a ( u ，4 ，3 ) = f i g 一1 ，3 ，2 ) 1 + 1 ， ；a ( u 一1 ，3 ，2 ) 1 ， 当v = 7 且a 兰1 ( m o d4 ) 时， 或当u 三7 ，1 1 ( m o d1 2 ) 且a 三2 ( m o d4 ) 时， 或当钉兰3 ( m o d1 2 ) 且入三6 ( m o d1 2 ) 时； 其它情形， 其中可能例外是入兰1 ( m o d4 ) 且u = 1 2 k + 7 ，k 1 ，2 ，3 ，4 ，5 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 6 ，2 1 ， 2 3 ，2 5 ，2 9 ) ；u = 2 7 且入兰2 ，5 ，7 ( r o o d1 2 ) ；u = 3 5 且a 三3 ( r o o d4 ) 或入= 2 关键词：覆盖，烛台型四元系，s f a n 设计，可分组t 设计 作者：单晓敏 导师：季利均( 副教授) m i n i m u mc o v e r i n g so ft r i p l e sb yq u a d r u p l e s英文摘要 m i n i m u m ft r i p l e sb yq u a d r u p l e s l n l m u m c o v e r i n g so l e su ar ul e s上v l t a b s t r a c t a t 一( u ，尼，入) c o v e r i n gd e s i g ni sap a i r ( x ，8 ) ，w h e r ex i sau s e to fe l e m e n t( p o i n t s ) a n d 召i sac o l l e c t i o no fk - s u b s e t s ( b l o c k s ) o fx ，s u c ht h a te a c ht - s u b s e to fxo c c u r si n a tl e a s tab l o c k si nb ，w h e r eti sc a l l e ds t r e n g t h t h e 一v ，七，入) c o v e r i n gd e s i g ni sv e r y i m p o r t a n ti nd e s i g nt h e o r y t h ec o v e r i n gn u m b e rg ( ，k ，t ) i st h en u m b e ro fb l o c k si n am i n i m u mt - ( v ，k ，a ) c o v e r i n gd e s i g n f o r = 2 ，m u c hw o r kh a sb e e nd o n eo nc o v e r i n g n u m b e r sg ( u ，k ，2 ) ( s e e 1 ) h o w e v e r ，f o rt 2 ，n o tm u c hi sk n o w n i nt h i sp a p e r ，w eu s eg d d d e s i g n s ，8 - f a nd e s i g n sa n dh a r t m a n sf u n d a m e n t a l c o n s t r u c t i o nf o r3 一d e s i g n st oo b t a i ns o m ec q s so rc a n d e l a b r aq u a d r u p l ec o v e r i n g d e s i g n s t h e y , t o g e t h e rw i t hh o l e yq u a d r u p l ec o v e r i n gd e s i g n s ，a r eu s e dt od e t e r m i n e t h ec o v e r i n gn u m b e r s ，i e ， f g ( u ，4 ，3 ) = 【 日a ( 钉一1 ，3 ，2 ) + 1 ， f ；g 一1 ，3 ，2 ) ， i fv = 7a n da 三1 ( m o d4 ) ， o ri fu 三7 ，1 1 ( m o d1 2 ) a n d 入三2 ( m o d4 ) ， o ri fv 三3 ( m o d1 2 ) a n d 入三6 ( m o d1 2 ) ； o t h e r w i s e ， w i t he x c e p t i o n so fq ( 7 ，4 ，3 ) = f i q ( 6 ，3 ，2 ) + 2a n dp o s s i b l ee x c e p t i o n so f 入兰l ( m o d4 ) a n du = 1 2 k + 7 ，k 1 ，2 ，3 ，4 ，5 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 6 ，2 1 ，2 3 ，2 5 ，2 9 ) ；u = 2 7 a n da 三2 ，5 ，7 ( m o d1 2 ) ；口= 3 5a n da 兰3 ( m o d4 ) o ra = 2 k e y w o r d s ：c o v e r i n g ，c a n d e l a b r aq u a d r u p l es y s t e m ，s 一a nd e s i g n ，g r o u pd i v i s i b l et d e s i g n i i w r i t t e nb ys h a hx i a o m i n s u p e r v i s e db yp r o f j i 删u n 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明二本入承担本 声明的法律责任。 研究生签名：。垦堕丝日期：型：生兰 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：睾盛。塑日期：型望：幺! 互 导师签名：鼋；牲e l 期：丑竖兰 强度为3 的四元系覆盖 一弓1 言 1 1 定义 第一章引言 给定正整数u ，k ，t ，且u k t ，t - ( v ，七，a ) 覆盖设计( c o v e r i n gd e s i g n ) 是一 个二元组( 五召) ，x 是v 元集合，召是x 上后元子集的多重集合，1 3 的元素 称作区组( b l o c k ) 这个二元组满足：对于x 上的任意t 元子集，至少有a 个 区组b 1 3 包含该t 元子集，其中t 称为强度若将“至少”改为恰好”， 则称( x ，8 ) 是t - ( v ，k ，a ) 设计，亦称斯坦纳系，记作毋( t ，k ，u ) 斯坦纳系是组 合设计中的经典设计，并被广泛关注h a n a n i 【4 证明了& ( t ，k ，u ) 存在的必 要条件是对任意h = 0 ，1 ，t 一1 ，、v 。- 叫h 、k - h ) 为整数当参数u ，k ，t ，a 不满 足必要条件时，显然不存在斯坦纳系，此时我们可研究其覆盖设计由此可 以看出，t - ( v ，k ，a ) 覆盖设计是斯坦纳系的推广 对覆盖设计我们主要关心的是覆盖数给定正整数u ，k ，t ，a ，使t - ( v ，k ，a ) 覆盖设计存在的最小区组数称为覆盖数( c o v e r i n gm u n b e r ) ，记为a ( 秽，k ，t ) 当 入= 1 时我们通常记为c ( v ，k ，t ) 1 2 研究背景 覆盖设计是组合设计中一类重要的设计，它与t u r d n 设计，常重量覆 盖码( e t z i o n ，w e i 和z h a n g 5 】) ，抽奖模式( m o r l e y 和v a nr e e s 【6 】) ，q u o r u m 系 ( c o l b o u r n ，d i n i t z 和s t i n s o n 7 】) ，有向覆盖d a ( 口，k ，t ) 都密切相关( s k i l l i c o r n ， a s s a f 和殷剑兴 8 ，9 ，1 0 ) 例如，( x ，1 3 ) 是一个( v ，m ，k ) t u r d n 设计当且仅 当( x ，x b ：b 1 3 ) 为一个( v m ) 一( u ，御一k ，1 ) 覆盖，且t u r s n 覆盖数为 c ( v ，u k ， 一m ) 当钆一u 0 ，一个( n ，u u v ) 常重量覆盖码是一个( 扎，u ，v ) 覆盖设计且覆盖数为c ( 礼，乱，口) a s s a f ，s h a l a b y 和殷剑兴【9 在覆盖设计基础 上确定了有向覆盖数d e a ( v ，4 ，2 ) ，a s s a f 【1 0 】确定了a 为偶数时有向覆盖数 强度为3 的四元系覆盖一引言 d e x ( v ，5 ，2 ) 由a ( 口，k ，) 定义和简单计算，有a ( u ，庇，t ) ；g ( u 一1 ，k 一1 ，t 一1 ) 1 ， 其中r x l 表示不小于z 的最小整数令厶( u ，k ，) = ：西v - 1 铧 1 1 ， s c h s n h e i m 1 1 】证明了对所有的u 七t 1 ，均有a ( 钉，k ，t ) l a ( u ，七，亡) ，其中 厶( u ，七，t ) 称为s c h s n h e i m 下界 定理1 1 1 1 】( s c h 5 n h e i m 下界) g ( 口，后，t ) ；g ( u 一1 ，k 一1 ，t 一1 ) 1 ，其中m 表示不小于z 的最小整数进一步，a ( ，k ，t ) l a ( u ，k ，t ) ，其中厶( t ，k ，u ) = f * 昔警等1 ” 对覆盖数的研究最早是f o r t 和h e d l u n d ，他们证明了c ( v ，3 ，2 ) = l ( v ，3 ，2 ) 【1 2 g a r yh a g g a r d 把指标推广到一般a ，并确定了g ( u ，3 ，2 ) 【1 3 自此，许多 人对t = 2 做了进一步的研究h a n a n i 证明了 定理1 2 1 4 】当入 一1 ) 兰0 ( m o dk 一1 ) 且a v ( v 一1 ) 三1 ( m o dk ) 时，a ( u ，七，2 ) 厶( u ，k ，2 ) + 1 下文中用b a ( u ，七，t ) 表示定理1 1 和1 2 的下界( 厶( u ，k ，t ) 或l ( u ，k ，t ) + 1 ) 此时有： 定理1 3 1 3 】a ( u ，3 ，2 ) = 毋( u ，3 ，2 ) ，其中 酏3 2 ) = r 学学1 1 ，+ 1 ，卧p - 1 ) _ 0 ( m d d 翼激叫_ 1 ( m o d 3 埘； m i l l s 1 5 ，1 6 】确定了覆盖数c ( v ，4 ，2 ) ，a s s a f 1 7 证明了当a 1 时， a ( 口，4 ，2 ) = 厶( ，4 ，2 ) l a m k e n ，m i l l s ，m u l l i n 和v a n s t o n e 1 8 证明了u 兰2 ( m o d4 ) 时c ( v ，5 ，2 ) = l ( v ，5 ，2 ) m i l l s 和m u l l i n 【1 9 ，m u l l i n ( 2 0 证明了口三3 ( m o d4 ) 时c ( v ，5 ，2 ) = l ( v ，5 ，2 ) ，c ( 1 5 ，5 ，2 ) = l ( 1 5 ，5 ，2 ) + 1 经过很多人的努 力， 三0 ，1 ( m o d4 ) 时，覆盖数c ( v ，5 ，2 ) 1 】已基本确定 a s s a f , s i n g h 2 1 】 2 强度为3 的四元系覆盖一引言 和b l u s k o v ，g r e i g 2 2 】基本确定了当a 1 时a ( u ，5 ，2 ) 的值还有许多已知结 果，我们在此不再赘述，详见 1 】 与此相比，对于t 2 的覆盖数研究不是很多，除一些特定参数的覆盖 数c ( t ，尼，u ) 外( 见 1 】) ，已有结果主要局限于( t ，庇) = ( 3 ，4 ) h a n a n i 【2 3 证明了 当u 兰2 ，4 ( m o d6 ) 时存在斯坦纳系s ( 3 ，4 ，u ) ，即c ( v ，4 ，3 ) = l ( v ，4 ，3 ) h a n a n i 2 4 又证明了文( 3 ，4 ，u ) 存在的充要条件是a u 三0 ( m o d2 ) ，入( u 一1 ) 一2 ) 三0 ( m o d3 ) ，a v ( v 一1 ) ( 一2 ) 三0 ( r o o d8 ) 定理1 4 【2 4 】& ( 3 ，4 ， ) 存在的充要条件是知三0 ( r o o d2 ) ，a ( u 一1 ) ( 一2 ) 兰0 ( r o o d3 ) ，a u ( u 一1 ) ( u 一2 ) 三0 ( r o o d8 ) m i l l sf 2 在已有基础上证明了对所有u 7 ( m o d 1 2 ) ，c ( v ，4 ，3 ) = l ( v ，4 ，3 ) 成 立k a l b f l e i s c h 和s t a n t o n 2 5 ，s w i f t 2 6 各自证明了c ( 7 ，4 ，3 ) = l ( 7 ，4 ，3 ) + 1 = 1 2 ， m i l l s 【2 7 证明了c ( 4 9 9 ，4 ，3 ) = l ( 4 9 9 ，4 ，3 ) 当u 5 2 4 2 3 时，h a r t m a n ，m i l l s 和 m u l l i n 2 8 证明了c ( v ，4 ，3 ) = l ( v ，4 ，3 ) 最近，季利均【3 在此基础上进行了改 进，证明了除u = 7 和一些可能例外，当u 三7 ( m o d1 2 ) 时，c ( v ，4 ，3 ) = l ( v ，4 ，3 ) 成立 定理1 5 【2 ，3 ，2 5 ，2 6 ，2 7 ，2 8 对任意正整数v ，c ( v ，4 ，3 ) = l ( v ，4 ，3 ) 成立，其中例外 是c ( r ，4 ，3 ) = l ( 7 ，4 ，3 ) + 1 ，可能例外是口= 1 2 k + 7 ，尼c = _ 1 ，2 ，3 ，4 ，5 ，7 ，8 ，9 ，1 0 ，1 1 ， 1 2 ，1 6 ，2 1 ，2 3 ，2 5 ，2 9 本文主要把指标推广到一般a ，研究( t ，七) = ( 3 ，4 ) ，a 1 的覆盖数，即强 度为3 的四元系覆盖 1 3 研究问题和结果 本文主要从指标为a 的烛台形四元系或指标为a 的烛台形四元系覆盖设计 出发，通过填洞构作获得四元系覆盖设计，即定理2 2 为了得到出发的烛台 3 强度为3 的四元系覆盖 一引言 形四元系或烛台形四元系覆盖设计，我们利用g d d 设计，s 一 a n 设计和关 于3 设计的基本构作，构作了一些烛台形四元系 我们对四元系覆盖设计的“过剩”作了细致分析，改进了某些情形的四 元系覆盖数的下界 设，b ) 是一个3 一( u ，七，a ) 覆盖设计，是x 中一些三元集的多重集 合若x 中任意三元集 z ，y ，z ) 在中出现i b b ：【z ，y ，z ) b ) i - a 次， 则称为该覆盖设计的“过剩”( e x c e s s ) 设x 1 ，x ：，轨是x 中t 个互异元令f ( z 1 ，z z ，耽) 表示包含 。，z 。， ，钆 的区组数，如( ，现) 表示过剩中包含 ，孔 的三元集 个数，由覆盖设计的定义和简单计算知，一个具有b 个区组的四元系覆盖设 计满足： 3 f ( x ) = 坐删2 + 尼( z ) ； ( 1 ) 吲= $ x 掣= 4 b 一巡蒯6 ( 2 ) 定理1 6 若钞= 7 且a 兰1 ( r o o d4 ) ，或 三7 ，1 1 ( m o d1 2 ) 且a 三2 ( m o d4 ) ，或 u 三3 ( r o o d1 2 ) 且a 三6 ( m o d1 2 ) ，贝0g ，4 ，3 ) ：a 一1 ，3 ，2 ) 1 + 1 证明：对于u = 7 且入兰1 ( r o o d4 ) ，由定理1 1 知，a ( 7 ，4 ，3 ) ；a ( 6 ，3 ，2 ) 假 定g ( 7 ，4 ，3 ) = f ；a ( 6 ，3 ，2 ) 1 ，则由 2 7 】知，过剩占满足：仅有一个点对z ，y x 出现7 次，其余点对均出现一次而i x i = 7 ，则必存在一点z 7 x 协秒) 且 尼( z 7 ，z ，y ) 1 ，这与，e ( z ，秒) = 1 矛盾，所以a ( 7 ，4 ，3 ) f ：a 一1 ，3 ，2 ) - 4 - 1 对于u 三7 ，1 1 ( r o o d1 2 ) 且a 三2 ( r o o d4 ) ，或u 三3 ( r o o d1 2 ) 且a 三6 ( m o d1 2 ) ， 由定理1 1 知，a ( u ，4 ，3 ) f ：a ( t ) 一1 ，3 ，2 ) i 假定a ( u ，4 ，3 ) = f ；a 一1 ，3 ，2 ) i ， 则由( 2 ) 和定理1 3 知过剩含两个三元集于是，对过剩中出现的点z ，有 l 尼( z ) 2 又由( 1 ) 知尼( z ) 兰0 ( r o o d3 ) ，这就产生矛盾所以a ( 口，4 ，3 ) i a ( u 一1 ，3 ，2 ) + 1 口 4 强度为3 的四元系覆盖引言 由定理1 1 和1 6 ，我们定义如下下界： f i g ( u 一1 ，3 ，2 ) + 1 ， 当口= 7 且a 兰1 ( r o o d4 ) 时， 酏4 7 3 ) = 甏v 恻- - 7 , 1 ( 1 删( m 0 1 2 ) d1 2 且) k 脚a = _ ( 2 删( m o d4 ) 日翳 【 ；a ( u 一1 ，3 ，2 ) i ， 其它情形 本文将证明除一些例外和可能例外，覆盖数a ( u ，4 ，3 ) 达到下界磁( u ，4 ，3 ) ，具 体叙述如下： 定理1 7 设v ，a 是正整数，则q ( 7 ，4 ，3 ) = 展( 7 ，4 ，3 ) + 1 ；除一些可能例外， 其余情形均成立g ( u ，4 ，3 ) = b i ( v ，4 ，3 ) ，其中可能例外是入三1 ( m o d4 ) 且 u = 1 2 k + 7 ，k 1 ，2 ，3 ，4 ，5 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 6 ，2 1 ，2 3 ，2 5 ，2 9 ) ；v ；2 7 上王入三2 ，5 ，7 ( m o d1 2 ) ；v = 3 5 且a 三3 ( m o d4 ) 或a = 2 ： 5 强度为3 的四元系覆盖 二 递推构作 二递推构作 为了建立本文的主要结果，我们需要一些设计理论中的术语和相关的结果， 本节将对此做些介绍 烛台形四元系在构造斯坦纳四元系时发挥了重要作用，具体可参阅文 献【2 9 设u ，s 为非负整数，t 为正整数，k 为某些正整数的集合一个阶 数为u 指标为入的烛台形t 设计( c a n d e l a b r at - s y s t e m ，t - c s 3 0 ) 是一个四元组 ( x ，s ，夕，a ) ，它满足下列五个条件： ( 1 ) 是一个v 元集； ( 2 ) s 是x 的一个8 元子集，称作干( s 匏呐； ( 3 ) 9 = g ，g 2 ，) 是由x 的一些非空子集构成的集合，且划分x 8 ，9 的 元素称作组或分支( g r o u p s 或b r a n c h e s ) ； ( 4 ) 4 是由x 的一些子集构成的多重集合，称其元素为区组，且对每个a 4 ，i a i k ； ( 5 ) 对于x 的每个t 元子集t ，如果对每个i ，i tn ( s ug i ) i t ，那么r 恰好 包含于4 中a 个区组，而对于任意i ，sug ；的任意t 元子集都不包含 于4 中任何区组 通常把这样的设计记作c & ( t ，k ，u ) 当a = 1 时，c & ( t ，k ，u ) 简记为c s ( t ，k ，u ) 若9 包含他个大小为g 。的组( 1 i r ) ，并且干的大小为s ，则称此c s 的型 为( 夕? ，9 孑2 够r ：s ) 若将此设计中“恰好改为“至少”，则称此设计是型为 ( 9 ，9 ；。妒：s ) 指标为a 的烛台形t 覆盖设计型为g n 的c s a ( g ”：0 ) 通常 称为g 设计，记为g an ，g ，k ，t ) 当k = 4 ) 时，c s a ( 3 ，k ，口) 称为指标为入的烛台形四元系，记为c q & ( 夕 z 鳢2 卵r ：s ) 对任意偶数s ，夕三0 ，s ( m o d6 ) 且g s ，h a r t m a n 【3 1 ，3 2 】直接构 6 强度为3 的四元系覆盖 二 递推构作 作了c q s ( 9 3 ：s ) 对任意偶数s ，g 且g s ，g r a n v i l l e 和h a r t m a n 【3 3 构作了 c q s ( 9 4 ：s ) m i l l s 和季利均证明了： 定理2 1 2 ，3 4 ，3 5 】对任意尼0 ，c q s ( 6 詹：0 ) 和c q s ( 1 2 ：0 ) 都存在对任意 k 3 ，c q s ( 6 ：6 ) ，c q s ( 1 2 惫：6 ) 和c q s ( 1 2 七：2 ) 都存在 下面给出一些关于c q & ( 贫1 夕孑2 好r ：s ) 存在的预备结论： 引理2 1设入是正整数，对任意偶数g ，c q s a ( 9 2 ：0 ) 存在；对任意g 2 ， c q 岛 ( 夕2 ：0 ) 存在 证明：若g 为偶数，设 硝，磅，巧一。) 是顶点集为g i0 = 1 ，2 ) 的完全图 的1 一因子分解，令召= _ 【_ z ，西，z ，叫) ：【z ，可) 碍，z ，叫) 碍，1 j g 一1 ， 则召是以g 。，g ：为组的c q s ( 9 2 ：0 ) 的区组集每个区组重复a 一1 次得到 c q s ) , ( 9 2 ：o ) 在h a r t m a n 和p h e l p s 3 6 】给出的四面体四元系2 倍构造中可以 看出对任意g 2 ，c q s 2 ( 9 2 ：0 ) 存在每个区组重复a 一1 次得到c q a ( 夕2 ：o ) 口 引理2 2 若对每个1 i 入，c q s ( g ? 1 9 ；2 妒：s t ) 存在，且1 9 曼a 鼠兰 0t o o d 入) ，则c q & ( 9 n l ，g ；：妒：单) 存在 证明：设x 是一个1 的o t 吼元集，9 将x 划分成o t 个大小为g i 的组 ( 1 i r ) 设& 是一个s t 元集( 1 i a ) ，( xu & ，最，毋，a ) 是一个 c q s ( g r l 夕；2 妒：s i ) ( 1 i a ) 若1 t a s t 三0 ( r o o d 入) ，可将上列所有 烛台型四元系柄上的点平均分成率份，每份入个点，将这入个点标记 成一个点，可得一个c q s a ( 夕? ，夕2 m 9 7 r ：毕) 凸 由烛台型四元系构作四元系覆盖设计时，需要将带洞四元系覆盖作为 辅助设计，因此，我们下面介绍带洞四元系覆盖设计 指标为入，洞大小s 的u 阶带洞四元系覆盖设计是一个三元组( x ，s ，4 ) ， 7 强度为3 的四元系覆盖 二 递推构作 其中x 为口元集，s 是x 的一个8 元子集，4 是x 中四元子集的多重集 合，称作区组( b l o c k s ) ，满足：对于x 上的任意三元子集r ，如果t 仁s ，那么 t 至少包含于4 的a 个区组中，而s 中任意三元子集不包含于a 中任何区 组若将“至少”改为“恰好 ，则称此带洞四元系为恰当的，记作日q & ：s ) 下面给出一个由烛台型四元系或烛台型四元系覆盖设计和带洞四元系 覆盖设计构作四元系覆盖设计的方法，它简单但非常有用 定理2 2假定c q & ( 9 3 订1 9 ；2 妒：8 ) 或型为( 9 3 贸，9 ；。鲜r ：s ) ，指标为a 的烛台形四元系覆盖设计存在，其区组数为a 若区组数为玩指标为a 的 g o + 8 阶四元系覆盖设计，以及区组数为鼠，指标为入洞大小为s 的g i + 8 ( 1 i r ) 阶带洞四元系覆盖设计都存在，则区组数为a + 岛+ 。 衙啦且， 指标为a 的u = 8 + g o + 。 衙a i g 。阶四元系覆盖设计存在 证明：设( x ，s ，9 ，a ) 是已知的c q & ( 9 3 9 7 1 鳢2 妒：8 ) 或型为( 砧9 ；1 谬妒： s ) ，指标为a 的烛台形四元系覆盖设计从组集乡中取定一个大小为g 。的 组g ，由假定，可在点集g us 上构作一个区组数为岛指标为入的g o + 8 阶四元系覆盖设计，记它的区组集为对9 中任意不为g 的组g ，由假 定，可在点集g 7us 上构作一个以8 为洞的区组数为鼠指标为a 的g i + 8 ( 1 i r ) 阶带洞四元系覆盖设计，其中ig ，l = g i ，记它的区组集为，则 ，a u 召gu ( u g j 9 ，g ，g 膨g ，) ) 是一个指标为入的_ u = s + g o + 1 s t ra i g i 阶四元 系覆盖设计，其区组数为a + 玩+ 1 3 且m 5 时，h ( m ，r ，4 ，3 ) 存在的充要条件是 r m 三0 ( m o d2 ) 且r ( m 一1 ) ( m 一2 ) 三0 ( r o o d3 ) 当m = 5 ，r 为偶数且r 2 ， 7 1 0 ，2 6 ( r o o d4 8 ) 时，h ( 5 ，_ 4 ，3 ) 存在 设( x ，s ，乡，丁) 是干大小为s 的c 3 ( 3 ，k ，u ) ，其中s = ( - ，。) 对 于1 i 8 ，令鼠= j e 7 z t ) ：b t ，x i b ，t 7 = b t ：bns = 仍) ， 则( x ，9 ，1 3 。，玩，r ) 称为s f a n 设计，记作s f g ( 可参阅 3 9 】) 反过来，设 ( x ，9 ，8 1 ) 一，统，丁) 是型为( 卯1 鳢2 扩：8 ) 的s - f g 对于1 i s ，令矽= bu o o t ) ：b 召) ，设s = 0 0 1 ，o 。) 且s nx = d ，则( xus ，s ，( u 1 9 曼。饯u 刃) 是型为( 贫，鳢2 矿：8 ) 的3 一c s 下面的构作是h a r t m a n 关于c s ( 3 ，k ，u ) 基本构作的一种特殊情况 定理2 4 3 9 】假定存在一个型为贫1 铲卵”的s f g ( 3 ，( 1 ( 1 ，k s ，k t ) ，u ) 若 对任意的k 。k 1 ，存在型为( b 七，：e 1 ) 的c s ( 3 ，l ，b k l + e 1 ) ，对任意的 ( 2 i s ) ，存在型为6 e i 的a d d ( 3 ，l ，b k i + e t ) ，对任意的k k r ，存在 型为6 j c 的a d d ( 3 ，l ，b k ) ，则存在型为( ( 的- ) n 1 ( 的z ) n 2 ( 吼) n ) ：，豳e ) 的 9 强度为3 的四元系覆盖 二 递推构作 c s ( 3 ，l ，b y + 1 t 。岛) 引理2 3 设入是正整数对任意七3 ，当( g ，8 ) ( 1 2 ，1 2 ) ，( 1 2 ，1 0 ) ) 时， c q s ( g 知：8 ) 存在；当( 9 ，s ) ( 1 2 ，1 1 ) ，( 1 2 ，9 ) ，( 1 2 ，7 ) ，( 1 2 ，3 ) ，( 6 ，3 ) ) 时，c q s 2 a ( 9 七： 8 ) 存在对任意k 1 ，c q s ( 6 2 七+ 1 ：2 ) 和c q s 2 a ( 6 2 七+ 1 ：1 ) 存在 证明：由定理2 3 知对任意k 3 ，h ( k + l ，1 2 ，4 ，3 ) 存在把一个组g 看作 干，由引理2 1 知，在任意两个不同组g ，g z ( g ，g ，g 。g ) 上可构作 c q s ( 1 2 2 ：o ) ，这样就得到c q s ( 1 2 七：1 2 ) 为了构作c q s ( 1 2 ：1 0 ) 和c q s ( 6 2 缸+ 1 ：2 ) ，我们需要先构作两个小设计 由【4 0 知存在包含子设计s ( 2 ，4 ，1 6 ) 的s ( 3 ，4 ，1 6 ) ，删去其中一点可得一个型为 3 5 的2 - f g ( 3 ，( 4 ，3 ，4 ) ，1 5 ) 根据 3 3 和定理2 3 ，分别存在c q s ( 2 4 ：o ) ，c q s ( 2 4 ：2 ) 和型为2 4 的g d d ( 3 ，4 ，8 ) 于是利用定理2 4 得到c q s ( 6 5 ：2 ) 和c q s ( 6 5 ：4 ) 当k 三0 ，1 ( r o o d3 ) 时，由【2 3 知从s ( 3 ，4 ，2 后+ 2 ) 中删去两点得到一个型 为2 。的2 - f g ( 3 ，( 3 ，3 ，4 ) ，2 k ) 根据 3 1 ，3 2 和定理2 3 ，分别存在c q s ( 6 3 ：4 ) 和 型为6 4 的g d d ( 3 ，4 ，2 4 ) 于是利用定理2 4 得到一个c q s ( 1 2 詹：l o ) 当k 三2 ( m o d3 ) 时，由定理2 1 知存在c q s ( 6 ( 州) 3 ：o ) ，从两个不同组中 各删去一点得到一个型为2 七的2 - f g ( 3 ，( 【3 ，5 ) ， 3 ，5 ) ， 4 ，6 - ) ，2 七) 由【3 1 ，3 2 和 前面构作知分别存在c q s ( 6 3 ：4 ) 和c q s ( 6 5 ：4 ) ，且由定理2 3 知存在型为 的c o d ( 3 ，4 ，6 j ) ( j 4 ，6 ) ) 于是利用定理2 4 得到一个c q s ( 1 2 2 ：l o ) 至此 我们得到对任意k 3 ，c q s ( 1 2 七：1 0 ) 存在 由【2 4 知对任意后1 ，s ( 3 ， 4 ，6 ) ，2 k + 2 ) 存在，删去其中一点可得型为 1 2 血+ 1 的1 - f g ( 3 ，_ 3 ，5 ) ， 4 ，6 ) ，2 k + 1 ) 根据【3 1 ，3 2 和前面构作，存在c q s ( 6 3 ：2 ) 和c q s ( 6 5 ：2 ) 由定理2 3 知存在型为6 j 的c o d ( 3 ，4 ，6 j ) ( j _ 4 ，6 ) ) 于是利 用定理2 4 可得一个c q s ( 6 2 + 1 ：2 ) 由定理2 1 知对任意k 1 ，c q s ( 6 2 m ：0 ) 存在，则由引理2 2 知存在c q s 2 ( 6 2 七+ 1 ：1 ) 每个区组重复a 一1 次，则得到 c q 岛a ( 6 2 1 ：1 ) 1 0 强度为3 的四元系覆盖 二 递推构作 由定理2 1 和前面构作知对任意k 3 ，c q s ( 1 2 2 ：6 ) ，c q s ( 1 2 k ：2 ) ， c q s ( 6 k ：o ) ，c q s ( 1 2 七：o ) ，c q s ( 6 k ：6 ) ，c q s ( 1 2 知：1 2 ) ，c q s ( 1 2 七：1 0 ) 都存在，则 由引理2 2 知当( g ，s ) ( 1 2 ，1 1 ) ，( 1 2 ，9 ) ，( 1 2 ，7 ) ，( 1 2 ，3 ) ，( 6 ，3 ) ) 时，c q s 2 ( g 七：s ) 存 在每个区组重复a 一1 次，得到c q 岛a ( 夕：s ) 口 下面的定理是指标为a 的烛台形四元系覆盖设计的存在性结果，应用 引理中定义的下界耳( u ，4 ，3 ) 我们得到： 定理2 5 对任意奇数a ，当( g ，s ) ( 1 2 ，3 ) ，( 1 2 ，1 1 ) ) 时，存在型为( g 知：s ) ，区组 数为磁( ，4 ，3 ) 一k b i ( g + s ，4 ，3 ) + ( 七一1 ) 磁( s ，4 ，3 ) ，指标为入的 = g k + 8 阶烛 台形四元系覆盖设计；当( g ，8 ) ( 6 ，1 ) ，( 6 ，3 ) ) 时，存在型为( 9 2 + 1 ：s ) ，区组数 为磁( u ，4 ，3 ) 一( 2 k + 1 ) 磁 + s ，4 ，3 ) + 2 七磁( s ，4 ，3 ) ，指标为入的u = ( 2 k + 1 ) g + 8 阶烛台形四元系覆盖设计 证明：对给定的g ，s ，由定理2 1 和引理2 3 知存在c q s ( g 七：s 一1 ) 或c q s ( 9 2 k + 1 ： s 一1 ) ，设( x ，e 乡，4 ) 是这样的设计，其中干为 ，。2 ，。纠) 由 4 1 】知， 对任意的m 3 ，g ( m ，夕，3 ，2 ) ( g 6 ，1 2 ) 存在设是9 上的一个h ( m ，g ，3 ，2 ) 设计的区组集，令召= ( bl l o o 。) ：b 矽 l ，则( x ，4u 召) 为型为( g ：8 ) 或 ( 9 2 k + l ：5 ) 的烛台形四元系覆盖设计由引理2 3 知对给定的g ，8 ，c q & 一，( 矿：8 ) 或c q 凡一，( 夕z m ：8 ) 存在，把这两部分区组集合并，则得到型为( g 七：s ) 或 ( 9 2 k + l ：5 ) ，指标为a 的u 阶烛台形四元系覆盖设计经简单计算知，当( g ，s ) ( 1 2 ，3 ) ，( 1 2 ，1 1 ) ) 时，区组数为磁( u ，4 ，3 ) 一k b i ( g + s ，4 ，3 ) + ( k 一1 ) b i ( s ，4 ，3 ) ；当 ( 夕，s ) ( 6 ，1 ) ，( 6 ，3 ) ) 时，区组数为磁( u ，4 ，3 ) 一( 2 后+ 1 ) 耳( 9 + s ，4 ，3 ) + 2 k b i ( s ，4 ，3 ) 口 若g d d ( 3 ，k ，u ) 的区组集8 可以划分为不相交的子集b ，岛，鼠和4 ， 且对每个( x ，夕，鼠) 是一个g d d ( 2 ，甄，u ) ( 1 i s ) ，则该a d d ( 3 ，k ，u ) 称作 s f a n 的，并记作s 一f a ng d d ( 3 ，( k 1 ，玩，k ) ，口) 最近葛根年证明了 定理2 6 【4 2 】当g 4 且g 2 ( m o d4 ) 时，型为9 4 的g - f a ng d d ( 3 ，4 ，4 9 ) 存 1 1 强度为3 的四元系覆盖 二 递推构作 类似于四元系构作( 3 6 】定理2 2 ) 我们得到： 引理2 4 当g 4 ，g 2 ( r o o d4 ) 且s g 时，c q 岛( 夕4 ：8 ) 存在 证明：所要设计将在集合x = ( gxz 4 ) u 0 0 ，0 0 。，( 3 0 。) 上构作，其中 i g i = 9 由定理2 6 知，可在gxz 4 上构作一个以gx i ) ( i z 4 ) 为组的9 一f a n g d d ( 3 ，4 ，4 9 ) 则区组集1 3 可以划分为不相交的子集b ，饬，岛，使得对每个 ( g 五， gx 协：i 互】_ ，琏) 是一个g d d ( 2 ，4 ，4 夕) 对1 i s ， z ，y ，z ，叫) 段， 在集合 x ，y ，z ，w ，0 上构作( 3 ，4 ，5 ) 对8 + 1 i g ， z ，y ，z ，叫) 鼠，在 集合( x ，y ，z ，w ) 上构作( 3 ，4 ，4 ) 对任意点对( i ，歹) c 五，在点集g i ) 和 g xd ) 上构作c q s 2 ( 9 2 ：o ) ，这些输入设计的存在性分别由定理1 4 和引理 2 1 保证经简单验证知，构作出的就是c q s 2 ( 9 4 ：s ) 口 下面我们介绍带洞的日设计指标为a 型为r m ，洞的型为r s 的h 设计， 记作风( ( 仇，s ) ，7 ，k ，t ) ，是指一个四元组( x ，9 ，1 3 ，f ) ，其中9 = g 。，g 2 ，g 。) 是x 的一个划分且i g i i = r ，f = g i 。，g i 。，g 。) cg ，满足：( 1 ) 舀是x 的某些 子集的多重集合，对任意b 1 3 ，g 9 ，有i b i k 且i bng i 1 ；( 2 ) 对于x 的 每个t 元子集t ，如果对任意g 9 ，有i tng l 1 且f t a ( u 。 g i j ) i ( t 一1 ) ， 那么t 恰包含于召的a 个区组中；否则，t 不包含于8 中任何区组，其中 f 称为洞 引理2 5 【4 3 j 玩( ( 7 ，3 ) ，3 ，4 ，3 ) ，i h 2 ( ( 1 l ，3 ) ，3 ，4 ，3 ) 和2 ( 9 ，3 ，4 ，3 ) 存在 根据本文的需要，我们构作型为( 扩：o ) ，指标为a 的m g 阶烛台形四元系 覆盖设计，其过剩恰好为以9 为组集的一个g o d ( ：，3 ，r a g ) ，记作m g a ( m ，9 ，4 ，3 ) 类似于定理2 4 我们得到： 定理2 7 假定存在一个型为g m 的1 - f c ( 3 ，( k 1 ，坼) ，r a g ) 若对任意的k 1 k 1 ， 1 2 强度为3 的四元系覆盖 二 递推构作 存在m g a ( 尼1 ，b ，4 ，3 ) ，对任意的k k r ，存在型为b 七的g d d ( 3 ，4 ，6 克) ，则存在 m g a ( m ，5 9 ，4 ，3 ) 证明：设( x ，9 ，1 3 ，丁) 是已知的一个型为9 ”的1 - f g ( 3 ，( 甄，坼) ，仇夕) 所要的 设计将在点集x ，_ x 磊上构作，其组集为9 7 = g 磊：g 9 ) 对每个区组b 1 1 3 ，由假定，可在b l 磊上构作一个m g a ( i b 。i ，b ，4 ，3 ) 其组为 z ) x 磊( z b ，) ，记它的区组集为4 卧对每个区组b t ，由假设， 可在bx 磊上构作一个型为b i b i 的g d d a ( 3 ，4 ，b