（运筹学与控制论专业论文）不可约的m圈分解.pdf

摘要 一个n 阶a 重m 一圈分解是指一个二元组( v 够) ，其中y 是a 的点 集，够是a j 厶的一些子图构成的集合，这些子图都是m 一圈，且a 的任 意一条边恰在够的一个m 一圈中出现 当a 1 时，设( v 毫乃是一个n 阶a 重m 一圈分解，如果够可以分解成 两个子集研和饬，使得( k 锈) 和( k ) 分别是a 1 重m 一圈分解和抛重 m 一圈分解，其中a l + a 2 = a 那么称( k 够) 是可约的分解若够不能这样 被分解，则称( k 管) 是不可约的分解 p e t e r j e n k i n s 证明了对于满足条件4 m n 的正整数m 和n ，( m ，佗) ( 5 ，5 ) ，如果存在n 阶m 一圈分解，那么就存在不可约的n 阶2 重m 一圈分 解 在这篇文章里我们将证明两个结论：( 1 ) 如果存在n 阶m 一圈分解，那么 就存在不可约的n 阶3 重m 一圈分解；( 2 ) 当m 4 ，5 ，6 ) ，n s ( 仇) 1 ，5 ) ， 则存在一个不可约的n 阶4 重m 一圈分解，其中s ( m ) 为存在m 一圈分解的正 整数n 的集合。 关键词不可约；圈分解：a 重 a b s t r a c t a n m c y c l es y s t e m o f o r d e r ，l a n d i n d e x a i s a p a i r ( k w h e r e v i s t h e v e r t e x s c to f a k a n d 够i sac o l l e c d o no f m - c y c l e sw h o s e e d g es e t sp a r t i t i o nt h ee d g e so f a a nm - c y c l es y s t e m ( k 叻o f o r d e rna n di n d e xa 1i ss a i dt ob er e d u c i b l ei f i ti sp o s s i b l et op a r t i t i o n 管i n t ot w os u b s e t s ，磁a n d ，s u c h t h a t ( k 锻) a n d ( k 饬) a r m - c y c l es y s t e m so f o r d e r 礼a n di n d i c e sa 1a n da 2 ，r e s p e c t i v e l y , f o rs o m ep a i ro f p o s i t i v ei n t e g e r sa 1a n da 2 ，w i t ha l + a 2 = a i f n o s u c hd e c o m p o s i t i o ni sp o s s i b l e , t h es y s t e mi ss a i dt ob ei r r e d u c i b l e p e t e rj e n k i n sh a ds h o w nt h a tf b fa n yp a i ro fi n t e g e r s ( m ，佗) w i t h4 墨m n ， i f t h e r ee x i s t sa nr a - c y c l es y s t e mo f o r d e rr t t h e nt h e r ee x i s t sa ni r r e d u c i b l e2 - f o l d m - c y c l es y s t e m o f o r d e rn e x c e p t w h e n ( m ，n ) ( 5 ，5 ) i nt h i sp a p e r , w es h o wt w oc o n c l u s i o n s ：( 1 ) i f t h e r ee x i s t sa nm - c y c l es y s t e m o f o r d e rt l ，t h e nt h e r ee x i s t sa ni n - e d u c i b l e3 - f o l dm - c y c l es y s t e mo f o r d e r n ；( 2 ) f o r e a c hr n 4 ，5 ，6 ) a n dn s ( m ) l ，5 ) ，t h e r ee x i s ta ni r r e d u c i b l e4 - f o l dm - c y c l e s y s t e mo f o r d e rn ，s ( m ) d e n o t et h es e to f p o s i t i v enf o rw h i c ht h e r ee x i s t sa nm - c y c l e s y s t e mo f o r d e r 亿 k e y w o r d si r r e d u c i b l e ；c y c l es y s t e m ；a - f o l d 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、创新”的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表 或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版； 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查 阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标 题和摘要汇编出版。保密的学位论文在解密后适用本规定 作者签名： 日期： 刖舌 组合设计问题是组合数学的一个重要分支，是一门研究将事物按特定要 求进行安排配置并讨论其性质的学问组合设计理论是一个既有古老历史渊 源而又相当年轻的数学分支它的历史可以追溯到很远，4 0 0 0 年以前我国 就有关于“河图洛书”的美丽传说，其中。洛书”就是一个简单的组合设 计，3 阶幻方历史上有许多著名的有关组合设计的难题。如互m e r 的3 6 军官 问题和k i r k m a n 女生问题等，它们以特有的应用价值和趣味性吸引了大量的 数学爱好者 其中k i r k m a n 女生问题( k i r k r a a n 三_ 元系的存在性问题) 从提出到完全 解决，历时1 0 0 多年1 8 5 0 年，德国一教师k i r k m a n 提出了如下一个问题： 一位女教师每天带领班上的1 5 个女生散步，她把这些女生分成每3 人一组， 共5 组，这样每个女生都有两个同伴问题就是能否作出一个连续七天的散 步计划，使得任意两个女生都正好有一次被安排在同一个组? 这个问题的解是从1 5 名女生组成的三人组中找到3 5 组，使得每两个女生 恰好出现在同一组中一次此外我们可以把3 5 人三人组分成7 部分，每部分 有5 个三人组( 一部分正好对应七天中的一天) ，而且这1 5 个女生正好是在 每一部分的一个三人组中我们知道k i r k m a n 女生问题存在解的前提条件 是：1 5 个女生三人一组构成的集合中必须至少有3 5 个三人组 后人在研究k i r k m a n 女生问题的同时，逐步把它发展成为一个数学问 题，并且用数学语言定义它，定义如下： 定义l 设t ，是正整数，我们称( x ，绷为s t e i n e r 三元系，其中x 是 个 元素的集合，留是x 的一个子集簇( 其中成员b 称为区组) ，满足以下两 个条件： ( 1 ) 如果b 曰，则l b l = 3 ： ( 2 ) x 中的任意两个不同元素恰好在留的一个区组中出现 例l 设x = 1 ，2 ，3 ，4 ，5 ，6 ，7 ) ， 留= 3 c o l b o u r n 和r o s a 在 5 】中证明了： 定理3 存在一个单纯不可约的扣，3 ，4 ) - 设计的充要条件为 t ，兰0 ，1 ( r o o d3 ) ，”9 d i m i t z 和沈灏在 3 ，4 】中证明了下面的结论： 定理4 当 8 ，t ，9 ，1 0 ，1 1 ，1 2 ，1 3 ，1 5 ，1 6 ，则存在一个单纯不可约昀 ( t ，3 ，6 ) 一设计 张学斌在 2 】中证明了： 定理5 当t ，三1 ，3 ( m a d6 ) ，口 7 ， 9 ，1 3 ，1 5 ，则存在一个单纯不可 一2 一 约的( 口，3 ，5 ) - 设计 最近几年。有人对( t ，k ，a ) 一设计进行了进步的推广 一个m 一圈是一个具有m 个点的简单图，点集记为 以li ) ，边 集记为 墨一l x i1 i m 1 ) u z o z 。一1 ，简记为( ：t ox l z 。一1 ) 或者 ( x 1 t 2 一1x 0 ) 。设a 珞是有 个顶点的完全多重图，其中任意2 个相 异的顶点z 和y 有a 条边z 相连 定义3 一个a 的m - m 分解是指一个二元组( k 够) ，其中y 是入j 厶 的点集，管是a 的一些子图构成的集合，这些子图都是m 一圈，且a 的任意一条边恰在够的一个m 一圈中出现 当a l 时，够可能包含相同的m 圈一个a 的7 7 1 一圈分解称为n 阶 a 重1 1 一圈分解，简称为a 重m 一圈分解，当a = l 时，简称为m 一圈分解 定义4 设是( k 够) 是一个a 重m 一圈分解，如果够可以分解成两个子集 钦和铭，( k 何) 和( k ) 分别是a l 重m 一圈分解和沁重m 一圈分解，其 中a l + 如= a ，那么称( v 够) 是可约的分解若够不能这样被分解，则称 ( k 叼是不可约的分解 j e n k i n s 在 1 】中证明了： 定理6 对于满足条件4 m n 的正整数m 和n ，( m ，佗) ( 5 ，5 ) ，如果 存在n 阶的m 一圈分解，那么就存在不可约的n 阶2 重m 一圈分解 在这篇文章里，我们将解决不可约的n 阶3 重m 一圈分解的存在性问 题，也对不可约的n 阶4 重m 一圈分解的存在性问题给予研究 第1 章不可约的3 重圈分解 i i 引言 个m 一圈是一个具有m 个点的简单图，点集记为 ii ) 。边 集记为 毛一i x il m 一1 u z o 。一l ，简记为( x 0z l 。一1 ) 或者 ( x l 现2 ：m - 1 勒) 假设c 是一个m - m ，善和暑，是c 的两个不同的点，如 果z 不是c 的边，那么z 称为c 的一条弦 设入风是有t ，个顶点的完全多重图，其中任意2 个相异的顶点z 和有 a 条边z 鲈相连一个a j 厶的m 一圈分解是指一个二元组够) 其中y 是 a 的点集，够是a 的一些子图构成的集合，这些子图都是m 一圈，且 a k 。的任意一条边恰在够的一个m 一圈中出现当a 1 时，够可能包含相 同的m 一圈。一个a k 。的m 一圈分解称为n 阶a 重m 一圈分解，简称为a 重 m 一圈分解。当a = 1 时，简称为m 一圈分解 假设( k 钎) 和( v 饬) 分别是a l 重t r t 一圈分解和a 2 重m 一圈分解，我 们可以发现( k 镜u 铣) 是a l + a 2 重m 一圈分解相反地，当a 1 时，设 ( k 管) 是a 重m 一圈分解，如果够可以分解成两个子集镜和镜，( k 锨) 和 似锡) 分别是a 1 重m 一圈分解和a 2 重m 一圈分解，其中a l + a 2 = a ，那么 称( k 叼是可约的分解若够不能这样被分解，则称( k 印是不可约的分 解 例1 i i 设v = 历，够= q ：i = 1 ，2 ，2 7 。 c l = ( 0 12 8 ) q = ( 0 138 ) ，c 3 = ( o l48 ) ， c 4 = ( 5 120 ) ，铝= ( 5 12o ) ，c 6 = ( 0285 ) ，c 7 = ( 528 1 ) ， c ；b = ( 6 13o ) ，c 9 = ( 6 13 0 ) ，c 1 0 = ( 0386 ) ，c i i = ( 6 3 8 1 ) ， c 1 2 = ( 7 14 0 ) ，c 1 3 = ( 7 14 0 ) ，c 1 4 = ( 0 4 87 ) ，c 1 5 = ( 7 48 1 ) ， i l l 6 = ( 4235 ) ，c 1 7 = ( 4 2 3 7 ) ，c 1 8 = ( 4236 ) ，c 1 9 = ( 587 4 ) ， c 2 0 = ( 58 63 ) ，c 2 1 = ( 6872 ) ，c 2 2 = ( 6257 ) ，c 2 3 = ( 72 56 ) ， c 2 4 - _ ( 7265 ) ，c 2 5 = ( 5346 ) ，c 2 6 = ( 7 3 45 ) ，c 2 7 = ( 7 3 4 6 ) 则( 够) 是一个不可约的9 阶3 重4 圈分解。通过考虑边0 1 。我们可 以发现( k 叨是不可约的假设( k 够) 是一个可约的3 重4 圈分解，设 ( v 镜) 和( v 够) 分别是l 重4 一圈分解和2 重4 一圈分解，管= 筑u 铴，那 么边0 1 一定在锈的一圈中出现，而包含边0 l 的圈只有0 1 ，c 2 和c 3 若 c l 镜，则c 4 ，岛，c 6 垡饭，容易发现铳不可能包含边0 2 ，所以c 1 叠铳。同 理c 2 岳研，c 3 砀，矛盾。 这一章主要讨论对于任意给定的m 一圈。存在一个不可约的3 重m 一圈 分解的n 的谱因为m = 3 的情况已经被解决了，所以可以假设m 4 。当 然如果不存在m 一圈分解，那么也不可能存在3 重m 一圈分解所以这里只 要考虑存在m 一圈分解的n 的谱。 对于给定的整数m 4 ，设s k 为存在m 一圈分解的正整数n 的集合，s 为m 一圈分解的谱现在已经知道品。包含的整数n 必须满足下列的条件： 1 当n 1 时，n2m ； 2 ，l 是奇数； 3 n m 一1 ) 2 m 是一个整数 下面将证明对于任意一对整数( m ，n ) ，m 4 ，n s ( m ) 1 ) ，存在不 可约的n 阶3 重m 一圈分解这一章中构造不可约的3 重m 一圈分解方法是 首先把3 个m 一圈分解放在一起，构成一个3 重m 一圈分解，然后通过等价 交换，使得它无法分解成一个m 一圈分解和一个2 重m 一圈分解如何等价 交换才能使得不可约是这篇文章要解决的关键问题。 下面介绍等价的概念，两个不相同的y n 一圈乃和易，若出现在丑( 乃) 的边同样出现在疋( 丑) 中，则称噩和乃是一等价的，记为乃一死或者 乃一乃 例1 1 2 设t = ( 口bcd ) ， = ( be d ，) ，= ( nbed ) ，, p n = ( bc d ，) ，那 么 移 一 0 ，, u i 是臼一等价的 銎! 譬j ：尘釜塑：i 型竺竺： 显然，如果( k 够) 是a 重m 一圈分解，n 一乃是等价的，噩够，那 么( v ( 汐u 疋) 乃) 也是一个a 重m 一圈分解 在第二节中，我们将构造一些不可约的3 重m 一圈分解，m 1 5 由引理1 2 1 ，存在洞为1 1 的仃阶5 一圈分解 ( k 叨 当m = 6 时，s ( 6 ) = 佗z + i n 量1o r9 ( m o d1 2 ) ) 。设礼三 1o r9 ( m o d l 2 ) ，n 1 3 。由引理1 2 2 ，存在洞为“的n 阶6 一圈分解叨， 当礼i9 ( r o o d l 2 ) 时，钍= 9 ，当n 兰1 ( r o o d l 2 ) 时，t = 1 3 口 1 3 一般的构造 这一节的主要目的是证明对于任意一对正整数m 和n ，7 m s n ，如 果存在一个n 阶m 一圈分解，那么就可以构造一个不可约的n 阶3 重m 一圈 分解我们所用的方法是在一个3 重m 一圈分解上进行等价交换首先我们 把n 阶m 一圈分解分成两类考虑 第一类n 阶m 一圈分解( k 够) 是：够含有一对圈c 1 和q ，龟包含c 1 的 一条弦：在c 2 中有一边，这条边的一个端点是弦的一个端点，另一端点不在 。1 中例如 c 1 = ( 知x l 黝一一1 ) ，c a = p 印x d y l 抛一3 ) 其中d 2 ，3 ，【m 2 j ，z 车 $ 1 ，z 2 ，一1 这样的n 阶 m 一圈分解( v 够) 称为类型1 。一个7 1 阶m 一圈分解( k 够) 如果不是类型l ， 那么就是类型2 定理1 3 1 如果存在一个类型l 的n 阶m 一圈分解，其中7 m n ，那么 存在一个不可约的竹阶3 重m 一圈分解。 证明：设( v 够) 是类型l 的1 9 , 阶m 一圈分解那么管含有一对固 c l = ( 勋x l 黝z m 一1 ) c 2 = ( z t , o x d y l 抛y m 一3 ) 绝 章矸：r 叮约的3 节岿廿解 。其中d 2 ，3 ，h 2 j ) ，z 隹 x l ，x 2 ，x m - 1 ) 定义点集y 上一个置换 口= ( x l m 一2 ) ( x dz f ，l 一1 ) 0 1z m 一3 ) ( x d + 2z m 一4 ) ( 拂l + 【毕jz m 一3 一【墨号型j ) 对够中的每一个圈进行a 置换，从而得到新的圈集设为口( 够) 则a ( 够) 含有下面的两个圈： a ( e t ) = ( 霉o z t n 一2 x 2 x 3 d l z m l z m 一3 z m 一4 l d + l 茹1 z d ) o 池) = p 知善m - - 1q ( 暮，1 ) 口( 驰) 口( 轳。一3 ) ) 我们用下面的两个圈代替q 和口( c 1 ) ： 缸= = ( x ox d j e d l l 一2 l j b “l j + 2 j 一1 ) 口= ( x o x m - 2 x 2 x 3 z d l x m - 1 茹m 一3 z m 一4 j + l l z 1 ) 在点集v 上，再定义一个置换卢= ( x m 1 名) ( y lz “1 ) 对够中的每一个 圈进行芦置换，从而得到新的圈集设为卢( 够) 则卢( 叼含有下面的两个圈： 卢( q ) = ( z o $ 1 1 ! 1 。f + 2 1 m 一3 m 一2z ) p ( 晚) = ( z m 一1 卫o x d z 西+ l 掣2 掣m 一3 ) 我们用下面的两个圈代替t ，和卢( c 1 ) ： 埘= ( x ox m - 2 x 2 奶黝一1z m 一1 z m 一3 z d + 2 讥z d z l ) 8 = ( - t o z l 黝m 1z 啪z 仇一3 z t n 一2z ) 容易证明 u ，”) 一 c - ，口( c 1 ) ) 和 伽，s ) 一 ”，卢( c ，) ) 都是g 。一等价的 那么，设9 = ( 够u 口( 叻u 卢( 叻u u ，t ，s ) ) 。1 口( c 1 ) ，卢( c 1 ) ) ，则( v9 ) 是一个n 阶3 重m 一豳分解 假设9 可以分成两个子集玩和奶，现) 和( k 易) 分别是m 一圈分 解和2 重m 一圈分解则玩中肯定有一圈包含边z z o ，而含有边狮的只有 圈c 2 ，a ( c 2 ) 和p 锄) 若饧玩，则边黝一1 岳现。若d b ) 玩，则边 $ o x d 勃。若p ( c 2 ) 要h ，则边z o z 。一l 隹幼所以c 2 ，口池) 和卢( c 2 ) 均不 在玩中，矛盾。所以( k9 ) 是一个不可约的仃阶3 重m 一圈分解。 口 下面证明对于类型2 的佗阶m 圈分解有同样的结果，首先给出三个引理。 引理1 3 1 如果( k 够) 是类型2 的n 阶m 一圈分解，c 够，那么够包含 一子集管”，使得( y ( c ) ，它) 是一个m 阶m 一圈分解 证明：设( k 够) 是类型2 的n 阶m 一圈分解，c = ( 知z l 一1 ) 是够中的一个圈对任意 ，j o ，1 ，；m 1 ) ，i j ，若边 墨彩c 1 c l 管，则圈c 1 的点集为 z o ，z 1 ，x m - 1 ) ，否则( k 够) 是 类型1 设汐是够中含有边$ 芦，的所有圈，那么( c ) ，够+ ) 是一个f r t , 阶 m 一圈分解 口 一个f y t , 阶m 一圈分解就是e r a 的哈密顿圈分解下面给出在 1 0 】中出现 过的结果，的哈密顿圈分解。 引理1 3 2 设m 为奇数，且m 5 ，v = z 。，霉o ，z 1 ，z 。一2 ) 记 c = ( 戤z l 州z m 一州。2 “一州z 孚“。孚“) 其中t ，1 ，( 仉一3 ) 2 ，所有的下标都是模m 一1 的。则 ( k c , l o i ( m 一3 ) 2 ) 是一个m 阶m 一圈分解。 引理1 3 3 存在不可约的7 阶3 重7 一圈分解 证明：设v = z 7 留= ：i = l ，2 ，9 ) ： c 1 = ( 0 123 456 ) c 2 = ( 0 1356 42 ) c a = ( 0 123546 ) c 4 = ( 0 3 165 24 ) 岛= ( 0 4 162 3 5 ) c e = ( 02 13645 ) 句= ( 03 4 1526 ) c s = ( 025 16 34 ) c 9 = ( 03 624 15 ) 则( k 叨是一个不可约的3 重7 一圈分解不可约性可从边0 1 看出。假设 ( k 研是一个可约的3 重7 一圈分解，设锈是管的一个子集，( k 研) 是一 个7 一圈分解因为边0 1 要在研的一个圈中出现，所以c 1 ，c 2 和c 3 必有一个 圈属于钣若c 1 铳，则c 2 ，c 3 ，c 5 荜钣容易发现钪不可能包含边3 5 所 第1 章h ：j 叮约的3 节蹦分解 以c 1 隹锐同理因为边2 3 ，沈盛锈因为边5 6 ，c 3 隹镜，矛盾。 定理1 3 2 存在不可约的m 阶3 重m 一圈分解，m 为奇数，且m 29 。 i 正n , q ：当矗9 时，设( v 是引理1 3 2 中的一个m 阶m 一圈分解。 那么够包含下列的圈： c 1 2 ( x o ox o x l 一2 现霉m _ 3 x 3 z 孚孚) c 2 2 ( x o ox l x 2 x o 勋一2 x 4 z 竿z 孚) 定义点集y 上一个置换口= ( 耽；r 4 ) 对够中的每一个圈进行。置换，从而得 到新的圈集设为o ( 够) 则a ( 叻也含有下面的两个圈： 口( c 1 ) = ( x o ox o z l z m 2z 4 z m 一3 z m 一4 x 2 。m 一5z 5 z 2 号生z 皿 ) 口( c 2 ) = ( x o oz 1z 4 x 0 x 3z ，n 一2 勋z m 一32 ：5 z m - 4 x 6 。塑笋z 吲生) 用u 和 代替圈c 2 和口( c 2 ) ，t 和”如下： 牡= ( - z c o z l z 2 x m - - 2 ：r 3z 0 瓤z m 一32 ：5 x m - 4 x 6 z 坚笋z 墨笋) = ( x c ox l z 4 z m 一2 黝x o 现$ t ，l 一3 2 5 z ”；_ 4z 6 。坚笋z 坚笋) 在点集y 上，再定义一个置换卢= ( 蜘z 1 ) ( z 2 霉3 ) ( 奶。一5 ) ( z 5 ：r m - - 4 ) 。对够 中的每一个圈进行卢置换，从而得到新的圈集设为p ( 够) 则p ( 叨也含有下 面的两个圈： 卢( c 1 ) = ( z $ 1 ：r 0z ，n 一2z 3z m 一3z 2z 5l - 43 ：m - - 4 善m 一5 z m 一6 茹6 z 2 号三z j 2 产) p 匕) = ( 。x o2 ：3x l z 2 z m 一2 瓤札3 。鼍笋互皿 ) 用伽和s 代替圈t 和卢( c 1 ) ，加和s 如下： 们= ( z z lz oz m 一2 黝舀n 一3 勋岛3 ：4 z m 一4 粕磊一5z 7 z 坚笋z 翌笋) 8 = ( x c o z lz 2 z m 一2 勋知瓤一33 ：5 一一5 一6 2 6 。孚茹孚) 容易证明 u ， ) 一 c 2 ，口池) ) 和 t t ，s ) 一 t ，p ( c 1 ) 是c k 一等价的那么， 设9 = 够u 口( 够) u p ( 够) u f ，埘，s ) ) c 2 ，口( c 2 ) ，p ( c 1 ) ，则( k9 ) 是一个m 第1 章水叫约的3 币豳分解 阶3 重m 一圈分解，且是不可约的不可约性可以从边知o o o 看出假设 ( v9 ) 是一个可约的3 重m 一圈分解，设玩是9 的一个子集，( k 玩) 是一 个m 一圈分解现必定包含一圈c ，使得边x o t , o o c 假设c l 玩，因为边x o t o o 和x 2 x m 一2 ，可以发现o ( c 1 ) ，b ，z ( c 2 ) 隹研。 容易看出勃不可能包含边x 4 x m 一3 所以e l 隹现 假设口( c 1 ) 玩，囡为边t , o x o o 和乳o 。一3 ，可以发现c 1 ，b ，p ( c 2 ) 隹勃。 容易看出玩不可能包含边z 2 。一2 所以口( c 1 ) 隹玩 假设p ( c 2 ) 玩，因为边知z 。和z 掣z m # ，可以发现c l ，a ( c 1 ) ，a 隹 现容易看出勃不可能包含边勋z 。一3 所以卢( c 2 ) 岳勃。 而9 中没有其它的圈包含边跏z 。，矛盾。 口 定理1 3 3 如果存在一个类型2 的佗阶m 一圈分解，其中7 m n ，那么 存在一个不可约的n 阶3 重m 一圈分解 证明：设( k 够) 是类型2 的n 阶m 一圈分解，c 够，根据引理1 3 1 存在 够的一子集矿，使得( 矿( c ) ，够+ ) 是一个m 阶m 一圈分解设( c ) ，9 ) 是一 个不可约的m 阶3 重m 一圈分解把够泸中的所有圈复制三次构成的圈 集记为占，设穸= g u 9 ，则( k 莎) 是一个不可约的1 7 , 阶3 重m 一圈分解。口 定理1 3 4 对于任意一对整数( m ，n ) ，4 m ，l ，如果存在一个n 阶 m 一圈分解，那么存在一个不可约的几阶3 重m 一圈分解 第2 章不可约的4 重圈分解 2 1 引言 在这一章里，我们将证明当m 4 ，5 ，6 ，l s ( m ) 1 ，5 ) 。则存在一 个不可约的n 阶4 重m 一圈分解。为了便于证明，我们给出下面的几个概 念： 一个可约的4 重m 一圈分解可以分解成两个2 重m 一圈分解，或者分 解成一个m 一圈分解和一个3 重m 一圈分解我们把前一种称为2 + 2 可 约，后一种称为1 + 3 可约。相反地，若一个4 重m 一圈分解不可以分解 成两个2 重m 一圈分解，则称它为2 + 2 不可约；若一个4 重m 一圈分解不 可以分解成一个m 一圈分解和一个3 重m 一圈分解，则称它为1 + 3 不可 约；若一个4 重m 圈分解既是2 + 2 不可约也是1 + 3 不可约，则称为不可约。 显然，由第二章得下面的结论： 如果存在一个n 阶m 一圈分解，那么存在一个2 + 2 不可约的7 7 - 阶4 重 m 一圈分解 同样根据 1 】中的结论，我们可以得到下面的结果： 如果存在一个n 阶7 7 1 一圈分解，( m ，n ) ( 5 ，5 ) ，那么存在一个1 + 3 不可 约的n 阶4 重m 一圈分解 下面证明不存在不可约的5 阶4 重5 一圈分解 定理2 1 1 不存在不可约的5 阶4 重5 一圈分解 证明：设v = z 5 ，( k 是一个5 阶4 重5 - $ 分解够中的圈与点q 相接的点对有下面的六种可能性： ( 1 ，2 ) ，( 1 ，3 ) ，( 1 ，4 ) ，( 2 ，3 ) ，( 2 ，4 ) ，( 3 ，4 ) 设它们与点0 相接的次数分别设为z 1 ，z 2 ，x 3 ，z 4 ，x 5 ，x 6 ，因为0 与1 ，2 ，3 ，4 各 笫2 章计：叮约的，于嘲行解 有四次相遇。所以必须满足下列方程组： o l + 勋+ 勋= 4 z 1 + 瓤+ 奶= 4 孔+ 蕊+ z 2 ：4 如+ + x 6 = 4 在同构的意义下方程组有下列三组整数解： - t 121 i z 1 。 如1 i z 。= x 3 。2 j x 35 飘：21 铂： z s _ 1 l 船= 0 6 = 1i 孙= x l = 0 x 22 1 - 2 ：3 23 x 4 = 3 x 5 = 1 - t 6 20 通过尝试可以发现上面三组解均不能构造出一个不可约的5 阶4 重5 - 圈 分解口 2 2 一些不可约的4 重m 一圈分解( m ，谚包含下列6 圈： ( 0 1o c d 夕) ，( ，6c 0e 1 ) ，( 0d 19e ，( 0 ，e d 6 口) ，( 1e 9 口，c ) ，( ec 9 ，d o ) ， ( 0 1 口e ，d ) ，0 d e 06 1 ) ，( 0 ，id 6 c ) ，( e96 ，c o ) ，( ，c d 口9e ) ，( b ec 夕，) ， ( 0 16c d ，) ，( b 9c 0 口1 ) ，( 0 d 1 ，d 夕) ，( 0e 口d 96 ) ，( 19 ，6 ec ) ，( 口c 1e d6 ) ， ( 0 1be ，g ) ，( dc e0 口1 ) ，( 0 ，19 1 7 , c ) ，c o d o ，c6 ) ，( 1c 96 de ) ，( 口0 9 d ，6 ) 可以发现留中包含的下面的圈： ( 0 1 口c d g ) ，( 0 1 凸e ，回，( 0 16c d ，) ，( 0 16 e ，9 ) ， ( b gc 0 口1 ) ，( ，c d 口9e ) ，( o o9d ，6 ) ， ( 9d e0b 1 ) ，( d ce0 口1 ) ，( 0 ，e db o ) ，( ec 9 ，d o ) 与定理2 2 2 的证明方法一样可以证明( k 叨是一个不可约的9 阶4 重6 一圈 分解 定理2 2 4 当m 4 ，5 ，6 ，t l s ( m ) l ，5 ) ，则存在不可约的扎阶4 重 m 一圈分解 证明：从定理2 2 1 ，2 2 2 ，2 2 3 ，我们可以发现对于下面集合p 中的任 意一对数( 7 7 1 , ，n ) ，都存在不可约的n 阶4 重m 一圈分解 p = ( 4 ，9 ) ，( 5 ，1 1 ) ，( 5 ，1 5 ) ，( 6 ，9 ) ，( 6 ，1 3 ) ) 一个不可约的n 阶4 重m 一圈分解可以通过如下的方法得到：设( kc ， 是一个洞为u 的7 , 阶7 r t , 一圈分解，首先把c 中的每一个圈复制4 次，然后加 上一个不可约的牡阶4 重7 7 7 , 一圈分解下面分别对7 7 1 进行讨论： 当m = 4 时。s ( 4 ) = 协z + l n 三1 ( r o o d8 ) ) 设n 兰1 ( r o o d8 ) ，n 箭2 章不r 叮约的4 母附廿解 9 。由引理l ：z 2 ，存在洞为9 的n 阶4 一圈分解( k 钥 当讯= 5 时s ( 5 ) = n z + i n 兰1o r5 ( m d dl o ) 。设佗三 1o r5 ( m 砸1 0 ) ，t l 1 5 。由引理1 2 1 ，存在洞为1 l 的7 1 阶5 一圈分解 ( k 幻 当m = 6 时，s ( 6 ) = 伽z + i n 三1d r9 ( r o o d1 2 ) 设n 三 1o r9 ( r o o d l 2 ) ，l 1 3 由引理1 2 2 ，存在洞为u 的佗阶6 一圈分解( k 够) ， 当n 三9 ( m o d l 2 ) 时，缸= 9 ，当n 兰l ( r o o d l 2 ) 时，“= 1 3 口 一1 9 一 参考文献 【1 】p e t e rj e n k i n s ，i r r e d u c i b l e2 - f o i dc y c l es y s m m , jc o m b md e s i g n s1 4 ：3 2 4 - 3 3 2 ，2 0 0 6 【2 】z h a n gx u eb i n , i n d e c o m p o s a b l et r i p l es y s t e m sw i t ha = 5 ，j c m c c1 6 ( 1 9 9 6 ) ， 1 5 3 1 6 2 【3 】j h d i m i t z , i n d e e o