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

果。 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、刨新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意。 作者签名 日期 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定。学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子 版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文 进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行 检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在解 密后适用本规定。 作者签名： 日期： 摘要 我们称( x ，_ ) 为一个( ”，4 ，1 ) 完全m e n d e l s o h n 设计，简记为 ( ”，4 ，1 ) p m d ，其中x 是”个点的集合，4 是x 的循环有序4 子 集( 称之为区组) 构成的集合，使得每一对x 的有序点对的t 一 间隔在且仅在a 中的一个区组中出现，1st 3 设a 是a 的 一个区组，若在_ 中有个区组与a 没有共同的元素，则称 a 是型为凤的区组本文一共找出1 3 8 个恰好有一个卢t 区组 的不同构的( 1 2 4 1 ) p m d 关键词：完全m e n d e l s o h n 设计，不同构，凤区组 2 a b s t r a c t a p 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 ( ”，4 ，1 ) 一p m d i sap a i r ( x ，a ) w h e r exi sav - 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 fx ( 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 fx a p p e a r st - a p a r ti ne x a c t l yo n eb l o c ko fa f o ra n yt ，w h e r el st 3 l e ta b eab l o c ko f t h e r eh a v ekb l o c k si n4w h i c hh a v en oc o u l m o 1e l e m e n t s w i t ha ，t h e nw es a yai 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 e a r e1 3 8n o n - i s o m o r p h i c ( 1 2 ，4 ，1 ) p m d sw i t he x a c t l yo n e 卢1 - b l o c k 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 3 前言 组合设计是离散数学的一个重要分支，是- - i 研究将事物按特定 要求进行安排配置并讨论其性质的学问区组设计理论是组合数学的 一个重要分支它主要研究某一个有限集的满足一定条件的子集系的 存在性问题，构造问题，以及( 在少数可能情况下的) 相应计数问题 历史上曾经有过一些著名的组合设计问题，例如e u l e r 3 6 军官问题 及正交拉丁方问题，k i r k m a n 女生闽题等等对这些同题的兴趣和研 究在一定程度上推动了组合设计理论的发展这些问题的原始形式虽 然仅仅表现为趣味数学的问题，但随着对它们研究的不断发展又提出 了许多需要以设计作为其数学工具的实际问题这洋，当设计理论自 身和科学技术都发展到了一定的阶段时，它就从原先的趣味数学课题 上升为具有强烈实际应用背景的一个数学领域了 我们先给出区组设计的一般定义 定义0l ：称有限集x 上的( 任意) 一个子集簇1 3 = s t b 2 ，岛) 为x 上的一个区组设计，记作d = ( x ，舀) x 称为此设计的基集，而子集簇 8 中的子集t 3 。( i = 1 ，b ) 则称为是此设计的区组 基集x 中的元素个数i x l 称为是设计的阶对i = 1 ，b ，区组 晟的基数b ：又称为是b ：的区组容量( 或区组大小，或区组长度) 对 。x ，层中含有z 的区组个数称为是元素。的重复数，记作r ( z ) 对 ，y ex 而。g 时，层中包含二元子集扛，f ) 的区组个数称为是元素 。祁y 的相遇数，记作a n ( x ，掣) 定义0 2 ：设d = ( x ，1 3 ) 是一个区组设计，又设8 l 是b 的一个子族如 果1 3 l 的区组构成了集合x 的一个划分，则称8 l 是设计d 的一个平 行类如果8 可划分成若干个两两不相交的平行类的集合，则称d 是 4 一个可分解设计 例l ：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 个女生由l 到1 5 来编号： 第一日： l ，2 ，5 ) “3 ，1 4 ，1 5 ，( 4 ，6 ，1 2 ， 7 ，8 ，i i ，( 9 ，1 0 ，1 3 第二日： l ，3 ，9 ) 7 ( 2 ，8 ，1 5 ，f 4 ，i i ，1 3 ，( 5 ，1 2 1 4 6 ，7 ，1 0 ) 第三日： l ，4 ，1 5 ， 2 ，9 ，1 1 ) ， 3 ，1 0 ，1 2 ， 5 ，7 ，1 3 ， 6 ，8 ，1 4 第四日： l ，6 ，1 1 ) ，( 2 ，7 ，1 2 ， 3 ，8 ，1 3 ， 4 ，9 1 4 ， 5 ，l o ，1 5 第五日：( 1 ，8 ，i o ，( 2 1 1 3 ，1 4 ， 3 ，4 ，7 ， 1 ，则必有 ( 口一1 ) ；0 ( m o d ( k 1 ) ) a v ( v 一1 ) 兰0 ( r o o dk ( k 1 ) ) 5 k i r k m a n 女生问题就相当于一个可分解( 1 5 ，3 ，1 ) 一b i b d 定义0 5 ：设口是正整数，我们称( x ，b ) 为s t e i n e r 三元系，其中x 是 口个元素的集合，廖是x 的一个子集簇( 其中的成员口称为区组) ，满 足以下两个条件： ( 1 ) 如果b 8 ，则i b i = 3 ； ( 2 ) x 中任意两个不同元素恰在8 的一个区组中出现 一个口阶的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 且口三1 或3 ( r o o d6 ) 我们记b = i b ，由定义显然b = v ( v 一1 ) t 6 例2 ：设x = ( 1 ，2 ，3 ，4 ，5 ，6 ，7 ) ， 8 = 1 ，2 ，3 ) ， l ，6 ，5 ) ， 1 ，7 ，4 ) ， 2 ，4 ，6 ) ， 2 ，7 ，5 ) ， 3 ，4 ，5 ) 3 7 6 ) ) 则( x 尽) 是一个7 阶s t e i n e r 三元系 1 9 7 1 年，m e n d e l s o h n 在区组设计中引入了区组中的元素是循环 有序的概念他首先着眼于s t e i n e r 三元系的自然推广，最初称为”循 环三元系”，后来被g a n t e re ta ( 1 9 7 7 ，f l 】) 命名为m e n d e l s o h n 三元系 ( m t s s ) m e n d e l s o n ( 1 9 7 7 ，【2 】) 提出了”完全循环设计”的概念，在h s u 和k e e d w e l l ( 1 9 8 5 ， 3 ) 所作的研究中将这种设计称为m e n d e l s o h n 设计 个不同元素的集合扣1 ，a 2 ，n k 是循环有序的若a l n 2 j ) 定义1 2 ：我们称( x ，a ) 为一个( u ，k ，a ) 完全m e n d e l s o h n 设计，简记为 ( v ，k ，a ) 一p m d ，其中z 是”个点的集合，4 是x 的循环有序k 一子集 ( 称之为区组) 构成的集合，使得每- - x 于x 的有序点对的t 间隔在且仅 在a 中的a 个区组中出现，1 t 曼k 一1 定义1 3 ：设 是4 的一个区组，若在_ 中有k 个区组与j 4 没有共同 的元素，则称a 是型为段的区组 定义1 4 ：设( x ，4 ) 是一个( ，k ，a j p m d ，a 一1 = f 池c ，b ，8 j j ( 8 ，6 c ，固 那么( x ，4 _ 1 ) 也是一个( v , k ， ) p m d 定义1 5 ：设4 和层都是x 的循环有序k 子集的集合，若存在映射妒 从x 到x ，使得妒( = 8 ，那么我们称( x ，4 ) 和( x ，8 ) 是同构的 l 2 基本定理和引理 定理1 6 ：( v , 4 ，1 ) 一p m d 存在的充要条件是口( 一1 ) i0 ( r o o d4 ) ，。4 ，8 定理1 7 ：设( x ，且) 是一个( 1 2 ，4 ，1 ) 一p m d ，设b = n ，b ，c ，町，b ，c ，d ) 9 椰，那么( x ，8 ) 是一个无重复区组的( 1 2 ，4 ，3 ) 一b i b d 定理1 8 ：设( x a ) 是一个f 1 2 ，4 ，1 ) - p m d ，a 是4 的一个区组，定 义为在4 中与a 恰好有i 个共同元素的区组个数，那么我们有下列等 式： z 0 + zl + 茁2 + 工3 + 2 7 4 = 3 3 z t + 2 2 2 + 3 x 3 + 4 2 4 = 4 4 。2 + 3 2 3 + 6 2 4 = 1 8 0 4 = l 其解为： ( 0 ) x o = 0 ，o l = 2 8 ，z 2 = 0 ，0 3 = 4 ，x 4 = l ( 1 ) x o = 1 ，o l = 2 5 ，x 2 = 3 ，0 3 = 3 ，z 4 = 1 ( 2 ) z o = 2 ，孤。2 2 ，2 ：2 = 6 、2 3 = 2 ，x 4 = l ( 3 ) x o = 3 ，t i = 1 9 ，2 2 = 9 ，z 3 = 1 ，x 4 = l ( 4 ) x o 。4 ，2 ：1 。1 6 ，x 2 = 1 2 ，x 3 = 0 ，x 4 = 1 证明：由于区组数是b = v ( v 一1 ) k = 3 3 ，且由题意知道，x o + x , + x 2 + x a + x 4 就是所有区组的总合等于3 3 ；我们知道每一个元素出现的次数是r = b k v ，在这里r = l l ，因而z i + 2 x 2 十3 2 3 + 4 x 4 表示所有与之相交的 区组的相交元素出现的个数；我们又知道每对元素对出现3 次，所以 。2 + 3 x 3 + 6 x 4 表示所有与之相交的区组的相交元素元素对出现的个数 引理1 9 ：设( x ，a ) 是一个( 1 2 ，4 ，1 ) - p m d ，a 是4 的个区组，那么4 是型为仇的区组，k = 0 ，1 ，2 ，3 ，4 定理1 1 0 ：设( x 。a ) 是一个( 1 2 ，4 ，1 ) p m d ，a 是a 的一个区组设z x 且z 岳a ，岛定义为a 中含有z 且与a 恰有i 个共同元素的区组个数， 那么我们有如下等式：( 易知qs 反) c 04 - c 1 + c 2 + 6 3 = 1 1 c l + 2 c 2 + 3 c 3 = 1 2 1 0 且由定理1 8 知道：c o + c 3 4 ( 因为。o + 。3 曼4 ) 其解为： c o 。3 ，c l = 5 ，c 2 = 2 ，c 3 = 1 c o = 2 ，c l = 7 ，c 2 。1 ，c 3 = 1 c o = 1 ，c l 。9 ，c 2 = 0 ，c 3 = 1 c 024 ，c t 。2 ，旬= 5 ，c 3 = 0 c o 3 ，o l = 4 ，c 2 。4 ，c 350 c 0 = 2 ，。l = 6 ，c 2 。3 ，c 3 。0 印= i ，c l = 8 ，c 2 = 2 ，c 3 = o c o20 ，c i = i 0 ，c 2 = 1 ，c 3 = 0 证明：因为每一个元素一个出现1 1 次，因此c o + c 1 + 吃+ c 3 表示。一 共出现的次数；而c i 十2 c 2 + 3 c 3 表示z 与a 中每个元素结成的元素对 所出现的次数，由于每对元素对出现3 次，而z 可与a 结成4 对元素 对，因此。i + 2 c 2 十3 c 3 = 3 4 = 1 2 引理1 1 l ：设( x 一4 ) 是一个( 1 2 ，4 ，1 ) 一p m d ，a 是a 的一个区组，那么a 是型为风的区组，k = l ，2 ，3 ，4 证明：假设区组a 是型为风的，由定理1 8 可知z o = z 2 = 0 设z a ，则有c o = c 2 = 0 代入定理11 0 的等式得到： o i + o = i t c l + 3 c 3 = 1 2 计算得到c 3 = i 2 ， 即c 3 非整数，与题意产生矛盾，因此a 不能为侥型 定理1 1 2 ：每个( 1 2 ，4 ，1 ) 一p m d 中的任意个区组总有型仇，k = 1 ，2 ，3 ，4 我 们定义一个( 1 2 ，4 ，1 ) p m d 的型向量形式( 卢l ，如，风，风) = ( n l ，n 2 ，n 3 ，n 4 ) ， 其中整数n 。表示在这个( 1 2 ，4 ，1 ) p m d 中型为反的区组出现的次数 引理1 1 3 ：设( x ，a ) 和( x ，且) 是两个( v , k ，a ) _ p m d ，若币是一个同构映 射，a 是一个_ 的觑- 区组，那么咖( a ) 也是一个8 的觑一区组 由引理1 1 3 我们可以知道 定理1 1 4 ：如果两个( 1 2 ，4 ，1 ) - p m d 的型向量不同，那么它们不同构 证明：不妨假设有两个型向量分别是( n l ，n 2 ，n 3 ，n 4 ) 和( n l l ，n 2 + 1 ，r $ 3 ，n 4 ) 的( 1 2 ，4 ，1 ) - p m d 同构，它们的区组集合分别为一4 和层，那么通 过一系列元素对换变化，可以使得这两个( 1 2 ，4 ，1 ) p m d 的区组集a = b ， 那么它们的型向量必然相等，由此产生矛盾，因此若( 1 2 ，4 ，1 ) p m d 的 型向量不同即不同构 1 2 第二章( 1 2 ，4 ，1 ) - p m d 的分析构造 在本章及以后的讨论中，若无特别说明，用 ，6 ，c ，d ) 表示无序的 区组，用( n b c ，d ) 表示循环有序的区组 2 1 对( 1 2 ，4 ，1 ) 一p m d 的分析 定理2 1 ：设( x ，4 ) 是一个( 1 2 ，4 ，1 ) 一p m d ，且= ，b ，c ，d ) l ( o ，b ，c ，d ) a ) 若存在一个区组型为卢。，那么在同构的意义下，不妨设b 为如下形式； b o = 3 ，6 ，9 ，t 2 b t = 1 ，4 ，7 ，l o 现= 1 ，3 ，6 ，9 ，b 3 = 4 ，6 ，9 ，1 2 ，b 4 = ( 7 ，3 ，9 ，1 2 ) 岛= t o ，6 ，1 2 ，2 ，口6 = l o ，3 ，1 2 ，趴b 7 = f n ，3 ，6 ，8 ) b 8 = b 9 = t = b l a = f 3 ， b t 4 b 1 5 - = 马9 = 6 ， 岛o = 岛1 一- = b 2 6 = ( 9 疡7 = 毋8 一= b 3 2 = 1 2 ， 证明：设a o 是型为卢l 的区组，不妨设a o 的元素为 3 ，6 ，9 ，1 2 ) 由定 理1 8 知z o = l ，凯= 2 5 ，z 2 = 3 ，z 3 = 3 ，z 4 = 1 在同构的意义下可以 设， b o = 3 ，6 ，9 ，1 2 b 1 = l ，4 ，7 ，l o b 2 = 口，3 ，6 ，9 ) ，_ 日3 = 口，6 ，9 ，1 2 ) ，b 4 = 口，3 ，9 ，1 2 ) 尾= ( 口，6 ，1 2 ，口 ，b 6 = ( 口，3 ，1 2 ，口 ，b 7 = 口，3 ，6 ，口 b 8 = b 9 一= b 1 3 = 3 ，) b 1 4 = b l 5 = = b 1 9 = ( 6 ， b 2 0 = _ b 2 l 一= b 2 s = 9 ，) b 2 7 ；b 2 s = 一b 3 2 t 2 ，r ) 由定理1 加，若。( 1 ，4 ，7 ，l o ，易知c o = 1 ，c i = 9 + 句= 0 ，c 5 = 1 或者 c o = 1 ，e i = 8 ，c 2 = 互c 3 = o ，因此不失一般性，在同构意义下有： z = l ，3 ，6 ，9 ) ，b 3 = 4 ，6 ，9 ，1 2 ，b 4 = 7 3 ，9 ，1 2 岛= ( 1 0 ，6 ，1 2 ，口 ，口6 = ( 1 0 ，3 ，1 2 ，口) ，b 7 = 口，3 ，6 ，口) 若； 2 ，5 ，8 ，1 1 ) ，易知c 0 = 0 ，c 1 = 1 0 ，c 2 = 1 ，c 3 = 0 ，因此不失一般性， 在同构意义下有： b 5 = ( 1 0 ，6 ，1 2 ，2 ，b 6 = t o ，3 ，1 2 ，5 ，岛= i l ，3 ，6 ，8 1 定理2 2 ：设( x ，) 是一个( t 2 ，4 ，1 ) 一p m d ，子= “8 ，6 ，c ，田，6 ，c l d ) 若存在型为舟l 的区组a o ，则在同构的意义下，a o ，a h ，a 7 有如下 的5 4 种形式 r i ：a o = ( 3 ，6 ，9 ，1 2 ) d rr 2 ：a o = ( 3 1 2 ，6 ，9 ) s 1 ：a t = ( 1 0 ，l 4 ，7 ) o r 岛：a 1 = ( 1 0 ，l ，7 ，4 ) 黾：a 1 = ( 1 0 ，4 ，1 ，7 ) 。rs 4 ：a 1 = ( 1 0 ，4 ，7 ，1 ) s ：a 1 = ( 1 0 ，7 ，1 ，4 ) & ：a 1 = ( 1 0 。7 ，4 ，1 ) 在矗i 下， 4 2 ，a 3 ，a 4 ，a 7 在同构意义下有如下形式： 孔：4 2 = ( 1 ，3 ，9 ，6 ) ，a 3 = ( 4 ，6 ，1 2 ，9 ) ，a 4 = ( 7 ，9 ，3 1 2 ) ，a 7 = ( 1 1 ，8 ，6 ，3 ) 疋：a 2 = ( 1 ，6 ，3 ，9 ) ，a 3 = ( 4 ，9 ，6 ，t 2 ) ，a 4 = ( 7 ，1 2 ，9 ，3 ) ，a t = ( 1 1 ，3 ，8 ，6 ) 在r l ，噩下，a s ，a 6 在同构意义下有如下形式： u t ：a 5 = ( 1 0 ，2 ，1 2 ，6 ) ，a 6 = ( 1 0 ，3 ，5 ，1 2 ) o r 阮：a 5 = ( 1 0 ，2 ，1 2 ，6 ) ，a 6 = ( 1 0 ，1 2 ，5 ，3 ) o r ：a 5 = ( 1 0 ，1 2 ，6 ，2 ) a 6 = ( 1 0 ，3 5 1 2 ) 在r l ，噩下，如，a 6 在同构意义下有如下形式： 巩：a 5 = ( i 0 ，2 ，1 2 ，6 ) ，a 6 = ( 1 0 ，5 3 ，1 2 ) o r 魄：a 5 = ( 1 0 ，1 2 ，6 ，2 ) ，a 6 = ( 1 0 ，5 ，3 ，1 2 ) o r ：a 5 = ( 1 0 ，1 2 ，6 ，2 ) ，a 6 = ( 1 0 ，3 ，1 2 ，5 ) 在飓下，也，a 3 ，a 4 ，a 7 在同构意义下有如下形式： 乃：a 2 = ( 1 ，6 ，3 ，9 ) ，a 3 = ( 4 ，1 2 ，9 ，6 ) ，山= ( 7 ，9 ，1 2 ，3 ) ，a r = ( 1 1 ，8 ，3 ，6 ) 在r 2 ，t 3 下。a 5 ，a 6 在同构意义下有如下形式： h ：a s = ( 1 0 ，2 ，6 ，1 2 ) ，a 6 = ( i o ，1 2 ，5 ，3 ) o r ：a s = ( 1 0 ，6 ，1 2 ，2 ) ，a 6 = ( 1 0 ，3 ，5 ，1 2 ) o r 确：a s = f 1 0 ，6 ，1 2 ，2 ) ，a 6 = ( 1 0 ，1 2 ，5 ，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 ) 完全相颠倒 因此由定义1 , 5 知，每一组是同构的例如： ( 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 ) 上面数组第列r - s t 丑c ，i 经过完全颠倒得到的仍是满足定义的前8 个区组，因此经过完全颠倒的区组我们称之为同构的 另於，我们再考虑下面的情况： ( 1 ) ( 2 )( 3 ) ( 3 , 6 ，9 ，1 2 )( 6 , 3 ，9 ，1 2 )( 3 , 9 ，1 2 ，6 ) ( 1 0 ，1 ，4 ，7 )( 1 0 ，l ，4 ，7 ) ( 1 0 ，1 ，7 ，4 ) ( 1 , 3 ，9 6 )( 1 , 6 ，9 ，3 )( 1 , 6 ，3 ，9 ) ( 4 , 6 ，1 2 ，9 ) 3h6 ( 4 , 3 ，1 2 ，9 ) 2h5 ( 4 , 9 ，6 ，1 2 ) ( 7 , 9 ，3 ，1 2 )( 7 , 9 ，6 ，1 2 ) 4h7 ( 7 , 3 ，1 2 ，9 ) ( 1 0 ，2 ，1 2 ，6 )( 1 0 ，2 ，1 2 ，3 )( 1 0 ，6 ，2 ，1 2 ) ( 1 d ，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 8 ，3 ，6 ) 经过( 3 6 ) ( 2 5 ) ( 4 7 ) 变换使得( 1 ) 与( 3 ) 同构，因此我们只用考虑山是 ( 3 , 6 ，9 ，1 2 ) 和( 3 ，1 2 ，6 ，9 ) 这两种情况了 而在a o - - - ( 3 ，1 2 ，6 ，9 ) 情况下，有 豇：a 2 = ( 1 ，6 ，3 ，9 ) ，a 3 = ( 4 ，1 2 ，9 ，6 ) ，a 4 = ( 7 ，9 ，1 2 3 ) a 7 = ( 1 1 ，8 ，3 ，6 ) t 4 ：a 2 = ( 1 ，9 ，6 ，3 ) ，a 3 = ( 4 ，6 ，1 2 ，9 ) ，a 4 = ( 7 ，3 ，9 ，i 2 ) ，a 7 = ( 1 l ，8 ，3 ，6 ) 并且在r 2 和乃下，有 a 5 ：( 1 0 ，6 ，2 ，1 2 ) ，a 6 = ( i 0 ，5 ，1 2 3 ) o r a 5 = ( 1 0 ，6 ，2 ，1 2 ) ，a 6 = ( 1 0 ，1 2 ，3 ，5 ) o r a s = ( 1 0 ，1 2 ，2 ，6 ) ，a s = ( 1 0 ，5 ，1 2 。3 ) 但是我们通过( 3 6 ) ( 2 5 ) ( 4 7 ) ( 1 1 8 ) 变换以及完全颠倒变换使得下面的( 1 ) 与( 4 ) 同构 ( 1 )( 2 )( 3 )( 4 ) ( 3 ，1 2 ，6 ，9 )( 3 , 9 ，6 ，1 2 )( 3 , 9 ，6 ，1 2 )( 3 ，1 2 ，6 ，9 ) ( 1 , 9 ，6 ，3 )( 1 , g ，3 ，6 )( 1 , 9 ，3 ，6 )( 1 , 6 ，3 ，9 ) ( 4 , 6 ，1 2 ，9 )( 4 , 3 ，1 2 ，9 ) 2 h 5 ( 7 , 3 ，1 2 ，9 )( 4 ，1 2 ，9 ，6 ) ( 7 , 3 ，9 ，1 2 j3 6 ( 7 , 6 ，9 ，i 2 ) 4 斗7 ( 4 , 6 ，9 ，i 2 j 完全颠倒( t 9 ，1 2 ，3 ) ( 1 0 6 2 1 2 )( 1 0 ，3 ，2 ，1 2 ) 1 l h 8 ( 1 0 ，3 ，5 ，1 2 )( 1 0 ，6 ，1 2 ，2 ) ( 1 0 5 1 2 3 )( 1 0 ，5 ，1 2 6 )( 1 0 ，2 ，1 2 ，6 )( 1 0 ，1 2 ，5 ，3 ) ( 1 1 , 8 ，3 ，6 )( 1 1 ，8 ，6 ，3 )1 1 ，6 ，3 ，8 )( 1 1 ，8 ，3 ，6 ) 由此我们发现，在a o = ( 3 ，1 2 ，6 ，9 ) 的情况下只有正一种情况 我们规定 h t = r l u t i u “ 3 = r l u 正u u 3 i t 5 = 且z u t 2 u 玩 h t = r 2 u t 3 u 啦= r i u 正u 巩 凰= r i u t 2 u 撬= r zu 乃u 魄 风= r 2 u u k 凰= r 2 u t 3 u u 引理2 3 ：在只讨论含一个卢1 区组的前提下，若( i ，j ) ，n ) ，那么& u 马和岛l j 砺是不同构的 2 2 含一个岛- 区组的( 1 2 ，4 ，1 ) 一p m d 的结果 利用计算机，我们搜索到结果如下，表格中的数字是相对应的甄 岛所搜索到的( 1 2 ，4 ，1 ) 一p m d 的个数： 表l s l s 3 s 4 玩 360433 h 2 326332 h 3 50 1 l1l 矾 31ol21 飓 242344 - 6 2 25 0 2 0 日7 204l62 - 8 253l34 凰 1 44 353 引理2 。4 ：至少存在1 3 8 个恰好含有一个鼠一区组的不同构( 1 2 ，4 ，1 ) - p m d 下面举一个甄5 i ( r i s l 互巩) 的例子： r l1 4 0 ：( 3 ，6 ，9 ，1 2 ) s la t ：( 1 0 ，1 ，4 ，7 ) na 2 ：( 1 ，3 ，9 ，6 ) a 3 ：( 4 ，6 ，1 2 ，9 ) a 4 ：( 7 ，9 ，3 ，1 2 ) 矿ia 5 ：( 1 0 ，2 ，1 2 ，6 ) a 6 ：( 1 0 ，3 ，5 ，1 2 ) 1 7 a 8 ：( 3 ，i ，2 ，4 a 9 ：( 3 ，2 ，1 0 ，7 ) a l o ：( 3 ，4 ，5 ，8 ) 儿：( 3 ，7 i ，5 ) a 1 2 ：( 3 ，8 ，1 1 ，2 ) a t 3 ：( 3 ，1 0 ，4 ，1 1 ) a 1 4 ：( 6 ，2 ，5 ，i i ) a 1 5 ：( 6 ，4 ，1 0 ，5 ) a 1 6 ：( 6 ，5 ，7 ，2 ) a 1 7 ：( 6 ，7 ，8 ，1 0 ) a 1 8 ：( 6 ：8 ，4 ，1 ) a 1 9 ：( 6 ，1 1 ，l ，7 ) a 2 0 ：( 9 ，1 ，1 0 ，“) a 2 1 ：( 9 ，2 ，1 1 ，4 ) a 2 2 ：( 9 ，5 ，2 1 ) a 2 3 ：( 9 ，7 ，4 8 ) a 2 4 ：( 9 ，8 ，5 ，1 0 ) a 2 5 ：( 9 ，1 0 茂2 ) a 2 6 ：( 9 ，1 1 , 7 ，5 ) a 2 7 ：( 1 2 ，1 ，1 l ，l o ) a 2 8 ：( 1 2 ，2 ，8 ，1 ) a 2 9 ：( 1 2 ，4 ，2 7 ) a 3 0 ：( 1 2 、5 1 ，8 ) a a t ：( 1 2 ，8 7 ，1 1 ) a 3 ：( 1 2 ，1 1 ，5 ，4 ) 乃a 7 ( 3 154 ) ( 3 ，2 ，1 0 ，8 ) ( 3 , 4 ，2 ，5 ) ( 3 ，7 ，1 1 ，2 ) ( 3 , 8 ，1 ，7 ) ( 3 ，1 0 ，4 ，1 1 ) ( 6 , 2 ，4 ，5 ) ( 6 ，4 ，1 ，t 1 ) ( 6 , 5 ，1 0 ，7 ) ( 6 ，7 ，8 ，1 0 ) ( 6 , 8 ，5 ，1 ) ( 6 ，1 1 ，7 ，2 ) ( 9 ，1 ，8 ，2 ) ( 9 ，2 ，7 ，4 ) ( 9 ，5 ，2 ，8 ) ( 9 ，7 ，5 ，1 1 ) ( 9 ，8 ，4 ，1 0 ) ( 9 ，1 0 ，l l ，1 ) ( 9 ，l l ，1 0 ，5 ) ( 1 2 ，l ，2 ，1 1 ) ( 1 2 ，2 ，l ，1 0 ) ( 1 2 ，4 ，8 ，7 ) ( 1 2 ，5 ，7 1 ) ( 1 2 ，8 ，l l ，4 ) ( 1 2 ，1 1 ，5 ，8 ) ( i 1 ，8 ，6 ，3 ) ( 3 ，1 ，1 1 , 2 ) ( 3 , 2 ，1 0 ，1 1 ) ( 3 ，4 ，1 ，5 ) ( 3 ，7 ，2 ，4 ) ( 3 , 8 ，5 ，7 ) ( 3 ，l o ，4 ，8 ) ( 6 ，2 ，7 ，5 ) ( 6 ，4 ，5 ，1 ) ( 6 , 5 ，1 0 ，7 ) ( 6 ，7 ，8 ，1 1 ) ( 6 , 8 ，l ，2 ) ( 6 ，1 1 , 4 ，1 0 ) ( 9 ，l ，1 0 ，8 ) ( 9 , 2 ，8 ，4 ) ( 9 , 5 ，4 ，1 1 ) ( 9 ，7 ，1 1 ，1 0 ) ( 9 ，8 ，2 ，5 ) ( 9 ，1 0 ，5 ，2 ) ( 9 ，l l ，7 ，t ) ( 1 2 ，1 ，8 ，1 0 ) ( 1 2 ，2 ，1 ，7 ) ( i 2 ，4 ，2 ，1 1 ) ( 1 2 ，5 ，1 1 ，1 ) ( 1 2 ，8 ，7 ，4 ) ( 1 2 ，1 1 ，5 ，8 ) 第三章同构分析 在计算机的帮助下我们找出了每个( 1 2 ，4 ，1 ) 一p m d 的每个区组的 型，这样我们就可以找出每个( 1 2 ，4 ，1 ) - p m d 的型向量，下面我们就利 用了型向量来进行恩构分析 3 1 型向量不同的含一个风一区组的( 1 2 ，4 ，1 ) p m d 由定理1 1 4 可知，型向量不同的( 1 2 ，4 ，1 ) - p m d 就不同构，下面给出具 体例子： ( 4 1 ，x ) ，型向量是( 1 , 0 ，1 3 ，1 9 ) ： ( 3 ，6 j 9 ，1 2 ) 卢l ，( 1 0 ，l ，4 ，7 ) 风，( 1 ，3 ，9 ，6 ) 卢3 ，( 4 ，6 ，1 2 ，9 ) 风，( 7 ，9 3 1 2 ) 卢3 ，( 1 0 ，2 ，1 2 ，6 ) 风， ( 1 0 ，3 ，5 ，1 2 ) f i 4 ，( t l ，8 ，6 ，3 ) 风，( 3 ，i ，2 ，4 ) 凤，( 3 ，2 ，i o ，7 ) 风，( 3 ，4 ，5 ，8 ) 风，( 3 ，7 ，1 ，5 ) 凰， ( 3 , 8 ，1 1 ，2 ) 风，( 3 ，l o ，4 ，1 1 ) m ，( 6 ，2 ，5 ，1 1 ) 凤，( 6 ，4 ，1 0 ，5 ) 风，( 6 ，5 ，7 ，2 ) 尻，( 6 ，7 ，8 ，i o ) 风， ( 6 , 8 ，4 ，1 ) 风，( 6 ，1 1 ，1 ，7 ) 风，( 9 ，1 ，1 0 ，1 1 ) 卢3 ，( 9 ，2 ，1 1 ，4 ) 良，( 9 ，5 ，2 ，1 ) 风，( 9 ，7 ，4 ，8 ) 卢4 ， ( 9 , 8 ，5 ，l o ) 岛，( 9 ，l o ，8 ，2 ) 风，( 9 ，1 1 ，7 ，5 ) 觑，( 1 2 ，1 ，1 1 ，l o ) 风j ( 1 2 ，2 ，8 ，1 ) 岛，( 1 2 ，4 ，2 ，7 ) 风， ( 1 2 ，5 ，1 ，8 ) 1 3 3 ，( 1 2 8 ，7 ，1 1 ) 风，( 1 2 ，1 1 ，5 ，4 ) 风 ( 一4 2 ，x ) ，型向量是( 1 ，4 1 7 ，1 1 ) ： ( 3 ，6 ，9 ，t 2 ) 1 3 1 ，( t o ，1 ，4 ，7 ) 1 9 4 ，( 1 ，3 ，9 ，6 ) 卢3 ，( 4 ，6 ，1 2 ，9 ) 卢3 ，( 7 ，9 ，3 ，1 2 ) p 3 ，( t o ，2 ，1 2 ，6 ) 卢3 ， ( 1 0 ，3 ，5 ，1 2 ) 风，( 1 l ，8 ，6 ，3 ) 觑，( 3 ，l ，5 ，4 ) 风，( 3 ，2 ，l o ，8 ) 屈，( 3 ，4 ，2 ，5 ) 岛，( 3 ，7 ，1 1 ，2 ) 岛， ( 3 , 8 1 7 ) 3 4 ，( 3 ，1 0 ，4 ，1 1 ) 风，( 6 ，2 ，4 ，5 ) 风，( 6 ，4 ，1 ，t x ) 风，( 6 ，5 ，l o ，7 ) 岛，( 6 ，7 ，8 ，t o ) h ， ( 6 , 8 ，5 1 ) 成，( 6 ，1 1 , 7 ，2 ) 岛，( g ，l ，8 ，2 ) 岛，( 9 ，2 ，7 ，4 ) 融，( 9 ，5 ，2 、8 ) 傀。( 9 ，7 ，5 ，1 1 ) 岛， ( 9 , 8 ，4 ，1 0 ) 卢4 ，( 9 ，1 0 ，1 1 ，1 ) 风，( 9 ，1 1 1 0 ，5 ) 良，0 2 ，l ，2 ，1 1 ) 风( 1 2 ，2 ，l ，1 0 ) 胁，( 1 2 ，4 ，8 ，7 ) 风 ( 1 2 ，5 ，7 ，1 ) 风，( 1 2 ，8 ，1 1 ，4 ) 阮，( 1 2 ，1 1 , 5 ，8 ) p 3 ， 3 2 型向量相同的含一个卢1 区组的( 1 2 ，4 ，1 ) 一p m d 引理3 1 ：对于型向量相同且只含一个卢1 ，区组的( 1 2 ，4 ，1 ) p m d ，若它们 的( i ，j ) ( m ，n ) ，那么它们不同构 这由引理2 3 显然可知 引理3 2 ：对于型向量相同且只含一个卢1 一区组的( 1 2 ，4 ，1 ) p m d ，若它们 的( i ，j ) = ( m n ) ，它们仍然不同构 证明：我们先对前8 个区组进行讨论，由于型向量相同，而且它们的 ( i ，j ) = ( m ，n ) ，因此我们不妨对下面的例子给出分析： ( 3 , 6 ，9 ，t 2 ) 卢1 ( 3 , 6 ，9 ，i 2 ) 向 ( 1 0 ，l ，4 ，7 )( 1 0 ，1 ，4 ，7 ) ( 1 , 3 ，9 ，6 )( 1 , 3 ，9 ，6 ) ( 4 , 6 ，1 2 ，9 )( 4 , 6 ，1 2 ，9 ) ( 7 , 9 ，3 ，1 2 )( 7 , 9 ，3 ，1 2 ) ( 1 0 ，2 ，1 2 ，6 )( 1 0 ，2 ，1 2 ，6 ) ( 1 0 ，3 ，5 ，1 2 )( 1 0 ，3 ，5 ，1 2 ) ( 儿，8 ，6 3 )( 1 1 , 8 ，6 ，3 ) ( 3 ，口，口，口)( 3 ，口，口口) 由于( 3 , 6 ，9 ，1 2 ) 是芦1 区组，因此由定理1 8 知与之相交为空的区组只 能有一个，即( 1 0 ，1 ，4 ，7 ) 因此( 1 0 ，l ，4 ，7 ) 只能映射到( 1 0 ，l ，4 ，7 ) 而含有 l o 又与( 3 , 6 9 ，1 2 ) 相交为2 的只有两个区组，因此1 0 只能映射到l o 叉由于区组是有顺序的，所以1 只能映射到1 ，4 只能映射到4 ，7 只鼹 映射到7 ，由此各个区组中由于与1 ，4 ，7 ，1 0 的顺序关系，只能是相同位 置的相同元素作映射，因此此映射是个恒等映射，所以若是两个型向 量相同且只含一个卢1 区组的( 1 2 ，4 ，1 ) 一p m d ，即使它们的( i ，j ) = ( m ，n ) ， 它们仍然不同构 我们将所有含一个卢1 区组的( 1 2 ，4 ，1 ) p m d 通过型向量和前8 个区组 的组合在下表中列出： 表2 型向量 ( i ，j ) ( 甄毋)型向量( i ，j ) ( 甄s j ) 1 ，0 ，9 ，2 3( 5 ，5 )1 ，0 ，1 3 ，1 9( 1 ，j j 1 ，0 ，9 ，2 3( 5 , 6 )1 , 0 ，1 3 ，1 9( 2 ，1 ) 1 , 0 ，1 5 ，1 7( 4 , 5 ) l ，0 ，1 9 ，1 3( 1 ，6 ) 1 , 0 ，1 5 ，1 7( 7 , 3 )1 ，0 ，1 9 ，1 3( 8 ，2 ) 1 , 0 ，1 5 ，1 7( 8 , 6 )1 ，0 ，1 7 ，1 5( 9 ，3 ) 1 ，1 ，1 9 ，1 2 ( 1 ，1 ) 1 1 ，1 5 ，1 6 ( 6 , 3 ) 1 ，1 ：1 9 ，1 2 ( 1 , 2 ) 1 1 ，1 5 ，1 6( 6 , 5 ) l ，1 ，1 9 ，1 2( 1 , 2 )1 ，1 ，1 5 ，1 6( 2 , 6 ) 1 ，l ，1 9 ，1 2( 3 , 3 )1 1 ，1 5 ，1 6( 7 ，3 ) 1 ，l ，1 9 ，1 2( 2 , 5 )1 ，1 ，1 3 ，1 8 ( 5 1 ) 1 ，l ，1 9 ，1 2 ( 7 ，1 ) l ，1 ，1 3 ，1 8( 3 ，4 ) l ，1 ，1 9 ，1 2( 8 ，2 )l ，l ，1 3 ，1 8( 1 ，5 ) l ，1 ，1 9 ，1 2 ( 9 ，6 )1 ，l ，l l ，2 0( 5 ，1 ) l ，1 ，1 7 ，1 4( 5 , 5 ) 1 1 ，2 1 ，1 0 ( 2 ，1 ) 1 ，1 ，1 7 ，1 4( 8 ，1 )l ，1 ，2 1 ，l o( 2 , 3 ) 1 ，1 ，i 7 ，1 4 ( 8 , 3 ) l ，1 2 1 1 0 ( 4 ，6 ) 1 ，l ，1 7 ，1 4 ( 9 , 3 ) l ，l ，2 1 ，1 0( 5 ，6 ) 1 1 2 3 8 ( 7 , 5 )l ，1 ，2 1 ，1 0( 9 , 4 ) 1 ，2 ，1 5 ，1 5( 3 ，1 ) l ，2 ，1 9 ，1 1( 4 ，1 ) 1 ，2 ，1 5 ，1 5( 6 ，1 )l ，2 ，t 9 ，1 1( 6 , 3 ) 1 ，2 ，1 5 ，1 5 ( 1 , 2 ) l ，2 ，1 9 ，1 1( 8 ，1 ) 1 ，2 ，1 5 ，1 5 ( 8 , 2 ) 1 ，2 ，1 9 ，n( 7 , 3 ) 1 ，2 ，1 5 ，1 5( 7 , 5 )l ，2 ，1 9 ，1 1( 7 , 3 ) 2 1 型向量 ( i ，j ) ( 甄s j )型向量( ，j ) ( 凰岛) 1 ，2 ，1 5 ，1 5( 8 , 6 )l ，2 ，1 7 ，1 3 ( 2 ，1 ) 1 ，2 ，1 5 ，1 5( 8 , 6 )l ，2 ，1 7 ，1 3( 2 , 3 ) l ，2 ，2 1 ，9( 4 ，2 )i ，2 ，1 7 ，1 3 ( 1 ，5 ) 1 2 2 1 9 ( 2 ，5 )i ，2 ，1 7 ，1 3 ( 3 , 6 ) 1 ，2 ，2 1 9 ( 9 , 5 )1 ，2 ，1 7 ，1 3( 9 , 2 ) l ，2 、2 3 ，7 ( 9 , 2 )1 ，2 ，1 7 ，1 3( 9 ，4 ) l ，2 ，2 3 ，7 ( 8 ，3 ) 1 ，2 ，1 7 ，1 3 ( 8 ，5 ) 1 ，2 ，2 3 ，7 ( 9 , 5 )l ，3 ，