（应用数学专业论文）区组长为4的不完全可分组设计.pdf

摘要 不完全可分组设计( i g d d ) 已经有很多学者进行了研究，这类设计常常应用于间 接构造其他组合设计问题，例如；可分组设计、正交拉丁方等 本文主要讨论区组长为4 ，组型为( g ，i 1 ) 弘的不完全可分组设计的存在性问题文章 分为五部分，首先给出了不完全可分组设计的基本概念和研究现状；第二部分介绍了一 些将会用到的相关设计的概念以及关于它们的一些结论；第三部分给出了构造不完全 可分组设计时常用的几个递归构造方法；第四部分给出了指标入= 3 时的存在谱；最后 给出区组长为4 ，组型为( 9 ，1 ) u 的不完全可分组设计存在的必要条件也是充分的，除了 3 个例外和6 个可能的例外 关键词t 不完全可分组设计可分组设计带洞可分组设计 i i i a b s t r a c t i n c o m p l e t eg r o u pd i v i s i b l ed e s i g n s ( i g d d s ) h a v eb e e ns t u d i e db ym a n yr e s e a r c h e r s t h i sd e s i g ni si n s t r u m e n t a li nt h ec o n s t r u c t i o no fv a r i o u sc o m b i n a t o r i a ld e s i g np r o b l e m s s u c ha sg d d ，m o l s ，e t c t h em a i np u r p o s eo ft h i sp a p e ri st oi n v e s t i g a t et h ee x i s t e n c es p e c t r u mo fi n c o m - p l e t eg r o u pd i v i s i b l ed e s i g n sw i t hb l o c ks i z ef o u r ，g r o u p - t y p e ( 9 ， ) u t h e r ea r ef i v e p a r t si nt h i sp a p e r f i r s t l y ，w es t a t et h ed e f i n i t i o na n db a c k g r o u n do fi g d d s e c o n d l y , w ei n t r o d u c es o m ed e f i n i t i o n sa n dn o t a t i o n sa sw e l la sp r e l i m i n a r yr e s u l t sw h i c hw i l lb e u s e di nt h es e q u e l t h i r d l y ，w es h o ws o m er e c u r s i v ec o n s t r u c t i o n sf o ri g d d f o u r t h l y , w eg i v et h ee x i s t e n c es p e c t r u mf o rt h ec a s ea = 3 f i n a l l y , w es h a l ls h o wt h a tt h en e c - e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c eo fi n c o m p l e t eg r o u pd i v i s i b l ed e s i g n sw i t hb l o c ks i z e f o u r ，g r o u p - t y p e ( g ， ) ua r ea l s os u f f i c i e n tw i t h3e x c e p t i o n sa n d6p o s s i b l ee x c e p t i o n s k e yw o r d s ：i n c o m p l e t eg r o u pd i v i s i b l ed e s i g ng r o u pd i v i s i b l ed e s i g nh o l yg r o u p d i v i s i b l ed e s i g n i v 学位论文原创性声明 本人所提交的学位论文 p i 指导教师确认( 签名) ： ? 年，月，6 同 学位论文版权使用授权书 荡按 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 论文作者( 签名) ： d 寥年岁月，舌同 磁 指导教师( 签名) ： ba 年，月f 同 雷扪 1 引言 不完全可分组设计在组合设计理论中有着重要的作用，不仅在于它本身的性质，更 重要的是它在构造其它类型的设计时有很多应用，例如t 可分组设计，正交拉丁方等 因此对不完全可分组设计的研究就显得尤为重要关于不完全可分组设计的文章，可以 参考【1 ，2 ，3 ，4 】 在介绍不完全可分组设计的定义之前，我们首先给出可分组设计的定义 定义1 1 设x 为一个有限集，9 为集合x 的一个分拆，m ，k 均为正整数集，召是 x 的一些子集构成的子集簇，满足。 1 ) i x i = t ，。 2 ) g 9 ，i g i m ，9 中元称为组， 3 ) v b 8 ，i b l k 且v g 鸟，i gnb l 1 ，召中元称为区组， 4 ) x 中任意一对不同组的元素恰好含在召的a 个区组中， 称三元组伍，夕，屡) 为一个可分组设计，记为g d d k ，a ，m ；移】 若9 中含有t 1 个m 1 长组，t 2 个m 2 长组，t 。个m 。长组，则称m 1 1 砖m 为此可分组设计的型，显然有壹挑岛= u 此时可分组设计也可称为型为m ；- m 挚m i = l 的( k ，a ) 一g d d 粗略的说，一个不完全可分组设计( i g d d ) 就是缺少一个子可分组设计的可分组 设计实际上，这个子设计可以不存在下面给出不完全可分组设计的定义 定义1 2 设x 为一个有限集，y 是x 的一个子集( 称为洞) ，9 为集合x 的一个分拆 ( 其中元称为组) ，b 是x 的一些子集构成的子集簇( 其中元称为区组) ，满足； 1 ) v b 召，g 9 ，i gnb l 1 ， 2 ) 任意一对不在同一组且不同时属于y 的点恰出现在a 个区组中， 3 ) y 中的任意点对不出现在任何区组中， 则称四元组( x ，k9 ，召) 为一个不完全可分组设计i g d d 一个型为( 0 1 ，h i ) u z ( v 2 ，j ；2 ) u 。( ，h s ) 让- 的( k ，a ) 一i g d d 是一个不完全可分组设 计，它的区组的长度均属于k ，共有u i 个仇长组，每个v i 长组与洞交个点，i = 1 1 ，2 ，8 当k = 七) 时，我们就把k 简记为k 注意到若y = 0 ，则这个不完全可 分组设计就是一个可分组设计 例1 一个型为( 3 ，1 ) 3 的( 3 ，1 ) - i g d d 点集， 洞为s 组为。 x = l ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 1 ，2 ，3 ) 1 ，4 ，7 ， 2 ，5 ，8 ) ， 3 ，6 ，9 区组为； l ，5 ，9 ) ， l ，6 ，8 ) ， 2 ，6 ，7 ) ， 4 ，5 ，6 ) 2 ，4 ，9 ) ， 3 ，5 ，7 ) ， 3 ，4 ，8 ) ， 7 ，8 ，9 ) 本文主要讨论型为( 夕， ) 私的( k ，a ) i g d d 的存在性问题经过简单的计算，我们 很容易得到它们存在的必要条件： 定理1 1 【1 】一个型为( g ， ) 1 的( k ，a ) - i g d d 存在的必要条件是；t k ，g ( k 一 1 ) h ，a 9 ( t 一1 ) 兰0 ( m o d 七一1 ) ，a ( 夕一j 1 ) ( u 一1 ) 兰0 ( r o o dk - 1 ) 且a u c u - 1 ) c 9 2 一 2 ) 兰0 ( r o o dk ( k 一1 ) ) m i a o ，z h u ，w h 和w d 在文章【1 ，2 】中证明型为( g ，危) u 的( 3 ，a ) 一i g d d 存在的必 要条件也是充分的 定理1 2f 2 】2 一个型为( g ， ) 缸的( 3 ，a ) 一i g d d 存在的充分必要条件是：u 3 ，g 2 h ，a 夕( 缸一1 ) 三0 ( r o o d2 ) ，a ( 夕一 ) ( u 一1 ) 三0 ( r o o d2 ) 且a u ( u 1 ) ( 9 2 一h 2 ) 兰0 ( r o o d6 ) 由定理1 1 ，我们得到型为( g ， ) 1 的( 4 ，a ) 一i g d d 存在的必要条件 引理1 1 一个型为( g ， ) u 的( 4 ，a ) 一i g d d 存在的必要条件是。锃4 ，g 3 h ，幻( 让一 1 ) 兰0 ( r o o d3 ) ，a ( 夕一 ) ( t 一1 ) 三0 ( m o d3 ) 且a u ( u 一1 ) ( 夕2 一h 2 ) 三0 ( m o d1 9 ) 对于型为( g ， ) u 的( k ，a ) 一i g d d ，虽然k = 3 时它存在的必要条件也是充分的，但 k = 4 时，这些条件就不是充分的了例如；由于不存在两个正交的6 阶拉丁方，因此 型为( 6 ，1 ) 4 的( 4 ，1 ) 一i g d d 也不存在文章【2 ，3 ，4 】中对型为( 夕， ) u 的( 4 ，a ) 一i g d d 已 经做了许多的工作 2 定理1 3 【3 】一个型为( g ，i 1 ) 的( 4 ，1 ) 一i g d d 存在的必要条件也是充分的，除了3 个例 外和6 个可能的例外例外值为( t ，g ，h ) ( 4 ，2 ，o ) ，( 4 ，6 ，o ) ，( 4 ，6 ，1 ) ) ，可能的例外值 为( u ，9 ，h ) ( 1 4 ，1 5 ，3 ) ，( 1 4 ，2 1 ，3 ) ，( 1 4 ，9 3 ，2 z ) ，( 1 8 ，1 5 ，3 ) ，( 1 8 ，2 1 ，3 ) ，( 1 8 ，9 3 ，2 7 ) ) 个型为g 的( 4 ，a ) - g d d 也可以看作是一个型为( 夕，0 ) u 的( 4 ，a ) 一i g d d ，它的存 在谱在文章【8 】中也已经被完全确定 定理1 4 【8 1 一个型为钉俨的( 4 ，a ) g d d 存在的充分必要条件为：n 4 ，a ( m n m ) 兰 0 ( m o d3 ) 且a m n ( m n m ) 三0 ( m o d1 2 ) ，当a = 1 ，( m ，n ) = ( 2 ，4 ) 或( 6 ，4 ) 时，g d d 不存在 本文继续研究型为( 夕， ) u 的( 4 ，a ) 一i g d d 的存在谱显然，若存在一个型为( g ， ) 缸 的( k ，a 1 ) 一i g d d 和一个型为( g ，1 ) 让的( k ，a 2 ) 一i g d d ，则存在一个型为( g ，九) 缸的( k ，a l + a 2 ) 一i g d d 因此通过计算，我们知道只需要考虑a 1 ，2 ，3 ，6 ) 时的情况对于a = 1 的情况，定理1 3 中已基本解决，所以本文主要来研究入 2 ，3 ，6 的情况因为h = 0 的情况在定理1 4 中已经被解决，那么我们在文章中只需要考虑0 3 h 夕的情况 3 2 预备知识 为了构造型为( 9 ， ) u 的( 4 ，a ) 一i g d d ，在本节我们将介绍一些相关设计及其结果 一个型为1 p 的( k ，a ) g d d 称为成对平衡设计( p b d ) ，记为b ( k ，a ；t ，) 一个型为 矿的( k ，1 ) g d d 称为横截设计，记为t o ( i , ，佗) 若一个( k ，a ) 一g d d 的区组可以划分 成一些q 平行类，使得每个点恰好在每个q 平行类中出现口次。则称这个g d d 是口 可分解的，记为可分解( k ，入) 一g d d 引理2 1 【1 0 】若让3 ， ( t 一1 ) 三0 ( m o d2 ) ，则存在一个型为胪的3 一可分解 ( 3 ，3 ) - c , d d 推论2 1 若i t , 3 ， ( u 一1 ) 兰0 ( r o o d2 ) 且t = h ( u 一1 ) 2 ，则存在一个型为h u t l 的 ( 4 ，3 ) 一c , d d 证明；取t 个无穷点 0 0 t ：1 i t ) 对手1 i t ，在一个型为h 口的3 - 可分解 ( 3 ，3 ) 一g d d 的第i 个3 平行类的每个区组中都添上无穷点o o i ，则结论成立 引理2 2 【8 】若u 兰0 ( r o o d3 ) 且牡9 ，则存在一个型为2 5 1 的( 4 ，1 ) 一g d d 引理2 3 【1 0 】一个型为3 t m l 的( 4 ，1 ) 一g d d 存在当且仅当t 三0 ( r o o d4 ) 且m 兰0 ( r o o d3 ) ，0 ms ( 3 t 一6 ) 2 , 或者t 三1 ( r o o d4 ) 且m 三0 ( r o o d6 ) ，0 仇 ( 3 t 一3 ) 2 ；或者t 兰3 ( r o o d4 ) 且m 三3 ( r o o d6 ) ，0 m ( 3 t 一3 ) 2 引理2 4 【1 8 】( 1 ) 今g 童2 ( m o d6 ) 且u 三0 ( r o o d3 ) ，乱6 ，则存在型为g u 2 1 和 矿( 夕( u 一1 ) 2 ) 1 的( 4 ，1 ) 一g d d ，除了型为2 6 5 1 的( 4 ，1 ) 一c , d d 不存在 ( 2 ) 令g 兰4 ( m o d6 ) 且u 兰0 ( r o o d3 ) ，u 6 ，则存在型为9 1 1 和夕u ( u 一1 ) 2 ) 1 的( 4 ，1 ) 一c , d d 引理2 5 【1 1 】若t 4 ，m 三0 ( r o o d3 ) 且0 m 3 t 一3 ，则存在一个型为6 t i n l 的 ( 4 ，1 ) g d d ，除了1 个例外和1 3 个可能的例外例外值为( t ，m ) = ( 4 ，o ) ，可能的例外值 为( t ，m ) o ，3 ，1 0 ，2 1 o ，5 ，1 4 ，1 9 o ，6 ，1 3 ，2 3 】， 0 ，6 ，1 3 ，2 3 引理2 9f 1 0 令b ( ) = _ 【t ，：存在一个b ( k ，l ；t ，) ) 若t ，兰2 ，3 ，6 ，i i ( m o d1 2 ) ，t ，6 且t ，g i i ，1 4 ，1 5 ，1 8 ，2 a ，贝qt ，b ( 4 ，5 ，6 ，9 ) 引理2 1 0 【1 0 】令b ( k ，a ) = 秒：存在一个b ( k ，a ；t ，) ) 若t ，三0 ，5 ，8 ，9 ( r o o d1 2 ) ，则 t ，6 b ( 4 ，3 ) 带洞可分组设计( h g d d ) 在构造不完全可分组设计时有重要的作用，因此下面我 们给出带洞可分组设计的概念 定义2 1 一个( k ，a ) - h g d d 是一个四元组( x ，咒，9 ，召) ，满足如下条件： ( 1 ) x 是一个u ( g l + + 鲰) 元集合， t ( 2 ) 多= g i g 扯) 划分x 成t 个组，每个组包含e 仇个点， ( 3 ) 咒= 日1 风) 是x 的另一个划分，它把x 划分成t 个洞，每个洞甄( 1 i t ) 都是一个u g i 元集合，满足对1 歹乱，i 甄ng j i - - - 吼， ( 4 ) 8 是x 的一个子集族，8 中元素称为区组，对于vb b ，j b i k ，其中k 是个正整数集， ( 5 ) 任意一对不在同一组且不在同一洞中的点恰好出现在a 个区组中，而在同一个 洞或同一个组中的点对不出现在任何区组中 若对每个1 堇i t ，咒中包含m 个长度为u g i 的洞，我们就用指数形式贫1 贫 来表示多重集t = 缈：歹= 1 ，2 ，t ) ，并称( t ，t ) 为此h g d d 的型 引理2 1 1 【1 2 】一个型为( u ，夕2 ) 的( 4 ，a ) - h g d d 存在当且仅当u ，t 4 ，且a ( u - 1 ) ( t - 1 ) g 三0 ( r o o d3 ) ，除了a = 1 时的1 个例外：( u ，夕，t ) - - - ( 4 ，1 ，6 ) 为了得到所要的不完全可分组设计，我们需要构造更多的带洞可分组设计为此我 们给出两个h g d d 的构造方法( 见【1 2 】，【1 4 0 6 构造2 1 若存在一个型为f 7 l i i 仇 的( k ，a 1 ) 一g d d 且对于每个n k ，存在一个 型为( “，矿) 的( 七，a 2 ) 一h c , d d 则存在一个型为( t ，( 9 m 1 ) - ( 夕m r ) ) 的( 七，a l a 2 ) i t c , d d 构造2 2 若存在一个型为( 牡，m ：i m ) 的( k ，入1 ) - h g d d 且对于每个n k ，存在一 个型为旷的( 七，a 2 ) 一c , d d ，则存在一个型为( 让，( 夕m 1 ) t ( 9 m r ) “) 的( 七，a l a 2 ) 一t i g d d 利用上述两个构造方法。我们得到了一些小阶数的带洞可分组设计 引理2 1 2 存在一个型为( 6 ，9 t m l ) 的( 4 ，3 ) - t i g d d ，其中( 9 ，t ，m ) ( 8 ，5 ，x 6 ) ，( 2 ，2 0 ，x 9 ) ， ( 6 ，1 0 ，2 7 ) ，( 2 ，1 0 ，5 ) ，( 2 ，1 0 ，7 ) ，( 2 ，1 0 ，9 ) ，( 2 ，5 ，4 ) 证明：由推论2 1 和引理2 1 1 可知，存在一个型为2 5 4 1 的( 4 ，3 ) 一g d d 和一个型为 ( 6 ，4 4 ) 的( 4 ，1 ) 一h g d d ，应用构造2 1 可得型为( 6 ，8 s 1 6 1 ) 的( 4 ，3 ) 一h g d d 对于其它情 况，由引理2 1 1 知存在一个型为( 6 ，1 4 ) 的( 4 ，1 ) 一h g d d ，且由推论2 1 知存在一个型 为g t m l 的( 4 ，3 ) 一g d d ，同样应用构造2 1 可得型为( 6 ，9 。m 1 ) 的( 4 ，3 ) 一h g d d 引理2 1 3 若( 9 ，t ，m ) ( 6 ，7 ，叫) ：t u = 3 ，6 ，9 ，x 2 u ( 1 4 ，5 ，2 1 ) ，( 1 4 ，5 ，2 8 ) ，( 2 0 ，4 ，1 0 ) ， ( 4 ，4 ，2 ) ，( 2 ，7 ，6 ) ，( 4 ，4 ，5 ) ，( 2 ，5 ，4 ) ，( 2 ，9 ，5 ) ，( 2 ，9 ，8 ) ，( 8 ，4 ，4 ) ，( 8 ，5 ，1 6 ) ，( 8 ，5 ，1 2 ) ，( 1 0 ，4 ，5 ) ， ( 4 ，7 ，1 0 ) ，( 4 ，7 ，1 2 ) ，( 1 0 ，7 ，3 0 ) ) ，则存在一个型为( 1 1 ，夕t m l ) 的( 4 ，3 ) 一h g d d 证明s 当( 9 ，t ，m ) ( 4 ，4 ，2 ) ，( 2 ，5 ，4 ) ，( 2 ，7 ，6 ) ，( 2 ，9 ，5 ) ，( 2 ，9 ，8 ) ，( 8 ，4 ，4 ) ，( 4 ，7 ，1 0 ) ) u ( 6 ，7 ，1 ) ) ：硼= 3 ，6 ，9 ，1 2 时，由引理2 1 1 可知，存在一个型为( 1 1 ，1 4 ) 的( 4 ，1 ) 一h g d d ，从推论2 1 ，引理2 2 ，2 5 或者2 8 中选取一个合适的型为夕2 仇1 的( 4 ，3 ) 一g d d ，应用构 造2 1 即可对于( 9 ，t ，m ) ( 8 ，5 ，1 2 ) ，( 8 ，5 ，1 6 ) ，( 1 4 ，5 ，2 t ) ，( 1 4 ，5 ，2 8 ) ) 的情况，由引理 2 1 1 可知，存在型为( 1 1 ，4 4 ) 和( 1 1 ，7 4 ) 的( 4 ，1 ) h g d d 由推论2 1 和引理2 8 可知，存 在型为2 5 t 1 的( 4 ，3 ) 一g d d ，这里t 3 ，4 ) ，分别应用构造2 1 即可由引理2 1 1 中型为 ( 1 1 ，5 4 ) 的( 4 ，1 ) h g d d 和引理2 8 中型为2 4 1 1 与4 4 2 1 的( 4 ，3 ) g d d ，应用构造2 1 可 以处理( 9 ，t ，m ) ( 1 0 ，4 ，5 ) ，( 2 0 ，4 ，1 0 ) ) 的情况而对( 9 ，t ，m ) ( 4 ，7 ，1 2 ) ，( 1 0 ，7 ，3 0 ) ) 的情况，同样可以对引理2 1 1 中型为( 1 1 ，亡4 ) 的( 4 ，1 ) 一h g d d ，t 2 ，5 ) 和推论2 1 中 型为2 7 6 1 的( 4 ，3 ) 一g d d 应用构造2 1 得到从一个t d ( 5 ，5 ) 的一个区组中删掉4 个 点，得到一个型为4 4 5 1 的( 4 ，5 ) ，1 ) g d d ，对它和引理2 1 1 中型为( 1 1 ，1 。) 的( 4 ，3 ) 一 h g d d ，t 4 ，5 ) ，应用构造2 1 可以处理( 夕，t ，m ) ( 4 ，4 ，5 ) ) 的情形 7 3 递归构造 下面我们给出构造不完全可分组设计时常用的几个递归构造对于这些构造，当指 标入- - 1 时，文章【1 ，3 ，4 ，1 3 】已经给出它们的证明而当指标为任意正整数a 时，它 们的证明也是类似的 构造3 1 若存在一个型为m i l 嘶的( k ，a 1 ) g d d 且对每个缸k ，存在一个型 为( 夕， ) “的( k ，a 2 ) i g d d ，则存在个型为( g r a l ，h m z ) 。l ( g m n ， ) k 的( k ，a i 屯) 一 i g d d 构造3 2 若存在一个b ( k ，a i ；t ，) ，且对每一个铭k ，存在一个型为( g ，愚) u 的( k ，如) 一 i g d d ，则存在一个型为( g ， ) v 的( k ，a i a 2 ) - i g d d 构造3 3 若存在一个型为( g ， ) 的( k ，a 夕一i g d d 和一个t d ( k ，m ) ，则存在一个型为 ( g m ，a m ) 弘的( k ，a ) 一i g d d 构造3 4 假设对每个1 i q ，存在一个型为( m + t i ，如) u 的( k ，a ) 一i g d d 和一个 t d ( u + 1 ，g ) ，则存在一个型为( m 口十r ，r ) u 的( k ，a ) - i g d d ，其中，= t l + + 岛 构造3 5 若对每个1 i s ，存在一个型为( m + t i ，如) 。的( k ，a ) i g d d ，一个t d ( u + 8 ，g + 1 ) 和一个型为m 与m ”1 t t j l 的( k ，a ) 一g d d ，则存在一个型为( 仇g + 叫+ ，伽+ r ) 私 的( k ，入) 一i g d d ，其中7 = t l + + 如 构造3 6 若存在一个型为( m + r ，r ) 2 的( k ，a 1 ) 一i g d d ，一个型为( u ，1 七) 的( k ，1 ) 一h g d d 和一个型为( 仇+ r + h ，r + ) u 的( k ，a 2 ) 一i g d d ，则存在一个型为( t m + t r 十h ，打+ 7 1 ) 的( k ，a l a 2 ) - i g d d 构造3 7 假设对每个1 i 7 - ，存在一个型为( g i + h ， ) u 的( k ，a ) i g d d 和一个 型为( 珏，9 ：1 酢r ) 的( k ，a ) h g d d ，则存在一个型为( g + ， ) u 与( 夕+ ，夕i + 广的 ( k ，a ) - i g d d ，其中1 i r ，g = 9 1 t l + + 夕r 靠 8 4 指标入= 3 的情况 本节讨论指标入= 3 的情况，我们将证明型为( 9 ，九) 。的( 4 ，3 ) 一i g d d 存在的必要 条件也是充分的 4 1 锃= 6 的情况 由引理1 1 可知，一个型为( 夕， ) 6 的( 4 ，3 ) - i g d d 存在的必要条件为9 一h 为偶数 且0 3 h 9 因此我们令夕一h = 2 v ，0 和一个型为( 3 ，1 ) 6 的( 4 ，3 ) 一i g d d ，应用构造3 7 即可得到所要结果 因此，我们只需要考虑5 h 移的情况 引理4 4 令口 5 ，6 ，1 0 ，1 5 ，2 0 ，3 0 ，6 0 ，h 为奇数且5 h 1 3 ，则存在一个型为 ( 2 u + h ， ) 6 的( 4 ，3 ) 一i g d d 证明：当砂= 5 时，由引理2 1 2 知存在一个型为( 6 ，2 5 4 1 ) 的( 4 ，3 ) h g d d ，又因为存在 一个型为( 3 ，1 ) 6 的( 4 ，3 ) 一i g d d ，应用构造3 7 即得到一个型为( 1 5 ，5 ) 6 的( 4 ，3 ) i g d d 当u = 6 时，对引理2 1 l 中型为( 6 ，4 4 ) 的( 4 ，3 ) h g d d 和引理4 2 中型为( 5 ，1 ) 6 的( 4 ，3 ) 一i g d d 应用构造3 7 ，即可得到一个型为( 1 7 ，5 ) 6 的( 4 ，3 ) i g d d 当 = 1 0 时，由引理2 1 2 可知，存在一个型为( 6 ，2 t o t l ) 的( 4 ，3 ) h g d d ，t 5 ，7 ，9 ) 我们利用一个型为2 6 的( 4 ，3 ) 一g d d 填上它的1 0 个洞，即可得到型为( 2 0 + h ，九) 6 的( 4 ，3 ) 一i g d d ，h 5 ，7 ，9 当u = 1 5 时，对于5 h 1 3 的情况，由引理2 6 可知，存在一个r r r ) ( 1 7 ，1 6 ) ，又知 存在一个型为2 6 的( 4 ，3 ) 一g d d 和型为( 2 + t t ，t i ) 6 的( 4 ，3 ) 一i g d d ，其中t i o ，1 ) ，1 i 1 1 ，应用构造3 5 即得所要结果而对于h = 1 5 ，由定理1 3 可知，存在一个 ( 4 ，1 ) 一i g d d 型为( 4 5 ，1 5 ) 6 ，把它的区组重复三次即可 当u = 2 0 时，对于5 hs1 5 ，由引理2 6 和定理1 4 可知，存在一个r r i ) ( 1 2 ，1 1 ) 和一个型为4 6 的( 4 ，3 ) 一g d d ，由引理4 1 和4 2 可知存在型为( 4 + t i ，如) 6 的( 4 ，3 ) 一 i g d d ，t i o ，1 ，2 ) ，l i 6 ，应用构造3 5 即可得到型为( 4 0 + h ， ) 6 的( 4 ，3 ) - i g d d ， 6 这里h = 4 + t i 对于h = 1 7 ，对引理2 1 2 中型为( 6 ，8 5 1 6 1 ) 的( 4 ，3 ) 一h g d d 和引 i = l 1 0 和引理4 3 中型为( 9 ，1 ) 6 的( 4 ，3 ) i g d d 应用构造3 7 即可而对于h = 1 9 ，由引理 2 1 2 可知存在一个型为( 6 ，2 2 0 1 9 1 ) 的( 4 ，3 ) - h g d d ，利用一个型为2 6 的( 4 ，3 ) 一g d d 填 上它的2 0 个洞就是所要结果 当t ，= 3 0 时，对于5 h 2 5 ，同样对一个a t ) ( x 7 ，1 6 ) 。一个型为4 6 的( 4 ，3 ) 一( 3 d d 以及型为( 4 + 岛，厶) 6 的( 4 ，3 ) 一i ( 3 d d ，t i o ，1 ，2 ) ，1 i 1 1 ，应用构造3 5 即可得到 一个型为( 6 0 + h ， ) 6 的( 4 ，3 ) i g d d ，其中h = 4 + t i 对于h = 2 7 ，将定理1 3 中 型为( 8 7 ，2 7 ) 6 的( 4 ，1 ) 一i g d d 的区组重复三次即可对于h = 2 9 ，由引理2 1 2 与4 1 可知，存在一个型为( 6 ，6 1 0 2 7 1 ) 的( 4 ，3 ) 一h ( 3 d d 和一个型为( 8 ，2 ) 6 的( 4 ，3 ) 一i ( i d d ，应 用构造3 7 就能得到一个型为( 8 9 ，2 9 ) 6 的( 4 ，3 ) i ( 3 d d 当钐= 6 0 时，5 h 5 9 ，由引理2 6 ，4 1 ，4 3 和4 4 可知，分别存在t d ( 7 ，1 2 ) 和型为( 1 0 + t i ，厶) 6 的( 4 ，3 ) 一i g d d ，t i 0 ，1 ，2 ，3 ，4 ，5 ) 。1 i 1 2 ，应用构造3 4 即可 得到一个型为( 1 2 0 + h ， ) 6 的( 4 ，3 ) 一i ( 3 d d ，这里h = t i i = 1 引理4 5 若h 为奇数，且5sh 口。令t ， 1 4 ，1 8 ，2 2 ，2 6 ，3 4 ，3 8 ，4 6 ，6 2 ) ，则存在一个 型为( 2 u + h ， ) 6 的( 4 ，3 ) 一i c , d d 证明：由引理2 6 可知，存在一个t d ( 7 ，v 2 ) ，又因为存在型为( 4 + t i ，t i ) 6 的( 4 ，3 ) 一 i c i d d ，其中t i o ，1 ，2 ) ，l i v 2 ，应用构造3 4 即可得到所要结果 引理4 6 令口g 5 ，6 ，1 0 ，1 4 ，1 5 ，1 8 ，2 0 ，2 2 ，2 6 ，3 0 ，3 4 ，3 8 ，4 6 ，6 0 ，6 2 ，h 为奇数且5 h 钞，则存在型为( 2 v + h ， ) 6 的( 4 ，3 ) 一i g d d 证明：由引理2 6 可知，存在一个t d ( 7 ，移) ，又知存在型为( 2 - t - t i ，如) 6 的( 4 ，3 ) 一i g d d ， 其中t i o ，1 ) ，1 i 口，应用构造3 4 即可知结论成立 结合以上结果，我们可以得到如下定理 定理4 1 令9 一h 三0 ( r o o d2 ) 且0 3 h 9 ，则存在一个型为( 9 ， ) 6 的( 4 ，3 ) 一i g d d 4 2 u = 1 1 的情况 由引理1 1 可知，若存在一个型为( 9 ， ) 1 1 的( 4 ，3 ) 一i g d d ，则9 一h 为偶数且 0 3 h 9 令9 一h - - d2 v ，其中0 h u 引理4 7 令h 为偶数且2 h 移，则存在一个型为( 2 + h ，九) 1 1 的( 4 ，3 ) - i g d d 1 1 证明。对于( 秒，h ) = ( 5 ，2 ) ，由引理2 1 1 可知，存在一个型为( 1 l ，2 6 ) 的( 4 ，3 ) - h g d d ， 利用型为2 u 的( 4 ，3 ) 一g d d 填上它的5 个洞即可对于其它情形，由定理1 3 与1 4 可 知，存在一个型为( 秒+ h 2 ，h 2 ) 4 的( 4 ，1 ) - i g d d 和一个型为2 1 1 的( 4 ，3 ) - g d d ，应用 构造3 1 即可得所要结果 引理4 8 存在型为( 3 ，1 ) 1 1 ，( 5 ，1 ) u 和( 7 ，1 ) 1 1 的( 4 ，3 ) 一i c , d d 证明；对于( 9 ，h ) = ( 3 ，1 ) ，我们取点集x = 历3 ，组集夕= o ，1 ，2 + 3 i ：0 i a o ， 洞集y = f 3 看：0si l o 对于( 9 ，h ) = ( 5 ，1 ) 和( 7 ，1 ) ，令死= 夕一h ，我们取点集 x = 磊l nu 啦：0 i a o ，组集9 = 戗，i ，1 1 + i ，1 1 ( n 一1 ) + i ) ：0 i l o 及洞集y = 啦：0 i l o 下面列出所需基区组 ( 夕，h ) = ( 3 ，1 ) ：( + 3r o o d3 3 ) o ，1 7 ，2 5 ，3 1 o ，1 6 ，2 3 ，3 1 o ，4 ，7 ，2 8 o ，8 ，1 3 ，2 5 ) o ，1 ，2 ，4 ) o ，l o ，1 4 ，2 9 ) o ，1 9 ，2 6 ，3 1 o ，5 ，8 ，2 9 o ，1 0 ，1 4 ，1 9 ) o ，l ，2 ，4 ) o ，l o ，1 4 ，2 3 o ，1 3 ，1 9 ，2 8 ) o ，5 ，8 ，2 8 o ，1 6 ，2 6 ，3 2 o ，l ，2 ，1 6 o ，1 7 ，2 0 ，2 9 o ，1 7 ，2 5 ，3 2 ) o ，5 ，7 ，2 0 o ，2 0 ，2 6 ，3 2 o ，7 ，1 3 ，2 3 ) ，h ) = ( 5 ，1 ) ：( + 1r o o d4 4 ，啦+ l = a j ，其中歹= i + 1r o o d1 1 ) a o ，6 ，1 9 ，3 1 ) 6 ，1 2 ，1 9 ，3 3 6 ；1 4 ，2 3 ，4 1 a o ，l ，2 ，3 ) ( a o ，2 ，5 ，9 ) a o ，5 ，1 0 ，2 9 a o ，5 ，1 0 ，3 0 a o ，6 ，2 0 ，3 2 a o ，1 ，2 ，4 a o ，4 ，8 ，1 8 6 ，1 2 ，2 2 ，4 0 6 ，1 2 ，2 7 ，3 5 6 ，1 3 ，2 2 ，3 7 o o ，1 ，3 ，6 ) o o ，3 ，7 ，1 5 ) ( 9 ，h ) = ( 7 ，1 ) ：( + lr o o d6 6 ，啦+ 1 = a j ，其中j = i + 1r o o d1 1 ) a s ，2 0 ，4 0 ，4 7 1 7 ，2 5 ，4 3 ，5 5 ) a o ，8 ，3 2 ，5 3 ) a o ，l ，4 ，8 ) a o ，2 ，6 ，1 4 ) l o ，1 9 ，3 8 ，4 7 ( 1 3 ，1 4 ，1 6 ，2 9 a o ，5 ，1 9 ，4 2 a o ，l ，3 ，6 ) 【咖，7 ，2 1 ，3 1 ( 1 1 ，2 6 ，4 2 ，6 0 1 2 ，2 7 ，4 3 ，6 1 9 ，1 6 ，3 5 ，5 5 ) a o ，1 ，2 ，3 ) n o ，4 ，1 0 ，1 6 1 4 ，1 8 ，4 1 ，5 5 ) 1 6 ，2 2 ，4 1 ，5 8 a o ，5 ，1 8 ，2 8 ) a o ，2 ，7 ，1 5 1 8 ，2 7 ，4 8 ，5 8 引理4 9 当 4 时，存在一个型为( 2 口+ 1 ，1 ) 1 1 的( 4 ，3 ) - i g d d 当 3 时，存在 一个型为( 2 + 3 ，3 ) 1 1 的( 4 ，3 ) - i c i d d 证明：对引理2 1 1 中型为( 1 1 ，2 竹) 的( 4 ，3 ) 一h g d d ，7 1 , t ，u + 1 ) 和引理4 8 中型为 ( 3 ，1 ) 1 1 的( 4 ，3 ) 一i g d d 应用构造3 7 即可 1 2 下面我们同样只需讨论5 h t ，的情况 引理4 1 0 令钐a = 5 ，6 ，7 ，8 ，9 ，1 4 ，2 1 ，3 5 且h 为奇数，满足5 hs v 。则存在一 个型为( 2 u + h ，7 1 ) 1 1 的( 4 ，3 ) i g d d 证明，当钐= 5 时，由引理2 1 3 可知存在型为( 1 1 ，2 5 4 1 ) 的( 4 ，3 ) h g d d ，又因为存 在一个型为( 3 ，1 ) 1 1 的( 4 ，3 ) i g d d ，应用构造3 7 即可得到一个型为( 1 5 ，5 ) 1 1 的( 4 ，3 ) 一 i g d d 当t ，= 6 时，对引理2 1 1 中型为( 1 1 ，4 4 ) 的( 4 ，3 ) h g d d 与引理4 8 中型为( 5 ，1 ) 1 1 的( 4 ，3 ) i g d d 应用构造3 7 ，即得一个型为( 1 7 ，5 ) u 的( 4 ，3 ) i g d d 当 = 7 时，由引理2 1 3 可知，存在型为( 1 1 ，4 4 2 1 ) 的( 4 ，3 ) - h g d d ，又知存在型 为( 3 ，1 ) 1 1 和( 5 ，1 ) 1 1 的( 4 ，3 ) i g d d ，应用构造3 7 可以处理h = 5 的情况而当h = 7 时，同样对引理2 1 3 中型为( 1 1 ，2 7 6 1 ) 的( 4 ，3 ) 一h g d d 和型为( 3 ，1 ) 1 1 的( 4 ，3 ) 一i g d d 应用构造3 7 即可得所要结果 当移= 8 时，对于h - - - - 5 ，由引理2 1 l 可知，存在一个型为( 1 1 ，4 5 ) 的( 4 ，3 ) 一h g d d ， 又知存在一个型为( 5 ，1 ) 1 j 的( 4 ，3 ) 一i g d d ，应用构造3 7 即可而对引理2 1 3 中型为 ( 1 1 ，4 4 5 1 ) 的( 4 ，3 ) 一h g d d 和引理4 7 中型为( 6 ，2 ) 1 1 的( 4 ，3 ) i g d d ，同样应用构造3 。7 可以解决h = 7 的情况 当口= 9 时，对于h = 5 ，由引理2 1 3 可知，存在一个型为( 1 1 ，2 9 5 1 ) 的( 4 ，3 ) 一 h g d d ，利用一个型为2 1 1 的( 4 ，3 ) g d d 去填上它的9 个洞，即可得到一个型为( 2 3 ，5 ) 1 1 的( 4 ，3 ) i g d d 对于h = 7 ，对引理2 1 1 中型为( 1 1 ，6 4 ) 的( 4 ，3 ) 一h g d d 和引理4 8 中型为( 7 ，1 ) 1 1 的( 4 ，3 ) 一i g d d 应用构造3 7 即可同样对于一个型为( 3 ，1 ) n 的( 4 ，3 ) 一 i g d d 和引理2 1 3 中型为( 1 1 ，2 9 8 1 ) 的( 4 ，3 ) h g d d ，应用构造3 7 可