（应用数学专业论文）三重kirkman填充设计kpd_3（4sv）.pdf

三重k i r k m a n 填充设计k p d 3 ( 4 ，s ) ， ) 摘要 三重k i r k m a n 填充设计k p d 3 ( 4 ，s + ，u ) 摘要 设x 为u 元集，a 为x 的某些子集( 叫做区组) 的集合如果x 中的任 意两点至多出现在a 的a 个区组中，则称( x ，4 ) 为一个填充设k 为整数 集，若区组的大小均属于k ，则此填充记为p a ( k ， ) 如果一个填充 ( k 口) 的区组可以划分成平行类，使每个平行类都构成x 的一个划分，则称这个 填充是可分解的一个阶为指标为a 的k i r k m a n 填充设计k p d ( 锄，8 ) ，口) ， 是指一个可分解的填充，它包含最大可能数目仇( 秽) 个平行类，并且每个平 行类由一个大小为s 的区组以及0 一s ) w 个大小为t t ，的区组构成 k i r k m a n 填充设计的概念最早是由e e r n f ，h o r 五k 与w a l l i s 提出来的c o l - b o u r n 与l i n g ，p h i l l i p s ，w a l l i s 与r e e s 讨论了当8 2 ，4 ) 时k p d ( 3 ，s ，甜) 的存 在性c a o 与d u 几乎完全解决了k p d ( 3 ，4 + ) ，勘) 的存在性问题，并利用之 在s 叫的情况下给出了完美的密钥分享方案而后c a o 与z h u 又考虑了当 口兰2 ( m o d3 ) 时k p d ( 3 ，5 + ) ，”) 的存在性问题但由于其中密钥数不能达到 我们理想的最值，c a o 与t a n g 考虑当u 兰2 ( , n o d3 ) 时k p d ( 3 ，4 “) ，t i ) 的存 在性问题，以提高密钥数c a o 与d 1 1 还考虑了当8 5 ，6 ) 时k p d ( 4 ，8 ) ，口) 的存在性问题而后z h a n g 与d u 完全解决了当8 4 ，5 ) 时k p d 2 ( 3 ，8 ) ， ) 的存在性问题本文将主要讨论s 5 ，6 ，7 ) 时k p d s ( 4 ，s + ) ，t ，) 的存在性问 题，并得出如下结果t 若t ，兰1 ( m o d4 ) 且t ，1 7 ，则存在包含”一3 个平行 类的k p d 。( 4 ，5 + ) ， ) ；若t ，量2 ( r o o d4 ) 且t ，2 6 ，则存在包含t ，一5 个平行类 的k p d 3 ( 4 ，6 。) ，t j ) ；若t ，三3 ( m o d4 ) 且t i 5 1 ，则存在包含u 一8 个平行类的 k p d z ( 4 ，7 ) ，u ) 关键词：k i r k m a n 填充设计，可分组设计，f r a m e 。 作者，吴爱红 指导教师：杜北梁 三重k i r k m s , t l 婆谩计k p d 3 ( 4 ，8 1 ，砧 a b 8 t r a c 乞 t h r e e - f o l dk i r k m a np a c k i n gd e s i g n sk t , r ) 3 ( 4 ，s + ，t ，) a b s t r a c t l e txb e8s e to ft ，p o i n t s ap a c k i n go fxi sac o l l e c t i o no fb u b s e t 8o fx ( c a l l e d b l o c k s ls u c ht h a ta n yp a i ro fd i s t i n c tp o i n t sf r o mxo c c l d 墙t o g e t h e ri na tm o s tab l o c k s i nt h ec o l l e c t i o n l e tkb e8s e to fp o s i t i v ei n t e g e r s d e n o t eb y ( k t ，) ap a c k i n g0 1 1 智p o i n t sw i t hb l o c ks i 硼a ui n 致ap a c k i n gi sc a l l e dr e s o l v a b l e 让i t sb l o c k ta d m i t ；s 8 p a r t i t i o ni n t op a r a _ l l dc l b 8 8 簋e a c l ap s r a 1 l e lc l a s sb e i n gap a r t i t i o no f t h ep o i n ts e tx ak i r k m a s ap a c k i n g ，d e n o t e dk p ( k ，t ，) ，i sar e s o l v a b l e ( 墨ak i r k n u mp a c k i n g d e s i g a ，d e n o t e dk p d ( t 叫，s ，t j ) ，i s8 r e s o l v a b l ep a c k i n go fav - s e tb yt h em a x i m u m 1 ) o s s i b en u m b e r 仇扣) o fp a r a l l dc t e , s 懒，e a c he o m a i n i n go n eb l o cko fs i z es8 n d i l o t h e rb l o c k so fs i z e t o e e r n s h o r m ka n d 籼8 i n t r o d u c e dt h ek i r k m a j ap a c k i n gd e s i g n c o l b o u ma n d l i n g p h i l l i l 粥，w a l l i sa n dr e e 8d i s c u s s e dt h ee x i s t e n c eo fk p d ( 3 ，8 ，w h e n8 2 ，4 ) t h es p e c t r u mp r o b l e mf o rk p d ( 3 ，4 ，锄) h 幽b e e na l m o s tc o m p l e t e l ys o l v e d a n db e e nu s e dt oc o n s t r u c tp e r f e c tt h r e s l a o l ds c h e m e sw h e n8 伽b yc a oa a di ) t t t h e f tc o o8 n dz h ue o m i d e r e dt h ee x i s t e n c eo fk p d ( 3 ，5 ) ，t ，) w h e n 口兰2 ( r o o d3 ) ， s i n c et i l en u m b e ro fp a r a l l e lc l a s s e sc 8 1 1n o t ；e , c h i e v et h ee x p i r e dl n s c , j m u m ，c a o8 r i d t a n gc o m i d e r e dt h ee x i s t e n c eo fk p d l ( t 3 ，4 + ) ，t ，) w h e n 掣兰2 ( 7 n o d3 ) c a oa n dd u c o n s i d e r e dt h ee x i s t e n c eo fk p d ( 4 ，s ，”) w h e n8 5 ，6 z h s n g8 n dd uc o m p l e t e l y s o l v e d t h es p e c t r u mp r o b l e m 妇t w o - f o l dk i r k m s , np a z l d n gd e s i g n sk p r ) 2 ( 3 ，s ) ，t ，) w h e n8 4 ，5 ) i nt h i sa r t i c l e ，w e8 h 8 1 1b er e s t r i c t i n go u ra t t e t l t i o nt ot h r e e - f o l d k i r k m a np a c k i n gd e s i g nk p d 3 ( t 4 ，8 ) ，u ) f o r8 5 ，6 ，7 ) t h ef o l l o w i n gr e s u l t sw i l l b ep r o o f e dlt h e r ee x i s t sak p d 3 ( 4 ，5 ) ，御) c o n t a i n i n gt ，一3p a r a l l e le l a 8 8 e 8f o re v e r y t ，羞l ( r o o d4 ) e n di , 1 7 ；t h e r ee x i s t sak p d 3 ( 4 ，6 。) ，功c o n t a i n i n g 移一5p a r a l l e l d s , s 嬲s f o r e v e r y t ，兰2 ( r o o d4 ) a n d t ，2 6 ；t h e r ee x i s t s a k p d 3 ( 4 ，7 ， ) c o n t a i n i n g 可一8p a r a l l dc l a 器鹤f o re v p , t yt ，兰3 ( m o d4 ) 眦d 5 1 i i - - tk i r k m a n 填充设计k p d a ( 4 ，5 ，t ，) k e yw o r d s ：k i r k m a np a c k i n gd e s i g n tg r o u p - d i v i s i b l ed e s i g n ，f r a m e i i i w r i t t e nb yw ua i h o n g 4 s u p e r v i s e db yd ub e i l i a u g 。y 。9 5 7 0 8 5 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：昊轰仁日期： 。6 ，牛2 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名： 更霞江 日 垒兰! ：璧日 期： ，6 掣2 - 期：寸乒之 - tk i r k n m n 填充设计k p d a ( 4 ，8 ) ，钉)一引言 一引言 设x 为和元集，4 为x 的某些子集( 叫做区组) 的集合如果x 中的任 意点对至多出现在4 的a 个区组中，则称僻，棚为一个填充设k 为整数 集，若区组的大小均属于，则此填充记为p a ( k ， ) 如果一个填充 ( k ) 的区组可以划分成平行类，使每个平行类都构成x 的一个划分，则称这个 填充是可分解的，记做k p 。( 瓦t ，) 如果一个可分解的填充k p - ( 丘t ，) 中，包含最大可能数目m ( v ) 个平行 类，并且每个平行类由一个大小为s 的区组以及扣一8 ) w 个大小为伽的区 组构成，则称为k i r k m a n 填充设计，并记之为k p d ( w ，s ，甜) 当8 = 埘时， 记为k p d ( t ，t ，) k i r k m a n 填充设计的概念最早是由e e 嘶，h o r d k 与w 出l i s 1 1 提出来的 c o l b o u r n 与l i n g 2 ，p h i l l i p s ，w a l l s 与r 嬲 3 1 讨论了当s 2 ，4 时k p d ( 3 ，8 ) ，u ) 的存在性c a o 与d u 【4 l 几乎完全解决了k p d ( 3 ，4 ，口) 的存在性问题，并利用 之在s 伽的情况下给出了完美的密钥分享方案而后c a o 与z h u 5 】又考虑了 当t ，毫2 ( r o o d3 ) 时k p d ( 3 ，5 ，t ，) 的存在性问题但由于其中密钥数不能达到 我们理想的最值，c a o 与t a n g 6 1 考虑当口i2 ( r o o d3 ) 时k p d ( 3 ，4 ) ，t ，) 的存 在性问题，以提高密钥数c a o 与d u 【4 1 还考虑了当8 t 5 ，6 时k p d ( 4 ，s ，t ，) 的存在性同题而后z h a n g 与d u 7 ，8 】完全解决了当5 4 ，5 ) 时二重k i r k - m a i l 填充设计k p d 2 ( 3 ，8 + ) ，t ，) 的存在性问题本文将主要讨论8 t 5 ，6 ，7 时 k p d 3 ( 1 4 ，5 + ) ，钉) 的存在性问题 通过简单计算，可以得到； 引理1 1 设t ，1 7 若k p d 3 ( 4 ，s ) ， ) 存在，则m ( 口) s 犯( u ) ，这里 m ) = v - 3 ，, 若若v - 1 ( m o d 答量置 引理1 2 设t ，1 5 若存在k p d s ( 4 ，r ) ， ) ，则有m ( t ，) sn ( u ) ，这里 f 材一8 ，若勘三3 ( m o d4 ) 且口之5 1 ， 礼扣) = t ，一7 ，若t ，三3 ( m o d4 ) 且2 3 t ，5 4 7 ， 【t ，一6 ，若射兰3 ( , n o d4 ) 且1 5st ，1 9 - - i tk i r k m a n 填乇设计k p d 3 ( 4 ，s ) ，w ) 一引吉 本文讨论了s ：5 ，6 和7 时k p d 。( 4 ，8 ， ) 的存在性并给出了如下结果 定理1 1 若t f 三1 ( r o o d 4 ) 且t ，1 7 ，则存在包含口一3 个平行类的k p d 3 ( 4 ，5 + ，t ，) 定理1 2 若口= - - 2 ( 脚d 4 ) 且t ，芝2 6 ，则存在包含v - 5 个平行类的k p d a ( 4 ，6 ) ，u ) 定理1 3 若口三3 ( r o o d 4 ) 且t ，25 1 ，则存在包含t ，一8 个平行类的k p d 3 ( 4 ，7 ，t ，) 2 三熏k i r k m a n 填完设计k p d a ( 4 ，s ) ，割) 二辅助设计 二辅助设计 为建立本文结果，我们需要若干类型的辅助设计及有关的存在性结果 本节我们对此作一介绍关于这些辅助设计，特别是可分组设计和f r a m e 在 1 9 】中有详细介绍 设k 与肘都是某些正整数的集合可分组设计( g d d ) g d ( k ，a ，m ；v ) 是一个三元组( 五g ，8 ) ，其中x 为 元集；9 是x 的一个划分，g 的元素叫 做组；8 是x 的某些子集的集合，b 的元素叫做区组这个三元组满足以 下四个条件： 1 对任意的b 召，都有i b l k ， 2 对任意的g 9 ，都有l g i m ， 3 对任意的b 且与任意的g g ，都有l b n g i 1 ， 4 x 中任意两个取自不同组的元素恰包含在a 个区组中 一、 在上述g d d ( x ，g ，召) 中，若9 包含如个大小为职的组，1 m ，则称此 g d d 的型为9 i 1 毋办 若召可划分为平行类，则称此g d d ( k ，a ，m ；可) 是可分解的 通常记g d ( 七) ，a ， m ) ；t ，) 为g d ( k ，九m ；口) ，记g d ( k , 入，m ；v ) 为( k 入) - g d d 若a = 1 ，则简记为k - g d d 若又k = 七) ，则记为k - g d d 横截设计 t d k ；州是指型为矿的k - g d d 若此横截设计含有一个平行类，则称它为幂 等的众所周知，存在一个t d k ；佗】等价于存在k 一2 个两两正交的竹阶拉 丁方 关于横截设计，已有如下存在性结果： 篁 定理2 4 ( 【9 ，1 0 ，1 1 ，1 2 】) ( 1 ) 对任意正整数t 之7 ，, f f 誊毋= l o ，1 4 ，1 8 ，2 2 ，2 6 ，3 0 ，6 0 ， 存在幂等的t d 6 ；可】 ( 2 ) 对任意正整数t ，7 j 秽岳丹u 足，这里b = z 2 ，1 5 ，2 0 ，2 1 ，2 8 ，3 3 ，3 4 ，3 5 ， 3 8 ，3 9 ，4 2 ，4 4 ，4 6 ，5 1 ，5 2 ，5 4 ，6 2 ) ，存在幂等的t d 7 ；v 3 z tk i r k m a n 填充设计k p d a ( 4 ，s ，t ，) 二辅助设计 ( 3 ) 对任意正整数掣2 5 ，且v 足，这里屁= v l g c d ( v ，2 1 0 ) = l u 2 5 ，2 7 ，3 2 ，4 9 ，6 4 ，存在幂等的v d u ；v ( 4 ) 对任意素数幂q ，存在t o q + l ；q 1 我们将会用到以下的关于g d d 的w i l s o n 基本构作( w f c ) 引理2 3 ( 【1 3 】) 设( x ，玩b ) 为一g d d ，加：x z 十u 0 为一权函数若任意区 组b 局都存在型为 & ：。b 的k - g d d ，则存在型为 & 口加( z ) ：g 9 ) 的k g d d g d d ( x ，蛋，召) 是f r a m e 可分解的，若b 的所有区组可以划分为一些带洞 平行类，每一个带洞平行类都是某个x 一岛的划分，其中q g 一个f r a m e 可分解的( a ) - g d d 又称为( 柚一f r a m e 它的组称为洞易知对每个岛，恰 好存在x 一岛上的刈岛i ( e 一1 ) 个带洞平行类 关于( 4 ，3 ) f r a m e ，已有如下存在性结果： 定理2 5 ( 1 ) ( 1 4 ，1 5 ，1 6 ) 存在型为铲的( 4 ，a ) - 加m e 当且仅当t 5 且h ( u 一 1 ) 兰0 ( m o d4 ) ，可能除当h 三2 ( 仃谢4 ) 且 1 h 2 ) u n ：1 0s 竹3 4 7 6 且t 2 3 ，2 7 ) ； 2 h = 6 且“ 7 ，2 3 ，2 7 ，3 9 ，4 7 ( 2 ) ( 【1 7 ，1 8 ，1 9 ，2 0 1 ) 存在型为g s r a l 的“，砂加m e 当且仅当9 罩0 ( r o o d4 ) ， t ，l 兰0 ( m a d4 ) ，且0 m 4 3 a 本文主要用$ t i n s o n 的。填洞构造”，这需要一些型不一致的( 4 ，3 ) f r a m e 为此，需要如下递推构作 引理2 4 ( 2 l j ) 如果存在型为疗谚妇的k g d d , 且对每一个詹k 都存 在型为h 。的( 4 ，3 ) - # a m e ，则存在型为( 幻。) 。t ( 锄) b ( 协。) h 的( 4 ，3 ) - k a m e 最后，我们引进三重不完全k i r k m a n 填充的概念它可以用来得到三重 k i r k m a n 填充设计，也可以作为。填洞构造”所需要的输入设计设s = 5 时 叫= 3 或5 ，8 = 6 时t l ，= 5 或6 ，s = 7 时钳= 8 或1 1 ，并且兰8 4 ( r o o d4 ) 一 个三重不完全k i r k m a n 填充i k p 3 ( 4 ，s + ) ，t ，埘) 是指个三元组( x ，y 舀) ，满足 以下条件： 4 三重k i r k m a n 填充设计k p d a ( 4 ，8 ，口) 二辅助设计 1 x 是t ，元集y ( 称为洞) 是x 的叫元子集日是由x 的某些子集 ( 称为区组) 所组成的集合，其中区组大小为4 或s ， 2 对任意的b 8 ，都有l y nb is1 3 x 的任意一个点对若非出现在y 里，则至多出现在8 的三个区组中； y 的任意点对都不出现在g 的区组中， 4 8 可划分为x 上的口一t l ，个平行类和x y 上的z ( 伽) 个带洞平行类其 中每一个平行类都包含一个大小为8 的区组和扣一8 ) a 个大小为4 的 区组，划分点集x ；每个带洞平行类都包含一, 0 ) 4 个大小为4 的 区组，划分点集x y 记上述定义中i k p s ( ( 4 ，8 ) ，t ，钾) 的第i 个带洞平行类为q 假设存在洞 y 上的的一个k p 。( 4 ，s ) ，训) 有。( 枷) 个平行类，记第i 个为只则可得到x 上的2 ) 个平行类只uq ，1 i $ ) 从而得到一个k p 3 ( 4 ，s ，t ，) ，它有 ( t 7 ) + t ，一t ，个平行类 下面我们给出三重不完全k i r k m a z 填充设计i k p d 3 ( 4 ，s ) m 伽) 的定义 设i k p 3 ( 4 ，s + ) ，弘叫) 的带洞平行类个数 z ( w ) = t l ，一3 伽一5 叫一8 t 盯一7 坩一6 若8 = 5 且彤1 7 ， 若s = 6 且t ，2 6 ， 若s = 7 且t ，5 1 ， 若8 = 7 且2 3 t i 4 7 ， 若s = 7 且1 5 s t ，1 9 称这样的三重不完全k i r k m a n 填充为三重不完全k i x k m a n 填充设计，记作 i k p d a ( 4 ，s 。) ，口，埘) 易知，若存在i k p d 。( 4 ，s ) ，弘 ) 和包含z ( 叻个平行类的k p d a ( 4 ，s ) ， ) ， 则存在k p d 3 ( 4 ，矿 ，u ) ，它有x ( w ) + 钉一t u 个平行类 现在我们可以给出如下的。填洞构造”法这将是我们得到所需结论的 主要依据 定理2 6 假设 1 存在一个型为g 1 9 2 g m 的“，s ) - y , a , n e , 5 三重k i r k m a n 填充设计k p d a ( 4 ，s ，t ，) 二辅助设计 2 对每个t m ，都存在个i k p d 3 ( 4 ，s ) ，玑+ 叫，叫) ， 只存在一个k p d a ( 4 ，8 ，+ ) ， 则存在一个k p d a ( 4 ，矿 ，伽+ l s 蜘历) 证我们先构造i k p d a ( 4 ，s ) ，删+ l 鲻。g i ，舫+ t c ，) 假设型为g x 9 2 鲕的 ( 4 ，3 ) f r a m e ( x ，g ，8 ) 中，g = a l ，g 2 ，g 。) ，且l g “= 历( 1 m ) 给定的 ( 4 ，3 ) f r a m e 中有霸个带洞平行类，以g t 为洞，l m 设第j 个为q ，在 g t u y ( y 为埘元集，且x n y = ) 上构造一个i k p d 3 ( 4 ，s ) ，g i + w ，埘) ，使得 它的洞为l ，它的平行类个数也是g i ，其第歹个记为而仍u 局( 1 歹靠) 是x u y 上的吼个平行类由于1 t m ，这样的平行类共有e ，垡一1 毋 个这就提供了所需三重不完全k i r k m a n 填充设计的所有平行类 对1st m ，i k p d s ( 4 ，s ) ，卯+ 锄，钳) 中均有。( 训) 个洞为y 的带洞平行 类，每一个都为g i 的一个划分记它们为岛，j l ，2 ，$ ) ，嚣) = 伽一3 若8 = 5 ，z ( 叫) = 叫一5 若8 = 6 ，( t c ) = 伽一8 若8 = 7 令b = u l 鳅。岛则b 是 x g 。的划分由此得到所求i k p d 3 ( 4 ，5 ) ，t + ，c 。c 。9 ，9 m + 协) 的霉( ) 个带 洞平行类，以g 。u y 为洞另外，在( 4 ，3 ) 。f r a m e 中有如个带漏平行类以组g m 为澜，划分集合x g k 从而可求得所求i k p d 3 ( 4 ，8 ，伽+ l s i ，1 1 ) 将初始平 行类p 重复三次，就得到我们需要的3 个平行类p 的区组列在下面 p ：012 345 67 8 91 0 显然这个k p a ( 4 ，7 ，1 1 ) 实际上也是一个包含3 个平行类的i k p 3 ( 4 ，7 ， 1 1 ，8 ) 口 引理2 1 3 若t ， 5 1 ，5 9 ，则存在i k p d 3 ( 4 ，7 。) ， ，i i ) 1 0 - - tk i r k m a n 填充设计k p d s ( 4 ，矿) ，t ，) 二辅助设计 证令g = z t ，t = 0 1 1 ) 2 取点集为x = ( 五x o ，i ) u v ，y = o 。1 ，o o l l ) 令b = o ，t 1 4 ，t 1 2 ，3 t 4 则bx o 与b 1 ) 一起在群g 的作用下生成一个 所需的带洞平行类再将之重复两次，就得到我们需要的三个带洞平行类 其余的t ，一1 1 个平行类由初始平行类p 1 与马在群g 的作用下循环生成 以下是初始平行类的区组 = 5 1 ： p l ：0 0 1 1 3 1 6 0 9 0 1 2 1 1 9 1o i 3 0 6 1 0 0 1 1 0 4 0 8 0 0 。22 0 2 1 4 1 0 0 s 5 0 9 1 1 0 i 0 0 45 1 1 3 1 i 5 0 0 0 57 0 1 4 1 1 5 1 c 1 0 67 1 1 4 0 1 8 0 0 0 7 8 1 1 6 1 i 7 0 0 0 5i 0 0 i 3 0 1 8 1 0 0 9i i o i 2 0 1 9 0 0 0 1 01 1 i 1 6 0 1 7 1 0 0 1 1 p 2 ：0 1 2 0 4 0 6 , 9 1 1 3 0 2 0 01 0 3 1 7 0 0 0 11 1 4 1 8 1 0 0 22 1 3 0 5 0 0 0 3 5 1 1 0 0 1 1 0 0 0 46 0 1 4 0 1 5 1 0 0 57 1 i s o i 6 0 0 。68 0 1 4 1 1 8 1 7 9 0 1 7 0 1 7 i 0 0 s 1 0 1 1 3 1 1 9 0 0 0 9i i i l 2 1 1 9 1 0 0 i o1 2 0 1 6 1 1 8 0 0 0 1 1 = 5 9 ： p l ：0 0 1 0 2 1 4 1 7 0 1 0 1 1 4 00 i 3 1 7 1 1 1 11 1 2 0 3 0 4 05 0 5 1 i 0 0 0 0 1 6 0 1 2 1 1 9 0 0 0 26 1 1 5 0 2 0 0 0 0 38 0 1 5 1 2 2 0 0 0 48 1 1 7 1 2 0 1 0 0 5 9 0 i 7 0 2 1 1 0 0 89 1i s 0 1 8 1 0 0 7 1 1 0 1 6 0 2 3 1 0 0 8 1 2 0 1 9 1 2 1 1 0 0 0 i 3 0 1 4 1 2 3 0 0 0 1 01 3 11 6 1 2 2 1 0 0 1 1 p 2 ：o l l z 3 0 5 0 7 1 1 i 0 1 4 11 0 4 0 8 0 1 2 0 2 0 2 1 3 1 4 1 5 i 6 0 1 0 1 0 0 1 6 i i 3 0 1 9 1 0 0 27 0 1 5 1 2 0 1 0 0 38 1 1 6 0 2 2 1 0 0 49 0 1 8 0 2 1 0 0 0 5 9 1 1 7 1 2 2 0 0 。6i 0 0 1 8 1 1 9 0 0 。7i i i l 6 1 2 4 0 0 0 s1 2 1 2 0 0 2 2 0 0 0 口 。 1 3 1 1 5 0 2 3 1 0 0 1 0i 4 0 1 7 0 2 3 0 0 0 1 1 引理2 1 4 若勘 5 5 ，6 3 ，则存在i k p d 3 ( 4 ，7 ) ，u ，i i ) 证令g = 磊，t = 扣一1 1 ) 2 取点集为x = 沲x o ，l ) u y ，y = o o l 一，c o n b l = 0 0 ，( o 一2 ) 4 ) 1 ，( u 2 ) o ，( ( 3 t 一2 ) 4 ) 1 ) 与岛= 0 1 ，( 0 + 2 ) 4 ) 0 ，( t 2 ) l ，( ( 射+ 2 ) 4 ) o 一起在群五的作用下生成一个所需的带洞平行类再将之重复两 次，就得到我们需要的三个带洞平行类其余的t ，一1 1 个平行类由初始平行 类p l 与恳在群g 的作用下循环生成以下是初始平行类的区组 t ，= 5 5 ： p 1 ：6 0 1 0 2 1 4 1 7 0 1 0 1 1 4 00 1 1 1 2 0 3 0 3 1 4 0 8 0 0 0 1 5 0 9 0 1 2 0 0 0 2 5 i 1 3 i 2 1 0 0 0 s6 0 1 4 i 2 0 1 0 0 46 1 1 5 1 1 8 1 0 0 57 1 1 7 0 1 7 1 0 0 8 8 1 1 1 1 i 9 0 0 0 79 1 1 6 0 1 8 d 0 0 81 0 0 i 5 0 2 0 0 0 0 91 1 0 1 3 0 1 9 1 0 0 i o 1 2 1 1 6 1 2 1 1 0 0 1 1 p 2 ：o l l l 3 0 5 0 7 1 1 1 0 1 4 11 0 2 0 2 1 3 14 0 4 1 8 1 0 0 15 1 9 1 1 2 i 0 0 2 6 0 i 4 0 2 1 1 0 0 36 1 1 5 0 2 1 0 0 0 4z o i 6 0 1 9 0 0 0 58 0 1 7 1 1 8 0 0 0 6 9 0 1 2 0 1 9 1 0 0 71 0 0 1 6 1 1 8 1 0 0 81 0 1 1 5 1 2 0 1 0 0 9i i i l 3 1 2 0 0 0 0 m i 3 0 1 7 0 2 2 0 0 0 1 1 i i - - tk i r k m a a 填充设计k p d 3 ( 4 ，5 ，t ，) 二辅助设计 w = 6 3 ： p l ：0 0 2 0 4 1 7 1 1 1 1 1 5 i 2 0 0o z 5 0 l 0 0 1 5 01 0 4 0 8 0 1 3 01 1 2 1 3 0 3 1 5 1 6 0 7 0 0 0 16 1 8 1 1 6 0 0 0 29 0 1 7 0 2 3 0 0 0 39 1 1 9 1 2 5 0 0 0 4 1 0 1 1 s 0 2 1 1 0 0 01 1 0 2 2 0 2 3 1 0 0 01 2 0 2 0 1 2 4 0 0 0 7 1 2 1 1 8 1 2 1 0 0 0 0 1 3 1 1 9 0 2 2 i 0 0 9i 4 0 1 6 i 2 5 1 0 0 1 0 1 4 1 1 7 1 2 4 1 0 0 l l b ：0 1 2 1 5 0 s o l 2 0 i s 0 2 0 l b 0 6 i 7 1 0 0 1 i i 0 1 8 i 2 2 0 0 0 5 1 4 0 1 9 1 2 3 0 0 0 9 1 0 5 1 i o z l 5 1 7 0 9 0 1 6 1 0 0 2 i i i 2 2 1 2 4 0 0 0 b 1 4 1 1 7 0 2 6 0 0 0 i 0 1 1 4 i 8 1 1 3 12 0 3 0 3 1 4 0 9 1 1 7 1 2 3 1 0 0 3 i 0 0 2 0 0 2 5 1 0 0 4 1 2 1 2 1 0 2 4 1 0 0 ri 3 0 1 9 0 2 1 1 0 。8 1 5 0 1 8 0 2 5 0 0 0 1 1 引理2 1 5 若t ， 6 7 ，7 5 ，7 9 ，8 7 ，9 1 ，9 9 ，1 0 3 ，1 1 1 ，1 1 5 ，1 2 3 ，1 2 7 ，1 3 5 ，1 3 9 ，1 4 7 ，1 5 1 ，1 5 9 1 6 3 ，1 7 1 ，1 7 5 ，1 8 3 ，1 8 7 ，1 9 5 ，1 9 9 ，2 0 7 ，则存在i k p d 3 ( 4 ，7 m 1 1 ) 证取点集为x = z t u y ，忙口一1 1 ，y = ( 。l ，0 0 1 1 ) 令b = o ，t 4 ，t 2 ，3 t 4 b 在群互的作用下生成一个所需的带洞平行类再将之重复两次，就得到 我们需要的三个带洞平行类其余的勘一1 1 个平行类由一个初始平行类在群 互的作用下循环生成初始平行类的区组详见我们的文献【2 3 | 口 引理2 1 6 若移 5 1 ，5 5 ，5 9 ，6 3 ，6 7 ，7 5 ，7 9 ，8 7 ，9 1 ，9 9 ，1 0 3 ，i i i ，1 1 5 ，1 2 3 ，1 2 7 ，1 3 5 ，1 3 9 ， 1 4 7 ，1 5 1 ，1 5 9 ，1 6 3 ，1 7 1 ，1 7 5 ，1 8 3 ，1 8 7 ，1 9 5 ，1 9 9 ，2 0 7 ，则存在k p d 3 ( 4 ，7 ，u ) 证当 5 1 时，一个k p d 3 ( 4 ，7 ) m 1 1 ) 包含t ，一8 个平行类，而一个。 i k p d s ( 4 ，7 m1 1 ) 包含”一1 1 个平行类和3 个带洞平行类由引理2 5 我们 知道存在二个包含3 个平行类的k p 3 ( 4 ，7 ，1 1 ) 将这3 个平行类与前面的3 - 个带洞平行类任意匹配在一起，就得到了三个新的- - r - - 行类这样我们就有了 构造k p d 3 ( 4 ，7 ，u ) 需要的t ，一1 1 + 3 = t ，一8 个平行类从而由引理2 1 3 至 引理2 1 5 就得证0 - tk i r k m a n 填充设计k p d 3 ( 4 ，s ， )三k p d 3 ( 4 ，5 ) ，t ，) 的存在牲 三k p d 3 ( 4 ，s + ) ，衫) 的存在性 本节中，将得到我们的主要结论，这需要由第二章的。填洞构造”法类 似得到如下结论： 定理3 7 假设当t 2 1 时， 1 存在一个型为3 。的似彤- 加m 岛 磐存在包含3 个平行类的m p 3 ( a ，7 ) ，1 1 ，8 ) ， 则存在包含黜个平行类的k p d 3 ( 4 ，7 ) ，3 t + 8 ) 证假设型为3 t 的( 4 ，3 ) f r a m e ( x ，g ，召) 中，9 = a l ，g 2 ，g ) ，且i q i - 3 ( 1s ) 给定的( 4 ，3 ) f r a m e 中有3 个带洞平行类，以g 为洞，1s t 设第歹个为q ，在quy ( y 为8 元集，且x ny = ) 上构造一个 i k p d 。( 4 ，7 ) ，1 1 ，8 ) ，使得它的洞为y 它的平行类个数也是3 ，其第j 个记为 而q u 马( 1s j g i ) 是x u y 上的3 个平行类由于1 i t ，这样的平 行类共有3 t 个这就提供了所需三重k i r k m a n 填充设计k p d 。( t 4 ，r ，3 t + 8 ) 的所有平行类 口 引理3 1 7 若存在幂等的t d 6 ；胡，则对55k t ，存在k p d 3 ( 4 ，5 。) ，2 0 t + 4 七+ 5 、 证在t d 6 ；胡中取一组，删去其中t k 个点，由引理2 3 ，则得到一个型为 6 k 5 t 一的 5 ，6 ，k ， 一g d d 对此g d d 的每个点加权4 ，由引理2 4 可得到型 为2 4 k 2 0 “的( 4 ，3 ) f r a m e 令伽= 5 ，应用定理2 6 ，就可得到所证结果其中 的输入设计i k p d 3 ( 4 ，科，2 5 ，5 ) 与i k p d 3 ( 4 ，5 ) ，2 9 ，5 ) 分别来自于引理2 5 与 2 6 口 引理3 1 8 若存在幂等的t d 7 ；t ，则对5 七t ，存在k p 3 ( 4 ，6 ) ，2 4 + 4 后+ 6 1 证证明类似于引理3 1 7 的证明其中的输入设计i k p d 3 ( 4 ，6 + ) ，3 0 ，6 ) 与 i k p d 3 ( 4 ，6 + ，3 4 ，6 ) 分别来自于引理2 9 与2 1 0 口 1 3 - l tk i r k m a n 填充设计k p d 3 ( 4 ，s ) ，t ，) 三 k p d s ( 4 ，s ，t ，) 的存在性 引理3 1 9 若存在幂等的t d 9 ；叱则对5 k t ，存在k p d 3 ( 4 ，6 ，3 2 抖4 路枷) 证这个证明也类似于引理3 1 7 的证明其中的输入设计i k p d a ( 4 ，6 ，3 8 ，6 ) 与i k p d 3 ( 4 ，6 ) ，4 2 ，6 ) 分别来自于引理2 9 与2 1 0 o 引理3 2 0 若存在幂等的t d 1 l ；司，则对5 k t ，存在k p d 3 ( 4 ，r ，4 0 t + 4 k + 1 1 ) 证这个证明也类似于引理3 1 7 的证明其中的输入设计i k p d 。( 4 ，r ) ，5 1 ，1 1 ) 与i k p d 3 ( 4 ，7 ) ，5 5 ，1 1 ) 分别来自于引理2 1 3 与2 1 4 1 口 引理3 2 1 若存在幂等的t d 1 2 ；胡，则对5 k t ，存在k p d 3 ( 4 ，7 ) ，4 4 t + 4 k + 1 1 ) 证这个证明也类似于引理3 1 7 的证明其中的输入设计i k p d a ( 4 ，7 ) ，5 5 ，1 1 ) 与i k p d 3 ( 4 ，7 ，5 9 ，1 1 ) 分别来自于引理2 1 4 与2 1 3 口 引理3 2 2 若存在幂等的t d 1 3 ；t ，则对5s 奄句存在k p d a ( 4 ，6 。 ，4 8 t + 4 k + 1 1 ) 证这个证明也类似于引理3 1 7 的证明其中的输入设计i k p d 3 ( 4 ，7 ) ，5 9 ，1 1 ) 与i k p d 3 ( 4 ，7 ，6 3 ，1 1 ) 分别来自于引理2 1 3 与2 1 4 口 由定理2 6 易得下面的引理 引理3 2 3 若存在型为9 5 m 1 的似，s ) - 加m e , i k p d 3 ( 4 ，s 。 ，g + w ，t ) 与k p d 3 ( a ， s ) ，m + 伽) ，则存在k p d 3 ( 4 ，s ) ，5 9 + m + 叫) 3 1 k p d 3 ( 4 ，5 + ) ，u ) 引理3 2 4 若t ， 口三1 ( m o d4 ) ：1 7 t ，9 7 ) u 1 0 9 ，则存在k p d 3 ( 4 ，5 + ) ， ) 包含t ，一3 个