（运筹学与控制论专业论文）2重完全图的不可约θ图分解.pdf

南京师范大学硕l 学位论文 摘要 设2 k , 是一个v 点的完全图，g 是一个没有孤立点的有限简单图2 k , 上 的一个图设计g g d 是一个对子( x ，召) ，其中x 是2 9 v 的顶点集合，b 是 2 凰的一些与g 同构的子图( 称为区组) 的集合，使得2 凰的任意一条边恰出 现在8 的两个区组中文中讨论的简单图是g ，即带有一条弦的k 长圈，( 我们 称其为口一图) 设( x ，b ) 是2 重p 一图设计，若8 不能分解成g 和q 使得( x ，g ) 和 ( x ，q ) 是1 重护一图设计，则称( x ，侈) 是不可约的 本文给出了k = 4 和6 时不可约g g d ( v ) 存在的充要条件；对于k = 5 ， 也有部分结果 关键词：分组设计：带涧的分组设计；图设计；带洞图设计；差；不可约 南京师范大学硕士学位论文 a b s t r a c t l e t2 b eac o m p l e t eg r a p hw i t huv e r t i c e sa n dgb eas i m p l es u b g r a p h w i t h o u ti s o l a t ev e r t i c e so f2 s l e tg g di sc a l l e dag r a p h d e s i g no f2 甄，w h i c h i sp a i r ( x ，b ) w h e r e xi sas e to f p o i n t so f2 凰，8i sas e to f b l o c k sw h i c hi si s o m o r p h i ct og ， a n de v e r ye d g eo f2 k ua p p e a r st w i c ei n8 i nt h i sp a p e r , c ki sk c y c l ew i t h o n ec h o r d ( i ti sc a l l e d0 一g r a p h ) l e t ( x ，召) b e2 一f o l d0 一g r a p hd e s i g n ，i f 召c a nn o tb ep a r t i t i o n e d i n t oc 1a n dqs u c ht h a t ( x ，c 1 ) a n d ( x ，q ) a r e1 一f o l d0 一g r a p hd e s i g n ， t h e nw es a yt h a t ( x ，召) i si r r e d u c i b l e i nt h i sp a p e r , w ew i l lg i v et h ec o m p l e t er e s u l t so fi r r e d u c i b l e2 f o l d 0 一g r a p hd e s i g nw h e nk = 4 ，6 w h e nk = 5 ，t h e r ea r es o m e r e s u l t s k e yw o r d s ：g r o u pd e s i g n ；h o l e yg r o u pd e s i g n ；i r r e d u c i b l e ；g r a p hd e s i g n ；h o l e y g r a p hd e s i g n - i 一 南京师范大学硕上学位论文 第1 章前言与基本概念 1 1 前言 组合数学是离散数学的一个重要的分支，是一门研究将事物按特定 要求进行安排配置并讨论其性质的学问它的历史可以追溯到很远我 国四千多年以前有关于”河图洛书”的美丽传说，其中的”洛书”就是一个 简单的组合设计，3 阶幻方历史上许多著名的有关组合设计的难题，如 e u l e r 的3 6 个军官问题和k i r k m a n 女生问题等，以其特有的魅力，吸引 了一代又一代学子，把他们领进数学研究的殿堂 然而组合设计又是一个年轻的数学分支对于组合设计的系统性研 究，是从2 0 世纪3 0 年代r c b o s e 等人的工作开始的，而从6 0 年代起，随着 关于正交拉丁方的e u l e r 猜想等重要问题的解决，特别是由于组合设计 的理论与方法在数理统计、运筹学、信息论和计算机科学中的重要应 用，组合设计的研究进入了一个飞速发展的时期有很多科学家在这个方 面做出了巨大贡献，其中朱烈、康庆德、沈灏、邵嘉裕、r o s a 、w i l s o n 在这方面的研究成果比较突出 组合数学的研究对象是排列、模式、设计、配置、调度、关联和布 局在当今世界中，活跃在各个领域的人们发现解决具有组合数学性质的 问题的必要性计算机科学家为了给复杂的语句编码，需要考虑数字和开 关的模式商店经理着手进行工具或工作场所的人员配置农业专家为不 同的田地分配实验苗电气工程师筛选电路布局银行家研究电子资金转 账的模式空间科学家研究把信息传送到遥远的卫星的模式工业工程师 为使生产高效考虑产品的调度和厂房的布局大学的教务官安排教室以 满足时间段和学生之间的调度化学家考虑不同的原子和分子的可能关 南京师范大学硕士学位论文 联以及分子中原子的排列运输管理员安排公共汽车或飞机的调度语 言学家考虑使用未知字母的单词排列遗传学家考虑把基的排列组合成 d n a 链、r n a 链等统计学家考虑为实验设计替代方案这些问题都是 组合数学研究和要解决的现实问题，可见它不但有很强的理论性的同时 有广泛的应用价值随着科学的发展，组合数学技术已在计算机科学、运 输、信息处理、工业规划、电机工程、实验设计、取样、编码、遗传 学、政治学等其他重要领域发挥着越来越重要的作用 组合设计理论这个既有古老的历史渊源又相当年轻的数学分支，是 一个生气勃勃、广有前途的研究领域并且饶有趣味，引人入胜这是一 座充满真花异草的美好园林，足以使观赏者流连，更能激发年轻一代创造 的愿望与热情 而在这篇文章中主要研究是组合设计中的一类图分解问题，它可应 用于现实生活的相遇问题当中 1 2 基本概念 现在我们来介绍一些术语 定义1 1 ：设g 是2 k v 的m 个点x o ，z 1 ，x m 一1 的没有孤立点 的简单子图，边集是 x o x l ，x l x 2 ，x m - - 2 x m 一1 ，x m - l x o 这种图记为 ( x o ，x 1 ，x m 一1 ) 如果圈的某两个不相连的点有一条边相连，我们称 这种图为目一图 定义1 2 ：带洞g 一设计是一个三元组( x ， x l ，x 2 ，) ，召) 其中x 是m 部图。，n 。的顶点集，五称为洞，b 是。，n 。， 的边不交的子图( 称为区组) 的并，使得每一个子图都同构于g ， 并且。，n 。的每一条边恰好出现在召的a 个区组中其中 ( n l ，n 2 ，n m ) 称为带洞g 一设计的组型，为了方便可用指数形式 南京师范大学硕上学位论文 表示：( 礼 - ，几；：，钆钫) ，即n l 出现k 1 次，l t 2 出现k 2 次，n m 出现 k 次这样的带洞设计常称为：g h d ( 佗 - ，礼l z ，扎静) 定义1 3 -2 甄的g 可约分解是指对子( x ，召) 中的召可分解为两 个子集g 1 和g 2 使得( x ，g 1 ) 和( x ，g 2 ) 是两个一重p 一图分解如 果没有这样的分解我们称其是不可约的 本文主要研究了一些2 重完全图的不可约的p 一图分解，为了方便下 面用瓯表示有k 个点的p 一图 关于图设计和不可约设计，国内外已有很多研究，参见参考文献【1 】- 【2 1 】 本文给出了k = 4 和6 时不可约仇一a d ( v ) 存在的充要条件；对于 k = 5 ，也有部分结果 南京师范大学硕上学位论文 第2 章引理和定理 为方便读者阅读本文，本章将介绍定理证明过程中需要用到的引理 及定理的证明 2 1 引理 引理2 1 1 1 7 ，1 8 设g 是含有k 个点和e 条边如果图分解( 钉，g ，入) 一 g d 存在，那么 ( 1 ) v k ， ( 2 ) 入u ( 钉一1 ) 三0 ( m o d2 e ) ， ( 3 ) 入( u 一1 ) 三0 ( m o dd ) ，d 是g 中点度的最大公约数 引理2 12 【1 7 ，1 9 】m 2 ，如果g h d ( n 2 ) 存在，则存在g h d ( n m ) 引理2 1 3 1 8 ，1 9 1i = 3 ，4 ，5 ，6 ，8 ，m 3 ，如果g h d ( n i ) 存在，则存 在g h d ( n m ) 例：设v = z 4u _ o 。) g 为形如下图的p 一图，记为a 一( b ，c ，d ) 其中 弦为( a ，c ) g = o - ( 1 ，3 ，o o ) ，1 一( 2 ，0 ，) ，2 一( 3 ，1 ，( 3 0 ) ，3 一( o ，2 ，o o ) 】 我们假设这种分解是可约的，那么0 一( 1 ，3 ，) 必属于其中的一个 1 重图分解，不失一般性我们不妨设其为( kg 1 ) ，由于区组0 一( 1 ，3 ，o o ) 和1 一( 2 ，0 ，0 0 ) 都含有边( 0 ，1 ) ，所以1 一( 2 ，0 ，o o ) 必是属于另一个1 重 图分解( vg 2 ) 因此3 一( 0 ，2 ，) 属于( vg 1 ) 又由于0 一( 1 ，3 ，( 2 0 ) 属 于( vg 1 ) ，从而2 一( 3 ，1 ，o o ) 属于( kg 2 ) 此时。一( 1 ，3 ，o o ) 和 南京师范大学硕士学位论文 3 一( 0 ，2 ，o o ) 有相同的边( 0 ，3 ) ，此时出现矛盾所以这种分解是不可 约的因此( vg ) 是2 重不可约的p 一图分解 2 2 构造定理 下面定理的证明类似于1 重的情形参见 1 8 1 定理2 2 1 仇2 ，如果2 - g h d ( n 2 ) 存在，则存在2 - g h d ( n m ) 对于m 3 ，存在一个p b d ( m ， 3 ，4 ，5 ，6 ，8 ) ) ，因此有下面的定理 定理2 2 2 i = 3 ，4 ，5 ，6 ，8 ，m 3 ，如果2 - g h d ( n ) 存在，则存在 2 一g h d ( n m ) ( u ，g ，2 ) 一g d 的存在性问题已有了下面的一些结论( 3 ，4 】) 定理2 2 3 ( v ，g ，2 ) 一g d 存在的必要条件k 4 也是充分的 定理2 24 2 】( u ，g ，2 ) 一g d 存在的必要条件k = 5 也是充分的 定理2 2 5 若存在2 g h d ( n 2 ) ，且存在一个不可约的( n ，k ，2 ) 一g g d ，则存在一个不可约的( m 几，k ，2 ) 一g g d 定理2 2 6 若存在2 g h d ( n 2 ) ，且存在一个不可约的( 佗+ 1 ，k ，2 ) 一 g g d ，则存在一个不可约的( m 几+ 1 ，k ，2 ) 一g g d 南京师范大学硕上学位论文 定理2 2 7 i = 3 ，4 ，5 ，6 ，8 ，m 3 ，若存在2 g h d ( n i ) ，且存在一个不 可约的( 礼，k ，2 ) 一g g d ，则存在一个不可约的( m n ，k ，2 ) 一g g d 定理2 2 8 i = 3 ，4 ，5 ，6 ，8 ，7 7 t 3 ，若存在2 一g h d ( n ) ，且存在一个不可 约的( n + l ，k ，2 ) 一g g d ，则存在一个不可约的( m n + l ，k ，2 ) 一g g d 南京师范大学硕上学位论文 第3 章1 5 i 一图的直接构造 在这部分，我们将给出2 重完全图分解为不可约的p 一图的方法 3 1 四个点9 一图的直接构造 m ：4 时p 一图在同构意义下只有一种的情况： 我们把这个图形记为：a 一( b ，c ，d ) ( v ，g ，2 ) 一g d 存在的必要条件是v 兰0 ，1 ( m o d5 ) 下面是构造过程： 步骤一：u = 5 ，6 ，1 0 ，1 1 ，构造不可约的( 口，g ，2 ) 一g d 2 g h d ( 5 3 ) 2 g h d ( 5 4 1 步骤二：构造2 g h d ( 5 5 ) 2 g h d ( 5 6 ) 2 g h d ( 5 8 1 于是得佗3 时的2 g h d ( 5 竹) 步骤三：根据第二章的引理和步骤一，二可得不可约的 ( u ，g ，2 ) 一g dv 三0 ，1 ( r o o d5 ) 南京师范大学硕l 学位论文 下面开始构造： 步骤一：v = 5 ，6 ，1 0 ，1 1 ，构造不可约的( v ，g ，2 ) 一g d v ：= 5 区组个数 b = 丝虹1 0 坐= 业5 = 4 设点集为x = z 4u o o ) ， 半差的集合为d = 1 ，2 ) 所以根据差集的思想可构造区组召为： 0 一( 1 ，3 ，) + i ( m o d4 ) i z 4 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 v = 6 区组个数 b = 型= 蚓5 = 6 设点集为x = z 6 半差的集合为d = 1 ，2 ，3 ) 所以根据差集的思想可构造区组召为： o 一( 1 ，5 ，3 ) + i ( m o d6 ) i z 6 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 v = = 1 0 区组个数 b = 丝坠1 0 型= 尘= 1 8 设点集为x = 为u o 。) 半差的集合为d = 所以根据差集的思想可构造初始区组召为： o 一( 1 ，5 ，7 ) + i ( m o d1 5 ) i z 1 5 弦为第一个点和第三个点的连边，于是得到( v ，g ，1 ) 一h d ，然后通 过重复区组可得到2 g h d ( 5 3 ) ( b ) 2 - g h d ( 5 4 ) 区组个数b = 掣= 6 0 设点集为x = z 2 0 将其分组为( 0 ，4 ，8 ，1 2 ，1 6 ) + i ，i z 4 半差的集合为d = 1 ，2 ，3 ，5 ，6 ，7 ，9 ，1 0 所以根据差集的思想可构造初始区组召为： 南京师范大学硕士学位论文 。一( 1 ，1 0 ，7 ) + i ( r o o d2 0 ) 0 一( 2 ，9 ，1 5 ) + t ( m o d2 0 ) o 一( 2 ，5 ，6 )+ i ( m o d2 0 ) i z 2 0 弦为第一个点和第三个点的连边于是得到2 g h d ( 5 5 ) ( c ) 2 - g h d ( 5 5 ) 区组个数 b = 壁5 篮= 1 0 0 设点集为x = 磊5 将其分组为( 0 ，5 ，1 0 ，1 5 ，2 0 ) + i ，i z 5 半差的集合为d = 1 ，2 ，3 ，4 ，6 ，7 ，8 ，9 ，1 1 ，1 2 所以根据差集的思想可构造初始区组召为： o 一( 8 ，9 ，1 2 ) + i ( m o d2 5 ) 0 一( 6 ，4 ，1 1 ) + i ( m o d2 5 ) i z 2 5 弦为第一个点和第三个点的连边 于是得到( v ，g ，1 ) 一h d ，然后通过重复区组可得到2 - g h d ( 5 5 ) ( d ) 2 一g h d ( 5 6 ) 区组个数 b ：肇= 1 5 0 设点集为x = z 3 0 将其分组为 ( 0 ，6 ，1 2 ，1 8 ，2 4 ) + i ，i z 6 半差的集合为d = 1 ，2 ，3 ，4 ，5 ，7 ，8 ，9 ，1 1 ，1 3 ，1 4 ，1 5 所以根据差集的思想可构造初始区组8 为： 0 一( 1 ，1 1 ，2 ) + i ( m o d3 0 ) 0 一( 5 ，8 ，1 5 ) + i ( m o d3 0 ) 0 一( 1 4 ，1 0 ，1 3 ) + i ( m o d3 0 ) 0 一( 7 ，1 1 ，9 ) + i ( m o d3 0 ) 0 一( 8 ，1 3 ，1 4 ) + i ( m o d3 0 ) i z 3 0 弦为第一个点和第三个点的连边，于是得到2 g h d ( 5 6 ) ( e ) 2 g h d ( 5 8 ) 区组个数 b = 卒= 2 8 0 设点集为x = z 4 0 将其分组为( 0 ，8 ，1 6 ，2 4 ，3 2 ) + i ，i z s 一1 m 一 南京师范大学硕上学位论文 半差的集合为 d = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，9 ，1 0 ，1 1 1 2 ，1 3 ，1 4 ，1 5 ，1 7 ，1 8 ，1 9 ，2 0 所以根据差集的思想可构造区组b 为( 其中i z 4 0 ) ： o 一( 1 ，1 5 ，1 9 )+ i ( m o d4 0 ) o 一( 1 8 ，1 3 ，7 )+ t ( m o d4 0 ) 0 一( 1 2 ，1 0 ，9 )+ t ( m o d4 0 ) 0 一( 1 4 ，1 1 ，1 5 ) + i ( m o d4 0 ) 0 一( 1 1 ，1 7 ，2 0 ) 卅( m o d4 0 ) 0 一( 1 7 ，1 9 ，1 0 ) + z ( m o d4 0 ) 0 一( 1 8 ，5 ，1 2 )+ ( m o d4 0 ) 弦为第一个点和第三个点的连边，于是得到2 g h d ( 5 8 ) 步骤三：根据根据第二章的引理和定理和步骤一，步骤二可得不可约的 ( u ，g ，2 ) 一g dv 兰0 ，1 ( m o d5 ) 3 2 五个点p 一图的直接构造 m = 5 时p 一图在同构意义下只有下图这一种的情况： e d a 我们把这种图形记为：e 一( a ，b ，c ，d ) ( v ，g ，2 ) 一g d 存在的必要条件是 b c 南京师范大学硕：l 学位论文 u ( u 一1 ) 三0 ，1 ( m o d6 ) ，即v 三0 ，1 ，3 ，4 ( m o d6 ) 根据前面的步骤我构造了u 三0 ，1 ，( m o d6 ) ( v - - 3 ，4 ( r o o d6 ) 的构造还 有一初始值没构造出来) 步骤一：u = 6 ，7 ，1 2 ，1 3 ，构造不可约的( v ，g ，2 ) 一g d 2 g h d ( 6 3 ) 2 g h d ( 6 4 ) 步骤二：构造 2 g h d ( 6 5 ) 2 o h d ( 6 6 ) 2 g h d ( 6 8 1 于是得到n 3 时的2 g h d ( 6 n ) 步骤三：根据第二章的引理和步骤一，二可得不可约的 ( 口，g ，2 ) 一g d ，v 三0 ，1 ( m o d6 ) 下面开始构造： 步骤一：口= 6 ，7 ，1 2 ，1 3 ，构造不可约的的2 重完全图的k = 5 的不可 约p 一图分解( v ，g ，2 ) 一g d 的构造： v = 6 区组个数 b = 型= 尘铲= 5 设点集为x = z 5u o o 半差的集合为d = 1 ，2 ) 所以根据差集的思想可构造区组召为： 0 一( 。o ，4 ，3 ，2 ) + i ( m o d5 ) i z s 弦为第一个点和第三个点的连边于是得到( v ，g ，2 ) 一g d 用前面 例子证明的方法证明这种分解是不可约的 u = 7 区组个数 b = 型= 业铲= 7 设点集为x = z r 半差的集合为d = 1 ，2 ，3 ) 所以根据差集的思想可构造区组召为： 南京师范大学硕上学位论文 。一( 5 ，3 ，4 ，1 ) + i ( r o o d7 )i 历 弦为第一个点和第三个点的连边于是得到( v ，g ，2 ) 一g d 用前面例子证明的方法证明这种分解是不可约的 口= 1 2 区组个数 b = 生止1 2 尘= 剑6 = 2 2 设点集为x = z l lu _ 。o ) 半差的集合为d = 1 ，2 ，3 ，4 ，5 ) 所以根据差集的思想可构造区组召为( 其中i z 1 1 ) ： o 一( 4 ，3 ，5 ，1 0 ) + i ( r o o d1 1 ) 0 一( o o ，2 ，7 ，3 ) + i ( m o d1 1 ) 弦为第一个点和第三个点的连边用前面例子的证明和方法证明这 种分解是不可约的 v = 1 3 区组个数 b = 生坠1 0 尘= 业= 2 6 设点集为x = z x 3 半差的集合为d = 1 ，2 ，3 ，4 ，5 ，6 ) 所以根据差集的思想可构造区组召为( 其中i z 1 3 ) ： o 一( 7 ，1 ，4 ，8 ) + i ( m o d1 3 ) 0 一( 2 ，4 ，5 ，8 ) + i ( m o d1 3 ) 弦为第一个点和第三个点的连边于是得到( v ，g ，2 ) 一g d 用前面 例子的证明和方法证明这种分解是不可约的 2 - g h d ( 6 3 ) 2 一g h d ( 6 4 ) 步骤二：构造 2 g h d ( 6 5 ) 2 g h d ( 6 6 ) 2 g h d ( 6 8 1 于是得到n 3 时的2 g h d ( 6 礼) ，： ( a ) 2 - g h d ( 6 3 ) 区组个数 b ：竿= 1 8 设点集为x = z 1 8 南京师范大学硕士学位沦文 将其分组为 ( o ，3 ，6 ，9 ，1 2 ，1 5 ) + i ，i 磊 半差的集合为d = 所以根据差集的思想可构造区组召为： o 一( 8 ，1 ，6 ，4 ) + i ( m o d1 8 ) i z 1 8 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的于是得到( v ，g ，1 ) 一h d ，然后通过重复区组可得到 2 一g h d ( 6 3 1 ( b ) 2 - g h d ( 6 5 ) 区组个数 b = 华= 6 0 设点集为x = z 3 0 将其分组为 ( 0 ，5 ，1 0 ，1 5 ，2 0 ，2 5 ) + i ，i z 5 半差的集合为d = 1 ，2 ，3 ，4 ，6 ，7 ，8 ，9 ，1 1 ，1 2 ，1 3 ，1 4 所以根据差集的思想可构造区组召为( 其中i z 3 0 ) ： o 一( 1 1 ，2 ，1 5 ，1 4 ) + i ( m o d3 0 ) 0 一( 1 2 ，4 ，1 0 ，7 ) + i ( m o d3 0 ) 弦为第一个点和第三个点的连边，于是得到( u ，g ，1 ) 一h d ，然后通 过重复区组可得到2 g h d ( 6 5 ) ( c ) 2 - g h d ( 6 4 ) 区组个数 b ：塑：7 2 设点集为x = 易4 将其分组为( 0 ，4 ，8 ，1 2 ，1 6 ，2 0 ) + i ，i z 4 半差的集合为d = 1 ，2 ，3 ，5 ，6 ，7 ，9 ，1 0 ，1 1 所以根据差集的思想可构造区组召为( 其中i z 2 4 ) ： 0 一( 6 ，1 ，1 2 ，2 ) “( r o o d2 4 ) o 一( 1 3 ，3 ，1 2 ，5 ) + ( m o d2 4 ) 0 一( 9 ，6 ，8 ，7 )+ i ( m o d2 4 ) 弦为第一个点和第三个点的连边于是得到2 g h d ( 6 4 ) 一1 4 _ 一 南京师范大学硕上学位论文 ( d ) 2 - g h d ( 6 6 ) 区组个数 b ：垒鱼6 篮= 1 8 0 设点集为x = z 3 6 将其分组为( 0 ，6 ，1 2 ，1 8 ，2 4 ，3 0 ) + i ，i 磊 半差的集合为d = 1 ，2 ，3 ，4 ，5 ，7 ，8 ，9 ，1 0 ，1 1 ，1 3 ，1 4 ，1 5 ，1 6 ，1 7 所以根据差集的思想可构造区组召为( 其中i z 3 6 ) ： 0 一( 8 ，1 ，1 8 ，2 )+ i ( r o o d3 6 ) 0 一( 1 3 ，3 ，1 8 ，4 )+ i ( m o d3 6 ) o 一( 2 0 ，5 ，1 8 ，7 )十( m o d3 6 ) o 一( 1 0 ，1 ，1 5 ，1 1 ) + i ( m o d3 6 ) o 一( 5 ，2 ，1 0 ，9 )+ i ( m o d3 6 ) 弦为第一个点和第三个点的连边，于是得到2 g h d ( 6 6 ) ( e ) 2 一g h d ( 6 8 ) 区组个数 b ：驾乒= 3 3 6 设点集为x = z 4 8 将其分组为( 0 ，8 ，1 6 ，2 4 ，3 2 ，4 0 ) + i ，i z 8 半差的集合为d = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，9 ，1 0 ，1 1 ，1 2 ， 1 3 ，1 4 ，1 5 ，1 7 ，1 8 ，1 9 ，2 0 ，2 1 ，2 2 ，2 3 所以根据差集的思想可构造区组召为( 其中i z 4 8 ) ： o 一( 1 0 ，1 ，2 4 ，2 )“( r o o d4 8 ) 0 一( 1 5 ，3 ，2 4 ，4 )+ i ( m o d4 8 ) o 一( 1 8 ，5 ，2 4 ，6 )“( m o d4 8 ) 0 一( 7 ，1 1 ，2 5 ，5 )+ t ( r o o d4 8 ) o 一( 1 0 ，1 ，2 4 ，2 )“( m o d4 8 ) o 一( 3 4 ，1 7 ，2 8 ，7 ) 卅( r o o d4 8 ) 0 一( 1 9 ，6 ，1 8 ，3 ) + i ( m o d4 8 ) 弦为第一个点和第三个点的连边，于是得到2 g h d ( 6 8 ) 步骤三：根据第二章的引理和步骤一，二不可约的可得 一1 5 - 一 南京师范大学硕上学位论文 苎! ! ! 苎! ! 曼! ! ! ! ! ! 苎! ! ! ! ! ! ! ! ! 曼! 曼! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 暑! 鼍i l i d ! m ( v ，g ，2 ) 一g d ，v 三0 ，1 ( m o d6 ) 构造钞三3 ，4 ( r o o d6 ) 步骤一：点v ：9 ，1 0 ，1 5 ，1 6 的2 一完全图的k = 5 的不可约的9 一图 分解( v ，g ，2 ) 一g d 的构造： v = = 9 区组个数 b = 丝型= 蝴6 = 1 2 设点集为x = z 9 半差的集合为d = 1 ，2 ，3 ，4 ) 所以根据差集的思想可构造区组召为( 其中i z 9 ) ： o 一( 1 ，2 ，3 ，6 ) + 3 i ( m o d9 ) o 一( 1 ，2 ，4 ，7 ) + 3 i ( m o d9 ) 0 一( 4 ，7 ，2 ，5 ) + 3 i ( m o d9 ) 0 一( 8 ，4 ，2 ，5 ) + 3 i ( m o d9 ) 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 v = 1 0 区组个数 b = 生坠1 2 型= 业= 1 5 设点集为x = z 1 0 半差的集合为d = 1 ，2 ，3 ，4 ，5 ) 所以根据差集的思想可构造区组召为( 其中i z l o ) ： 0 一( 1 ，2 ，3 ，4 ) + 2 i ( m o d1 0 ) 0 一( 2 ，5 ，1 ，3 ) + 2 i ( m o d1 0 ) 0 一( 5 ，7 ，1 ，4 ) + 2 i ( r o o d1 0 ) 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 v = 1 5 区组个数 b = 丝长尘= 业= 3 5 南京师范大学硕上学位论文 设点集为x = z 1 5 半差的集合为d - - - - 1 ，2 ，3 ，4 ，5 ，6 ，7 ) 可以根据差集的思想可构造区组召( 未构造出来) v = 1 6 区组个数b = 必1 2 = 业6 = 4 0 设点集为x = z 1 6 半差的集合为d = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) 所以根据差集的思想可构造初始区组召为( 其中i z 1 6 ) ： 0 一( 1 ，2 ，3 ，4 )+ 2 i ( m o d1 6 ) o 一( 2 ，5 ，1 ，3 )+ 2 i ( m o d1 6 ) o 一( 4 ，9 ，1 ，6 )+ 2 i ( m o d1 6 ) o 一( 6 ，1 3 ，1 ，1 7 ) + 2 i ( m o d1 6 ) 0 一( 9 ，1 1 ，5 ，8 )+ 2 i ( m o d1 6 ) 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 2 g h d ( 9 3 )2 - g h d ( 9 4 ) 步骤二：构造2 g h d ( 9 5 ) 2 - g h d ( 9 6 ) 2 g h d ( 9 8 1 于是得到佗3 时的2 - g h d ( 9 n ) ： ( a ) 2 一g h d ( 9 3 ) 区组个数 b ：1 9 2 c r 2 = 8 1 设点集为x = z 2 7 将其分组为( 0 ，3 ，6 ，9 ，1 2 ，1 5 ，1 8 ，2 1 ，2 4 ) “，i 历 半差的集合为d = 1 ，2 ，4 ，5 ，7 ，8 ，1 0 ，1 1 ，1 3 ) 所以根据差集的思想可构造初始区组召为( 其中i 易7 ) ： o 一( 7 ，1 4 ，1 5 ，1 7 ) “( m o d2 7 ) 0 一( 1 3 ，8 ，6 ，1 6 )+ i ( m o d2 7 ) o 一( 5 ，4 ，8 ，1 6 )+ i ( m o d2 7 ) 一1 7 一 甫京师范大学硕士学位论文 弦为第一个点和第三个点的连边，于是得到2 g h d ( 9 3 ) ( b ) 2 一g h d ( 9 4 ) 区组个数 b ：盟9 篮= 1 6 2 设点集为x = 磊6 将其分组为( 0 ，4 ，8 ，1 2 ，1 6 ，2 0 ，2 4 ，2 8 ，3 2 ) + i ，i 玩 半差的集合为d = 1 ，2 ，3 ，5 ，6 ，7 ，9 ，1 0 ，1 1 ，1 3 ，1 4 ，1 5 ，1 7 ，a s 所以根据差集的思想可构造初始区组召为( 其中i z 3 6 ) ： 0 一( 1 4 ，2 9 ，4 ，2 1 ) + 2 i ( m o d3 6 ) 0 一( 2 9 ，1 9 ，1 ，1 8 ) + 2 i ( m o d3 6 ) o 一( 1 7 ，2 7 ，6 ，3 1 ) + 2 i ( m o d3 6 ) 0 一( 1 ，2 ，3 ，5 )+ 2 i ( m o d3 6 ) 0 一( 2 ，5 ，3 ，6 )+ 2 i ( m o d3 6 ) o 一( 3 ，6 ，1 ，7 )+ 2 i ( m o d3 6 ) o 一( 7 ，1 3 ，2 ，1 1 )+ 2 i ( m o d3 6 ) 0 一( 9 ，1 0 ，1 ，1 4 )+ 2 i ( r o o d3 6 ) 0 一( 1 0 ，2 3 ，1 ，1 5 )+ 2 i ( m o d3 6 ) 弦为第一个点和第三个点的连边，于是得到2 g h d ( 9 4 ) ( c ) 2 - g h d ( 9 5 ) 区组个数 b ：掣= 2 7 0 设点集为x = 历5 将其分组为 ( 0 ，5 ，1 0 ，1 5 ，2 0 ，2 5 ，3 0 ，3 5 ，4 0 ) + i ，i z 5 半差的集合为拈 1 ，2 ，3 ，4 ，6 ，7 ，8 ，9 1 1 , 1 2 1 3 ，1 4 ，1 6 ，1 7 ，1 8 ，1 9 ，2 1 ，2 2 所以根据差集的思想可构造初始区组召为( 其中i 乙5 ) ： 0 0 0 0 2 ，4 ，7 ) 7 ，1 ，9 ) 1 2 ，1 ，1 3 ) 1 7 ，1 ，1 8 ) 一1 & 一 5 5 5 5 4 4 4 4 d d d d o o o o m m m m ，fi、，ii、i，f d o 0 n o z + + + + 南京师范大学硕上学位论文 0 一( 9 ，2 3 ，2 ，2 1 )+ t ( m o d4 5 ) 0 一( 1 4 ，3 2 ，6 ，2 2 ) + t ( m o d4 5 ) 弦为第一个点和第三个点的连边，于是得到2 g h d ( 9 5 ) ( d ) 2 一g h d ( 9 6 ) 区组个数b = 警= 4 0 5 设点集为x = 磊4 将其分组为( 0 ，6 ，1 2 ，1 8 ，2 4 ，3 0 ，3 6 ，4 2 ，4 8 ) + i ，i 磊 半差的集合为d = 1 ，2 ，3 ，4 ，5 ，7 ，8 ，9 ，1 0 , 1 1 , 1 3 , 1 4 , 1 5 ，1 6 ，1 7 ，1 9 ，2 0 ，2 1 ，2 2 ，2 3 ，2 5 ，2 6 ，2 7 所以根据差集的思想可构造初始区组召为( 其中i z 5 4 ) ： o 一( 1 ，2 ，3 ，4 )+ 2 i ( m o d5 4 ) o 一( 2 ，5 ，1 ，3 )+ 2 i ( m o d5 4 ) o 一( 4 ，9 ，1 ，8 )+ 2 i ( m o d5 4 ) 0 一( 7 ，9 ，1 ，8 )+ 2 i ( m o d5 4 ) 0 一( 7 ，1 0 ，1 ，1 1 )+ 2 i ( m o d5 4 ) o 一( 1 0 ，2 1 ，1 ，1 4 )+ 2 i ( m o d5 4 ) 0 一( 1 3 ，1 6 ，2 ，1 5 )+ 2 i ( m o d5 4 ) 0 一( 1 5 ，1 9 ，2 ，2 1 )+ 2 i ( m o d5 4 ) o 一( 1 6 ，3 3 ，2 ，2 2 )+ 2 i ( m o d5 4 ) o 一( 2 0 ，4 3 ，3 ，2 2 )+ 2 i ( m o d5 4 ) 1 一( 6 ，2 9 ，3 ，1 2 )+ 2 i ( m o d5 4 ) 0 一( 2 5 ，3 5 ，6 ，3 7 )+ 2 i ( m o d5 4 ) o 一( 3 9 ，2 5 ，4 0 ，2 7 ) + 2 i ( m o d5 4 ) 0 一( 4 9 ，2 7 ，5 2 ，2 6 ) + 2 i ( m o d5 4 ) 1 一( 1 7 ，3 9 ，2 ，3 5 )+ 2 i ( m o d5 4 ) 弦为第一个点和第三个点的连边，于是得到2 g h d ( 9 6 ) ( e ) 2 - g h d ( 9 8 ) 区组个数b ：彳9 2 i - , , 2 = 7 5 6 一1 9 一 南京师范大学硕七学位论文 设点集为x = 历2 将其分组为( 0 ，8 ，1 6 ，2 4 ，3 2 ，4 0 ，4 8 ，5 6 ，6 4 ) “，i 磊 1 ，2 ，3 ，4 ，5 ，6 ，7 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ， 半差的集合为扛1 4 ，1 5 ，1 7 ，1 8 ，1 9 ，2 0 ，2 1 ，2 2 ，2 3 ，2 5 ， 2 6 ，2 7 ，2 8 ，2 9 ，3 0 ，3 l ，3 3 ，3 4 ，3 5 ，3 6 所以根据差集的思想可构造初始区组召为( 其中i z 7 2 ) ： 0 一( 1 ，2 ，3 ，4 )+ 2 i ( m o d7 2 ) 0 ( 2 ，5 ，1 ，3 )+ 2 i ( m o d7 2 ) o 一( 4 ，9 ，2 ，1 1 )+ 2 i ( m o d7 2 ) o 一( 6 ，1 2 ，1 ，7 )+ 2 i ( m o d7 2 ) 0 一( 1 0 ，2 0 ，1 ，1 1 ) + 2 i ( m o d7 2 ) o 一( 1 2 ，2 5 ，2 ，1 5 ) + 2 i ( m o d7 2 ) 0 一( 1 4 ，2 8 ，1 ，1 5 ) + 2 i ( m o d7 2 ) o 一( 1 7 ，1 9 ，1 ，1 8 ) + 2 i ( m o d7 2 ) 0 一( 1 7 ，2 0 ，1 ，1 8 ) + 2 i ( m o d7 2 ) 0 一( 1 9 ，2 2 ，1 ，2 1 ) + 2 i ( m o d7 2 ) 1 一( 2 1 ，2 5 ，2 ，2 8 ) + 2 i ( m o d7 2 ) o 一( 2 2 ，4 9 ，2 ，2 9 ) + 2 i ( r o o d7 2 ) 0 一( 2 6 ，5 7 ，3 ，2 9 ) + 2 i ( m o d7 2 ) 0 一( 3 0 ，6 1 ，1 ，3 4 ) + 2 i ( m o d7 2 ) 1 一( 6 ，3 6 ，2 ，3 5 )+ 2 i ( m o d7 2 ) 0 一( 3 3 ，3 9 ，2 ，4 3 ) + 2 i ( r o o d7 2 ) 0 一( 3 5 ，4 5 ，1 ，4 3 ) + 2 i ( m o d7 2 ) o 一( 3 5 ，4 7 ，6 0 ，5 1 ) + 2 i ( m o d7 2 ) o 一( 4 1 ，6 7 ，2 ，5 9 )+ 2 i ( m o d7 2 ) 1 一( 2 1 ，4 3 ，7 ，5 1 )+ 2 i ( m o d7 2 ) 0 一( 4 9 ，6 3 ，2 9 ，3 6 ) + 2 i ( m o d7 2 ) 弦为第一个点和第三个点的连边，于是得到2 一g h d ( 9 8 ) 一2 m 一 南京师范大学硕上学位论文 步骤三：根据第二章的引理和步骤一，二可得不可约的 ( v ，g ，2 ) 一g d ，口三3 ，4 ( m o d6 ) 3 3 六个点p 一图的直接构造 m = 6 时p 一图有两种的情况，一种是弦为第一个点与第三个点的连 我们把这种图形记为：，一( a ，b ，c ，d ，e ) 另一种是弦为第一个点与第四个点的连边： b c b d 南京师范大学硕士学位论文 我们把这种图形记为：a 一( b ，c ，d ，e ，) ( u ，g ，2 ) 一g d 存在的必要条件是 v 三0 ，1 ( m o d7 ) ，即v 三0 ，1 ( r o o d7 ) 按照下面的步骤先构造弦为第一个点与第三个点的连边的图分解： 步骤一：u = 7 ，8 ，1 4 ，1 5 ，构造不可约的( 钉，g ，2 ) 一g d 2 - g h d ( 7 3 ) 2 一g h d ( 7 4 ) 步骤二：构造2 - g h d ( 7 5 ) 2 - g h d ( 7 6 ) 2 g h d ( 7 8 、 步骤三：根据第二章的引理和步骤一，二可得不可约的 ( v ，g ，2 ) 一g d ，v 三0 ，1 ( m o d7 ) 现在开始构造： 步骤一：构造不可约的( u ，g ，2 ) 一g d 口= 7 ，8 ，1 4 ，1 5 。 v = 7 区组个数 b = 生告尘= 业乒= 6 设点集为x = 磊u ) 半差集合为d = 1 ，2 ，3 ) 所以根据差集的思想可构造初始区组召为： 0 一( 3 ，1 ，2 ，4 ，o o ) + ii 磊 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 v = 8 区组个数 b = 生业1 4 尘= 业产= 8 设点集为x = 磊 半差集合为d = 1 ，2 ，3 ，4 ) 所以根据差集的思想可构造初始区组召为： 1 一( 0 ，3 ，7 ，4 ，2 ) + ii z 8 南京师范大学硕上宁位论文 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 v = 1 4 区组个数 b = 生业1 4 尘= 尘乒= 2 6 设点集为x = z 1 3u ) 半差集合为d = 1 ，2 ，3 ，4 ，5 ，6 ) 所以根据差集的思想可构造初始区组召为： o 一( 6 ，5 ，1 1 ，7 ，2 ) + i0 一( o o ，1 ，3 ，6 ，1 0 ) + i ，i z x 3 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 v = 1 5 区组个数 b = 捌1 4 = 蚓7 = 3 0 设点集为x = z 1 5 半差集合为d = 1 ，2 ，3 ，4 ，5 ，6 ，7 ) 所以根据差集的思想可构造初始区组8 为( 其中i z 1 5 ) ： 0 一( 1 ，3 ，8 ，2 ，7 ) + i ( m o d1 5 ) 0 一( 7 ，3 ，4 ，8 ，6 ) + i ( m o d1 5 ) 弦为第一个点和第三个点的连边用前面例子证明的方法证明这种 分解是不可约的 2 g h d ( 7 3 ) 2 g h d ( 7 4 ) 步骤二：构造2 g h d ( 7 5 ) 2 g h d ( 7 6 ) 2 g h d ( 7 8 ) 于是可得到佗3 时的2 一g h d ( 7 n ) ： ( a ) 2 一g h d ( 7 3 ) 区组个数 b ：z 丝7 = 2 1 设点集为x = 汤1 将其分组为( 0 ，3 ，6 ，9 ，1 2 ，1 5 ，1 8 ，2 1 ) “，i z