（运筹学与控制论专业论文）恰有两个β1型区组的（1241）pmd.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均己在论文中作了声明并表示了 谢意。 作者签名：边 日期：2 q q 生! 旦2 旦 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子 版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文 进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行 检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在解 密后适用本规定。 作者签名： 日期：2 q q 生且2 8 旦 摘要 我们称( 盖，4 ) 为一个( ”，4 ，1 ) 完全m e n d e l s o h n 设计，简记为( u ，4 ，1 ) - p m d ， 其中x 是”个点的集合，a 是x 的循环有序4 子集( 称之为区组) 构 成的集合，使得每一对x 的有序点对的t 间隔在且仅在4 中的一个区 组中出现，1 t 3 设a 是4 的一个区组，若在4 中有k 个区组与a 没有共同的元素，则称a 是型为厥的区组本文一共找出3 个恰好有 两个卢1 一区组的不同构的( 1 2 ，4 ，1 ) p m i ) 关键词：完全m e n d e l s o h n 设计，不同构，凤区组 a b s t r a c t ap e r f e c tm e n d e l s o h nd e s i g n ，d e n o t e db y ( u ，4 ，1 ) - p m di sap a i r ( x ，a ) w h e r exi sa 口一s e t ( o fp o i n t s ) a n dai sac o l l e c t i o no fc y c l i c a l l yo r d e r e d4 - s u b s e to f x ( c a l l e db l o c k s ) ，s u c ht h a te v e r yo r d e r e dp a i ro fp o i n t so fxa p p e a r st - a p a r ti ne x a c t l y o n eb l o c ko f 4 f o ra n y t ，w h e r e l 3 l e t ab eab l o c ko f a ，t h e r eh a v ekb l o c k s i n aw h i c hh a v en oc o l n n l o ne l e m e n t sw i t ha ，t h e nw es a ya i sa 隗- b l o c k i nt h i sa c t i c l e ， w ew i l ls h o wt h a tt h e r ea r ee x a c t l y3n o n - i s p m p r p h i c ( 1 2 ，4 ，1 ) 一p m d sw i t he x a c t l yt w o 卢1 b l o c k s k e yw o r d s ：p e r f e c tm e n d e l s o h nd e s i g n ，n o n - i s o m o r p h i s m ，仇一b l o c k 前言 组合设计是离散数学的一个重要分支，是一门研究将事物按特定要求进行安排配 置并讨论其性质的学问区组设计理论是组合数学的个重要分支，它主要研究 某一个有限集的满足一定条件的子集系的存在性问题，构造问题，以及( 在少数 可能情况下的) 相应计数问题。 历史上曾经有过一些著名的组合设计问题，例如e u l e r 3 6 军官问题及正交拉丁 方问题，k i r k m a n 女生问题等等对这些问题的兴趣和研究在一定程度上推动了 组合设计理论的发展这些问题的原始形式虽然仅仅表现为趣味数学的问题，但 随着对它们研究的不断发展又提出了许多需要以设计作为其数学工具的实际问 题这样，当设计理论自身和科学技术都发展到了一定的阶段时，它就从原先的 趣味数学课题上升为具有强烈实际应用背景的一个数学领域了 我们先给出区组设计的一般定义 定义：称有限集x 上的( 任意) 一个子集簇日= b ，b 2 ，玩) 为x 上的一个区组 设计，记作d = ( x ，b ) x 称为此设计的基集，而子集簇b 中的子集最“= 1 ，b ) 则称为是此设计的区组 基集x 中的元素个数i x i 称为是设计的阶，对i = l ，b ，区组鼠的基数l b ；l 又 称为是鼠的区组容量( 或区组大小，或区组长度) 对。x ，b 中含有。的区组 个数称为是元素z 的重复数，记作r ( z ) 对z ，y ex 而z y 时，8 中包含二元 子集 。，计的区组个数称为是元素z 和y 的相遇数，记作b ( z ，) 定义：设d = ( x ，b ) 是一个区组设计，又设b 1 是b 的一个子族如果b 。的区 组构成了集合x 的一个划分，则称层，是设计d 的一个平行类如果b 可划分 成若干个两两不相交的平行类的集合，则称d 是一个可分解设计 例：k i r k m a n 女生问题 在1 8 5 0 年，德国一教师k i r k m a n 提出如下一个问题：一位教师每天带领他班 上的1 5 名女学生出去散步，他把这些女生分成5 组，每3 人一组，能否作出一 个连续七天的计划，使得任意两名女生在7 天内都正好只有一次被安排在同一 组? k i r k m a n 女生问题也就是一个可分解设计，下面就是k i r k m a n 女生问题的一 个解，我们不妨设这1 5 个女生由1 到1 5 来编号； 第一日： 1 ，2 ，5 ) ， 3 ，1 4 ，1 5 ， 4 ，6 ，1 2 ， 7 ，8 ，1 1 ， 9 ，1 0 ，1 3 第二日： l ，3 ，9 ) 2 ，8 ，1 5 ) ， 4 ，l l ，1 3 ) ， 5 ，1 2 ，1 4 ， 6 ，7 ，1 0 ) 4 第三日： 1 ，4 ，1 5 ) ， 2 ：9 ，1 1 ) ， 3 ，1 0 ，1 2 ， 5 ，7 ，1 3 ) ， 6 ，8 ，1 4 第四日： 1 , 6 ，1 1 ) ，f 2 ，7 ，1 2 ， 3 ，8 ，l a ， 4 ，9 ，1 4 ， 5 ，l o ，1 5 ) 第五日； 1 , 8 ，l o ) 2 ，1 3 ，1 4 ， 3 ，4 ，7 ) ， 1 ，则必有： 一1 ) 三0 ( r o o d ( k l 骁 a v ( v 一1 ) 兰0 ( r o o dk ( k 一1 ) ) k i r k m a n 女生问题就相当于一个可分解( 1 5 ，3 ，1 ) 一b i b d 定义：设”是正整数，我们称( x ，8 ) 为s t e i n e r 三元系，其中x 是个元素 的集合，舀是x 的一个子集簇( 其中的成员b 称为区组) ，满足以下两个条件： ( 1 ) 如果b 廖，则i b i = 3 ； ( 2 ) x 中任意两个不同元素恰在尽的一个区组中出现 一个口阶的s t e i n e r 三元系就是一个( v , 3 ，1 ) b i b d 由b i b d 存在的必要条件知 ”阶s t e i n e r 三元系存在的必要条件为”3 且”三l 或3 ( m o d6 ) 我们记b = i 层i ， 由定义显然b = v ( v 一1 ) 6 例：设x = 1 ，2 ，3 ，4 ，5 ，6 ，7 ) ， 舀= “1 ，2 ，3 ) ， j ) 设u ， 是正整数一个( 、k ， ) 一m e n d e l s o h n 设计，简记为( u ，k ， ) m d ，定义 为一个二元组暖，研，其中工是。个点的集合，8 是x 的循环有序肛子集( 称 为区组) 的集合，使得点集x 的每对有序对恰好在8 的 个区组中出现若对 所有担1 ，2 ，k 一1 ，点集x 的有序对的扣间隔恰在口中a 个区组中出现，那 么( u ， ) 一m d 被称为是完全设计，简记为( ，a ) 一p m d 若我们忽略循环有序性，一个女，1 ) p m d 就是一个平衡不完全区组设计， 简记为( ”，女，女一1 ) 一b i b d ，群这个b i b d 的 = 一1 因此，我们可以将一个完全 m e n d e l s o h n 设计( p m d ) 看成是一个平衡不完全区组设计( b i b d ) 的推广 我们知道( u ，k ，a ) - p m d 的区组数目b = 加扣一1 ) k 因而，( u ， ) 一p m d 存在 的一个基本必要条件是蛔扣一1 ) 三0 ( r o o dk ) 这条必要条件在大多数情况下都 是可行的，但并不适用所有的情况 m e n d a w o h n ( 1 9 6 9 ，【4 1 ) 首先通过一系列拟群设计证明了沁4 ，l 卜p m d s 的存在性 但是并没有致力于找出其所有结果直到b e n n e t ( 1 9 8 5 ，【5 1 ) 利用p b d 闭包对口il ( r o o d4 ) 的情况给出了几乎完全的解张学斌( 1 9 9 0 ，【6 1 ) 相当成功的解决了”e0 ( r o o d4 ) 的情况经过连续不断的研究后，b e n n e t te ta 1 ( 1 9 9 0 ，【7 】) 关于h4 ，a ) p m d s 给出了总结性的结论 定理：( b e n n e t t ，1 9 8 5 ) ( u ，4 ，1 ) 一p m d 存在当u ；l ( r o o d4 ) ，除了v = 3 3 ，5 7 ，9 3 ，1 3 3 定理：( x u e b i nz h a a g ，1 9 9 0 ) ( ，4 ，1 ) 一p m d 存在当 ；0 ( r o o d4 ) ，除了v = 8 ，1 2 ，3 3 定理：( b e n n e t t ，x u e b i nz h a n g ，z h ul i e 1 9 9 0 ) ( 口，4 ，a ) _ p m d 存在的充要条件是 ( 1 ) ) 兰0 ( r o o d4 ) ，除了( 1 2 ，4 ，1 ) p m d 关于最引人注目的( 1 2 ，4 ，1 ) 一p m d 的存在性问题， b e n n e t t ，f e ，s h e n ，h ，y i n ，j ， ( 1 9 9 4 ， 8 】) 合作的一篇文章提供了个具体的例子，这说明了( 1 2 ，4 ，1 ) 一p m d 是存在 的- 但这个例子是通过纯计算机搜索得到的本文主要工作是分析研究了0 2 ，4 ，1 ) 。 p m d 的构造，并且对其中一种情况即恰好含有两个岛型区组的( 1 2 ，4 ，1 ) 一p m d 进 行了分析构造，得到3 个不同构的这种设计。 6 第一章引人 1 1 基本定义，定理，引理 定义1 1 ：设 ，k ， 为非负整数，( x ，肛) 是一个( 。， ， ) 平衡不完全区组设计( 简 称b i b d ) ，如果x 是u 集( 元索称作点) ，矗是x 的元子集簇( 称作区组) ，使得 x 的任意两个不同元素恰好出现在 个区组中 定义1 2 ：如果一个b i b d 的区组可以把区组分成一些平行类，则称这个b i b d 是可分解的b i b d ( 简记r b i b d ) 定义1 3 ：设f ，k ， ，n 为非负整数， 扛l ，x 2 ，) 称为扛l ，2 ：2 ，。t 的循环 有序k - 子集，且在 ( q ) - ：i 曩t ，j = 1 ，2 ，k ) 集合中，任何一个有序对 ( 甄，q ) 称为( j i ) 一间隔0 i ) 或者( b + j i ) 一间隔 n 定义1 4 ：( x ，a ) 是一个( ，a ) 完全m e n d e l s o h n 设计，筒记为( ，k ， ) 一p m d ，其 中x 是。个点的集合，么是x 的循环有序k 子集( 称之为区组) 构成的集合， 使得每一对x 的有序点对的t 间隔恰好在4 中的a 个区组中出现，1 t k - 1 我们知道( ，a ) - p m d 的区组数目b = 如扣一1 ) k 因而，( ，k ， ) 一p m d 存 在的一个基本必要条件是, k v ( v 1 ) i0 ( r o o dk ) 这条必要条件在大多数情况下 都是可行的，但并不适用所有的情况 定义1 5 ：如果一个p m d 的区组可以把点集分成一些平行类，则称这个p m d 是可分解的p m d ( 简称r p m d ) 定义1 6 ：设a 是4 的一个区组，若在a 中有k 个区组与a 没有共同的元素， 则称a 是型为凤的区组 定义1 7 ：两个( 1 2 ，4 ，1 ) - p m d ( x ，p 1 ) 和( x ，鲍) 是同构的，如果有一个双射妒 x 时x 使得对每一个b b l ，有l p ( b ) 召2 设( x ，4 ) 是一个( u ，k ，a ) 一p m d ，a 一1 = ( ( d ，c ，b ，酬( n ，6 ，c ，d ) a ) 那么( x ，a 一1 ) 也是一个( v , k ，a ) p m d 设_ 和召都是是x 的循环有序k 一子集的集合，由定义1 7 知，若嚣= a ，我们 称它们是同构的也就是( x ，4 ) 和( x ，b ) 是同构的 7 定理1 8 ( b e n n e t te ta 1 ，1 9 8 0 ) 设p 时一个奇素数，r 是一个整数并且r 1 ，那么就存在杪，p ，1 ) 一p m d 定理1 9 ( m e n d e l s o h n ，1 9 7 7 ) 设口= p r 是任意一个素数幂，k 是”一1 的一个因子且k 2 ，那么就存在( ”，k ，1 ) 一 p m d 定理1 1 0 ( m e n d e l s o h n ，1 9 7 1 ；b e n n e t t ，1 9 8 2 ) ( ，3 ，a ) 一p m d 存在的必要条件，a v ( v 一1 ) ；0 ( m o d3 ) 也是充分条件，除了( 6 , 3 ，1 ) - p m d 不存在 定理1 1 1 ( b e n n e t ，1 9 8 5 ；b e n n e t te ta 1 ，1 9 9 0 b ，1 9 9 4 ；m e n d e l s o h n ，1 9 6 9 ；z h a n gx u e b i n ，1 9 9 0 ) ( ”，4 ， ) 一p m d 存在的必要条件，a v ( v 一1 ) e0 ( r o o d4 ) 也是充分条件，除了v = 4 时a 为奇数，以及v = 8 时a = i 不存在 推论1 1 2 ：( ，4 ，1 ) 一p m d 存在当且仅当 扣一1 ) e0 ( r o o d4 ) 一4 ，8 1 2 满足条件的一些方程( 组) 定理1 1 3 ：若存在( ，k ，a ) 一b i b d ，其中 1 ，则必有： a ( 口一1 ) 兰o ( m o d ( k 1 ) ) a v ( v 一1 ) ；o ( m o dk ( k 一1 ) ) 引理1 1 4 设( x ，8 ) 是( 1 2 ，4 ，3 ) 一b i b d ，b = 蚰，9 2 ，蜘，玑) b ，用q 表示苴中恰有 b 的i 个元素的区组的个数则有： 0 0 + 0 1 + 0 2 + 0 3 + x 4 = 3 3 z 1 + 2 x 2q - 3 x 3 - b 4 x 4 24 4 z 2 + 3 ：r 3 + 6 x 4 = 1 8 证明：b i b d 存在的必要条件是 r = b k ，r ( 一1 ) = a ( v 一1 ) 这里， = 1 2 ，k = 4 ， = 3 ，所以有r = 1 1 ，b = 3 3 第一个方程表示区纽数是 b = 3 3 ，第二个方程表示b 中元素出现的次数是4 r = 4 4 ，第三个方程表示b 中元 8 素对个数是6 a = 1 8 以上方程组有7 个解 $ o = 0 ，x l 。2 8 ，0 2 = 0 ，9 3 = 4 ，z 4 。1 o o 。l ，o 】= 2 5 ，x 2 。3 ，9 3 = 3 ，x 4 = 1 o o = 2 ，1 = 2 2 ，2 = 6 ，3 = 2 ，2 ；4 = 1 x 0 = 3 ，0 1 。1 9 ，z 2 = 9 ，茁3 。1 ，x 4 = 1 o o = 4 ，0 1 = 1 6 ，0 2 = 1 2 ，正3 = 0 ，0 4 = 1 z o20 ，q = 2 7 ，2 = 3 ，z 3 = 1 ，x 4 = 2 x 0 2 1 ，0 1 22 4 ，3 7 2 = 6 ，0 3 20 ，z 4 。2 定理1 1 5 ：设( x ，) 是一个( 1 2 ，4 ，1 ) p m d ，设日= “n ，b ，c ，d i ( o ，b ，c ，d ) 一4 ) ，那么 ( x ，嚣) 是一个无重复区组的( 1 2 ，4 ，3 ) b i b d 由定理1 1 5 ，引理1 1 4 的方程组只有前5 个解 引理l ，1 6 ：设( x ，4 ) 是一个( 1 2 ，4 ，1 ) - p m d ，a 是a 的一个区组，那么a 是型为凤 的区组，k = o ，1 ，2 ，3 ，4 引理1 1 7 ：设( x ，) 是一个( 1 2 ，4 ，1 ) 一p m d ，a 是4 的一个区组设2 x 且2g a ， q 定义为中含有z 且与a 恰有i 个共同元素的区组个数，那么我们有如下等 式： c o + c l + c 2 + c 32 1 1 c j + 2 c 2 + 3 c 3 = 1 2 证明：第一个方程表示元素z 的度数是r = 1 1 第二个方程表示b 中元素与z 构成的元素对有4 a = 1 2 个 以下是这个方程组的所有解 “) ：c o = 7 ，c 1 = 0 ，c 2 = o ，e 3 = 4 ( i i ) ：c 0 = 6 ，c l = 1 ，。2 = 1 ，c 3 = 3 ( i i i ) ：c o = 5 ，c 1 = 3 ，c 2 = 0 ，c 3 = 3 ( i v ) ：c o = 6 ，c 1 = 0 ，沈= 3 ，c 3 = 2 扣) ：c 0 = 5 ，c l = 2 ，c 2 = 2 ，c 3 = 2 ( ”i ) ：句= 4 ，c i = 4 ，c 2 = l ，国= 2 ( 疵) ：c o = 3 ，c 1 = 6 ，c 2 = 0 ，c 3 = 2 ( v i i i ) ：c 0 = 5 ，c 1 = 1 ，c 2 = 4 ，c 3 = 1 ( i 。) ：c o = 4 ，c l = 3 ，c 2 = 3 ，c 3 = 1 忙) ：c a = 3 ，c l = 5 ，c 2 = 2 ，。3 = 1 9 0但锄 ( x i ) ：c o 。2 ，e 1 = 7 ，c 2 = l ，c 321 ( x i i ) ：c o = 1 ，。】= 9 ，c 2 = 0 ，c 3 = 1 ( x i i i ) ：c o = 5 ，c 1 = 0 ，c 2 = 6 ，c 3 = 0 ( x i i i ) ：c o = 4 ，c i = 2 ，c 2 = 5 ，e z = o ( x i i i ) ：c o = 3 ，c 1 = 4 ，c 224 ，e 3 = 0 ( x i i i ) ：c o = 2 ，c 1 = 6 ，e 2 = 3 ，c 3 = 0 ( x i i i ) ：c o = 1 ，c 1 = 8 ，。2 = 2 ，c 3 = 0 ( x i i i ) ：c o = 0 ，。1 = l o ，。2 = 1 ，e 3 = 0 引理1 1 8c 。sz d i = o ，1 ，2 ，3 ) 则这个方程组只有以下几组解： c o 。3 ，e l = 5 ，c o = 2 ，c 3 = 1 c 0 22 ，c 1 = 7 ，c 2 = 1 ，c 3 = 1 c o = 1 ，o l = 9 ，c 2 = 0 、c 3 = 1 c o24 ，e 1 = 2 ，c 2 = 5 ，c 3 = 0 c o = 3 ，e l = 4 ，0 2 = 4 ，c 3 = 0 c o22 ，c 1 = 6 ，c 2 = 3 ，c 3 = 0 c 0 2 1 ，c 1 = 8 ，c 2 = 2 ，c 3 = 0 c o = 0 ，c 】= 1 0 ，c 2 = 1 ，c 3 = 0 第二章恰有两个历型区组的( 1 2 ，4 ，1 ) 一p m d 的同构分类 在本章及以后的讨论中，若无特别说明，用k 坑岛毋表示无序的区组，用( 吼b ，c ，d ) 表示循环有序的区组 2 i 对( 1 2 ，4 ，1 ) 一p m d 的分析 定理2 1 ；设( x ，4 ) 是一个( 1 2 ，4 ，1 ) - p m d ，8 = 。，b ，c ，d ) ：( o ，b ，c ，d ) 枷若存在 一个区组型为角，那么在同构的意义下，不妨设b 为下形式： b o = 3 ，6 ，9 ，1 2 ) b 1 = 1 ，4 ，7 ，1 0 ) b 2 = 1 ，3 ，6 ，9 ) ，b 3 = ( 4 ，6 ，9 ，1 2 ，b 4 = 7 ，3 ，9 ，1 2 b 5 = 1 0 ，6 ，1 2 ，2 ) ，b 6 = 1 0 ，3 ，1 2 ，5 ) ，b 7 = 1 1 ，3 ，6 ，8 ) b s = 岛b i a f 3 ， b 1 4 b 1 5 一b 1 9 = 6 ，) b 2 0 b 2 1 一b 2 6 = 9 ，) b 2 7 = b 2 b = b a 2 1 2 ，) 证明；设a o 是型为卢1 的区组，不妨设a 。的元素为 3 ，6 ，9 ，1 2 ) 因为z o = l ，z l = 2 5 ，。2 = 3 ，。3 = 3 ，x 4 = 1 ，在同构的意义下可以设： b o = 3 ，6 ，9 ，z 2 b i = 1 ，4 ，7 ，1 0 ) b 2 = 卜，3 ，6 ，9 ) ，b a = 一，6 ，9 ，1 2 ，b 4 = 一，3 ，9 ，1 2 ) b 5 = 一，6 ，1 2 ，一) ，b 6 = 一，3 ，1 2 ，一) ，b 7 = 一，3 ，6 ，一) 玩b 9 = b l a = 3 ， b 1 4 b 1 5 - = b 1 9 = 6 ，) b 2 0 b 2 1 一b 2 s = 9 ，) b 2 r = b 2 8 = 。b a 2 i 2 ，) 若ze 1 ，4 ，7 ，1 0 ，易知c o = 1 ，c 1 = 9 ，c 2 = o ，c 3 = 1 或者c o = 1 ，。l = 8 ，。2 ：2 ，c 3 ： 0 ，因此不失般牲，在同构意义下有： b 2 = 1 ，3 ，6 ，9 ) ，b a = 4 ，6 ，9 ，1 9 ，b 4 = 7 ，3 ，9 ，1 2 b 5 = o o ，6 ，1 2 ，一) ，风= 1 0 ，3 ，1 2 ，一) ，岛= ( 一，3 ，6 ，一) 若z 2 ，5 ，8 ，1 1 ，易知c o = 0 ，c l = i 0 ，c 2 = 1 ，。3 = 0 ，因此不失一般性，在同构意 义下有： 1 1 b 5 = l o ，6 ，1 2 ，2 ) ，b 6 = l o ，3 ，1 2 ，5 ，b t = l l ，3 ，6 ，8 ) 定理2 2 ：设( x ，4 ) 是一个( 1 2 ，4 ，1 ) p m d ，b = “。，b ，c ，d ) 1 ( 。，b ，c ，d ) 椰若存在型 为卢。的区组a o ，则在同构的意义下，a o 只有如下的2 种形式： a o = ( 3 ，6 ，9 ，1 2 ) 或山= ( 3 ，1 2 ，6 ，9 ) 证明：由定理2 1 ，b o = 3 ，6 ，9 ，1 2 ，则a o 有6 种可能( 不失一般性从元素3 开始) ： ( 3 ，6 ，9 ，1 2 ) ，( 3 ，1 2 ，9 ，6 ) ，( 3 ，6 ，1 2 ，9 ) ，( 3 ，9 ，1 2 ，6 ) ，( 3 ，9 ，6 ，1 2 ) ，( 3 ，1 2 ，6 ，9 ) 由于( 3 ，6 ，9 ，1 2 ) 和( 3 ，1 2 ，9 ，6 ) 完全相颠倒，则对于任何一个拥有区组( 3 ，1 2 ，9 ，6 ) 的( 1 2 ，4 ，1 ) p m d ，总可以找到一个拥有区组( 3 ，6 ，9 ，1 2 ) 的p m d ，使得两者的区组 完全颠倒由定义1 7 知，他们是同构的例如： ( 3 ，6 ，9 ，1 2 )( 3 ，1 2 ，9 ，6 ) ( 1 0 ，1 ，4 ，7 )( 1 0 ，7 ，4 ，1 ) ( 1 ，3 ，9 ，6 )( 1 ，6 ，9 ，3 ) ( 4 ，6 ，1 2 ，9 ) 完全颠倒 ( 4 ，9 ，1 2 ，6 ) ( 7 ，9 ，3 ，1 2 ) 毒 ( 7 ，1 2 ，3 ，9 ) ( 1 0 ，2 ，1 2 ，6 )( 1 0 ，6 ，1 2 ，2 ) ( 1 0 ，3 ，5 ，1 2 )( 1 0 ，1 2 ，5 ，3 ) ( 1 1 ，8 ，6 ，3 )( 1 1 ，3 ，6 ，8 ) 同理，由于( 3 ，6 ，1 2 ，9 ) 和( 3 ，9 ，1 2 ，6 ) 完全相颠倒，得到的( 1 2 ，4 ，1 ) 一p m d 同构； ( 3 ，g ，6 ，1 2 ) 和( 3 ，1 2 ，6 ，9 ) 完全相颠倒，得到的( 1 2 ，4 ，1 ) p m d 同构 因此，我们只要考虑三种情况：( 3 ，6 ，9 ，1 2 ) ，( 3 ，9 ，1 2 ，6 ) 和( 3 ，1 2 ，6 ，9 ) 另外，我们发现对于任何一个拥有区组( 3 ，9 ，1 2 ，6 ) 的( 1 2 ，4 ，1 ) p m d ，交换元素3 与6 ，得到一个拥有区组( 3 ，6 ，9 ，1 2 ) 的p m d 例如： ( 3 ，6 ，9 ，1 2 )( 6 ，3 ，9 ，1 2 )( 3 ，9 ，1 2 ，6 ) ( 1 0 ，1 ，7 、4 ) ( t 0 ，1 ，7 ，4 )( 1 0 ，1 ，4 ，7 ) ( 1 ，3 ，9 ，6 )( 1 ，6 ，9 ，3 )( 1 ，6 ，3 ，9 ) ( 4 ，6 ，1 2 ，9 ) 3 h6 ( 4 ，3 ，1 2 ，9 ) 2 h5 ( 4 ，9 ，6 ，1 2 ) ( 7 ，9 ，3 ，1 2 )( 7 ，9 ，6 ，1 2 ) 4 h7 ( 7 ，3 ，1 2 ，9 ) ( 1 0 ，2 ，1 2 ，6 ) ( 1 0 ，2 ，1 2 ，3 )( 1 0 ，6 ，2 ，1 2 ) ( 1 0 ，3 ，5 ，1 2 )( 1 0 ，6 ，5 ，1 2 )( 1 0 ，5 ，1 2 ，3 ) ( 1 1 ，8 ，6 ，3 )( 1 1 ，8 ，3 ，6 )( 1 1 18 ，3 ，6 ) 这样我们可以知道( 3 ，6 ，9 ，1 2 ) 和( 3 ，9 ，1 2 ，6 ) 也是同构的因此我们只用考虑( 3 ，6 ，9 ，1 2 ) 和( 3 ，i 2 ，6 ，9 ) 这两种情况了 定理2 3 ：区组b l 不可能是簖型的 证明；反设日1 是岛型的，z o = 1 ，。1 = 2 5 ，z 2 = 3 ，z 3 = 3 ，；t 4 = 1 ，则在b 8 一b 3 2 中要出现b l 的3 个3 一组合，3 个2 一组合，2 0 个1 一组合( 已经出现5 个) 但 是在b 8 一b 3 ：中只有2 5 个区组，无法安排这些组合矛盾 推论2 4 ：若b 8 一岛2 中的区组聩与b l 相交为3 ，则最不可能是卢l 型的 证明：由定理2 3 ，b ；不可能有x 3 = 3 定理2 5 ：区组b 2 一b 4 只可能是卢3 型的 证明：由于在b 8 一b 3 2 中每个区组只有一个 3 ，6 ，9 ，1 2 ) 的元素，故玩一鼠只可 能与b o 相交为3 ，即岛型 定理2 6 ：区组b 5 一b 7 不可能是岛型的 证明：反设b 5 是岛型的，则元素对( 2 ，1 0 ) 要在b 8 一b 3 2 中出现3 次，则4 个 ( 2 ，1 0 ) 元素对中必然有两个有相同的间隔矛盾 b 6 ，口7 同理 定理2 7 ：若有第二个卢l 型区组，则这个区组必然在b 8 一日3 2 中出现 证明：由引理2 3 2 6 可得 2 2 同构分类 在这些由计算机找到的p m d 中没有找到至少有三个型为卢1 的区组的p m d ， 则可以把它们可以分为恰有一个风型区组的和恰有两个口1 型区组的两大类 对于只有一个芦l 型区组的p m d ，因为唯一的觑型区组是由f 3 ，6 ，9 ，1 2 ) 构成， 故若有同构映射必然把元素( 3 ，6 ，9 ，1 2 ) 映射成1 3 ，6 ，9 ，1 2 ) 从构造方法看出，两 个有相同组型的p m d 是否同构等价于他们的前8 个区组是否同构，因此同构分 类可以很快进行对有两个卢型区组的p m d ，因为若有同构映射不一定把元素 3 ，6 ，9 ，1 2 映射成 3 ，6 ，9 ，1 2 ) ，故同构分类无法仅仅从对前8 个区组的同构分类 来做 定理2 8 ：p m d ( b i b d ) 的组型是同构不变量 由定理2 2 知，若两个( 1 2 ，4 ，1 ) - p m d 组型不同，则它们不同构我们需要解 决的是组型相同的p m d 的同构分类问题 推论2 9 ：如果两个p m d ( x ，层1 ) 和( x ，岛) 同构，且有同构映射妒：x - x 使 得对任意妒( 。) ：f ( z ，g x ) ，则蝮( z ) = 畦( ) 这里，噶( ) o 1 ，2 ) ，i 1 ，2 ，3 4 ) ，o x ) 表示元素。在( x ，岛) 中的岛型区组的度数 对于两个有相同组型的p m d ( x ，日1 ) 和( x ，且2 ) ，如果有一个双射妒o ：d 盘( x ) 卜 磕) ，则如果同构映射l p ：x x 存在，妒。应该是l p 的限制，而且由此可以 很快找到这个同构映射相反，如果这样的双射啪不存在，则由推论2 3 ，这两 个p m d 不同构 西者部青蝉岛型区组，卫伞1 臼r 型馐组叶俨伞1 9 昏铲个一芦r 型医组融 设两者同掏，回构映射叫l 广由型为印山g 区组知呻删f r l 而冠嘉百邵驵2 梧 风超戳圣维的虞婺萌t 男4 是5 3 2 ，3 弛3 ，巨】k 一财1 咐哥舒辞越挣1 - 七3 母 卧r 即 l p m 芦尚斟卡叫$ 弗呼再通过比较五泰盛锄胡矗戳妾虱挣赛数微快哥琶好峥 封褥掏映射( 16 3u ) ( 25 9 8z 】24 ) ，这蓠伞十醒旷| 可杯 定理2 1 0 ：三组含有2 个风型区组的( 1 2 ，4 ，1 ) 一p m d 均每组同构 证明：同榉的寿法r - 其他两组p m q 也互必找珥犀梅e 蚶融 一、2 个岛型，6 个卢2 型，2 2 个风型，3 个角型 区组组型 区组组型区组组型 | ( 3 ，1 2 ，6 ，9 ) 风( 1 0 ，1 ，7 ，4 )风( 1 ，9 ，6 ，3 )风 ( 4 ，6 ，1 2 ，9 )岛( 7 ，3 ，9 ，1 2 ) 卢3 ( 1 0 ，1 2 ，2 ，6 ) 疡 ( 1 0 ，5 ，1 2 ，3 )侥( 1 1 ，8 ，3 ，6 ) 风 ( 3 ，2 ，7 ，5 ) 岛 ( 3 ，4 ，8 ，2 )玩( 3 ，5 ，1 ，t 0 ) 卢3 ( 3 ，7 ，2 ，1 1 ) 岛 ( 3 ，8 ，4 ，1 ) 岛 ( 3 ，1 1 ，1 0 ，4 ) 风( 6 ，1 ，5 ，1 1 )风 ( 6 ，2 ，1 0 ，8 ) 岛 ( 6 ，4 ，2 ，5 ) 卢3 ( 6 ，5 ，4 ，7 ) 岛 ( 6 ，7 ，1 1 ，1 )卢3 ( 6 ，8 ，7 ，1 0 ) 伤 ( 9 ，1 ，8 ，5 ) 风 ( 9 ，2 ，4 ，1 1 )风( 9 ，5 ，2 ，8 ) 岛 ( 9 ，7 ，1 ，2 ) 风 ( 9 ，8 ，1 0 ，7 )岛( 9 ，1 0 ，1 1 ，4 )卢l( 9 ，1 1 ，5 ，1 0 )风 ( 1 2 ，1 ，1 1 ，2 )风( 1 2 ，4 ，5 ，7 )岛( 1 2 ，5 ，8 ，1 1 )岛 ( 1 2 ，8 ，1 ，4 ) 愚( 1 2 ，1 0 ，2 ，1 )岛( 1 2 ，1 1 ，7 ，8 )伤 1 4 区组组型区组 组型区组 组型 ( 3 ，1 2 ，6 ，9 ) 风( 1 0 ，7 ，4 ：1 ) 风( 1 ，6 ，3 ，9 ) 侥 ( 4 ，1 2 ，9 ，6 ) 岛( 7 ，9 ，1 2 ，3 ) 风( 1 0 ，6 ，1 2 ，2 ) 岛 ( 1 0 ，3 ，5 ，1 2 ) 胁( 1 1 ，8 ，3 ，6 ) 风( 3 ，1 ，8 ，4 ) 卢3 ( 3 ，2 ，5 ，7 ) 角( 3 ，4 ，7 ，2 ) 岛 ( 3 ，8 ，2 ，1 ) 风 ( 3 ，加，4 ，1 1 )虎( 3 ，1 1 ，1 0 ，5 ) 疡( 6 ，1 ，7 ，1 1 ) 屉 ( 6 ，2 ，4 ，5 )风( 6 ，5 ，1 1 ，7 ) 风( 6 ，7 ，1 0 ，8 ) 岛 ( 6 ，8 ，5 ，4 )岛( 6 ，1 0 ，1 ，2 ) 阮 ( 9 ，2 ，1 1 ，1 ) 侥 ( 9 ，4 ，1 0 ，1 1 )岛( 9 ，5 ，i ，4 ) 觑 ( 9 ，7 ，8 ，1 0 ) 角 ( 9 ，8 ，7 ，5 )屁( 9 ，1 0 ，2 ，8 ) 风( 9 ，1 1 ，5 ，2 ) 岛 ( 1 2 ，1 ，5 ，1 0 )岛( 1 2 ，4 ，2 ，7 ) 岛( 1 2 ，5 ，8 ，1 ) 岛 ( 1 2 ，7 ，1 ，1 1 )风( 1 2 ，8 ，1 1 ，2 ) 风( 1 2 ，l l ，4 ，8 ) 岛 区组组型区组组型区组 组型 ( 3 ，6 ，9 ，1 2 )岛( 1 0 ，1 ，4 ，7 ) 隗 ( 1 ，3 ，9 ，6 ) 风 ( 4 ，6 ，1 2 ，9 ) 风( 7 ，9 ，3 ，1 2 )风( 1 0 ，2 ，1 2 ，6 ) 角 ( 1 0 ，1 2 ，5 ，3 ) 风 ( 1 1 ，8 ，6 ，3 ) 风( 3 ，1 ，2 ，1 0 )风 ( 3 ，2 ，4 ，8 ) 风 ( 3 ，4 ，1 0 ，1 1 ) 风( 3 ，5 ，1 ，7 )风 ( 3 ，7 ，5 ，2 ) 岛( 3 ，8 ，1 1 ，4 )夙( 6 ，2 ，5 ，1 1 )风 ( 6 ，4 ，l ，5 ) 风 ( 6 ，5 ，4 ，2 ) 国 ( 6 ，7 ，8 ，1 0 ) 岛 ( 6 ，8 ，7 ，1 )岛( 6 ，1 1 ，l o ，7 ) 如 ( 9 ，1 ，加，4 ) 风 ( 9 ，2 ，1 1 ，1 ) 岛 ( 9 ，5 ，7 ，1 1 ) 岛 ( 9 ，7 ，2 ，8 ) 风 ( 9 ，8 ，4 ，5 ) 风 ( 9 ，1 0 ，8 ，2 ) 岛 ( 9 ，1 1 ，5 ，1 0 ) 岛 ( 1 2 ，1 ，8 ，5 )也( 1 2 ，2 ，7 ，4 ) 卢3 ( 1 2 ，4 ，1 1 ，7 ) 岛 ( 1 2 ，8 ，1 ，1 1 ) 岛 ( 1 2 ，1 0 ，5 ，8 ) 岛( 1 2 ，1 1 ，2 ，1 )岛 1 与2 的同构映射：( 25 ) ( 47 ) ( 36 ) 2 与3 的同构映射：( 1 27641 01 21 1 5 ) ( 3 8 9 ) 二、2 个卢l 型，3 个岛型，1 8 个卢3 型，1 0 个风型 区组组型区组组型区组组型 ( 3 ，1 2 ，6 ，9 ) 岛 ( 1 0 ，4 ，7 ，1 )岛( 1 ，9 ，6 ，3 ) 岛 ( 4 ，6 ，1 2 ，9 )岛( 7 ，3 ，9 ，1 2 )岛 ( 1 0 ，1 2 ，2 ，6 ) 风 ( 1 0 ，5 ，1 2 ，3 )岛 ( 1 1 ，8 ，3 ，6 ) 角 ( 3 ，2 ，8 ，4 ) 岛 ( 3 ，4 ，1 ，5 ) 良 ( 3 ，5 ，1 0 ，1 1 ) 岛 ( 3 ，7 ，4 ，2 ) 尻 ( 3 ，8 ，2 ，1 )岛( 3 ，1 1 ，7 ，1 0 )岛( 6 ，l ，2 ，1 1 )角 ( 6 ，2 ，4 ，5 )角( 6 ，4 ，1 1 ，1 0 )风( 6 ，5 ，7 ，8 )岛 ( 6 ，7 ，5 ，1 ) 卢3 ( 6 ，8 ，1 0 ，7 )岛 ，1 ，4 ，1 0 )风 ( 9 ，2 ，1 0 ，8 )岛 ( 9 ，5 ，8 ，7 ) 岛 ( 9 ，7 ，1 1 ，4 ) 履 ( 9 ，8 ，1 ，1 1 ) 屁 ( 9 ，l o ，2 ，5 ) 尾 ( 9 ，1 1 ，5 ，2 ) 岛 ( 1 2 ，1 ，7 ，2 ) 岛( 1 2 ，4 ，8 ，l i )岛 ( 1 2 ，5 ，1 l ，1 ) 风 ( 1 2 ，8 ，5 ，4 ) 岛 ( 1 2 ，1 0 ，1 ，8 ) 角 ( 1 2 ，1 1 ，2 ，7 ) 屁 1 5 区组组型 区组组型 区组 组型 ( 3 ，6 ，9 1 2 ) 序l( 1 0 ，7 ，4 ，1 ) 岛( 1 ，6 ，3 9 ) 尻 ( 4 ，9 ，6 ，1 2 ) 风( 7 ，1 2 ，9 ，3 ) 侥( 1 0 ，1 2 ，6 ，2 )岛 ( 1 0 ，5 ，3 ，1 2 ) 风( 1 1 ，3 ，8 ，6 ) 屈( 3 ，1 ，1 1 ，1 0 ) 角 ( 3 ，2 ，8 ，4 ) 卢l( 3 ，4 ，7 ，8 )岛 ( 3 ，5 ，2 ，1 ) 风 ( 3 ，1 0 ，4 ，2 ) 岛( 3 ，1 1 ，5 ，7 )角( 6 ，1 ，5 ，4 ) 风 ( 6 ，4 ，1 1 ，7 ) 觑( 6 ，5 ，8 ，1 0 ) 岛( 6 ，7 ，1 ，2 ) 成 ( 6 ，8 ，7 ，5 ) 岛( 6 ，1 0 ，2 ，1 1 )岛( 9 ，2 ，4 ，8 ) 侥 ( 9 ，4 ，1 0 ，1 1 ) 触( 9 ，5 ，1 1 ，2 )风( 9 ，7 ，2 ，5 ) 风 ( 9 ，8 ，5 ，1 0 ) 风( 9 ，1 0 ，1 ，7 )岛( 9 ，1 1 ，8 ，1 ) 风 ( 1 2 ，l ，8 ，2 ) 风 ( 1 2 ，2 ，7 ，1 1 ) 风( 1 2 ，5 ，l ，4 ) 岛 ( 1 2 ，7 ，1 0 ，8 )角( 1 2 ，8 ，1 1 ，1 ) 岛 ( 1 2 ，1 1 ，4 ，5 ) 岛 同构映射：( 1 794 1 0 ) ( 2 5 1 2 ) ( 3 8 6 ) 三、2 个风型，2 个岛型，1 6 个卢3 型，1 3 个角型 区组 组型区组组型区组组型 ( 3 ，6 ，9 ，1 2 )卢1( 1 0 ，4 ，7 ，1 )风( 1 ，6 ，3 ，9 )岛 ( 4 ，9 ，6 ，1 2 ) 岛( 7 ，1 2 ，9 ，3 )岛( 1 0 ，1 2 ，6 ，2 )岛 ( 1 0 ，3 ，1 2 ，5 )风 ( 1 1 ，3 ，8 ，6 ) 反 ( 3 ，1 ，4 ，8 ) 角 ( 3 ，2 ，8 ，7 ) 卢4 ( 3 ，4 ，1 0 ，5 ) 岛 ( 3 ，5 ，l i ，2 ) 风 ( 3 ，1 0 ，2 ，1 )威 ( 3 ，1 1 ，7 ，4 ) 良 ( 6 ，1 ，5 ，7 ) 卢l ( 6 ，4 ，1 1 ，加)反 ( 6 ，5 ，1 ，1 1 ) 风 ( 6 ，7 ，8 ，5 ) 风 ( 6 ，8 ，2 ，4 ) 卢4 ( 6 ，1 0 ，7 ，2 )岛( 9 ，2 ，1 1 ，1 ) 岛 ( 9 ，4 ，2 ，7 ) 觑 ( 9 ，5 ，8 ，1 0 ) 岛 ( 9 ，7 ，1 0 ，1 1 ) 角 ( 9 ，8 ，4 ，5 ) 岛 ( 9 ，1 0 ，1 ，8 )风( 9 ，1 1 ，5 ，2 ) 岛 ( 1 2 ，1 ，7 ，5 )风( 1 2 ，2 ，5 ，4 )觑( 1 2 ，7 ，1 1 ，8 ) 卢3 ( 1 2 ，8 ，1 ，2 )风 ( 1 2 ，1 0 ，8 ，1 1 ) 风 ( 1 2 ，1 1 ，4 ，1 ) 风 区组组型区组组型区组组型 ( 3 6 ，9 ，1 2 ) 岛 ( 1 0 ，7 ，1 ，4 ) 岛 ( 1 ，3 ，9 ，6 )