（运筹学与控制论专业论文）关于有向θ图的图设计.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外。不包含其他人或其它机构已经发 表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢 意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版； 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查 阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标 题和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者签名： 日期： 摘要 设虬是一个v 点的有向完全图，g 是一个简单有向图，凰的一 个g 一设计，i a 为( v ，g ，1 ) 一g d ，是指一个二元组( x ，留) ，其中x 为的点 集，留为j 厶的一些子图( 也称为区组) 构成的集合，使得任一子图( 区组) 与g 同 构，且k ，的任意两个不同点组成的有向边恰在劈的一个区组中出现。本文研 究了六点有向日图和七点有向日图的图设计的存在性问题。 关键词完全有向图；口图；图设计；带洞图设计 南r i 卿危人学砂! 上学戗论史 a b s t r a c t l e t b eac o m p l e t ed i r c t e dg r a p hw i t huv e r t i c e s ，gb eas i m p l ed i r e c t e d s u b g r a p h a g d e s i g n o f 玩，d e n o t e d b y ( v ；k ，1 ) - o h ，i s a p a i r ( x ，留) ，w h e r e x i s t h e v e r t i e e s 吼o t k 。a n d 国i s t h e c o l l e c t i o n o f s u b g r a p h s ( c a l l e d b l o c k s ) o f k v ，s u c h t h a te a c hb l o c ki si s m o r p h i ct og ，a n da n ye d g ei nk uo e c u l n 3i ne x a c t l yo n es u b g r a p h i nt h i sa r t i c l e ，t h ea n t h o rs t u d yt h ee x i s t e n c eo f g r a p hd e s i g no f n o n - i s o m o r p h i cs i m p l e d i r e c t e d0g r a p h sw i t hs i xv e r t i c e s ，a n de i g h tn o n i s o m o 删es i m p l ed i r e c t e d0g r a p h s w i t hs e v e nv e r t i c e sa n dd i r e c t e dc y c l e k e y w o r d sc o m p l e t ed i r e c t e dg r a p h ；0g r a p h ；d i r e c t e dg r a p hd e s i g n ；h o l e yg r a p h d e s i g n 2 一 南京帅翘，、学硕上学竹论艾 第1 章前言 组合设计问题是组合数学的一个重要分支，是一门研究将事物按特定 要求进行安排并讨论其性质的学问。组合设计理论是一个既有古老历史渊 源而又相当年轻的数学分支。它的历史可以追溯到很远，4 0 0 0 年以前我国 就有关于”河图洛书”的美丽传说，其中”洛书”就是一个简单的组合设计， l i p 3 阶幻方。历史上有许多著名的有关组合设计的难题，如e u l e r 的3 6 军官问 题和i o r k m a n 女生问题等，它们以特有的应用价值和趣味性吸引了大量的数 学爱好者。 其中l ( i 岫女生问题( a 正元系的存在性问题) 从提出到完全解 决，历时1 0 0 多年。1 8 5 0 年，德国一名教师k i r k m a n 提出如下一个问题：一 位女教师每天带领班上的1 5 个女生散步，她把这些女生分成每三人一组， 共5 组，这样每个女生都有两个同伴。问题就是能否作出一个连续七天的散 步计划，使得任意两个女生都正好有一次被安排在同一个组? 我们知道k i r k m a n 女生问题存在解的前提是：1 5 名女生集合一定有3 5 个 三人组，使得每队女生同在一个且仅在一个三人组中。更一般地，考虑下面 的问题： 定义1 1 ：设u 是正整数，我们称( x ，留) 为s t e i n e r 三元系，其中x 是u 个元 素的集合，留是x 的一个子集簇( 其成员b 称为区组) ，满足以下两个条件： 1 ) 如果b 留，则j 引= 3 。 2 ) x 中任意两个不同元素恰在留的一个区组中出现。 我们记6 = i 留l 根据定义显然有6 = 业产，则鼬女生问题中”= 1 5 ，b = 3 5 。 例：设x = 1 ，2 ，3 ，4 ，5 ，6 ，7 历： 1 ，2 ，4 ) ， 2 ，3 ，5 ) ， 3 ，4 ，6 ) ， 4 ，5 ，7 ) ， 5 ，6 ，l ， 6 ，7 ，2 ) ，7 ，1 ，3 ) ) 。 4 则( x ，留) 就是一个7 阶s t e i n e r 三元系。 随着对s t e i n e r - - - 元系的研究，人们进一步考虑当i 口i = 时的情形，从而 引入了区组设计的概念。 定义1 2 ：设 ，七，a 为给定的正整数，我们称( x ，留) 为平衡不完全区组设 计，其中x 是u 个元素的集合。留为x 的一个子集簇( 其中它的成员b 称为区 组1 ，满足以下两个条件： 1 ) 如果b 历，则l b i = 七。 2 ) x 中任意两个不同元素恰在留的a 个区组中出现。 后来h e l l 和r o s a 用图结构的思想推广了区组设计的概念，这些设计就称 为图设计( g 设计) 。近几十年关于图设计的存在性问题，有着广泛的研究， 本文主要讨论了部分有向图的图设计。 南京师范人学硕j 学位论史 第2 章引入 2 1 基本定义与基本定理 一个n 点的简单有向图g ，是指对任意的z ，y v ( a ) ，边( z ，) 与( 可，z ) 不 能同时在边集e ( g ) 中，且( z ，$ ) 也不在边集e ( g ) 中。设凰是一个口点有向 完全图，g 是一个不带孤立点的简单有向图。甄的一个g 一设计，记 为( ，g ，1 ) 一g d ，是指一个二元组( x ，留) ，其中x 为k ，的点集，留为k ，的一 些子图( 也称为区组) 构成的集合，使得任一子图( 区组) n g n 构，且k ，的任意 两个不同点组成的有向边恰在留的一个区组中出现。 一个m 圈是指一个有m 个顶点的简单图，它的顶点集记 为： z o ，z 1 ，x m - 1 ) 边集记为： $ i l x d l i m 一1 u x o x 。一1 ，表示 为：( z o ，z l ，x m - 1 ) 或( 。一l ，z 。2 ，x o ) 。若c 是一个m 圈：。和y 是c 的两 个不同的点，且满足z 不是c 的一条边，则我们称z f 为c 的弦。则一个圈c 加 上它的一条弦我们称为一个0 图。若一个0 图有2 n 个顶点，它的弦的两个端 点之间有r 个顶点，则这个口图记为d ? 。 例：如下图的六点目图，可以记为：唾1 或c 扩。 近几十年关于无向图的图设计的存在性问题，有着广泛的研究，其 中关于p 图的研究也颇多，2 0 0 1 年a n d r e w b l i n c o 在文章 1 l e e 研究了当r = 一 1 时晓2 的图设计的存在性问题。得到了下面的定理： 定理2 1 h ( 1 ) 对于n 是奇数，当t ，三0 ( m o d2 n + 1 ) 时，存在一个u 点的嘲一设 计，( 几， ) = ( 3 ，7 ) 除外。 ( 2 ) 对于礼= 5 ，n = 9 或n 兰3 ( m o d4 ) ，当口三1 ( m o d2 n + 1 ) 时存在一 个t 点的c 躲一设计。 ( 3 ) 对于n 兰1 ( r o o d4 ) m 1 3 ，当t ，三1 ( m o d4 n + 2 ) 时存在个 点 的哦2 一设计。 2 0 0 3 年a 1 1 d r e wb l i n c o 在文章【2 】研究了少于十条边的口图的图设计的存在 问题。 2 0 0 4 年康庆德、左慧娟等在文章【4 】研究了六点、七点、八点目图，得到 如下的结论： 定理2 1 2 ： ( 1 ) ( ，诺”，a ) 一g d 存在的充要条件为：a v ( v 一1 ) i0 ( r o o d1 4 ) 口6 ( 口，货，入) 一g d 存在的充要条件为：a v ( v 一1 ) 兰0 ( m o d1 4 ) t i 6 且( 弘a ) ( 7 ，1 ) ( 2 ) 对于r = l ，2 ，( ”，哕，a ) 一g d 存在的充要条件为：a v ( v 一1 ) 三0 ( r o o d l 6 ) 口7 ( 3 ) 对于r = 1 ，2 ，3 ，( 口，c 1 5 ：r ) ，a ) 一g d 存在的充要条件为：a v ( v 一1 ) 三0 ( r o o d1 8 ) 口8 ，( 口，r ，a ) = ( 9 ，3 ，1 ) 除外 2 0 0 5 年单秀玲、康庆德在文章【5 】解决了1 0 点口图的图设计问题，并且给 出了下面的存在谱： 定理2 1 3 ：对于r = l ，2 ，3 ，4 ，c f ；一g d ( u ) 的存在谱是u 三o ，1 ( m o d1 1 ) 且u 1 1 以上都是对无向图的研究，但对有向图的图设计的存在讨论颇少。我们 知道m e n d e l s o h n 设计( 见文章 6 】) 中讨论的区组设计中点对是有序的，反映在 图上就是有向图。 本文研究了六点有向日图及含有有向圈的七点有向口图的图设计。 我们给出下面的引理 引理2 1 1 ：若有向图g 有k 个顶点，e 条边，且各个顶点正度数的最大公因 子为d + ，负度数的最大公因子为d 一，则( ，g ，1 ) 一g d 存在的必要条件为： v ( v 一1 ) 三0 ( r o o de ) 扣一1 ) 兰0 ( r o o dd + ) 一1 ) 兰0 ( m o dd 一) k 口k k 证明：设( x 留) 是一个( ，k ，1 ) 一g d ，其中l x f = ，则共有1 留l = ! 气型个区组。因为i 毋l 为整数，所以 扣一1 ) 兰0 ( r o o de ) ， 口2k 。 对任意的点v o ，则在中入度d + ( v o ) = 一1 设有向图g 中个点 的入度分别为d + ，d 妄，砧，且历中含有如的区组有s 个，这些区组e e v o a , 度为对的有8 1 个，入度为对的有s 2 个，入度为d + 的有s k 个贝u s l d + + s 2 d j + + 船对= 口一1 因为( d + ，对，d j ) = d + ， 所以 一1 ) 三0 ( m o dd + ) ， 口k 。 同理可证： 扣一1 ) 三0 ( r o o dd - ) ， 七。 定义2 1 1 ：设k 。，。为m 部有向图。带洞g 一设计是一个三 元组( x ， 置，恐，) ，) ，其中x 是k ，。，。的顶点集，x = ( x l ，岛，j ) ( 蜀称为洞) ，是k 。，t 1 2 ，。的边不交的子图( 称为区组) 构成 集合，使得每个子图都同构于g ，并且k 。，。的每一条边恰出现在的 一个区组中。其中( n l ，砌，一，竹。) 称为带洞g 一设计的组型，为了方便可用 指数形式表示：( n ：，n ! 。，嘲) ，即m 出现k 1 次，n 2 出现k 2 次，n m 出 现七。次。这样的带洞g 一设计常记为：g h d ( n ：1 ，磅，n 静) 。 定义2 1 2 ：设耳为正整数集合，我们称( x ，) 为成对平衡区组设计，记 为p b d ( v ，k ) ，其e e x 是u 个点的集合，是x 的一个子集簇( 区组) ，且满足 以下两个条件： ( 1 ) 如果a ，则i a i k 。 ( 2 ) x 中的任意两个不同的元素恰在的一个区组中出现。 定义2 1 3 ：设k 为一些整数的集合，且设b ( k ) = p ：存在一 个p b d ( v ，k ) ，则称b ( k ) 是k 的闭包。 2 2 不同构的有向图 定义2 2 1 ：两个有向图g 和h 称为同构的( 记为：g 型日) ，若存在双 射：v ( g ) 一y ( 日) 满足( 钍， ) e ( g ) ，当且仅当( ( u ) ，( u ) ) e ( 日) 。 例2 2 1 ：有向图g 和日分别如下图所示： b c困：因： gh 则显然存在这样的双射，使得：( 口) = a l ，妒( 6 ) = d l ，妒( c ) = c 1 ，妒( d ) = b l 易 验证：g 兰h 首先，若两个有向图满足这样的条件，即这两图对应边的方向完全相反如 上述例2 2 1 中的两图，我们可设( x ，留) 为一个( 口，4 ，1 ) 一g g d ，其中i x i = t ， ，留= 玩，岛，b m ) ，晟0 = 0 ，1 ，m ) 表示与g 同构的的子图，不妨假 设b 1 = ( a l0 , 2a 3 口4 ) ，则边为口1 a 2 ，a 3 a 2 ，a 4 a 3 ，a 4 a l ，a 4 a 2 ，若改变b l 中边的方 向变为口2 a 1 ，a 2 a 3 ，a 3 a 4 ，a l a 4 ，a 2 6 4 ，则可证b l 与日同构，所以，留) 同样是一 个( ，4 ，1 ) 一日一g d 其次，若有向图g 满足这样的条件：通过同构置换( 如对称变换) 之后得到 有向图g ，若g 与g 对应边的方向完全相反，则可由它们所对应的无向图g + 得 到有向图g 的图设计如上述例2 2 1 中的有向图g ，对g 做置换( 6 d ) ，则可以得到 图h ，它们所对应的无向图g 如图： 南京师范人学硕j 中f 硷史 6 d 若( x ，劈) 为一个( t ，4 ，1 ) 一g 一g d ，其中l x l = t ，留 = b o ，b l ，b m ，晟0 = 0 ，1 ，m ) 表示与g + 同构的的子图- 不妨假 设b 1 = ( n 1a 2a 38 4 ) ，则将其加上方向0 1 a 2 ，a 3 a 2 ，a 4 a 3 ，a 4 a l ，a , i a 2 之后与g 同 构，然后对其进行置换( 眈n 4 ) 得到b ：，我们在对b 中的所有的区组都进行类 似的这种置换，得到，所以( x ，留u 留) 是一个( 口，4 ，1 ) 一g g d ，同样的 方法可以得到一个( ，4 ，1 ) 一日一g d 下面我们给出了本文中所讨论的有向图，如下：( 图中只画出了逆时针 方向的边，无方向标记的边为顺时针方向) l 型的六点有向日图：( 下面我们只给出了一半的图形，改变弦的方向会得 到另一半图形) g ，g g 1 1 i i 型的六点有向口图：( 下面我们只给出了一半的图形，改变弦的方向会 得到另一半图形1 口5 日” a 3 a 4 4 3 4 4 j 日1 j 4 j 日 如 以 b 钆r l 屯 仓仓量e 吖0 i 吼钆 仓三仓；命 名人 l q 岔t 9 e d 6 4 5 h 3 l 含有有向圈的七点有向口图： 口5 月暂 一1 2 a 3 4 1 4 j 月 u 乏锄uu 夏吒u 八v屯八u吒吒e a 7 a l o , 2 a 7 a l a 2 a 7 a l 眈 本文得到的结论为： a 5 a 4 a a a 5 a 4 a a a 5 a 4 a 3 a 7 a l a 2 a 7 a l a 2 a 7 a l a 2 a 5 a 4 a 3 a a a 4 a 3 a 5 a 4 a 3 a 7 a l a 2 0 7 0 1 a 2 a 5 a 4 a 3 a 5 a 4 a a 定理2 2 1 ：对于 = 1 ，2 ，3 ，1 2 ，存在一个( 口，g i ，1 ) 一g d 的充要条 件是v 三0 ，1 ( m o d7 ) 7 3 八日岱八日 八d g八日詈八日 定理2 2 2 ：对于i = 1 ，2 ，3 ，3 6 ，存在一个( ，皿，1 ) 一g d 的充要条 件是口兰7 ，8 ( m o d1 4 ) 。 定理2 2 3 对于t = 1 ，2 ，3 ，8 ，存在一个( 口，g ：，1 ) 一g d 的充要条件 是t 兰0 ，1 ( m o d8 ) 8 一1 4 第3 章一般构造 下面的引理可以在书 3 1 e 找到。 引理3 1 ：对下面的k 和g 有b ( g ) = ： ( i ) k 3 = 口：t ，3 ，g = 3 ，4 ，5 ，6 ，8 ) ； ( i i ) k = 口：钉三1 ( r o o d2 ) ) ，g = 3 ，5 ) 引理3 2 ：如果存在g h d ( n 2 ) ，那么对于m22 ，g h d ( n m ) 也存在。 证明：设x 是一个m ( 2 ) 元集，磊为模礼的剩余加群，y = x 磊。 由于当 2 时，必存在一个( ，2 ，1 ) 一b i b d ，所以我们可以设( x ，) 为一 个( m ，2 ，1 ) 一b i b d 。我们任取中的一个区组a ，贝l j l a i = 2 ，由于存在g h d ( n 2 ) ，我们可以设它的点集为ax 磊，区组集为玖。令留= u 。玩容 易验证，( y ，留) 就是一个g h d ( n n ) 。 引理3 3 ：如果存在g h d ( n 3 ) ，g h d ( r $ 4 ) ，g h d ( n 5 ) ，g h d ( n 6 ) 及g h d ( n 8 ) ，那么对于m23 ，g h p ( n ”) 也存在。 证明：设x 是m 3 元的集合，k = 3 ，4 ，5 ，6 ，8 ，磊为模n 的剩余加 群，y = x 磊，根据引理2 1 可设( x ，) 为p b d ( m ，k ) ，任取中的一个 区组a ，其中i a i = k 3 ，4 ，5 ，6 ，8 ，又由于g h d ( n 3 ) ，g h d ( n 4 ) ，g h d ( n 5 ) ，g h d ( n 6 ) y a c h d ( n 8 ) ，也就是一定存在g h d ( n ) ，设点集 为a 磊，区组为j 玖，令留= u a 一玖，易证( y ，劈) 是个g 一日d ( n ”) 。 引理3 4 ：如果存在g h d ( n 3 ) g t g h d ( n 5 ) ，那么对于m 1 ，g h p ( n 2 ”+ 1 ) 也存在。 证明：类似引理3 3 的证明。 定理3 1 ：对于给定的图g 及任意正整数h ，m ，若同时存在g 一 日d ( 危”) 和g g d ( h + u ) ( 其中叫= 0 或1 ) ，则存在g g d ( h m + u ) 。 南京帅范人o 硕l 辱 奇沦艾 证明：设( x ，劈) 是一个g h d ( h ”) ，其中x =u 咒，设点 集w = o o ) ( 当u = 1 时) 或w = 0 ( 当u = o 时) ，且w n x = 0 ，在 每个集合咒u w j = 嵌入设计g g d ( h + u ) ，其区组集为玩，令= ( ug 暖) u 劈，则u w ，) 是所求g 二- g d ( h m + u ) 。 1 6 筇4 章? 、j 仃向日罔 第4 章六点有向9 图 对于以下的构造中我们将其区组记为：( o l ，n 2 ，0 3 ，啦，口5 ，n 6 ) 如2 2 节 中的图g l 中，这个区组所含有的有向边 有：( 啦，0 1 ) 。( 0 2 ，a 3 ) ，( 0 3 ，0 4 ) ，( 钆，a s ) ，( 口5 ，) ，( ，0 1 ) ，( 舢，n 1 ) ( 其中( n 4 ，口1 ) 为 图g 1 的弦) 。 4 1i 型的六点有向0 图 我们可以得到如下的构造步骤： 1 构造口= 7 ，8 时( 口，g ，1 ) 一g di = 1 ，2 ，1 2 。 2 构造& 一日d ( 7 2 ) ，由引理3 2 可得q 一日d ( p ) m 2 也存在。 3 由构造1 ，2 及定理3 1 可得存在( 口，g ，1 ) 一g d ，其中u 三0 ，1 ( r o o d7 ) 口7i = 1 ，2 ，1 2 。 定理4 1 1 ：对于l = 1 ，2 ，1 2 ，口；7 ，8 ，存在( ，g ，1 ) 一g d 。 证明：当口= 7 时，设x = 磊历u 。 2 而且当 = 8 时，设x = 磊贝定 义如下基区组： 嘶：( 2 00 0l o2 10 0 0 1 ) 砺：( 2 0o o l o2 1o 。0 1 ) 蹈：( 0 0 l o0 12 02 1o 。) 顽：( 2 0 i l l oo o2 1o o ) 磁：( o o 0 1l o2 12 0 ) 蹈：( 2 00 1 l o0 0o 。2 1 ) 砺：( 0 0 1 1o 。l o2 12 0 ) 蛹：( 2 00 1 l o0 0o 。2 t ) 媚：( 1 12 00 0 l o0 1o 。) 奶o ：( 2 0 1 10 a2 10 0 ) 崩l ：( 1 0 1 l 0 1 ) ( r o o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) ( m o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) ( r o o d ( 3 ，2 ) ) 一1 7 留1 ：( 0 16 257 ) ( r o o d8 ) 留2 ：( 052 67 1 ) ( m o d8 ) g 阮：( 2 150 63 ) ( r o o d8 ) 现：( 6 2 10 53 ) ( r o o d8 ) 既：( 4750 12 ) ( r o o d8 ) ：( 457 036 ) ( r o o d8 ) 6 爵：( 6 4 1032 ) ( m o d8 ) 编：( 4570 36 ) ( r o o d8 ) 骗：( 67 4 0 25 ) ( m o d8 ) 玩o ：( 465 0 72 ) ( r o o d8 ) 爰致i ：( 637 0 14 ) ( r o o d8 ) 南片：师范人予五：j 上学他沦史 斫2 ：( 1 0 0 02 0l l0 0 0 1 ) ( r o o d ( 3 ，2 ) ) 留1 2 ：( 436 0 25 ) ( m o d8 ) 容易验证：( x ，磁) 为( 7 ，g ，1 ) 一g d ，( x ，觋) 为( 8 ，g t ，1 ) 一g d ，i = 1 ，2 ，一，1 2 定理4 1 2 ：对于i = 1 ，2 ，1 2 ，存在 一日_ d ( 7 2 ) 证明：设x = 历z 2 ，则定义如下基区组： 硝：( o a6 05 12 04 10 0 ) ( m o d ( 7 ，2 ) ) 。晒：( 0 12 04 t4 03 16 0 ) ( r o o d ( 7 ，2 ) ) 妫：( 1 15 05 1 4 12 0 ) ( r o o d ( 7 ，2 ) ) 确：( 4 12 02 to oi l5 0 ) ( r o o d ( 7 ，2 ) ) 磁：( 5 14 01 1o o0 x2 0 ) ( m o d ( 7 ，2 ) ) 蹈：( 2 x2 05 1o o6 13 0 ) ( r o o d ( 7 ，2 ) ) 砺：( 5 14 03 l0 02 12 0 ) ( r o o d ( 7 ，2 ) ) 磁：( 2 t2 05 10 04 13 0 ) ( m o d ( 7 ，2 ) ) 妫：( 6 x6 04 10 01 1 钿) ( r o o d ( 7 ，2 ) ) 西o ：( 1 13 0 3 10 05 14 0 ) ( r o o d ( 7 ，2 ) ) 斫1 ：( 6 14 0 0 10 03 15 0 ) ( r o o d ( 7 ，2 ) ) 磁2 ：( 1 ll o3 x0 06 13 0 ) ( r o o d ( 7 ，2 ) ) 容易验证：( x ，磁) 为 一- d ( 7 2 ) ，i = 1 ，2 ，1 2 由定理4 1 1 ，定理4 1 2 及定理3 1 知定理2 2 1 得证。 4 2 型的六点有向0 图 我们可以得到如下的构造步骤： 1 构造 = 7 ，8 时( ，凰，1 ) 一g d ( i = 1 ，2 ，3 2 ) 。 2 构造皿一日d ( 7 3 ) 及凰一h d ( 7 5 ) ( i = 1 ，2 ，3 2 ) ，由引理3 4 可得凰一 日d ( 7 2 m + 1 ) 价2 也存在。 3由构造l ，2 及定理3 1 可得存在( 口，风，1 ) 一g d ，其中口兰7 ，8 ( r o o d1 4 ) ，( i = 1 ，2 ，3 2 ) 。 定理4 2 h 对于l = 1 ，2 ，3 2 ，u = 7 ，8 存在( ，凰，1 ) 一g d 证明：当t ，= 7 时，设x = 磊历u 而且当= 8 时，设x = z 8 _ 除风，胁，胁，日l i 则定义如下基区组： 嘶：( 0 01 1l o2 1o o2 0 ) ( r o o d ( 3 ，2 ) ) 留l ：( 670 251 ) ( r o o d8 ) 奶：( 0 0l o1 1o o0 12 0 ) ( r o o d ( 3 ，2 ) ) 留1 ：( 610342 ) ( r o o d8 ) 一1 8 一 砺：( 1 0 l ao o2 0o 。2 1 ) ( r o o d ( 3 ，2 ) ) 确：( o o2 x l oo 。i t0 1 ) ( r o o d ( 3 ，2 ) ) 磁：( o o i t l o2 to 。2 0 ) ( r o o d ( 3 ，2 ) ) 繇：( 1 0 1 1o o2 0o 。0 1 ) ( r o o d ( 3 ，2 ) ) 砺：( 0 0 1 i l oo l 2 0 ) ( m o d ( 3 ，2 ) ) 确：( o o0 1 l oo o2 t1 1 ) ( r o o d ( 3 ，2 ) ) d g ：( t 0 1 1o o2 0o o o x ) ( r o o d ( 3 ，2 ) ) 硝o ：( 2 11 12 0o 。l oo o ) ( r o o d ( 3 ，2 ) ) 新1 ：( 1 0 l xo o2 0o 。2 1 ) ( m o d ( 3 ，2 ) ) 研2 ：( 0 0 1 11 0 0 1o 。2 0 ) ( r o o d ( 3 ，2 ) ) 嘶3 - ( o o1 1 l o2 1o 。2 0 ) ( r o o d ( 3 ，2 ) ) 嘶4 - * ( 1 0l lo o2 00 0 2 1 ) ( r o o d ( 3 ，2 ) ) 新5 ：( 0 0 1 1 i o2 1o 。2 0 ) ( m o d ( 3 ，2 ) ) 奶6 ：( 1 0 1 1o o2 0o 0 0 1 ) ( r o o d ( 3 ，2 ) ) 研7 ：( o o1 1 l oo lo 。2 0 ) ( m o d ( 3 ，2 ) ) 顽8 ：( o o2 1 l oo o1 1o t ) ( m o d ( 3 ，2 ) ) 斫9 ：( o o1 1l o2 1o 。2 0 ) ( r o o d ( 3 ，2 ) ) 砺o ：( 1 01 1o o2 00 0 0 1 ) ( r o o d ( 3 ，2 ) ) 奶l ：( 1 01 1o o2 00 0 0 1 ) ( r o o d ( 3 ，2 ) ) 蛹2 ：( o o1 1l o0 10 0 2 0 ) ( r o o d ( 3 ，2 ) ) 奶3 ：( o o1 1l oo ao o2 0 ) ( r o o d ( 3 ，2 ) ) 奶4 ：( o oo x l oo o1 12 1 ) ( r o o d ( 3 ，2 ) ) 奶5 ：( o ol x i o2 1o o2 0 ) ( r o o d ( 3 ，2 ) ) 奶6 ：( 1 01 1o o2 0o o0 1 ) ( r o o d ( 3 ，2 ) ) 磁7 ：( o o1 1 l o2 ao o2 0 ) ( r o o d ( 3 ，2 ) ) 蚝：( 1 01 1o o2 0o o0 1 ) ( r o o d ( 3 ，2 ) ) 幽：( o o1 1l o2 1o o2 0 ) ( r o o d ( 3 ，2 ) ) 砺o ：( 1 0 1 1o o2 0o o2 1 ) ( r o o d ( 3 ，2 ) ) 砺l ：( 0 0 1 1l o2 ao o2 0 ) ( r o o d ( 3 ，2 ) ) 一1 9 一 编：( 67 025 1 ) ( r o o d8 ) 玩：( 65034 2 ) ( r o o d8 ) 留6 ：( 230 57 6 ) ( m o d8 ) 编：( 27 0 4 13 ) ( r o o d8 ) 留l o ：( 230 7 16 ) ( r o o d8 ) 留1 2 ：( 230 7 l5 ) ( r o o d8 ) 留1 3 ：( 26 05 41 ) ( r o o d8 ) 舅1 4 ：( 6 4 0 325 ) ( r o o d8 ) 劈1 5 ：( 6 10 752 ) ( m o d8 ) 留1 6 ：( 450 346 ) ( m o d8 ) 留1 7 ：( 450 236 ) ( m o d8 ) 留1 8 ：( 6 4 07 25 ) ( r o o d8 ) 玩9 ：( 450 l36 ) ( r o o d8 ) 留2 0 ：( 450 l36 ) ( r o o d8 ) 锄1 ：( 2 l05 36 ) ( m o d8 ) 舅t z 2 ：( 6 4 07 23 ) ( r o o d8 ) j 目2 3 ：( 2 l0 637 ) ( m o d8 ) 历2 4 ：( 6 4 07 25 ) ( r o o d8 ) g 吃5 ：( 230 4 65 ) ( r o o d8 ) - 留2 6 ：( 6l03 42 ) ( r o o d8 ) 现7 ：( 650 731 ) ( r o o d8 ) 毋2 8 ：( 2 6 03 41 ) ( r o o d8 ) 踢9 ：( 2 50 l76 ) ( m o d8 ) ：( 250 431 ) ( r o o d8 ) g 既1 ：( 6 l0 375 ) ( r o o d8 ) 确2 ：( o o1 1 l o2 x0 1o 。) ( m o d ( 3 ，2 ) ) 留3 2 ：( 05 23 71 ) ( m o d8 ) 设x = 历x 忍 既：( 3 03 1l o0 01 10 1 ) ( r o o d ( 4 ，2 ) ) 锄：0 10 0l o2 11 1 ) ( r o o d ( 4 ，2 ) ) 嘞：( 2 02 10 0l o0 x1 1 ) ( r o o d ( 4 ，2 ) ) 留1 1 ：( 2 02 10 01 0 0 13 x ) ( r o o d ( 4 ，2 ) ) 容易验证：，磁) 为( 7 ，凰，1 ) 一g d ，( x ，锄) 为( 8 ，1 ) 一g d ，i = 1 ，2 ，3 2 定理4 2 2 ：对于，i = 1 ，2 ，3 2 ， 证明：对于7 3 ：设x = 历z 3 ； 基区组； 存在甄一日d ( 7 3 ) ，凰一h d ( 7 5 ) 对于7 5 ：设x ：历磊测给出下面的 嘶：( 1 15 00 20 04 12 0 ) ( 1 25 00 10 04 22 0 ) ( r o o d ( 7 ，3 ) ) 劈l ：( i t5 00 30 14 32 0 ) ( 1 25 0 0 10 24 12 0 ) ( 1 35 00 40 34 42 0 ) ( 1 45 00 20 44 2 2 0 ) ( r o o d ( 7 ，5 ) ) 注：下面的基区组中磁，玩的第二座标分别与西，留1 的第二座标相 同，的第一座标与锄的第一座标相同i = 1 ，2 ，3 6 。 砺，锄：( 63 022 1 ) 蛹，绲：( 130 0 4 2 ) 确，历4 ：( 6302 乏1 ) 磁，玩：( 6 6 035 1 ) 蛹，疏：( 1306 44 ) 奶，厮：( 6 60 25 1 ) 玩，绲：( 2 4 0 655 ) 确，为：( 6 6 025 1 ) 斫o ，留1 0 ：( 2 4 06 65 ) 新l ，霸1 ：( 6 6 0 253 ) 秭2 ，留1 2 ：( 2 4 0 663 ) 硝3 ，留1 3 ：( 450 0 21 ) 研4 ，留1 4 ( 130 6 64 ) 确5 ，留1 5 ：( 620 034 ) 研6 ，留1 6 ：( 46 0 355 ) 确7 ，留1 7 ：( 130 4 42 ) 研8 ，留1 8 ：( 130 064 ) 研9 ，历1 9 ：( 0 4 06 l2 ) 奶o ，现o ：( 46 0335 ) 奶1 ，现1 ：( 250 0 43 ) 奶2 ，囊：( 13 0 0 52 ) 锄，踢3 ：( 250 0 43 ) 吮，锄4 ：( 130 054 ) 砺5 ，纥：( 2500 63 ) 奶6 ，玩6 ：( 2 4 06 33 ) 砺7 ，锄7 ：( 40 0 6 12 ) 砺8 ，受 鹳：( 6 20 0 14 ) 奶9 ，玩9 ：( 250 0 43 ) 粕，统o ：( 2 4 0 6 63 ) 硒1 ，编1 ：( 2 4 0 6 65 ) 砺2 ，留3 2 ：( 0 42 36o ) 容易验证：僻，砺) 为凰一h d ( 7 3 ) ，识) 为玩一- d ( 7 5 ) ，i = 1 ，2 ，一，3 2 由定理4 2 1 ，定理4 2 2 及定理3 1 知定理2 2 2 得证。 一2 0 第5 章l 点白向日罔 第5 章七点有向0 图 我们可以得到如下的构造步骤： 1 构造f = 8 ，9 ，1 6 ，1 7 时( 口，谚，1 ) 一g d ( i = 1 ，2 ，8 ) 。 2 构造四一h d ( 8 3 ) ，g ；一日d ( 8 4 ) ，g ：一日d ( 8 5 ) ，g ：一h d ( 8 6 ) 及g ：一 日d ( 8 8 ) ( i = 1 ，2 ，8 ) ，由引理3 3n - i 得g ：一h d ( 8 ”) m 3 也存在。 3由构造1 ，2 及定理3 1 可得存在( ，g ：，1 ) 一g d ，其中口三0 ，1 ( m o d8 ) 8 ( i = 1 ，2 ，8 ) 。 定理5 1 ：对于l = 1 ，2 ，8 ，仃= 8 ，9 存在( u ，g ：，1 ) 一g d 证明：t ，= 8 时设x = 历u f o o ) ，钉= 9 时x = 历，则定义如下基区组： d l ：( 2 ，3 ，6 ，4 ，0 ，o 。，1 ) ( m o d7 ) b 1 ：( 0 ，1 ，3 ，6 ，2 ，4 ，5 ) ( r o o d9 ) 奶：5 ，2 ，3 ，0 ，o o ，1 ，6 ) ( r o o d7 ) 锄：( 0 ，4 ，5 ，8 ，6 ，1 ，3 ) ( r o o d9 ) 妫：( 0 ，o 。，1 ，3 ，2 ，6 ，5 ) ( r o o d7 ) 玩：( 0 ，1 ，5 ，4 ，2 ，8 ，6 ) ( r o o d9 ) 确：( 3 ，1 ，o 。，0 ，5 ，6 ，2 ) ( r o o d7 ) 级：( 0 ，3 ，5 ，2 ，7 ，6 ，1 ) ( m o d9 ) 磁：( 2 ，1 ，o o ，0 ，3 ，4 ，6 ) ( r o o d7 ) 玩：( 0 ，7 ，4 ，6 ，2 ，3 ，8 ) ( r o o d9 ) 蕊：( 2 ，1 ，o o ，0 ，3 ，5 ，6 ) ( r o o d7 ) 玩：( 0 ，8 ，1 ，2 ，7 ，3 ，6 ) ( m o d9 ) 砺：( 0 ，o 。，l ，5 ，6 ，4 ，3 ) ( r o o d7 ) 锄：( 0 ，3 ，2 ，8 ，1 ，6 ，4 ) ( r o o d9 ) 蛹：( 0 ，o 。，1 ，5 ，4 ，2 ，6 ) ( r o o d7 ) 绲：( 0 ，6 ，8 ，2 ，1 ，5 ，4 ) ( r o o d9 ) 容易验证：( x ，磁) 为( 8 ，g ，1 ) 一g d ，玩) 为( 9 ，g ，1 ) 一g di = 1 ，2 ，8 定理5 2 ：对于l = 1 ，2 ，8 ，口= 1 6 ，1 7 存在( 口，g ：，1 ) 一g d 。 证明：钉= 1 6 时设x = 而5 u o 。) ，v = 1 7 时x = z 1 7 ，则定义如下基区 2 l 一 组： 研：( 0 ，o 。，1 ，2 ，5 ，3 ，7 ) ( r o o d1 5 ) ( 0 ，1 ，6 ，1 1 ，2 ，9 ，3 ) ( r a o d1 5 ) 留1 ：( 0 ，l ，3 ，4 ，6 ，2 ，5 ) ( r o o d1 7 ) ( 0 ：9 ，4 ，1 0 ，2 ，1 3 ，3 ) ( r o o d1 7 ) 奶：( 2 ，0 ，。o ，1 ，4 ，5 ，9 ) ( r o o d1 5 ) ( o ，4 ，1 ，6 ，1 3 ，7 ) ( r o o d1 5 ) 锄：( 0 ，1 ，2 ，4 ，7 ，3 ，8 ) ( r o o d1 7 ) ( 0 ，5 ，2 ，8 ，1 ，1 2 ，1 0 ) ( r o o d1 7 ) 秭：( o ，o o ，1 ，2 ，4 ，5 ，8 ) ( r o o d1 5 ) ( 0 ，5 ，l ，1 1 ，3 ，9 ，6 ) ( r o o d1 5 ) 玩：( 0 ，1 ，3 ，2 ，5 ，8 ，1 2 ) ( r o o d1 7 ) ( o ，6 ，1 6 ，1 0 ，1 ，9 ，4 ) ( r o o d1 7 ) 崩：( 0 ，0 0 ，1 ，2 ，3 ，5 ，8 ) ( m o d1 5 ) ( 0 ，5 ，1 ，1 1 ，2 ，9 ，3 ) ( r o o d1 5 ) 觋：( 0 ，1 ，3 ，2 ，5 ，8 ，1 2 ) ( r o o d1 7 ) ( 0 ，6 ，1 6 ，1 0 ，1 ，9 ，4 ) ( m o d1 7 ) 蛹：( 0 ，o o ，1 ，2 ，4 ，3 ，6 ) ( r o o d1 5 ) ( 0 ，3 ，l o ，6 ，1 ，9 ，4 ) ( r o o d1 5 ) 编：( 0 ，1 ，3 ，2 ，5 ，9 ，1 2 ) ( r o o d1 7 ) ( 0 ，5 。1 ，1 0 ，3 ，1 4 ，6 ) ( m o d1 7 ) 蕊：( 0 ，o o ，1 ，2 ，4 ，5 ，8 ) ( r o o d1 5 ) ( 0 ，5 ，1 ，1 1 ，3 ，9 ，6 ) ( m o o d1 5 ) 甄：( 0 ，1 ，3 ，2 ，5 ，8 ，4 ) ( m o d1 7 ) ( 0 ，5 ，1 3 ，8 ，1 4 ，3 ，1 0 ) ( m o d1 7 ) 嘶：( o ，o 。，1 ，2 ，4 ，3 ，6 ) ( r o o d1 5 ) ( o ，4 ，1 ，1 0 ，2 ，1 2 ，8 ) ( r o o d1 5 ) 留7 ：( 0 ，1 ，3 ，2 ，5 ，9 ，1 4 ) ( r o o d1 7 ) ( o ，6 ，2 ，1 0 ，3 ，1 4 ，9 ) ( r o o d1 7 ) 蛹：( 0 ，0 0 ，1 ，2 ，4 ，3 ，6 ) ( r o o d1 5 ) ( o ，3 ，9 ，5 ，1 0 ，1 4 ，7 ) ( r o o d1 5 ) 留1 ：( 0 e l ，3 ，2 ，5 ，9 ，4 ) ( r o o d1 7 ) ( 0 ，6 ，1 3 ，7 ，2 ，1 l ，3 ) ( r o o d1 7 ) 容易验证：( x ，磁) 为( 1 6 ，研，1 ) 一g d ，玩) 为( 1 7 ，g ，1 ) 一g d