（应用数学专业论文）α可分解的圈系统.pdf

摘要 本文主要讨论了几种带有o t 可分解性质的圈系统的存在性和一类f r a m e 广义平衡 竞赛设计的存在性 设a k ( a d k v ) 是a 重 阶完全( 有向) 图一个m 长无向圈( 简称圈) 是一个由m 个 不同点乱l ，2 ，t l m 构成的点边序列记作( 让l ，u 2 ，u m ) 。其边集合为 ，u i + l ：i = 1 ，2 ，m 1 ) u “u m ，u l 一个仇长有向圈也是一个由m 个不同点u l ，缸2 ，u m 构 成的点边序列，记作( t l ，“2 ，t l m ) ，其有向边集合为 ( “t ，札件1 ) ：i = 1 ，2 ，m 一1 ) u ( 钆m ，锃- ) 若a 虬( 或a d 虬) 的边集可以分拆为m 长圈( 或m 长有向圈) 的集合。则称 这些圈( 或有向圈) 构成a 纸( 或a d k , ) 上的一个m 一圈系统( 或m 一有向圈系统) 。并记作 m c s ( v ，a ) ( 或m d c s ( v ，入) ) 若一个m c s ( v ，入) ( 或m d c s ( v ，入) ) 的圈( 或有向圈) 集 合可以分拆为若干个q 平行类，即设计中的每一个点在每一个平行类中均恰好出现q 次， 则称它是q 一可分解的本文的第一部分应用直接构作和递推构作的方法得出了q - 可分解 的4 - c s ( v ，a ) 和q 可分解的m d c s ( v ，a ) 在m = 3 ，4 时存在的充要条件 如果一个型为夕u 的( 4 ，3 ) g d d ( x ，夕，b ) 的区组集8 可以排列成一个( 9 u 4 ) xg u 的阵列，满足：( 1 ) 主对角线由乱个大小为( g 4 ) xg 的空子阵列组成；( 2 ) 每一列的区组 集构成x g ( 对某个g 9 ) 的一个部分1 一平行类，而每一行的区组集构成x e ( 对某 个g 9 ) 的一个部分4 平行类，则称该设计是一个f r a m e 广义平衡竞赛设计，并记作 f g b t d ( 4 ，g u ) 本文的第二部分基本解决了f g b t d ( 4 ，g u ) 的存在性问题 关键词：0 1 可分解圈系统可分组设计 i i i a b s t r a c t i nt h i sp a p e r , w ed i s c u s st h ee x i s t e n c eo ft h eq - r e s o l v a b l ec y c l es y s t e m sa n df r a m e g e n e r - a l i z e db a l a n c e dt o u r n a m e n td e s i g n s l e ta 石乙( a d 局0 ) b e ( d i r e c t e d ) c o m p l e t em u l t i g r a p ho fo r d e r a n di n d e xa ac y c l eo f l e n g t hm i sas e q u e n c eo fmd i s t i n c tv e r t i c e s u 1 ，u 2 ，乱m ，d e n o t e db y ( u 1 ， u 2 ，u m ) ，a n d i t se d g es e ti s u ，l t i + 1 ) ：i = 1 ，2 ，m 一1 u u l ，u 仇 ad i r e c t e dc y c l eo fl e n g t h mi sas e q u e n c eo fmd i s t i n c tv e r t i c e s u 1 ，1 2 ，“m 。d e n o t e db y ( u l ，u 2 ，乱m ) 。a n di t s d i r e c t e de d g es e ti s ( u t ，u i + 1 ) ：i = 1 ，2 ，m 一1 ) u ( 札m ，札1 ) ) i ft h e ( d i r e c t e d ) e d g e s o faa k ( a d k v ) c a nb ed e c o m p o s e di n t o ( d i r e c t e d ) c y c l e so fl e n g t hm ，t h e nt h e s e ( d i r e c t e d ) c y c l e sa l ec a l l e da ( d i r e c t e d ) m c y c l es y s t e m ，a n dd e n o t e db ym - c s ( v ，a ) ( m - d c s ( v ，入) ) a n m - c s ( v ，a ) ( m - d c s ( v ，a ) ) i ss a i dt ob eq r e s o l v a b l ei fi t s ( d i r e c t e d ) c y c l e sc a nb ep a r t i t i o n e d i n t oc l a s s e s ( c a l l e do t - r e s o l u t i o nc l a s s e s ) s u c ht h a te a c hp o i n to ft h ed e s i g no c c u r si np r e c i s e l y d c y c l e si ne a c hc l a s s i nt h ef i r s tp a r to ft h i sp a p e r , w ed e r i v et h ee x i s t e n c eo ft h eq r e s o l v a b l e 4 - c s ( v ，a ) a n do r e s o l v a b l em d c s ( v ，a ) f o r 2 = 3 ，4 i ft h eb l o c k so fa ( 4 ，3 ) 一g d d ( x ，乡，召) o ft y p eg uc a nb ea r r a n g e di nt oa ( g u 4 ) g u a r r a yw i t hp r o p e r t i e s ：( 1 ) t h em a i nd i a g o n a lc o n s i s t so fue m p t ys u b a r r a y so fs i z e ( g 4 ) 夕： ( 2 ) t h eb l o c k si ne a c hc o l u m nf o r map a r t i a l1 - r e s o l u t i o nc l a s s e sp a r t i t i o n i n gx gf o rs o m e g 9 ，w h i l et h eb l o c k si ne a c hr o wf o r map a r t i a l4 - r e s o l u t i o nc l a s s e sp a r t i t i o n i n gx gf o r s o m eg 9 ，t h e ni ti sc a l l e daf l a m eg e n e r a l i z e db a l a n c e dt o u r n a m e n td e s i g n ，a n dd e n o t e db y f g b t d ( 4 ，g u ) i nt h es e c o n dp a r to f t h i sp a p e r , w es o l v et h ee x i s t e n c eo f t h ef g b t d ( 4 ，g ) b a s i c a l l y k e yw o r d s ：q - r e s o l v a b l ec y c l es y s t e mg r o u pd i v i s i b l ed e s i g n i v 学位论文原创性声明 本人所提交的学位论文c i 一可分解的圈系统，是在导师的指导下，独立进行研 究工作所取得的原创性成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写过的研究成果。对本文的研究做h 重要贡献的个人和集体，均 已在文中标明。 本声明的法律后果由本人承担。 指导教师确认： 司砂 - z 0 4 多年了户jt o 同 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 论文作者：巧乏 力郴年弓户j t o 同 指导教师：匀衫 硼年3 月劢f t 引言 本文共分为两个部分，第一部分研究了q 可分解的4 - c s ( v ，a ) 和q 可分解的m d c s ( v ，a ) 在m = 3 ，4 时存在的充要条件第二部分基本解决了一类f r a m e 广义平衡竞 赛设计的存在性问题 令m ，咒，u ，a 为正整数，x 是一个 元集，n x 是指x 中每个点恰好重复n 次的多 重集x 上的一条无向边( 简称边) 是指无序对 z ，秒 ，一条有向边是指有序对( z ，可) ，这 里z ，y 是x 中任意两个不同点x 上的入重完全图，记作a k , ，是指x 上任意两个不同 点2 7 ，y 之间均恰有a 条边 z ，y 相连所构成的图x 上的a 重完全有向图，记作a d k , , ， 是指x 上任意两个不同点z ，y 之间均恰有a 对有向边( z ，y ) 和( y ，z ) 相连所构成的图 一个m 长无向圈( 简称圈) 是一个由m 个不同点n 。，“2 ，u m 构成的点边序列，记作 ( u l ，u 2 ，u 竹。) ，其边集合为 ，t i + l ：i = 1 ，2 ， 2 1 ) u “札m ，t i ) ) 一个m 长有 向圈也是一个由m 个不同点u l ，u 2 ，乱m 构成的点边序列，记作( u 。，u 2 ，u m ) ，其有向 边集合为 ( u ，u i + 1 ) ： = 1 ，2 ，m 一1 u ( u n 1 ) ) 若a k 。( 或a d k p ) 的边集可以分拆为t 1 1 长圈( 或7 n 长有向圈) 的集合，则称这些圈 ( 或有向圈) 构成入( 或入d 砥) 上的一个仇圈系统( 或m 一有向圈系统) ，并记作m - c s ( v ，入) ( 或矾一d c s ( ? 3 ，入) ) 一个3 - c s ( v ，a ) 即为区组长为3 的平衡不完全区组设计，并记 作b ( 3 ，a ；u ) ，而一个3 - d c s ( v ，入) 通常称为m e n d e l s o h n 三元系，并记作m t s ( v ，入) 一 个o t 平行类是一些圈( 或有向圈) 的集合，使得a k 。( 或a d k v ) 中的每个点在每个类中均 恰好出现。次若一个m c s ( v ，a ) ( 或m d c s ( v ，a ) ) 中的圈( 或有向圈) 可以分拆为若干 个o t 一平行类，则称它是q 可分解的1 可分解的m c s ( v ，a ) ( 或m d c s ( v ，a ) ) 简称为可 分解的m c s ( v ，a ) ( 或m d c s ( v ，a ) ) 易知0 1 可分解的m c s ( v ，a ) 存在的必要条件为： m l 避半，2 1 , x ( v 1 ) ，m l o r v ，q l 掣， 而乜一可分解的m d c s ( v ，a ) 存在的必要条件为： m c w ， o l a ( v 一1 ) ( 半木) 对口可分解的m c s ( v ，a ) ( 或m d c s ( v ，a ) ) 的存在性问题的研究已有相当长的一 段时间目前已知结论主要集中于m = 3 ，4 及q = 1 的情况1 9 9 1 年，d j u n g n i c k e l ，r c m u l l i n 和s a v a n s t o n e 完全解决了o t 可分解的3 - c s ( v ，a ) 的存在性问题 引理o 1 【1 】a 可分解的3 - c s ( v ，a ) 存在的充要条件为： a ( u 一1 ) 三o ( m o d2 ) ，a 勘( 移一1 ) 三o ( m o d6 ) ，3 1 。! u ，口l 掣， 除去口= 6 ，q = 1 ，a 三2 ( m o d4 ) 的情形 1 9 9 7 年，pg v o z d j a k 对任意m 3 给出了如下可分解的m c s ( v ，a ) 的存在性结果 引理0 2 1 2 l 令a ，d 和m 是正整数并且仇3 则a 虬m 有一个可分解m 圈系统当且仅当 不是下列情形： ( 1 ) a 三2 ( m o d4 ) ，d = 2 ，m = 3 ： ( 2 ) a 是奇数，d = 2 ，m = 3 ： ( 3 ) 入= 1 ，d = 4 ，m = 3 当m = 3 ，4 时，pa d a m s 给出可分解的m d c s ( v ，a ) 的存在性结果 引理o 3 【3 l 对m 3 ，4 ) ，存在可分解的m - d c s ( v ，a ) 当且仅当r e l y ，且( m ，口，a ) g ( 3 ，6 ，2 i + 1 ) ，( 4 ，4 ，2 i + 1 ) ：i 芝o 本文第一章讨论了条件( ，c ) ，( 木木) 分别对应于o e 一可分解的4 - c s ( v ，a ) 和。一可分解的 仇一d c s ( v ，a ) 在m = 3 ，4 时的存在性问题 设u ，a 为正整数，k 是一个正整数的集合一个可分组设计( k ，a ) 一g d d 是一个三元 组( x ，9 ，么) ，满足： ( 1 ) x 是一个v 元集： ( 2 ) 乡是x 中一些子集( 称作组) 的集合，且9 构成x 的一个分拆； ( 3 ) 4 是x 中一些子集( 称作区组) 的集合，对任意的a a ，l a l k ，并且每一对 属于不同组的点都恰好同时出现在a 个区组中，而属于同一组中的点对不出现在任意一 个区组中 ： ( k ，入) - g d d 的型为多重集t = i v ：g 乡) ，我们通常用指数形式来表达，o i b j 是指 该g d d 有i 个a 长组，j 个b 长组，如此类推当k = 忌 时，简记为k 一个型为舻的( k ，1 ) 一g d d 通常称为横截设计，并记作t d ( k ，n ) 若t d ( k ，n ) 的 区组集可以分拆为1 平行类，则称其为可分解横截设计，并记作r t d ( k ，n ) 并且已知 r t d ( k 一1 ，佗) 的存在性与t d ( k ，n ) 的存在性是等价的一个型为1 的( k ，a ) 一g d d 通 常称为成对平衡设计，并记作b ( k ，a ；u ) 设g ，让，k 为正整数，且kj g ，乱k + 2 对o i ，j u l ，定义r = w + ( i g k ) ： w = 0 ，1 ，( g k ) 一1 ) ，q = s + j g ：8 = 0 ，1 ，g 1 ) ( x ，9 ，4 ) 是一个型为9 u 的( k ，k 一1 ) 一g d d ，其中9 = g - ，g 2 ，g u ) 若其区组集4 中的区组可以排列成一个 ( i x i k ) xl x i 阵列f ( 其行和列分别用凰，兄l ，吼一l 和g o ，g l i g u l 中元标记) ，并 满足下列性质： ( 1 ) 设r ( 0 i u 一1 ) 为由尼和g f 中元标记的子阵列，则r 是空子阵列，也即阵 列f 的主对角线由u 个大小为( 9 k ) g 的空子阵列构成： 2 ( 2 ) 对任意r r ( o i u 一1 ) x g i 中的每个点都恰好在第r 行的k 个区组中 出现而g i 中的每个点不在第r 行的任意一个区组中出现： ( 3 ) 对任意c c j ( 0 j 冬珏一1 ) ，x g j 中的每个点都恰好在第c 列的一个区组中 出现，而g j 中的每个点不在第c 列中任意一个区组中出现； 则称该设计为一个f r a m e 广义平衡竞赛设计，并记作f g b t d ( k ，g u ) 显然f g b t d ( k ，g u ) 存在的必要条件为： k l g ，u k + 2( 木奉 ) f g b 丁d 实际上是殷剑兴，严洁和王成敏在研究广义平衡竞赛设计g b t d 时引入的 一类辅助设计，其中f g b t d ( 3 ，g u ) 和f g b t d ( 4 ，4 “) 的存在性已基本解决。 引理0 4 【4 j 令g ，乱为正整数，g 三o ( m o d3 ) ，牡5 则除了至多5 个可能的例外值即 ( 9 ，u ) ( 6 ，t 5 ) ，( 9 ，1 8 ) ，( 9 ，2 s ) ，( 9 ，3 4 ) ，( 3 0 ，1 5 ) 以外，f g b t d ( 3 ，9 u ) 存在 引理o 5 f 5 】令q o = 1 9 ，2 1 2 8 ，3 0 ，3 2 3 5 ，3 8 4 0 ，4 5 ，4 7 则对任意的整数乱6 ，且 缸叠q o ，f g b t d ( 4 ，4 缸) 存在 本文第二章通过讨论条件( 木车木) 的充分性基本解决了f g b t d ( 4 ，g ) 的存在性问题 3 1 口一可分解的圈系统 记满足必要条件( 率) 或( 枣木) 的o l ，a 的最小值为o t o ，a o 类似于【6 】中引理2 1 2 3 ，我 们有如下几个引理 引理1 1 若o t 可分解m - c s ( v ，a ) ( 或仇一d c s ( v ，a ) ) 存在，则o t o lo z ，a o ia 引理1 2 若0 1 可分解m c s ( v ，a ) ( 或仇d c s ( v ，a ) ) 存在，则t o t - 可分解m c s ( v ，n a ) ( 或 t o e 可分解m d c s ( v ，n a ) ) 也存在，其中扎是正整数，t 是整除避( 或业) 的正整数 引理1 3 若o l o 可分解m c s ( v ，a o ) ( 或 z d c s ( v ，a o ) ) 存在，口，a 为满足必要条件( 枣) ( 或 ( 木木) ) 的正整数，则。一可分解m c s ( v ，a ) ( 或m d c s ( v ，a ) ) 也存在 因此，为了证明必要条件( 幸) 和( 木木) 的充分性，只需讨论a o 一可分解，z c s ( v ，入o ) 和 a o 可分解m d c s ( v ，a o ) 的存在性即可我们先给出一些定义和记号 设m ，秽为正整数，o o 为无穷大元，磊为r o o du 剩余类加群令z = 磊 o c 为在磊 或磊t j 上构作的一些，7 z 长圈或m 长有向圈的集合对c c ，若c = ( c i ，c 2 ，c m ) ， 则定义c + j = ( c l + j ，c 2 + j ，c 仇+ j ) ，若c = ( c l ，c 2 ，c m ) ，则定义c + 歹= ( c l + 歹，c 2 + 歹，c m + j ) ，这里若o o c ，则+ 7 = o o ，而c + j = c + j ：c c ，j 磊 定义圈c 上的差z x c = c i + l c i ，c i q + l ：i = 1 ，2 ，m 一1 u c i c m ，c m c 1 ) ，这里若 o o c ，则一j = j o 。= o o ；有向圈c 上的差a c = c i + 1 一c t ：i = 1 ，2 ，m 一1 u c l c m 】，这里若o o c ，则o o j i = 。，歹一。o = 一。o ，并且以上的运算均在乙中进行 1 1q 一可分解4 圈系统 本节我们将用直接构作的方法解决q 一可分解4 - c s ( v ，a ) 的存在性问题根据必要条 件( 木) ，分为如下五种情形进行讨论： 1 三0 ( r o o d4 ) ，此时a o = 1 ，a o = 2 ： 2 u 三1 ( r o o d8 ) ，此时o l o = 4 ，a o = 1 ； 3 u 三5 ( r o o d8 ) ，此时o 0 = 4 ，a o = 2 ； 4 钞三2 ( r o o d4 ) ，此时q o = 2 ，a o = 4 ； 5 三3 ( r o o d4 ) ，此时o o = 4 ，, x o = 4 引理1 4 三0 ( r o o d4 ) 时存在可分解的4 - c s ( v ，2 ) 证明：由于此时q o = l ，由引理0 2 可知此类设计已存在 口 引理1 5 三1 ( m o d8 ) 时存在4 可分解的4 - c s ( v ，1 ) 证明：取点集为磊七+ l ，k 为正整数该设计所含圈的个数为必2 m = ( 8 k + 1 ) k ，所含平 4 行类的个数为驾= k 构作如下惫个4 长圈构成集合c ： (1 ，0 ，2 k ，4 k + 1 ) ， (2 ，0 ，2 k 一1 ，4 k + 1 ) ， (3 ，0 ，2 k 一2 ，4 k 十1 ) ， ， ( k 一1 ，0 ， k + 2 ， 4 七+ 1 ) ， (七，0 ，是+ 1 ，4 是+ 1 ) 容易验证，c 中圈的差ua c = 魄+ l ，从而 c + i ：i 磊七+ i ) 即是一个4 - c s ( v , 1 ) ，且对每 个圈c c ， c + i ：i 磊是+ l 恰好是该设计的一个4 平行类，所以该设计是一个4 可 分解的4 - c s ( v ，1 ) 口 引理1 6 秽三5 ( r o o d8 ) 时存在4 - 可分解的4 - c s ( v ，2 ) 证明：取点集为z 8 七十5 ，k 为非负整数该设计所含圈的个数为掣= ( 8 k + 5 ) ( 2 k + 1 ) ， 所含平行类的个数为掣= 2 k + 1 。我们构作2 k + 1 个圈形成集合c ： 第一类圈( 共k 个，每个重复2 次) ： (1 ，0 ，2 ，4 奄+ 3 ) ， ( 3 ，0 ，4 ，4 七+ 3 ) ， (5 ，0 ，6 ，4 k + 3 ) ， ( 2 七二3 ，0 ，2 k 一2 ，4 龙+ 3 ) ， ( 2 七一1 ，0 ，2 k ，4 k + 3 ) 第二类圈( 共1 个) ： ( 2 七十1 ，0 ，2 k + 2 ，4 尼+ 3 ) 由于ua c = 2 z 玉+ 5 ，从而 c + i ：i 磊是+ 5 形成一个4 - c s ( v ，2 ) ，且对每个圈c c ， c + i ：i z s 七+ 5 恰好是该设计的一个4 一平行类，所以该设计是一个4 - 可分解的4 - c s ( v ，2 ) 口 引理1 7u 三2 ( r o o d4 ) 时存在2 - 可分解的4 - c s ( v ，4 ) 证明：取点集为z 4 k + l u o 。) ，忌为正整数该设计所含圈的个数为型掣= ( 4 七+ 1 ) ( 2 七十1 ) ， 所含平行类的个数为剡2 a = 4 k + 1 构作如下2 k + 1 个圈的集合c ： 第一类圈( 共七个) ： (后，3 k 一1 ，3 k ，七一2 ) ， ( 忌+ 1 ，3 k 一2 ，3 k + 1 ，k 一3 ) ， 气 ( 七+ 2 ，3 k 一3 ，3 k + 2 ，七一4 ) ， ( 2 七一2 ，2 k + 1 ，4 k 一2 ，0) ， ( 2 七一1 ，2 k ，4 k 一1 ，4 k) 第二类圈( 共k 一1 个) ： 第三类圈( 共2 个) ： ( 1 ， ( 2 ， (3 ， ( k 一2 ， ( 七一1 ， 2 七一1 2 k 一2 ， 2 k 一3 七十2 七+ 1 2 七十1 2 后+ 2 。 2 七+ 3 3 七一2 3 k 一1 ， 4 后一1 ) ， 4 七一2 ) ， 4 尼一3 ) ， 3 七+ 2 ) ， 3 七+ 1 ) ( 。，0 ，2 k 4 k ) ，( 。o ，3 k ，惫，k 1 ) 同理由于ua c = 4 ( z ；k + iu ) ) ，则 c + i ：i z 4 k + 1 ) 形成一个4 - c s ( v ，4 ) 进一步由 c e c 于c 恰好是该设计的一个2 一平行类，则c ，c + 1 ，c + 4 k 恰好是该设计的所有2 一平行 类，所以该设计是一个2 一可分解的4 - c s ( v ，4 ) 口 引理1 8u 兰3 ( m o d4 ) 时存在4 可分解的4 - c s ( v ，4 ) ， 证明：( 1 ) 刨三3 ( m o d8 ) ，取点集为z 8 七+ 3 ，k 为正整数该设计所含圈的个数为型2 1 m 业= ( 8 七+ 3 ) ( 4 k + 1 ) ，所含平行类的个数为驾= 4 七十1 构作如下4 k + 1 个圈形成集合c ： 6 第一类圈( 共2 后个) ： 第二类圈( 共2 七个) ： ( 8 七一7 ，0 ，8 k 一6 ，8 k 一1 4 ) ， ( 8 七一3 ，0 ，8 k 一2 ，8 k 一6 ) ( 3 ，0 ，4 ，9 ) ， ( 7 ，0 ，8 1 7 ) ， 、l，、l，、-， 5 坞 缸；乙民加； 0 0 0 ； 1 5 9 ； (1 1 ，0 ， 1 2 ， 2 5 ) ， ；ii ( 8 奄一5 ，o ，8 k 一4 ，8 k 一1 0 ) ， ( 8 七一1 ，0 ，8 k ，8 k 2 ) 第三类圈( 共1 个) ： ( 1 ，0 ，2 ，3 ) 类似于前面的引理，容易验证 c + i ：i 磊老+ 3 形成一个4 - c s ( v ，4 ) ，且对每个圈c c ， c + i ：i z s k + 3 ) 恰好是该设计的一个4 一平行类，所以该设计是一个4 一可分解的4 一 c s ( v ，4 ) 。 ( 2 ) 口兰7 ( m o d8 ) ，取点集为z 8 七+ 7 ，k 为非负整数该设计所含圈的个数为型2 1 m 业= ( s k + 7 ) ( 4 k + 3 ) ，所含平行类的个数为避= 4 k + 3 构作如下4 k + 3 个圈形成集合c ： 第一类圈( 共k 个，每个重复4 次) ： ( 1 ，0 ，2 ， 4 七十4 ) ， (3 ，0 ，4 ，4 k + 4 ) ， (5 ，0 ， 6 ， 4 七十4 ) ， ， ( 2 七一3 ，0 ，2 k 一2 ，4 七十4 ) ， ( 2 七一1 ，o ， 2 七，4 七+ 4 ) 第二类圈( 共1 个，将其重复2 次) ： 二 ( 2 七+ 1 ，0 ，2 七+ 2 ，4 七十4 ) 第三类圈( 共1 个) ： ( 2 七十1 ，0 ，2 七十3 ，4 k + 4 ) 易知 c + i ：i 磊七+ 7 ) 即是一个4 - c s ( v ，4 ) ，且对每个圈cec ， c + i ：i z s k + 7 ) 恰好 是该设计的一个4 平行类，所以该设计是一个4 一可分解的4 - c s ( v ，4 ) 口 综合引理1 4 1 8 可得本节的主要结论： 定理1 9o f 可分解的4 - c s ( v ，a ) 存在的必要条件 4 i 掣，2 i _ 1 ) 4 l 。口刊掣 也是充分的 7 1 2q 一可分解的m t s ( v ，a ) 本节将通过递归构造和直接构造相结合的方法得到0 f 可分解m t s ( v ，a ) 的存在谱 为此先给出一些引理和定义，其中一些容易理解的引理的证明已省略 引理1 1 0 若d 可分解m t s ( v ，a 1 ) 和q 可分解m t s ( v ，a 2 ) 都存在，则q 一可分解 m t s ( v ，a l + a 2 ) 也存在 引理1 1 1 若口一可分解b ( 3 ，a ； ) 存在，则q 一可分解m t s ( v ，a ) 也存在 证明：设( x ，4 ) 为一个o l 一可分解b ( 3 ，a ；z ，) ，令 b = u ( z ，y ，z ) ，( z ，名，3 ，) ) ， z ，! ，z e a 则( x ，b ) 即为一个o t - 可分解m t s ( v ，入) 此时原b ( 3 ，a ；u ) 的一个o z 一平行类产生2 个 m t s ( v ，a ) 的o 平行类 口 引理1 1 2 若o t 一可分解m t s ( v ，a ) 存在，则q 一可分解b ( 3 ，2 a ；u ) 也存在 证明：给定一个q 一可分解m t s ( v ，a ) ，将其每个区组( z ，y ，z ) 均改写为 z ，y ，z ) ，即可得 到一个b ( 3 ，2 a ；u ) 而此时原m t s ( v ，a ) 的一个o t 平行类对应给出b ( 3 ，2 a ；u ) 的一个q - 平行类 口 一个设计的一个部分q 一平行类是由一些区组构成的集合，使得点集中的每个点要么 恰好出现在该平行类的q 个区组中，要么不出现在任意一个区组中不在部分q - 平行类 中出现的点称为该部分平行类的补 一个m e n d e l s o h n 可分组设计m g d d ( v ，a ) 是一个三元组( x ，9 ，4 ) ，满足： ( 1 ) x 是一个u 元集； ( 2 ) 9 是x 中一些子集( 称作组) 的集合，且9 构成x 的一个分拆； ( 3 ) 4 是x 中一些3 长有向圈( 通常称为循环三元组，简称为区组) 的集合，使得每 一个属于不同组的有序对都恰好同时出现在a 个区组中，而属于同一组的有序对不出现 在任意一个区组中 m g d d 的型的定义和g d d 的型的定义类似 设( x ，乡，4 ) 是一个m g d d ，p 是4 的部分o l 一平行类尸的集合，满足： ( 1 ) up = 4 ； p p ( 2 ) 对每个p p ，均存在某g i 9 ，ua = q ( x g i ) ，即p p 恰好以某一个组为 补， 则称其为一个q - 可分解m e n d e l s o h nf r a m e ( v ，a ) ，其型与原m g d d 的型一致当q = 1 时，简称其为m e n d e l s o h n r a m e ( v ，a ) r 如下两个引理分别是f 7 】中引理2 2 和f 1 】中引理6 3 的直接推广 引理1 1 3 设( x ，g ，4 ) 是一个g d d ( 指标为1 ) ，u ：x _ z + u 0 ) 是加权函数如果对每 个区组a 4 ，均存在型为 u ( z ) ：z a ) 的n - 可分解m e n d e l s o h nf r a m e ( u ( z ) ，a ) ， 则存在o r 一可分解m e n d e l s o h nf r a m e ( 叫( z ) ，a ) ，其型为 u ( z ) ：g 9 z xz ( ； s 引理1 1 4 若型为鲜1 9 。的o z 一可分解m e n d e l s o h n ，7 a m e ( g i u i ，a ) 和o r - 可分解 z = l s m t s ( g , + l ，入) ( i = 1 ，2 ，8 ) 都存在，则& 一可分解m t s ( g i u i + l ，a ) 存在 为了应用上面的构造，我们需要一些有关g d d 和q 一可分解m e n d e l s o h nf r a m e 的 结果 引理1 1 5 【8 】一个型为夕。的( u ，4 ，1 ) g d d 存在当且仅当9 ( 乱一1 ) 三0 ( r o o d3 ) ，9 2 u ( u 一1 ) 三 0 ( r o o d1 2 ) ，并且( g ，u ) z ( 2 ，4 ) ，( 6 ，4 ) ) 引理1 ，1 6 【8 】对任意 4 ，ug 6 ，1 2 ，1 4 ，1 8 ，2 6 ，3 0 ，b ( k ，l ；u ) 存在，其中k = 4 ，5 ，7 ，8 ，9 ， 1 0 ，1 l ，1 5 ，1 9 ，2 3 ，2 7 ) 引理1 1 7 【7 l 若u 三l ( r o o d3 ) ，则存在型为1 “的m e n d e l s o h nf r a m e ( u ，1 ) 引理1 1 8 【7 l 若乱4 且u 6 ，则存在型为3 u 的m e n d e l s o h nf r a m e ( 3 u ，1 ) 引理1 1 9 存在型为1 u 的3 - 可分解m e n d e l s o h nf r a m e ( u ，3 ) ，其中u 4 ，5 ，7 ，8 ) 证明：对 t ( 4 ，7 ，因为u 三l ( r o o d3 ) ，由引理1 1 7 ，型为1 “的m e n d e l s o h nf r a m e ( u ，1 ) 存在，将其区组重复3 遍即可得到型为1 u 的3 一可分解m e n d e l s o h nf r a m e ( u ，3 ) ，新设计 的部分3 平行类由原设计的1 个部分1 平行类重复产生的3 个部分1 一平行类合并而成。 对u = 5 ，取点集为磊，其基区组集为 a o ：( 1 ，2 ，3 ) ，( 2 ，4 ，1 ) ，( 3 ，1 ，4 ) ，( 4 ，3 ，2 ) 由于么。恰好是一个以 o 为补的部分3 一平行类，所以由它r o o d5 生成的设计即为所求的 型为1 5 的3 可分解m e n d e l s o h nf r a m e ( 5 ，3 ) 对锰= 8 ，取点集为历t _ j ，其区组集为 a ：( 0 ，1 ，2 ) ，( 0 ，2 ，4 ) ，( 0 ，5 ，4 ) ，( 0 ，4 ，3 ) ，( 0 ，2 ，6 ) ，( o o ，2 ，5 ) ，( 。o ，3 ，1 ) ，( ，5 ，4 ) ，m o d7 其部分3 一平行类为： r ( 。) ：( 0 ，1 ，2 ) ，( 1 ，2 ，3 ) ，( 2 ，3 ，4 ) ，( 3 ，4 ，5 ) ，( 4 ，5 ，6 ) ，( 5 ，6 ，o ) ，( 6 ，0 ，1 ) ； r ( 0 ) ：( 1 ，3 ，5 ) ，( 2 ，4 ，6 ) ，( 4 ，6 ，1 ) ，( 6 ，1 ，3 ) ，( o o ，2 ，5 ) ，( o 。，4 ，2 ) ，( o 。，5 ，3 ) ； r ( 1 ) ：( 0 ，5 ，4 ) ，( 2 ，0 ，6 ) ，( 5 ，3 ，2 ) ，( 6 ，4 ，3 ) ，( 。o ，4 ，o ) ，( ，3 ，2 ) ，( ，6 ，5 ) ； r ( 2 ) ：( 0 ，4 ，3 ) ，( 1 ，5 ，4 ) ，( 3 ，0 ，6 ) ，( 1 ，6 ，5 ) ，( ，6 ，4 ) ，( 。o ，3 ，1 ) ，( ，0 ，5 ) ； 9 n ( 3 ) ：( 0 ，2 ，6 ) ，( 2 ，4 ，1 ) ，( 5 ，o ，4 ) ，( 6 ，1 ，5 ) ，( ，0 ，6 ) ，o o ，2 ，1 ) ，( o o ，5 ，4 ) ； r ( 4 ) ：( 3 ，5 ，o ) ，( 1 ，3 ，o ) ，( 5 ，2 ，1 ) ，( 2 ，6 ，5 ) ，( o o ，2 ，o ) ，( ，l ，6 ) ，( ，3 ，6 ) ； n ( 5 ) ：( 6 ，3 ，2 ) ，( 4 ，6 ，3 ) ，( o ，2 ，4 ) ，( 3 ，1 ，o ) ，( o o ，6 ，2 ) ，( o o ，1 ，o ) ，( ，l ，4 ) ； n ( 6 ) ：( 3 ，5 ，2 ) ，( 5 ，o ，2 ) ，( 4 ，1 ，o ) ，( 4 ，2 ，1 ) ，( o o ，5 ，1 ) ，( o o ，0 ，3 ) ，( o o ，4 ，3 ) 这里兄( o o ) 以 o o ) 为补，n ( i ) 以 i ) 为补，i = 0 ，1 ，6 口 下面我们将分情形讨论口可分解的m t s ( v ，a ) 的存在性由必要条件( 木木) 容易算 出： 1 u 兰0 ( m o d3 ) ，此时q o = l ，a 0 = 1 ； 2 移三1 ( m o d3 ) ，此时0 1 0 = 3 ，a o = 1 ； 3 钉兰2 ( m o d3 ) ，此时a o = 3 ，a o = 3 对情形1 ，即v 三0 ( m o d3 ) 时，o o = 1 ，a o = l ，有关可分解m t s ( v ，1 ) 的结果可由引 理0 3 得到，为了完整起见我们将其用m t s 的语言并以定理的形式给出 定理1 2 0 若u 三0 ( m o d3 ) 且秽6 ，则存在可分解m t s ( v ，1 ) 由定理1 2 0 ，为证v 三0 ( m o d3 ) 时a 可分解m t s ( v ，a ) 的存在性，我们只需考虑 钉= 6 的情况 定理1 2 1 存在q 一可分解m t s ( 6 ，a ) ，其中q ，a 满足必要条件( 木毒) 并且a 三0 ( m o d2 ) 。 证明：首先存在可分解m t s ( 6 ，2 ) 取点集为磊，区组集为b = r ( i ) ：i = o ，1 ，9 ，这 里只( i ) ( i = 0 ，1 ，9 ) 定义如下： n ( o ) ：( 0 ，2 ，1 ) ，( 3 ，4 ，5 ) ；r ( 1 ) ：( 0 ，1 ，3 ) ，( 2 ，5 ，4 ) ； r ( 2 ) ：( 0 ，4 ，1 ) ，( 2 ，3 ，5 ) ；r ( 3 ) ：( 0 ，1 ，5 ) ，( 2 ，4 ，3 ) ； a ( 4 ) ：( 0 ，3 ，2 ) ，( 1 ，4 ，5 ) ；r ( 5 ) ：( 0 ，2 ，4 ) ，( 1 ，5 ，3 ) ； r ( 6 ) ：( 0 ，5 ，2 ) ，( 1 ，3 ，4 ) ；r ( 7 ) ：( 0 ，4 ，3 ) ，( 1 ，2 ，5 ) ； r ( s ) ：( 0 ，3 ，5 ) ，( 1 ，4 ，2 ) ；r ( 9 ) ：( 0 ，5 ，4 ) ，( 1 ，2 ，3 ) 容易验证每个r ( i ) 均为1 个1 平行类 进一步再由引理1 2 即可得结论成立 口 定理1 2 2 不存在可分解m t s ( 6 ，a ) ，其中a 三1 ( r o o d2 ) 证明：若该类设计存在，则由引理1 1 2 可知可分解8 ( 3 ，2 a ；6 ) 存在，此时2 a 三2 ( r o o d4 ) ， 这与引理0 1 矛盾 口 由于m t s ( 6 ，1 ) 不存在，所以不考虑其o z 一可分解性则对口可分解m t s ( 6 ，a ) ，只需 再考虑a 3 且a 三1 ( r o o d2 ) ，n 2 的情况下面在点集磊或z s u o o ) 上构作这些设 1 0 计 引理1 2 3 若存在5 一可分解m t s ( 6 ，a i ) ，a l 三1 ( m o d2 ) 且a l 3 和a 2 一可分解 m t s ( 6 ，a 2 ) ，a 2 三1 ( r o o d2 ) 且a 2 3 。则n 一可分解m t s ( 6 ，入) 存在这里q 和a 是 满足必要条件( 木奉) 的正整数，且q 2 ，a 三1 ( m o d2 ) ，a 3 证明：首先考虑必要条件( 幸宰) 。由于此时移= 6 ，所以3 a v 显然成立，而由o i 整除a ( v 一1 ) ( 即5 a ) 可知，o 是5 的倍数或是a 的因子因此若5 一可分解m t s ( 6 ，a 1 ) ( a t 三1 ( m o d2 ) 且a l 3 ) 和人2 一可分解m t s ( 6 ，a 2 ) ( 入2 三l ( r o o d2 ) 且a 2 3 ) 都存在，则对题设中任 意要求的q 和a ，若q 是5 的倍数，不妨设q = 5 k ，k 为正整数，而a 三1 ( m o d2 ) ，则由 5 - m t s ( 6 ，a ) 出发应用引理1 2 即可得q 可分解m t s ( 6 ，a ) 存在；若q 是a 的因子。不妨 设a = s o l ，s 为正整数，则。必为奇数由q m t s ( 6 ，d ) 出发应用引理1 2 即可得q 一可