（基础数学专业论文）k4内全部子图组tch的meta（h＞tλ）.pdf

摘要 设h 是有限简单图。丁是它的子图图设计a k v h 是一个序偶( v 屡) ，其中 y 是虬的顶点集。而召为纸中与h 同构的若干子图的族( 称为区组集) ，使得甄中 每条边恰好出现在召的a 个区组中今将b 中每个区组b 分拆成b 和b b ，其中口 同构于t 若口( h 丁) = b f ：b b 中的全部边可被重新安排成一族与t 同构 的子图( 记为口( 丁) ) ，那么( vb ( t ) ud ( t ) ) 就恰为一个图设计a 甄l 其中b ( t ) = ：b 召 上述过程被称为是a k v h 向a 托辛丁的转型( m e t a m o r p h o s i s ) ，记为 ( h t ) g 地( 可) 记m e t a ( h t ，a ) = u ：j ( t ) 一g 慨( u ) ) 为( h 丁) 一a m , ( v ) 的存在谱本文 对于任意a 和所有的tch 托，完全确定了它们的m e t a ( h t ，a ) 关键词：转型图设计可分组设计按对平衡设计 i i i a b s t r a c t l e thb eaf i n i t es i m p l eg r a p h tb ea s u b - g r a p ho fh ag r a p hd e s i g na 纸h i sap a i r ( v 召) ，w h e r ev i st h ev e r t e x - s e to fk 侈i saf a m i l yo f s u b g r a p h si s o m o r p h i ct oh ，s u c ht h a t e a c he d g ei nk va p p e a r si ne x a c t l yab l o c k so fb n o w ，p a a i t i o ne a c hb 8i n t ob a n db b 。 w h e r eb i si s o m o r p h i ct ot i ft h ee d g e si n 秒( h 丁) = b j e 7 ：b b c a nb er e a r r a n g e d 酗au n i o nd ( 丁) o ft c o p i e s ，t h e n ( kb ( t ) u 口( 丁) ) f o r m sag r a p hd e s i g na 虬t ，w h e r e b ( t ) = b ：b 召 t h ep r o c e d u r ef r o ma j 乙h t oa j 已ti sc a l l e dam e t a m o r p h o s i s o f t h e ( vt 3 ) ，d e n o t e db y ( h 丁) 一g u x c v ) t h ee x i s t e n c es p e c t r u mo f ( h 丁) 一g m x ( v ) i sd e n o t e db ym e t a ( h t ，a ) = ： j ( h t ) 一g 慨( 秽) i nt h i st h e s i s ，f o ra l la v a i l a b l etch 托a n da n ya ，t h ec o r r e s p o n d i n gs p e c t r u m sm e t a ( h t ，a ) a l ec o m p l e t e l yd e t e r m i n e d k e y w o r d s ：m e t a m o r p h o s i sg r a p hd e s i g ng r o u pd i v i s i b l ed e s i g np a i r w i s eb a l a n c e d d e s i g n i v 学位论文原创性声明 本人所提交的学位论文k 内全部子图组t ch 的m e t a ( h t ，入) ，是在导师的指 导下，独立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献 的个人和集体，均已在文中标明。 本声明的法律后果由本人承担。 敝储c ：红呼 研年；月沙r 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 论渺j ：及呼 础年；月沙同 。 舯撕c 签孙鼻杰尼 埘年多月矽同 诺o，弦 ，孱 ： 、，11 釉 口三 别 l s l 0 月 认； 确 f i y ， 刻竹 黝 洲 指 引言 设g ，h ，丁是有限简单图，其中tch g 称a g = ( x ，e ) 为一个a 重图g ，它的顶 点集x 由g 的全部顶点构成，它的边集合e 则是g 每条边均重复a 次的多重集如果图 a g 能分拆成若干个与h 同构的子图( 称为区组) ，使得a g 的每条边均恰出现在一个区组 中。则称其构成一个图设计a g h 当g = 甄时，图设计a 纸h 即是经典的图设计 h g d x ( v ) 。 对于一个h a d d ( v ) = ( x ，侈) 。将b 中每个区组b 分拆为b 和b b ，其中b 同构于 t 若d ( 嚣? ) = b b ：b 移) 中的全部边可被重新安排成一族与丁同构的子图( 记为 d ( 丁) ) ，那么( x ，b ( t ) u 刃( 丁) ) 就恰为一个图设计a 纸丁，其中b ( t ) = b ：b 召 上述过程被称为是叁坠乏向垒丁的转型( m e t a m o r p h o s i s ) ，记为( a g ，片 t ) 一 设计或( x ，1 3 ，b ( t ) ud ( 丁) ) 为了表述简洁，给出以下一些记号： ( a 虬，h ) 一设计一一+ h g d a ( v ) ， ( a k 口，h 7 ) 一设计一一( 日 7 ) 一g m a ( v ) ； ( a k , 毗，n 。，日) 一设计一十h h d a ( n l n 2 n c ) ， ( a k 。，n 。，mh 丁) 一设计一一+ ( h 丁) 一h 地( n l n a 仇) ； ( 心+ 牡纸，h ) 一设计一一h i d ( v 十乱，“) 。 ( 虬+ 缸玩，h 丁) 一设计一一( 日 t ) i m ( v + u ，让) 定义m e t a ( h t ，入) = 钌：j ( 目 丁) 一g 厶( 臼) ) ，b ( h ，久) = 移：3h g d a ( 暂) ) 迄今为止，对于( h ，t ) ( w 4 ，a ) ，( 眦，凰虬) ，( 心，a ) ，( 凰，蚝) ，( 凰，虬+ e ) ，( k 4 ， 甄一e ) ，( + e ，) ，( k 4 + e ，k 4 ) ，( k 4 一e ，a ) ，( 凰一9 ，k a + e ) ，( k 3 ，3 ，瓯) ) ，它们的存在 谱m e t a ( h za ) 已经被完全确定( 见 4 ，7 ，8 ，9 ，1 1 ，1 2 ，1 3 ，1 5 1 ) 本文将对任意a 和所有 可能的tch 磁，逐一确定其存在谱m e t a ( h t ，a ) ( 日，t )k 4 一eq编+ ek 3p 4k 1 3b2 岛忍 砥 【9 】 1 3 】 7 】 8 】 丰 幸幸牛 k 4 一e【1 1 ，1 2 】【4 】1 2 8967 木 c 4 5 车堆拳 k a + e 【1 5 】1 0 1 1 木 幸 k a 宰 局 5 3 ，i k 1 3 4 | c 马 木 2 尼 木 上面的表格给出了所有可能的对子( 日，7 ) ( tch k 4 ) 其中，标记对应的t 不是日的予图；标记h 中相应的m e t a ( h t ，a ) 在文献中已被得到；标记书中的 ( h 丁) 一g 慨( ) 是平凡的，它们将在2 中被统一解决；标记七中相应的m e t a ( h 瓦a ) 将在本文的七中被确定，其中3 k 1 2 ；而标记中相应的m e t a ( h t ，a ) 是由袁兰 党博士最近确定的 以下各节中，对于给定的图h 和丁，在不致混淆时，可将( h 丁) g m a ( v ) ，( h t ) - h m a ( g ) 和( h 丁) - i m a ( u + 8 ，8 ) 分别简记为c m a ( v ) ，h m a ( g ) 和i m a ( u + 8 ，s ) 而 区组b t 表示区组b 重复出现t 次； 区组b = ( z ，y ，z ) + i 表示b = ( z + i ，y + i ，z + i ) ； 区组b = 陋，y ，z 】+ i 表示b = p + i ，y + i ，z + i 】： 磊z 中的元素( z ，a ) 可简记为x 。 一般来讲，在自同构群磊的作用下，设计中的基区组b = ( a ，b ，c ) 将产生一族区组 日+ z = ( a + z ，b + z ，c + z ) ，z 磊本文中，对于下列形式的一族区组 ， b + z ：| ! ( 口，6 c ，d ) + z若o z 吲， i ( n ，乱，c ，d ) + z若【j z n 一1 也采用类似基区组的记法，将其简记为b = ( a ，6 ( 札) ，c ，d ) 设k 是一个正整数集，而8 ，b 为正整数，r ，s 为非负整数可分组设计k g d d ( a 7 b 3 ) 是一个三元组( x ，9 ，8 ) ，其中x 是( a r + b s ) 元集，9 是x 的一个分拆，包含7 个a 元组 和8 个b 元组，8 是x 的一些子集( 称为区组，其长度) 的族，对任意b 召，g 夕， 有l b i k ，i bng l l ，且x 中不在同一组的任意2 一子集恰出现在8 的一个区组 中而按对垩衡设计b k ，a ；u 】是一个序偶( u 么) ，其中y 是一个u 元集，么是y 的一些 子集( 称为区组，其长度k ) 的族，使得y 的任意2 一子集恰出现在4 的a 个区组中 b 【 后 ，a ；v 】可简记为b 限a ；钉】一个u 阶拟群( q ，) 指的是一个u 元集q 及其上满足结 合律的二元运算，使得方程a z = b 及y a = b 对任意a ，b q 都有唯一的解x ，y q 2 1 递归构作 引理1 1 【4 】若存在b l ，a ；钌】，则 ( 1 ) 3 ( h 丁) 一h a 乳( 9 ) vl 上，哥3 ( h 丁) 一日a 以“( 9 付) ； ( 2 ) 3 ( h 丁) - a m ( t ) vl l 爿3 ( h t ) g 地p ( t ，) 引理1 2 【4 1 若存在( h t ) h g j , ( n ) 和( h t ) ，慨( n + s ，s ) 。则 ( 1 ) | ( h 丁) c g a ( n + s ) 爿j ( 丁) c m ( n t + s ) ； ( 2 ) j ( h 丁) 一g m a ( s ) 爿| ( h 丁) 一g 慨( n + s ) 引理1 31 4 ) 对于非负整数n ，b ，a 和胁 ( 1 ) j ( h 丁) 一日慨( 9 ) 和( h 丁) 日心( 9 ) 爿3 ( 丁) 一坛a + 蛳国) ； ( 2 ) j ( h 丁) 一g 慨( u ) 和( h 丁) 一g 嗨( 秽) 爿3 ( h 丁) 一g 地a + 啦( 秒) 引理1 4 设日是k 4 的真子图，tch ，r 为正整数，则 3 ( h 丁) 一日地( m ) 考了( h t ) 一i - i m a ( ( r m ) ) 构造：设有如下的( h t ) 一n m a ( m ) ： h h d a ( m ) = ( x ，乡，8 ) _ t h d a ( m ) = ( x ，9 ，b ub ) ， 其中b + 是诸b ( cb b ) 构成的族( b 同构于h ，b 同构于t ) ，而侈则是诸删去的边 b ：b 8 重新安排成的与丁同构的区组族因h 和丁均为托的子图，可将召中 同构于h 的图记为( o ，6 ，c ，d ) ，召或b 中同构于丁的图记为【o ，6 ，c ，d 1 由于日和丁是 甄的真子图，所以h 和t 中均至少有两顶点( 不妨即为c ，d ) 间未连边今对于r 阶拟群 ( l ，- ) 及上述已知，构作( h 丁) 一日 众( ( r m ) ) 如下： 日一日d a ( ( 7 m ) ) = ( xxl ， g l ：g 乡 ，4 ) j t - 日d a ( ( r m ) ) = ( xx ， g ：g 9 ) ，4 + u4 ) ， 其中区组集的定义是：v t ，歹l ，( o 6 ，c ，d ) 召一( a i ，幻，c i j ，如j ) 以， k 6 ，c ，d 】8 + ( 召) 一k 幻，c i j ，d i j 】4 ( 4 ) 当日和t 的顶点数少于4 时，区组集的定义变为：( d ，b ，c ) 一( 吼，6 j ，c i 歹) ，( n ，b ，c l 一 【吼，如，c i j 或( o ，6 ) j ( 口i ，幻) ，f n ，b j 【q i ，如】 证明可仅考查日和丁的顶点数均为4 的情形，顶点数为3 或2 时类似首先来说明区组 集4 构作的合理性 对于任意 z 。，玑 x ，z ，可属于9 的不同组( 从而z y ) ， z ，y ) 应恰出现在 召的a 个区组中( 作为与此区组同构的图片之一条边) 今考查它们中的一个，设此区组中 另二点为札，u 鉴于区组标记已给定顺序，在不区分z ，秽( 及u ，u ) 的考虑下，有以下可能： ( z ，可，n ，u ) 召，于是有( z 。，弧，u l ，饥) 4 ，其中f = s 七； 3 ( z ，乱，芗，秒) 或( z ，“，”，可) 8 于是有( 乳，让，纨，锹) 或( z 。，牡f ，巩，弧) 4 ，其中七= s z ； ( 牡，z ，1 , 1 ，u ) 或( 乱，z ， 1 3 ，剪) 召，于是有( 缸f ，2 2 。，七，v i e ) 或( t l ，z 。，口七，可七) a ，其中七= l s 这里，下标z 的唯一存在性是由拟群性质决定的而( 札，u ，z ，秒) 1 3 是不可能的，因为按 照构造规定：此区组对应的图日不含边 z ，夕 由上所述，按所给构造，与艿中包含边 z ，可) 的一个区组相对应，且包含边 ，u k 的4 中区组是唯一确定的故( ，玑 恰出现在4 的a 个区组中注意：前述构造规定是 必要的因若不然，8 中区组( 钍， ，z ，爹) 含有边 z ，爹) 时将给出r 对下标 l i ，m 0 暑l ，使得 l i m i = s ( = 七) ( 此时必只能是s = 后) ，从而b 中包含边 z ，y 的一个区组对应了么中包 含边 z 。，玑 的7 个区组( u “ m i ，玑) 当然，这一构造规定缘于所应用的拟群它只能 允许在一个区组中出现三种不同的下标：i ，j 和i j 因此，在所构作的新设计区组中，取 相同下标的顶点必须是在图h 和丁中无连边的 类似可以证明 z 。，瓠 也恰出现在4 + u4 的a 个区组中于是，方法所得到的确是一 个( h 丁) - 日慨( ( 7 m ) ) 口 引理1 5 【6 】存在以下按对平衡设计： ( 1 ) b 【 3 ，4 ，5 ) ，1 ； 】，其中口3 ，口6 ，8 ； ( 2 ) b i 4 ，5 ，1 2 ，1 4 ，1 5 ，1 8 ，1 9 ，2 3 ，1 ；钞】，其中 4 ； ( 3 ) b 【 4 ，5 ，8 ，9 ，1 2 ，l ；u j ，其中 三0 ，lr o o d4 ； ( 4 ) b 【 4 ，9 ，1 2 ，1 ；移】，其中钞兰0 ，l ，4 ，9r o o d1 2 ，u 2 1 ，2 4 ； ( 5 ) b f 5 ，6 ) ，1 ；u 】，其中u 三0 ，1r o o d5 ，u 1 0 ，1 1 ，1 5 ，1 6 ，2 0 ，3 5 ，4 0 ，5 0 ，5 1 ，8 0 对于整数o ，b ( o b ) 及正整数t ，记 f b ，厶】= 8 ，盘+ 1 ，6 1 ，6 ： 口，b t = ( n ，n + t ，6 一t ，6 ，若。三bm o d t 磊中元o ，b 间的无序差被定义为m i n ( b o ) r o o dn ，( n b ) r o o d 佗) 故磊上的无序差集 为【l ，【j 】今将集合以s 磊到其相应无序差的集合b 的转化记作a _ * j e 7 则有 引理1 6 【1 4 】设佗为正整数。n 磊n + l 且1 n 亿则 当。为奇数日寸，【o ，2 n o 】2 _ * 【n ，h i ；而当n 为偶数日寸，【n ，2 n + 2 一o 】2 _ * 【口一1 ，佗】 对于d 1 ，2 ，【g j ) ，定义g ( d ，9 ) 为点集乙上的一个图，其边集包含了以d 中 元为差的所有边 引理1 7 如果d d 1 ，【；j ) ，且上g c a ( a , g ) 是偶觌那么毛上的图g ( d ，夕) 存在一 个1 因子 引理1 8 对于给定的图h 正 t 2 ，如果存在( h 正) - g 地( 掣) ，且五能够被分拆成同 构于疋的子图，那么存在( h 7 2 ) 一g 慨( ) 4 证明设一g 慨( ) = ( x ，t 3 ) 一正一a m a ( v ) = ( x ，b 。u1 3 ) 是一个( h 五) g 地( ) 其中伊是诸( cb 8 ) 构成的族( b 同构于日，b 同构于蜀) ，而b 则是诸删去的边 b ：b 1 3 重新安排成的与五同构的区组族 对于任意的a 8 + u 召，因a 同构于正，它可被分拆成同构于正的子图，记它们为 “令c = c a ：a 8 + uz 3 1 ，于是 h - g 地( ) = ( x ，b ) _ t 2 一g 慨( 口) = ( x ，c ) 恰为一个( h t 2 ) g 地( 秒) o 5 2 平凡情形 引理2 1 对于给定的图日和t 如果h 能被分拆成同构于t 的子图，那么m e t a ( h z a ) = b ( t 4 ，a ) nb ( r ，a ) 证明显然，m e t a ( h t ，a ) b ( i - i ，a ) nb ( r ，a ) 对任意口b ( - ，a ) nb ( la ) ，存在 h g d a ( v ) = ( k t 3 ) 对任意b 1 3 ，记b ( 与同构) 所分拆成的与丁同构的子图族为 4 且令4 = 4 日：b b 则( u 么) 是一个t g d a ( u ) ，故( h 丁) 一g g a ( v ) 存在 口 引理2 2 对于任意至少包含两条边的简单图h ，m e t a ( h 1 2 ，a ) = b ( 1 4 ，a ) 证明设t = b ，h 是m 边图由于h 能被分拆成m 个同构于t 的子图，则由引理3 1 可知m e t a ( h 恳，a ) = b ( 1 4 ，a ) nb ( 岛，a ) 又因b ( p 2 ，a ) = 口：u 2 ) 三b ( i - i ，入) ，故 b ( h ，a ) nb ( b ，a ) = b ( i i ，入) 口 引理2 3 ( 1 ) 若日 凰，a ，风+ e ，则m e t a ( h b ，a ) = b ( h ，a ) nb ( r ，a ) ； ( 2 ) 若h k 4 ，c 4 ，贝4m e t a ( h 2 1 2 ，a ) = b ( i - i ，a ) nb ( 2 p 2 ，a ) ； ( 3 ) m e t a ( 纸 p 4 ，a ) = b ( k 4 ，a ) nj e i ( p 4 ，a ) 证明各结论均可应用引理2 1 ，其理由如下： ( 1 ) 设t = b 显然h = k 4 能被分拆成三个同构于丁的子图，而h = q ( 或凰+ e ) 能被分拆成两个同构于丁的子图 ( 2 ) 设t = 2 p 2 显然h = 甄能被分拆成三个同构于t 的子图，而h = c 4 能被分拆 成两个同构于丁的子图 ( 3 ) 显然h = k 4 能被分拆成两个同构于只的子图 口 弓i 理2 4 【6 】( 1 ) b ( 托，a ) = u 4 ：1 2 1 , x v ( v 一1 ) ，3 l a ( u 一1 ) ) ， ( 2 ) b ( k 4 一e ，a ) = v - 4 ：1 0 1 , 入v ( v 一1 ) ，( u ，a ) ( 5 ，1 ) ) ， ( 3 ) b ( a ，a ) = 3 4 ：8 1 , 入v ( v 一1 ) ，2 1 a ( v 一1 ) ， ( 4 ) b ( 虬+ e ，a ) = u 4 ：8 1 , 、v ( v 一1 ) ) ， ( 5 ) b ( k a ，a ) = 口3 ：6 1 , 、v ( v 一1 ) ，2 1 a ( v 一1 ) ) ， ( 6 ) b ( 只，a ) = 4 ：6 1 a v ( v 1 ) ， ( 7 ) b ( k 1 3 ，a ) = 口4 ：6 1 , 入v ( v 一1 ) ，a 奇时u 5 ) ， ( 8 ) b ( b ，a ) = u 3 ：4 1 , 入v ( v 一1 ) ， ( 9 ) b ( 2 p 2 ，a ) = u 4 ：4 1 , x v ( v 1 ) 一 6 3 g e t a ( p 4 恳，入) 由引理2 4 可知，b ( b ，a ) = 移3 ：4 1 , 、v ( v 一1 ) ，b ( 只，a ) = l l 4 ：6 1 , 、v ( v 一1 ) ) 则( 局 恳) 一c m a ( v ) 存在的必要条件为a u ( 口一1 ) 三0m o d1 2 ，秒4 ，即 t j 三0 ，1 ，4 ，9m o d1 2 ， 4 当a 兰1 ，5m o d6 时； 口三0 ，1r o o d3 ， 4当a 兰2 ，4m o d6 时； u 三0 ，lr o o d4 ，u 4当入三3r o o d6 时； 秒4当a 三0r o o d6 时 本节将分别对a = l 23 ，6 确定m e t a ( p 4 b ，入) 区组只和尼则被分别记为( n ，b ，c ，d ) 和f c t ，b ，c 】，而p 4 _ 尸3 时被删去的边约定为 c ，d o b c d q b c 定理3 1m e t a ( p 4 1 3 ，1 ) = u 4 ：u 三0 ，1 ，4 ，9r o o d1 2 证明首先，对于t ，= 4 ，9 ，1 2 ，2 1 ，2 4 构作( 只 2 p 2 ) g m ( v ) 如下 型点集z 4 ；p 4 一g d ( 4 ) ：( 0 ，1 ，2 ，3 ) ，( 2 ，o ，3 ，1 ) ；d ( b ) ：【2 ，3 ，1 】 址丑点集z 3 磊； 只一g d ( 9 ) ：( 1 1 ，o o ，l o ，0 1 ) ，( 1 2 ，0 1 ，1 1 ，0 2 ) ，( 2 2 ，0 0 ，0 2 ，1 2 ) ，( 2 0 ，0 2 ，0 1 ，0 0 ) ，m o d ( 3 ，一) ； 刃( 岛) ：f l o ，0 t ，o o ，【lx ，0 2 ，1 2 】，r o o d ( 3 ，一) 型三1 2 点集z l lt j ) ；只c d ( 1 2 ) ：( 0 ，l ，4 ，9 ) ，( 0 ，2 ，6 ，。0 ) ，r o o d1 l ； 刃( b ) ：【0 ( 3 ，0 ，5 】m o d1 1 型：三至! 点集历z 3 ； 局一c d ( 2 1 ) ：( 4 2 ，l o ，2 2 ，3 2 ) ，( 0 2 ，2 0 ，4 2 ，6 2 ) ，( 4 2 ，0 0 ，0 2 ，3 2 ) ，( 0 2 ，l o ，1 l ，1 2 ) ， ( ( i l ，0 0 ，i o ，( 2 i + 3 ) 1 ) 鍪l ，( ( i 2 ，0 t ，i l ，( 2 i + 3 ) 2 ) ) 鍪l ，r o o d ( 7 ，一) ； d ( b ) ： i o ，( 2 i + 3 ) 1 ，( 3 i + 6 ) 2 】) 名l ，【1 2 ，0 2 ，2 2 1 ，【3 2 ，0 2 ，o l 】，r o o d ( 7 ，一) 型三丝点集z 2 3u o o ) ； p 4 一g d ( 2 4 ) ： ( 1 2 + 3 i ，4 + 2 i ，i ，o ) ) 鏊l ，( o o ，1 2 ，4 ，o ) ，r o o d2 3 ； 口( b ) ：小，0 ，2 + 司) 冬lr o o d2 3 进而，由引理1 5 ( 4 ) 可知，当钞三0 ，l ，4 ，9r o o dl2 ，u 2 1 ，2 4 时，存在b 4 ，9 ，1 2 ，1 ；u 】，再 应用引理1 1 ( 2 ) 即得结论 口 引理3 2 ( 1 ) 当( a ，u ) = ( 2 ，6 ) ，( 3 ，5 ) ，( 6 ，5 ) 时存在( 局 最) - g 地( 钞) ? ( 2 ) 当( a ，9 ) = ( 2 ，3 ) ，( 3 ，4 ) ，( 6 ，3 ) ，( 2 ，6 ) 时存在( 局 b ) 日慨( 夕2 ) ? ( 3 ) 当( a ，u ，心) = ( 6 ，5 ，2 ) ，( 2 ，9 ，3 ) 时存在( 只 b ) i m a ( v ，u ) 证明( 1 ) ( a ，u ) = ( 2 ，6 ) 点集磊u o 。) ；只一g d 2 ( 6 ) ：( ，0 ，1 ，3 ) ，( 4 ，2 ，1 ，。o ) ，r o o d5 ； 7 ( a ， ) = ( 3 ，5 ) 点集z s ； 勿( p 3 ) ：【o o ，1 ，3 】m o d5 只一g d 3 ( 5 ) ：( 4 ，2 ，1 ，o ) ，( 1 ，3 ，2 ，o ) ，r o o d5 ： 口( 3 ) ：【1 ，0 ，2 】r o o d5 ( a ，钉) = ( 6 ，5 ) 可由( 只 b ) - c m 3 ( 5 ) 和引理1 3 得到 ( 2 ) 尘，9 ) = ( 2 ，3 ) 点集z 3 x z 2 ；只h d 2 ( 3 2 ) ：( 2 1 ，l o ，0 1 ，o o ) ，( 0 0 ，0 l ，l o ，2 1 ) ，m o d ( 3 ，一) ； 口( 尼) ：【0 1 ，0 0 ，1 1 】m o d ( 3 ，一) ( a ，9 ) = ( 3 ，4 ) 点集乙z 2 ； 只- h d 3 ( 4 2 ) ：( 2 l ，2 0 ，1 l ，o o ) ，( 3 l ，1 0 ，2 l ，o o ) ， ( 3 l ，1 0 ，0 l ，0 0 ) ，( 2 l ，2 0 ，1 1 ，o o ) ，m o d ( 4 ，一) 刃( 尼) ：【0 1 ，0 0 ，l l 】，f 2 1 ，0 1 ，1 1 】，r o o d ( 4 ，一) ( a ，9 ) = ( 6 ，3 ) 由( p 4 尼) - h m 2 ( 3 2 ) 和引理1 3 可得 ( a ，9 ) = ( 2 ，6 ) 由( p 4 3 ) 一h m 2 ( 3 2 ) 和引理1 4 可得 ( 3 ) ( a ，钞，让) = ( 6 ，5 ，2 ) 点集邑u a ，6 ) ： 只一，仇( 5 ，2 ) ：2 ( 1 ，n ，0 ，2 ) ，2 ( 2 ，0 ，b ，1 ) ，2x ( b ，1 0 ，o ) ，m o d3 ； 刃( b ) ：【0 ，1 ，2 】，2 ho ，6 】r o o d3 ( a ，秒，u ) = ( 2 ，9 ，3 ) 点集( 历汤) u a ，b ，c ) 可由以下三个设计拼组成： 历历上的一个c m 2 ( 6 ) ，存在性见( 1 ) ： ( 磊x i ) u a ，b ，c ) ，i 易，上的各一个h m 2 ( 3 2 ) ，存在性见( 2 ) f l 定理3 3 ( 1 ) g e t a ( p 4 b ，2 ) = u 4 ： 三0 ，1r o o d3 ； ( 2 ) g e t a ( p 4 局，3 ) = u 4 ：u 兰0 ，1r o o d4 ) ； ( 3 ) m e t a ( p 4 b ，6 ) = ：口4 ) 证明下表中，已知的设计由定理3 1 和引理3 2 可得，其中带下划线的由定理3 1 中a = l 结论及引理1 3 得到 t 2 a = 2t = 1 hmg mlm 3 + 1 4 3 2 4 6 舌6 6 26 6 + 3 9 6 2 9 ( 9 ，3 ) t 2 a ut = 1 hmg ml m 34 t4 4 24 + _ - 4 + 15 4 25 63 t + 25 3 2 5 ( 5 ，2 ) 当 兰0 ，1m o d3 ，口4 时，( p 4 b ) - a m 6 ( v ) 由( 局 b ) 一a m 2 ( v ) 和引理1 3 可得 1 1 定理3 4j ( 4 b ) 一g m a ( v ) 仁专a ( 一1 ) 兰0r o o d1 2 ， 4 证明由引理1 3 和定理3 i ，3 3 可得 8 d 4 m e t a ( k 1 ，3 p a ，入) 由引理2 4 可知，b ( k l 3 ，3a ) = v 4 ：6 1 a v ( v 1 ) ，a 奇时u 5 ，b ( b ，a ) = t ，： 4 l a v ( v 1 ) 则( k 1 3 p 3 ) 一a m a ( v ) 存在的必要条件为a v ( v 1 ) 三0m o d1 2 ，且a 偶 ( 奇) 时钉4 ( 5 ) ，即 本节将分别对a ( o ；b ，c ，d ) 和l b ，n ， v 三0 ，1 ，4 ，9m o di2 ，t ，9 当a 三i ，5r o o d6b e ； 秒三0 ，1m o d3 ， 4 当a 三2 ，4m o d6 时： 秽兰0 ，1m o d4 ，秒5 当入兰3r o o d6 时； 4 当a 三0m o d6 时 = 1 ，2 ，3 ，6 确定m e t a ( k 1 3 只，a ) 区组k 1 ，3 和岛则被分别记为 c 】，而k 1 ，3 - - - + p 3 时被删去的边约定为 a ，d ) c bac - _ _ _ - _ _ - _ _ 。_ _ _ _ _ _ - _ _ - _ - 定理4 1m e t a ( k l ，3 p 3 ，1 ) = 钞9 ：t ，兰0 ，l ，4 ，9r o o d1 2 构造以下的参数t 1 箜三! 丝点集z 1 2 一1u o o ) ； k l ，3 g d ( v ) ： ( o ；6 i + 4 ，6 i + 6 ，6 i + 2 ) ) 江2 t - 0 2 ，( o ；o o ，口一2 ，秒一4 ) ，m o d ( u 一1 ) ； 口( p 3 ) ： p 2 i + 2 ，0 ，1 2 i + 8 ，t 。一- jm o d ( t ，一1 ) 望三! 至! ! 。点集z 1 2 + 1 ；k 1 ，3 一c d ( v ) ： ( o ；6 i + 4 ，6 i + 6 ，6 i + 2 ) ) 信2 t - 0 1r o o du ； 口( 屁) ： 1 2 i + 2 ，0 ，1 2 i + 8 】 葛r o o d v 型三1 2 1 垒点集z 6 t + 2x 历； k 1 3 - g d ( v ) ：( 0 0 ；0 1 ，( 3 t + 1 ) o ( ( 3 t + 1 ) 1 ) ，i o ) ，( 0 1 ；( v - 。2 ) 0 ，( ；) 1 ( ( i ) o ) ，l o ) ， ( o o ；i o ，( ；一i ) l ，i l ) ) 鍪2 ， ( o l ；( 3 i ) 1 ，( 3 i 一2 ) l ，( 3 i 一1 ) 1 ) ) ：l ，m o d ( ；，一) ； 秒( 忍) ： 1 0 ，o l ，2 l 】， ( 3 t 1 ) 1 ，0 1 ，( ；一洲) ：2 ， ( + 2 i 一1 ) 1 ，o o ，( t + 2 i ) 1 】) ：l ，r o o d ( ；，一) ， 【( 2 i ) o ，( 2 i + 1 ) 0 ，( 2 i + 2 ) 0 1 w = o 型三! 至! 垒点集( z 6 t + 4x 易) u 口) ； k l l 3 g d ( v ) ：( 0 0 ；1 1 ，( 下v - 3 ) - ，l o ) ，( 0 0 ；0 - ，( 孚) o ( ( 孚) 1 ) ，o ) ，( 0 1 ；( 学) l ，( 字) l ( ( 字) o ) ，乜) ， ( ( o l ；( 3 i ) l ，( 3 i 一2 ) 1 ，( 3 i 一1 ) 1 ) ：l ， ( o o ；i o ，( ! 宁一i ) l ，z 。l ，x ，1 i 3 ：t + 2 1 ，m o d ( 字，一) ； 刃( 恳) ：【o o ，a ，o , 1 ， ( 3 i 一4 ) l ，0 1 ，( 孚一洲 出， 【( + 2 i ) l ，0 0 ，( t + 2 i + 1 ) 1 1 1 ，m o d ( 孚，一) ，( 【( 2 i ) o ，( 2 i + 1 ) o ，( 2 i + 2 ) 0 1 诘3 t + 0 1 幽点集( 磊xz 2 ) u o 。) 。 k l ，3 一g d ( 9 ) ：( 0 0 ；3 l ，2 0 ( 2 1 ) ，o 。) ，( 0 1 ；1 1 ，2 l ( 2 0 ) ，o o ) ，( 0 0 ；o l ，1 l ，1 0 ) ，m o d ( 4 ，一) 9 d ( b ) ：f o o ，0 1 】m o d ( 4 ，一) ，f o o ，l o ，2 0 ，【2 0 ，3 0 ，o o 证明仅对四个无穷类给出证明( 参数t 1 ) 。其中包含o o 的边也不再赘述 型三l 些k i 。3 一g d ( 1 2 t ) 基区组中的差： 6 l + 2 ，6 i + 4 ，6 z + 6 岛2u a 2 t 一4 ，1 2 t 一2 = 【2 ，1 2 t 一2 】2 - * 【1 ，6 t 一1 1 所删去边的差： 6 i + 2 诘2 t - 0 2u 1 2 t 一4 = 【2 ，1 2 t 一4 】6 ， 口( 尼) 基区组中的差： 1 2 i + 2 ，1 2 + 8 ) 冬6 = f 2 ，1 2 一4 】6 型三! 至! ! k l ，3 - g d ( 1 2 t + i ) 基区组中的差： 6 i + 2 ，6 i + 4 ，6 ”- u ，仁2 t - 0 1 = 所删去边的差： 6 i + 2 活2 t - 0 1 = f 2 ，1 2 t 一4 】6 ， d ( b ) 基区组中的差： 1 2 f + 2 ，1 2 i + s i - j = f 2 ，1 2 t 一4 】6 f 2 ，1 2 t 1 , _ * 【1 ，6 t 型三! 呈i 垒k l 。3 一g d ( 1 2 t + 4 ) 基区组中差的分布： ( o ，o ) 纯差： 1 ，3 t + 1 u ( z | r 诗3 t2 = f 1 ，3 + 1 】； ( 1 ，1 ) 纯差： a t + 1 ) u 3 i ，3 i l ，3 i 一2 i ：i = 【1 ，3 t 十1 】； ( 0 ，1 ) 混差： 0 ，3 t + l ，l ，6 + l u i ，6 t + 2 一z r 注3 t2 = 【0 ，6 t + 1 】 d ( b ) 基区组中差的分布( 恰好覆盖了删去的边) ： ( o ，0 ) 纯差：1 ： u = 1 2 t + 9 ( 1 ，1 ) 纯差： 2 ) u 3 i l i ：2 = 【2 ，3 t 一1 】3 ； ( o ，1 ) 混差： 6 t + 1 ) u t + 2 i ，t + 2 i 一1 名iu i 名2 = 【2 ，3 t 】u 6 t + 1 k l ，3 - g d ( 1 2 t + 9 ) 基区组中差的分布： ( 0 ，0 ) 纯差： l ，3 + 2 ) u i ) 忙3 t + 2 1 = 【1 ，3 + 2 】； ( 1 ，1 ) 纯差： a t + 1 ，3 + 2 ) u 3 i ，3 i 一1 ，3 i 一2 名l = 【1 ，3 + 2 】； ( o ，1 ) 混差： 1 ，6 + 3 ，3 + 2 ，o ) u i ，6 t + 4 一i _ 3 t + 2 1 = 【0 ，6 t + 3 】 d ( 马) 基区组中差的分布基区组中差的分布( 恰好覆盖了删去的边) ： 纯差： 纯差： 混差： i 一4 ：2 i t + 1 = 【2 ，3 t 一1 1 3 ； + 2 i ，t + 2 i + l i ：l u ) 甚3 = 【2 ，3 t + l 】 引理4 2 ( i ) 当( a ，u ) = ( 2 ，4 ) ，( 2 ，6 ) ，( 3 ，5 ) ，( 3 ，8 ) 和( 6 ，5 ) 时存在( k l ，3 b ) g 地( 钉) ； ( 2 ) 当( a ，9 ) = ( 2 ，3 ) ，( 2 ，6 ) ，( 3 ，4 ) ，( 3 ，8 ) 和( 6 ，3 ) 时存在( k 1 ，3 b ) 一h m a ( 9 2 ) ； ( 3 ) 当( a ，u ，钆) = ( 2 ，9 ，3 ) ，( 3 ，1 2 ，4 ) 和( 6 ，5 ，2 ) 时存在( k l ，3 b ) 一z m x ( v ，让) 证明( 1 ) = 4 ，5 时取点集磊，口= 6 ，8 时取点集乙一lu 1 0 ( 垒! 1 2 三! 兰! 生k l ，3 一g d 2 ( 4 ) ：( o ；2 ，3 ，1 ) m o d4 ；刃( b ) ：【0 ，1 ，2 】，【2 ，3 ，o 】 ! 垒! ! ! 三f 竺! 盟k 1 ，3 - g d 2 ( 6 ) ：( o ；1 ，2 ，) 2m o d5 ；d ( b ) ： 0 ，( 3 0 ，1 】m o d5 ! 垒! 1 2 三曼堕k 1 ，3 一g d a ( 5 ) ：( o ；1 ，3 ，2 ) ，( o ；1 ，2 ，5 ) ，m o d5 ；d ( b ) ：【5 ，0 ，2 】m o d5 ( 垒! ! ! 三曼堕k 1 ，3 - g d 3 ( 8 ) ：( o ；3 ，1 ) ，( o ；3 ，o o ，2 ) ，( o ；2 ，o o ，1 ) ，( o ；3 ，1 ，2 ) ，m o d7 ； 口 d ( p 3 ) ：【l ，0 ，2 1x2r o o d7 ( a ， ) = ( 6 ，5 ) ( k i ，3 b ) g m ( 5 ) 可由( k 1 3 岛) 一g m ：i ( 5 ) 和引理1 3 得到 ( 2 ) ( a ，9 ) = ( 2 ，3 ) 点集磊，洞 0 ，2 ，4 ， 1 ，3 ，5 ； k l 3 _