（运筹学与控制论专业论文）关于六点八边图的图设计.pdf

果。 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均己在论文中作了声明并表示了 谢意。 作者签名 日期 学位论文使用授权声明 蛰塑! 翌! 竺：丝2 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版；有权将学位论文用于非赢利目的的少量复制井允许论文进 入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行检 索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密 后适用本规定。 作者签名：壶i 数! 日 期：么尘生竺2 摘要 摘要 设j 0 是个t ，点的完全图。g 为一个不含孤立点的简单图的一个g - 设 计，常记为( u ，g ，1 ) g d ，是指一个二元组( x ，8 ) ，其中x 为的顶点集，b 是 墨，的一些子图( 亦称为区组) 构成的集合，使得每一个区组与g 同构。且噩，的 任何一条边恰在8 的一个区组中出现1 7 个六点八边图( 不含孤立点的简单图) 中，文章1 解决了三个图g l ，g 2 和g 3 的图设计存在性问题本文讨论了其余1 4 个六点八边图的图设计存在问题，除了第1 6 和1 7 个图外基本解决了另外1 2 个图 的图设计存在性问题 关键词t 图设计；带洞图设计；p b d 一闭集 a b s t r a c t a b s t r a c t 2 l e tk ”b eac o m p l e t eg r a p hw i t huv e r t i c e s ，a n dgb eas i m p l es u b g r a p hw i t h o u t i s o l a t ev e r t i c e so f 噩，ag d e s i g no f 甄，d e n o t e db y ( u ，g ，1 ) 一g d ，i sap a i r ( x ，b ) ， w h e r exi st h ev e r t e xs e to f 凰，a n d 口i st h ec o l l e c t i o no fs u b g r a p h s ( c a l l e db l o c k s ) o f k m s u c ht h a te a c hb l o c ki si s o m o r p h i ct og ia n da n ye d g ei nk uo c c u r si ne x a c t l yo n e b l o c k t h e r ea r es e v e n t e e nn o n i s o m o r p h i cg r a p h s ，e a c ho fw h i c hh a ss i xv e r t i c e sa n d e i g h te d g e s ，i np a p e r 1 w eh a ds o l v e dt h ee x i s t e n c ep r o b l e m so f ( u ，g t ，1 ) 一g df o r i ：1 ，2 ，3 i nt h i sp a p e rw ew i l ld i s c u s st h ee x i s t e n c ep r o b l e m so f ( ，g i ，1 ) 一g df o r i = 4 ，1 7 ，a n dw ea l m o s ts o l v et h ee x i s t e n c ep r o b l e m so fg - d e s i g nf o rt h er e m a i n i n g f o u r t e e ng r a p h se x c e p tf o rg 1 sa n dg 1 7 k e y w o r d s ：g r a p hd e s i g n ，h o l e yg r a p hd e s i g n p b d c l o s e ds e t 前言 前言 3 在1 8 5 0 年k i r k m a n 提出下面一个阅题，一位教师每天带领他班上的1 5 名女学 生去散步，他把这些女生按3 人一组分成5 组，这样每位女生有2 名同伴问能否 作出一个连续散步七天的计划，使得没有一个女生和她的同学在一个三人组中的 次数多于一次? 这个问题的解是在1 5 名女生组成的( 无序) 三人组中找到3 5 组， 使得每一对女生同在一个且仅在一个三人组中。此外，我们可以把3 5 个三入组分 成7 批。每批有5 个三人组( 一批对应7 天中的一天) ，而且每名女生恰好在每一 批的一个三人组中 我们知道k k k m a n 女生问题存在解的前提是；1 5 名女生构成的集台中一定存 在3 5 个三人组。使得每一对女生同在一个且仅在一个三人组中现在如果我们把 1 5 名女生看作具有1 5 个点的集合中的点，每一个三人组看作这个点集的一个三 元子集甚至更一般地，有以下定义 定义i 设u 是正整数。称( x ，8 ) 为一个 阶s t e i n e r 三元系，其中x 是一个”元 点集，踺x 的一个子集( 称为区组) 簇，满足如下两个条件t i ) 对任意b 8 ，有1 日1 = 3 ； i i ) x 中任意两个不同的元素在恰在一个区组中出现 若记b = 吲，根据定义显然有b = u ( u i ) 8 在k i r k m a n 问题中u = 1 5 ，b = 3 5 下面我们来看一个例子t 例1 ：设x = z v ， 口= “o ，i ，3 ) ， 1 ，2 ，q ， 2 ，3 ，5 ) ，n4 ，6 4 ，5 ，o ) ， 5 ，6 ，l ， 6 ，0 ，2 ， 则( x ，日) 是一个7 阶s t e i n e r 三元系 定义2 设g 是一个有限加法群，最，曰2 ，丑k 是8 孛的部分区组。如果满足。 b = u 翌l 鼠+ 9 ，口g ) 则称每一个鼠“= 1 ，2 ，m ) 为初始区组， 例2 ：例i 中的7 阶s t e i n e r - - 舔 o ，i ，3 就是一个初始区组，因为日= u 蚱御( 吼1 + 9 ，3 + 9 ) 为了方便我们把舀可以简写为； 舀t 0 ，i ，3 )( m o d7 ) 前言 随着对s t e i n e r 三元系研究的深入 的概念 4 人们开始考虑i b i = k 情形，从而有了下面 定义3 设u ，k ，a 是正整数，称( x ，日) 为一个( k ，a ；u ) 平衡不完全区组设计( 记作 b ( k ， ；u ) ) ，其中x 是一个”元点集。8 是x 的一个子集( 称为区组) 簇，满足如 下两个条件： i ) 对任意b 8 ，有l b = k ； i i ) x 中任意两个不同的元素在恰在 个区组中出现 根据定义我们得到下面的定理 定理1 若b ( k ，凡u ) 存在，则 一1 ) - - 0 ( r o o d ( k - 1 ) ) a v ( v 一1 ) = - 0 ( r o o d ( 女- 1 ) ) 在平衡不完全区组设计s ( k ，a ； ) 中每一个区组实际上是一个女个点的完全图 h e l l 和r o s a 用任意图结构代替区组( 完全图) 从而推广了区组设计的概念，这些 设计就称为图设计( g 设计) 在这篇文章中，我们讨论的图都是有限、无向、不 含孤立点的简单图与图和设计相关的术语，读者可参考著作【2 】【3 】 一个a 重”点的完全图，记为a 致，。是一个完全图，其任意两个不同点z ，y 之 间均恰有 条边( z ，y ) 相连当 = 1 时，我们简记为凰 定义4 设g 是一个不含孤立点的筒单图，虬的一个g 设计，记为( v ，g ，1 ) 一 g d ，是指一个二元组( x ，8 ) ，x 为的顶点集。8 为噩，的一些子图( 称为区 组) 构成的集合，使得任一区组均与图g 同构，且的任意一条边恰在b 的一个 区组中出现 例3 ：构造一个( 7 ，g ，1 ) g d 。其中g 如图1 所示 入 b 二c 图1 构造( 7 ，g ，1 ) 一g d 也就是把硒分解成7 个三角形，使碍硒的任意一条边 恰在一个三角形中出现不妨取x = o ，1 ，2 ，3 ，4 ，5 ，6 ，则可分解成如下： ，厶。厶。厶。厶。厶。厶，。厶。 若记为：b = “o ，1 ，3 ) ， 1 ，2 ，4 ) ， 2 ，3 ，5 ) ， 3 ，4 ，6 ， 4 i5 ，o ) ， 5 ，6 1 ) ， 6 ，0 ，2 ) ) ， 前言 而这正是例1 的结果 从例3 中我们还知道t 图分解某些问题可以转化为图设计问题 构造图设计中起重要作用的一个概念 5 下面是在递推 定义5 给定一个图g ，若。可拆分成若干个与g 同构的边不交的 子图的并，则称( x ，9 ，且) 为带洞g 设计，其中x 为匠。，。，m 的点集，g = x 1 ，葛。) ( 墨亦称为洞) ，a 为与g 同构的边不交子图( 亦称为区组) 构 成的集合，( n - ，n 2 ，n 。) 称为带洞设计的组型为了方便，也可用指数形式记为 ( n l h ，n 2 k 。，f l 。m ) 。即n 1 出现k 1 次，n 。出k 现次这样。一个带洞g 设 计常记为g h d ( n i k l ，b 2 b ，n m m ) 特别地，一个g h d ( i 一。u 1 ) 也称为不完全的g 设计，记为( v , w ；g ，1 ) i d 易 知，一个( u ，g ，1 ) 一g d 也是一个g h d ( i ”) 或是一个( u ，u ；g ，1 ) 一i d ，其中u = 0 或i 例4 ：构造一个( 7 ，3 ；g ，1 ) 一i d ，其中g 如图1 所示我们记g 为；( o ，6 ，c ) 设x = f l ，2 ，3 , 4 u f0 0 1 ，0 0 2 ，3 j ，夕= “l ，f 2 ) ， 3 j ，( 4 ，( o o i ，0 0 2 ，0 0 3j ) 令 a = ( ( 1 ，2 ，0 0 1 ) ，( 1 ，3 ，0 0 2 ) ，( 1 ，4 ，0 0 3 ) ，( 2 ，4 ，0 0 2 ) ，( 2 ，3 ，。3 ) ，( 3 ，4 ，0 0 1 ) ) ， 则( x ，9 ，4 ) 是一个( 7 ，3 ；g ，1 ) 一i d j c b e r m o n d ( i 9 8 0 ) 等在文章【4 】中首先给出了g 一设计存在的必要条件，即 定理2 若图g 有_ j 个顶点，e 条边，且的各顶点度的最大公因子为d 时， ( u ，g ，1 ) 一g d 存在的必要条件是t ( i ) 七， ( i i ) 一1 ) 0 ( r o o d2 e ) ， ( i i i ) t p 一1 0 ( m o dd ) 关于各种图的g 设计的存在性曾经引起很多数学家的兴趣，下面的这些结果可以 参考文章【4 】1 【5 】 定理3 对于图的顶点数女s4 ，( u ，g ，1 ) 一g d 存在的必要条件也是充分的 定理4 对于图的顶点数 = 5 ，除了一些子图( 见附录表1 ) 外。( u ，g ，1 ) 一g d 存在的必要条件也是充分的 对于= 6 情形，殷剑兴等( 1 9 9 8 ) 首先在文章【6 】中研究了g 设计的存在性， 并给出了当3 s e ( g ) 6 时的存在谱对于k = 6 且e ( g ) = 7 情形，田子红和康庆 前言 6 德( 2 0 0 2 ) 在文章( 7 】中讨论了( u ，g ，a ) 一g d 的存在性，其中g = k 2 , 3 + e 。这一问 题的完全解是由徐爱庆( 2 0 0 3 ) 在文章【8 和文章 9 】中给出的。因此，我们有下面 的定理 定理5 对于图的边数e ( v ) s 7 和顶点数女= 6 ，除了一些子图( 见附录表2 ) 外， ( ，g ，1 ) g d 存在的必要条件也是充分的。 当k = 6 且e ( g ) = 8 时，1 7 个图( 不含孤立点的简单图) 中，文章 1 】已讨论 了3 个图g l ，g 2 和g 3 的图设计的存在性。在本文中我们将讨论其余图的图设计 存在问题根据图的结构的不同，我们把其余1 4 个图分为4 类。分别是第一类图 g 。0 = 4 ，5 ) ，第二类图g 6 第三类图g 。( i = 7 ，9 ，1 5 ) ，第四类图g 1 6 ，g 1 7 。 本文得到如下结论： i ) ( 第一类图) g i ，1 ) 一c d ( i = 4 ，5 ) 存在的必要条件”；0 ，lr o o d ( 1 6 ) 且”21 6 也 是充分的。 j i ) ( 第二类图) ( ，g 6 ，1 ) 一g d 存在的必要条件ui l r o o d ( 1 6 ) ，且 21 7 也是充分 的 i i i ) ( 第三类图) ( u ，g ，1 ) 一g d ( i = 7 ，8 ，：1 5 ) 存在的必要条件u ；0 ，1m o d ( 1 6 ) 且 ”1 6 、除u = 3 2 可能不存在外也是充分的。 i v ) ( 第四类图) 当 = 1 6 ，1 7 ，3 2 ，3 3 ，4 8 ，4 9 时，( u ，g 。1 ) 一g d ( i = 1 6 ，1 7 ) 存在。 毫唿哩 ed g 1 fd g 2 第一类图： ab f e g 4 ed g 3 前言 第：类图 abc g 6 第三类图 警伞图 早f e d 蛔 e 丛dcb g 1 0g 1 1 g 1 2 翊fab 田efa 幻abc g 1 3 g 1 4 第四类图 g 1 5 翘茧 fe g 1 6 abc g 1 7 7 第一章递推构造方法 第一章递推构造方法 8 所谓递推构造方法是指利用一些已知的( 往往是阶数较小的) 设计来构造一些 新的( 往往是阶效较大的) 设计，从而获得一些具有新的参数的设计的方法本章 将引入本文所用递推方法以及与其相关的定义、引理、定理的证明 1 1基本定义 首先我们给出在递推构造方法中一个重要的概念一成对平衡设计( p b d ) 定义1 1 设k 是个正整数集合，称( 矿，8 ) 是一个成对平衡设计，记为p b d v ，k 】 ，其中y 是有u 个点的有限集合，且是y 的一个子集( 区组) 簇，且满足下列两 个条件： ( i ) 如果b 8 ，则l b i k ； ( i i ) v 中任意两个不同的元素恰在8 的一个区组中出现 由上述定义可见，成对平衡设计实际上是平衡不完全区组设计定义中的区组等 长要求的一个放松，而b ( k ，l ；u ) 则是p b d v ，k 的当k = k ) 时的特殊情形 定义1 , 2 设s 是一个正整数集合，若p b d v ，司存在有 属于集合s ，则称s 是p b d 一闭集 定义1 3 设k 是一个正整数集合，且有b ( 耳) - 扣l3 p b d v ，k 】) ，则p b d 闭集 b ( k ) 称为k 的闭包 下面再引入可分组设计( g d d ) 的概念 定义1 4 设u ， 为正整数。耳与m 为给定的正整数集称( x ，口，) 为可分组设 计，记为g d 瞄， ，m ；u 】，其中x 是外点的集合，9 是x 的一个划分即把x 划 分成n 个互不相交的子集g ( 称为组) 。4 是x 的一个子集( 区组) 簇，满足下列 五个条件t i ) l x l = u i j ) 盆f ：g 譬 c m ， i i i ) 1 4 l ：b ea ) ck ， i v ) 对每个g 9 和每个b a ，都有l g n b i s l ， v ) 不同组中的任意两个元索恰在的 个区组中出现 第一章递推构造方法 9 特别地，如果g 中大小为n 组出现k ，次，大小为n 。组出k 现次，这 时我们称组型为( n l h ，r ；2 b ，n 。m ) 的g d d 如果k = k 且 = 1 ，我们将 g d k ， ，m ；u l 简记为k g d d p b d 和g d d 之阅有密切的关系事实上p b d 可以看成是g d d 的特殊情形。 当划分蛋中的各个组都是x 的单元素予集时，x 中任意两个不同元素必定属于 不同的组，此时的g d d 就是一个p b d 下面引入在递推构造图设计中起重要作用的两个概念 定义1 5 设。n 是一个具有顶点集x = u l k 墨的完全多部图，满足以 下两个条件t j ) x d lsi h ) 是两两互不相交的集合，其中i 墨i - - - n l 一= 垒1 i i ) 若其边集为e ，对任意z 墨，局，j ，边 q 订e ，而当i = j 时， 边 z ，) 车e 定义1 , f i 给定一个图g ，若。可拆分成若干个与g 同构的边不交的 子图的并，则称( x ，蛋，一4 ) 为带洞g 设计，其中x 为。，。的点集，昏= x l ，托，x 。 ( x 亦称为洞) ， 为与g 同构的边不交子图( 亦称为区组) 构 成的集合，( n t ，啦，n 。) 称为带河设计的组型为了方便，也可用指数形式记为 ( n l k ，n 2 h ，n 。m ) ，即n l 出现1 次，n 。出k 现次这样，一个带洞g 设 计常记为g h d ( n i k i ，铆h ，n m k m ) 特别地，一个g h d ( i ”“w 1 ) 也称为不完全的g 一设计，记为( v , w ；g ，1 ) 一i d 易 知，一个( u ，g ，1 ) 一g d 也是一个g h d ( i u ) 或是一个( ，u ；g ，1 ) 一i d ，其中u = 0 或1 1 2 相关引理 下面的这些引理是本文用到的一些递推构造方法，读者可以参考文献 7 1 1 s l ，1 1 0 1 引理1 1 若记全体正整效所成的集合为，则日( 2 ) ) = n 由引理1 , 1 我们可得到下面一个引理 引理1 2 ( 见【7 】) 如果一个g 一日d ( n 2 ) 存在。那么对于m 2 ，g h o ( n m ) 也 存在 第一章递推构造方法 l o 引理1 3 ( 见【1 0 】) 设凰= ul u 2 3 ) ，鹏( 3 ，4 ，5 ，6 ，8 ) ，那么b ( e ) = k 3 由引理1 3 我们可得到下面的引理 引理1 4 ( 见【8 】) 如果g h d ( n 3 ) ，g h d ( n 4 ) ，g h d ( n 5 ) ，g h d ( n 6 ) 及g h d ( n 8 ) 存在，那么对于m 23 ，g h d ( n ”) 也存在 引理1 5 ( 见【8 】) 如果下面条件满足 i ) 存在组型为0 l ，卯，珊) 的( u ，g ，1 ) 一l i d ， i i ) 对于( 1 s h ) c g i ，g ，1 ) - g d 和( 甄+ i ，g ，1 ) - g d 存在， 那么( t j ，g ，1 ) g d 和扣+ l ，g ，1 ) - c d 存在 第二章第一类囝的圉设计 第二章第一类图的图设计 本章主要讨论了第一类六点八边图的图设计的存在性，即( ”，g i ，1 ) 一g d ( i = 4 ，5 ) 存在当且仅当u e 0 ，1r o o d ( 1 6 ) 且 1 6 我们首先直接构造出当u = 1 6 ，1 7 ，3 2 ，3 3 时，( ，g ，1 ) - g d ( i = 4 ，5 ) ，然后构造出g i h d ( 1 6 3 ) ，g i h d ( 1 6 4 ) ，g ，一h d ( z 6 5 ) ，g i h d ( 1 6 6 ) 及g i h d ( 1 6 8 ) “= 4 ，5 ) ，再运用第一章中的递推构造方法得到结论 2 1 图g 4 的图设计 图g 4 昼 记图g 4 为- ( a , b ，c ，d ，e ，f ) ab f e 引理2 1 1 存在( ，g 4 ，1 ) ，其中 = 1 6 ，1 7 证明；当u = 1 6 时，取x = z 1 5u o o ，可定义区组集如下t ：( o o ，0 ，1 ，3 ，1 2 ，7 )( r o o d l 5 ) 易验证( x ， ) 是一个( 1 6 ，g 4 ，1 ) - g d 当t j 一- - - 1 7 时，取x = z 。7 ，可定义区组集如下； 4 ： ( 0 ，l ，3 ，6 ，0 ，1 0 )( r o o d1 7 ) 易验证( x ， ) 是一个( 1 7 ，g 4 ，1 ) - g d 引理2 i 2 存在( u ，g 4 ，1 ) ，其中”= 3 2 ，3 3 证明t 当v = 3 2 时取x = z 3 lu o o 。可定义区组集如下t 4 ：( 0 ，1 4 ，2 2 ，1 0 ，2 3 ，7 )( r o o d3 1 ) ( ，2 0 ，2 6 ，2 1 ，1 2 ，i 0 )( r o o d3 1 ) 易验证( x ，) 是一个( 3 2 ，g 4 ，1 ) ，g d 当v = 3 3 时，取x = z 3 3 ，可定义区组集如下t ：( 0 ，1 2 ，1 7 ，8 ，3 1 ，1 4 )( r o o d3 3 ) ( 0 ，1 8 ，7 ，1 0 ，2 4 ，1 1 ) ( r o o d3 3 ) 第二章第一类图的图设计 1 2 易验证( x ，一4 ) 是一个( 3 3 ，g 4 ，1 ) 一g d 引理2 1 3 存在组型为( 1 6 0 ) 的( 鼠，1 ) - h d ，其中k = 3 ，4 ，5 ，6 ，8 证明t 当k = 3 时，取x i = o + i ，3 + i ，4 5 + 1 ) ，其中o 2 ，可定义区组集如 下l ： ( 1 4 ，1 9 ，2 0 ，3 ，1 6 ，4 4 )( r o o d4 8 ) ( 2 8 ，3 0 ，3 4 ，“，1 5 ，4 )( r o o d4 8 ) 易验证( x ，g ， ) 是一个组型为( 1 6 3 ) 的( qg 4 ，1 ) - h d 当k = 4 时，取x i = g x 6 x i 其中0 i 2 ，x s = z 1 州o 。) ，可定义区组集如下t 4 ：( ( 3 ，o o ) ，( 1 1 ，1 ) ，( 1 0 ，3 ) ，( 1 2 ，2 ) ，( 6 ，o ) ，( 1 2 ，o o ) )r o o d ( 1 6 ，3 ) ( 0 4 ，o ) ，( 7 ，1 ) ，( o ，o ) ，( 5 ，2 ) ，( 9 ，o o ) ，( 7 ，o ) )r o o d ( 1 6 ，3 ) ( ( 5 ，o o ) ，( 2 ，2 ) ，( 1 0 ，1 ) ，( 7 ，o ) ，( 1 ，2 ) ，( 1 4 ，o o ) )r o o d ( 1 6 ，3 ) ( ( 3 ，2 ) ，( 1 4 ，) ，( 9 ，2 ) ，( 5 ，o ) ，( 8 ，2 ) ，( 4 ，1 ) )r o o d ( 1 6 ，3 ) 易验证( x ，9 ，4 ) 是一个组型为( 1 6 4 ) 的( u ，c 4 ，1 ) - h d 当k = 5 时，取x i = 0 + i ，5 + i ，7 5 + 咄其中0 s i 4 ，可定义区组集如 下： 4 ： ( 5 4 ，3 ，5 9 ，1 0 ，2 7 ，l i )( r o o d8 0 ) ( 0 ，4 8 ，7 1 ，2 7 ，7 3 ，5 )( m o d8 0 ) ( 6 9 ，2 7 ，6 6 ，5 3 ，7 2 ，2 5 ) ( r o o d8 0 ) ( 2 8 ，1 ，1 0 ，4 ，8 ，7 0 )( r o o d8 0 ) 易验证( x ，岔，4 ) 是一个组型为( 1 6 5 ) 的( q 国，1 ) 1 i d 当k = 6 时。取x i = z 1 8 x i ，其中0 i 4 ，托= z 1 6 。 ，可定义区组集如 下z 4 ： ( ( 1 ，o ) ，( 6 ，3 ) ，( 1 2 ，2 ) ，( 6 ，1 ) ，( 9 ，) ，( 1 4 ，4 ) )r o o d ( 1 6 ，5 ) ( ( 1 2 ，1 ) ，( 1 3 ，3 ) ，( 1 5 ，1 ) ，( 7 ，o 。) ，( 2 ，1 ) ，( 1 1 ，2 ) )r o o d ( 1 6 ，5 ) ( ( 1 0 ，) ，( 1 0 ，4 ) ，( 1 ，o o ) ，( 4 ，2 ) ，( 7 ，4 ) ，( 1 1 ，3 ) )r o o d ( 1 6 ，5 ) ( ( o ，3 ) ，( 9 ，1 ) ，( 1 5 ，) ，( 1 1 ，3 ) ，( 1 ，1 ) ，( 1 2 ，4 ) )r o o d ( 1 6 ，5 ) ( ( 2 ，3 ) ，( 2 ，2 ) ，( 5 ，3 ) ，( 4 ，) ，( 3 ，o ) ，( 6 ，4 ) )r o o d ( 1 6 ，5 ) ( ( 0 ，) ，( 7 ，2 ) ，( 9 ，1 ) ，( 1 4 ，0 ) ，( 2 ，3 ) ，( 3 ，1 ) ) m d d ( 1 6 ，5 ) 易验证( x ，9 ， ) 是一个组型为( 1 6 6 ) 的( u ，g 4 ，1 ) i t d 当七= 8 时，取置= 蜀6 x 尽 ，其中0 i 6 ，赫= z 1 6 o 。 ，可定义区组集如 第二章第一类囝的图设计 f t 1 3 a ： ( ( 1 4 ，) ，( 1 4 ，6 ) ，( 9 ，2 ) ，( 1 ，3 ) ，( 1 2 ，5 ) ，( 3 ，o ) )r o o d ( 1 6 ，7 ) ( ( 5 ，1 ) ，( 2 ，2 ) ，( 1 4 ，5 ) ，( 1 4 ，1 ) ，( 4 ，4 ) ，( 1 4 ，0 ) )r o o d ( 1 6 ，7 ) ( ( 1 1 ，1 ) ，( 1 2 ，4 ) ，( 8 ，5 ) ，( 1 0 ，o o ) ，( 1 5 ，4 ) ，( 0 ，2 ) )r o o d ( 1 6 ，7 ) ( ( 1 1 ，2 ) ，( 1 5 ，5 ) ，( 8 ，1 ) ，( 2 ，o ) ，( 9 ，5 ) ，( 6 ，o o ) )r o o d ( 1 6 ，7 ) ( 5 ，0 ) ， 1 1 ，2 ) ，( 1 2 ，3 ) ，( 2 ，1 ) ，( d ，6 ) ，( 3 ，。) )r o o d 1 6 ，7 ) ( ( 1 5 ，1 ) ，( 7 ，5 ) ，( 1 0 ，1 ) ，( 1 0 ，6 ) ，( 1 5 ，5 ) ，( 5 ，4 ) )r o o d ( 1 6 ，7 ) ( ( 7 ，6 ) ，( 1 2 。2 ) ，( 1 3 ，1 ) ，( 1 l ，5 ) ，( 2 ，1 ) ，( 1 0 ，3 ) )r o o d 【1 6 ，7 ) ( ( 0 ，2 ) ，( 2 ，0 ) ，( 1 l ，o o ) ，( 5 ，5 ) ，( 1 2 ，6 ) ，( 1 ，。0 ) )r o o d ( 1 6 ，7 ) 易验证( x ，口， ) 是一个组型为( 1 6 8 ) 的( ”，g 4 ，1 ) 一豇d 定理2 1 4 ( u g 4 ，1 ) 一g d 存在的必要条件u 兰0 ，lr o o d ( 1 6 ) 且 21 6 也是充分 的 证明t 由引理2 1 1 ，2 1 2 ，2 1 _ 3 ，1 4 及引理1 5 可知存在( “g 4 ，1 ) 一g d 当且仅当 v = 0 ，lr o o d ( 1 6 ) 且”1 6 2 2图g 5 的图设计 图g 5 c 记图g 5 为；( a , b ，c ，d ，e ，f ) 引理2 2 1 存在( u g 5 ，1 ) ，其中 = 1 6 ，1 7 证明z 当”= 1 6 时，取x = z 1 5u o o ，可定义区组集如下 一4 ： ( o o 。o ，1 ，3 ，1 0 ，4 )( r o o d1 5 ) 易验证( x ，a ) 是一个( 1 6 ，g 5 ，1 ) 一g d 当”= 1 7 时，取x = z 1 7 ，可定义区组集如下- 4 ： ( 0 ，l ，3 ，6 ，1 4 ，7 )( r o o d1 7 ) 易验证( x ，a ) 是一个( 1 7 ，g 5 ，1 ) g d 第二章第一类图的图设计 引理2 2 2 存在( ，g s ，1 ) ，其中u = 3 2 ，3 3 证明，当v = 3 2 时。取x = z 3 u ，可定义区组集如下 a ： ( ，5 ，1 ，2 5 ，2 7 ，1 9 )( r o o d3 1 ) ( 0 ，2 6 ，1 4 ，1 3 ，1 0 ，2 0 )( r o o d3 1 ) 下 下t 下 1 4 易验证( x ，4 ) 是一个( 3 2 ，g 5 ，1 ) 一g d 当u = 3 3 时，取x = z 3 3 ，可定义区组集如下t a ： ( 0 ，2 1 ，3 1 ，4 ，1 7 ，1 8 )( r o o d3 3 ) ( 0 ，2 8 ，2 ，2 0 ，6 ，4 j ( m o d3 3 ) 易验证( x ，4 ) 是一个( 3 3 ，g 5 ，1 ) - g d 引理2 2 3 存在组型为( 1 6 ) 的( u ，g s ，1 ) h d ，其中k = 3 ，4 ，5 ，6 ，8 证明t 当= 3 时，取x i = 0 + i ，3 + i ，4 5 + i ) ，其中o g 2 ，可定义区组集如 a ： ( 3 3 ，4 3 ，2 6 ，1 8 ，4 4 ，9 ) ( m o d4 8 ) ( 4 5 ，1 6 ，3 6 ，3 2 ，2 l ，2 3 )( r o o d4 8 ) 易验证( x ，9 ，4 ) 是一个组型为( 1 6 3 ) 的( u ，g 5 ，1 ) 一h d 当k = 4 时，取墨= z l 州i 其中o i 2 ，x 3 = z t 6 x 。) ，可定义区组集如下： a ：( ( 4 ，2 ) ，( 4 ，o 。) ，( 1 2 ，1 ) ，( 1 l ，2 ) ，( 5 ，1 ) ，( 7 ，2 ) )r o o d ( 1 6 ，3 ) ( ( 9 ，) ，( 8 ，1 ) ，( 6 ，2 ) ，( 1 3 ，。) ，( 3 ，o ) ，( 1 4 ，) ) r o o d ( 1 6 ，3 ) ( ( 1 1 ，1 ) ，( 1 5 ，2 ) ，( 8 ，0 ) ，( 1 1 ，o o ) ，( 9 ，o ) ，( 1 3 ，o 。) ) r o o d ( 1 6 ，3 ) ( ( 1 2 ，1 ) ，( 1 ，o ) ，( 1 ，1 ) ，( 4 ，2 ) ，( 8 ，1 ) ，( 9 ，2 ) )r o o d ( 1 6 ，3 ) 易验证( x ，9 ，且) 是一个组型为( 1 6 4 ) 的( ，g 5 ，1 ) - h d 当k = 5 时，取墨= 0 + ，5 + ，7 5 + ，其中0 i 4 ，可定义区组集如 a ： ( 5 7 ，2 6 ，4 0 ，3 9 ，4 8 ，6 9 )( m o d8 0 ) ( 5 ，7 ，7 6 ，1 5 ，3 3 ，4 5 )( r o o d8 0 ) ( 3 5 ，4 1 ，3 4 ，7 5 ，2 4 ，5 7 )( r o o d8 0 ) ( 5 8 ，2 2 ，4 6 ，4 9 ，2 6 ，5 4 )( r o o d8 0 ) 易验证( x ，g ，一4 ) 是一个组型为( 1 6 5 ) 的( d ，g 5 ，1 ) - h d 当k = 6 时，取置= z 1 6 ，其中0 墨l 茎4 ，x s = z 1 6 o 。) ，可定义区组集如 第二章第一类圉的圉设计 1 5 ：【( 7 ，3 ) ，( 4 ，o ) ，( 0 ，) ，( 9 ，4 ) ，( 6 ，3 ) ( 9 ，2 ) )r o o d ( 1 6 ，5 ) ( ( 2 ，o ) ，( 1 4 ，1 ) ，( 1 4 ，o ) ，( s ，2 ) ，f l2 。) ，( 7 ，2 ) )r o o d ( 1 6 ，5 ) ( ( 8 ，l 】，【1 4 ，2 ) ，( 7 ，】，( 1 5 ，0 ) ，( 0 ，4 ) ，( 1 4 ，o ) )皿q d ( 1 6 ，5 ) ( ( 1 l ，。) ，( 1 1 ，4 ) ，( 2 ，1 ) ，( 7 ，2 ) ，( 6 ，) ，( 3 ，2 ) )r o o d ( 1 6 ，5 ) ( ( 3 、1 ) ，( 1 l ，o ) ，( 9 4 ) ，( 5 ，3 ) ，( 1 4 ，2 ) ，( 1 0 ，4 ) )r o o d ( 1 6 ，5 ) ( ( 0 1 0 ) ，( 徊，) ，( 1 l7 ，( s ，4 j ，f i 3 ，2 ) ( ，川jm o d ( 1 6 ，5 j 易验证( x ，口，且) 是一个组型为( 1 6 6 ) 的( u ，g 5 ，1 ) ，h d 当t = 8 时取蕾= z 1 6 碍，其中0 s f 墨6 ，x t = z 1 6 x 。o ) ，可定义区组集如 下， a ： ( ( 5 ，4 ) ，( 1 4 ，6 ) ，( 1 ，o o 】，1 5 ，2 ) ，( 2 ，3 ) ，( 4 ，4 ) )r o o d ( 1 6 ，7 ) ( ( 1 4 ，。) ，( 1 4 ，3 ) ，( 9 ，4 ) ，( 8 ，o ) ，( 9 ，5 ) ，( 1 2 ，4 ) )r o o d ( 1 6 ，7 ) “，d ，d ) ，( 2 ，o o ) ，( 3 。d ) ，( 1 ，4 ) ，( 6 。5 ) ( 1 z ，2 ) )r o o d ( 1 6 ，7 ) ( ( 9 】，( 5 ，6 ) ，( 7 ，1 ) ，( 1 5 ，5 ) ，( 1 4 ，4 ) ，( 1 4 ，3 ) ) n d ( 1 6 ，7 ) ( ( 1 ，4 ) ，( 1 3 ，1 ) ，( 1 4 ，0 ) ，( 1 0 ，6 ) ，( 6 ，4 ) ，( 4 ，。) )r o o d ( 1 6 ，7 ) ( ( 1 3 ，3 ) ，( 7 ，。) ，( 1 1 ) ，3 ) ，( 1 2 ，1 ) ，( 2 0 ) ，( 1 4 ，1 ) )r o o d ( 1 6 ，7 ) f f 2 ，4 j ，( i 曩，( 1 5 ，5 j ，( 5 ，印，f1 4 ，5 ；，( z ，砷， r o o df z 颤7 ) ( ( o ，3 ) ，( 0 ，0 ) ，( 5 ，4 ) ，( 1 3 ，2 ) ，( 1 1 ，5 ) ，( 6 ，2 ) )r o o d ( 1 6 ，7 ) 易验证僻，9 ，4 ) 是一个组型为( 1 6 8 ) 的( ，g 5 ，1 ) h d 定理2 2 4 岛，1 ) 一g d 存在的必要条件u ；o ，lr o o d ( 1 6 ) 且v 三1 6 也是充分 的 证明；由引理2 2 1 ，2 2 2 ，2 2 3 ，1 4 及引理1 5 可知存在( ”，g 5 ，1 ) 一g d 当且仅当 v - 0 ，1m d d f 】6 ) 且砣：1 6 第三章第二类围的圉设计 第三章第二类图的图设计 1 6 本章主要讨论了第二类六点八边图的图设计的存在性，即0 ，g 6 ，1 ) 一g d 存 在当且仅当”1r o o d ( 1 6 ) 且”1 7 我们首先直接构造出当u = 1 7 ，3 3 时， ( u ，g 6 ，1 ) 一g d ，然后构造出g 6 一h d ( 1 6 3 ) ，g 6 一h d ( 1 6 4 ) ，g 6 一s d ( 1 6 5 ) ，g 6 一h d ( 1 6 6 ) 及g 6 一h d ( 1 0 s ) ，再运用第一章中的递推构造方法得到结论 3 1图g 6 的图设计 下； 图g 6 引理3 1 1 存在( u ，g 6 ，1 ) ，其中 = 1 7 ， 证明，当u = 1 7 对，取x = z 1 7 ，可定义区组集如下r ： ( 0 ，1 ，3 ，1 0 ，1 3 ，4 )( r o o d1 7 ) 易验证( x ，) 是一个( 1 7 ，g 6 ，1 ) 一g d 引理3 1 2 存在( u ，g 6 ，1 ) ，其中u = 3 3 证明：当u = 3 3 时。取x = z 3 3 ，可定义区组集如下t 4 ：( 0 ，3 ，4 ，2 2 ，1 1 ，1 0 )( r o o d3 3 ) ( 0 ，1 6 ，9 ，1 8 ，1 2 ，1 3 )( r o o d3 3 ) 易验证，4 ) 是一个( 3 3 ，g 6 ，1 ) - g d 引理3 1 3 存在组型为( 1 6 ) 的( 仉g 6 ，1 ) - l i d ，其中k = 3 ，4 ，5 ，6 ，8 ， 证明。当女= 3 时，取墨= o + ，3 + i ，4 5 + 嘎其中o g 2 ，可定义区组集如 ： ( 8 ，9 ，1 3 ，2 9 ，2 2 ，1 8 ) ( 8 ，0 ，4 6 ，1 7 ，2 2 ，3 1 ) ( r o o d4 8 ) ( r o o d4 8 ) 第三章第二类囝的图设计 1 7 易验证伍，蛋，a ) 是一个组型为( 1 8 3 ) 的忆g 6 ，1 ) - l i d 当自= 4 时，取x i = z , 1 6 ) i ，其中0 s f s 2 ，x a = 而“ o 。 ，可定义区组集如下t ：( ( o ，0 ) ，( 0 ，1 ) ，( 1 ，0 ) ，( 3 ，2 ) ，( 5 ，0 0 ) ，( 7 ，1 ) )r o o d ( 1 6 ，3 ) ( ( o ，2 ) ，( 1 ，0 ) ，( 0 ，) ，( 4 ，2 ) ，( 7 ，o 。) ，( 1 4 ，1 ) )r o o d ( 1 6 ，3 ) ( ( o ，1 ) ，( 6 ，o ) ，( 1 ，1 ) ，( 1 ，o 。) ，( 1 0 ，1 ) ，( 8 ，2 ) )r o o d ( 1 6 ，3 ) ( ( o ，) ，( 6 ，2 ) ，( 1 1 ，( 3 ，o 。) ，( 1 5 。o ) ( 2 ，0 ) )r o o d ( 1 6 ，3 ) 易验证僻，蛋， ) 是一个组型为( 1 6 4 ) 的( ”，g 6 ，1 ) - i t d ， 当t = 5 时，取置= o + ，5 + i ，7 5 + i ，其中o s f s 4 ，可定义区组集如 下t 4 ：( 2 6 1 6 4 ，1 2 ，7 5 ，7 1 ，2 7 ) ( r o o d8 0 ) ( 7 l ，“，6 5 ，8 ，6 2 ，3 0 )( m o d8 0 ) ( 1 3 ，2 l ，3 5 ，2 3 ，7 2 ，6 0 )( r o o d8 0 ) ( 1 8 ，4 2 ，2 3 ，3 9 ，3 3 ，5 2 )( r o o d8 0 ) 易验证( x ，9 ，4 ) 是一个组型为( 1 6 5 ) 的“g 蚕，1 ) l i d ， 当= 6 时，取墨= z 1 6 x i ) ，其中0 ts 4 ，x s = z 1 6 ，可定义区组集如 a ：( ( 1 2 ，。) ，( 1 3 ，2 ) ，( 9 ，c o ) ( 1 1 ，4 ) ，( 5 ，o ) ，【5 ，2 ) )r o o d ( 1 6 ，5 ) ( ( 6 ，4 ) ，( 3 ，3 ) ，( 3 ，4 j ，( 1 0 ，1 ) ，( 1 3 ，o ) ，( 1 1 ，3 ) )r o o d ( 1 6 ，5 ) ( ( 1 3 ，1 ) ，( 1 0 ，4 ) ，( 6 ，2 1 ，( 7 ，1 ) ，( 5 ，2 ) ，( 9 ，3 ) )r o o d ( 1 6 ，5 ) ( ( o ，4 ) ，f 1 5 ，】) ，( 1 2 ，o 。) ，( 8 ，2 ) ，( 1 0 ，d 。) ，( 8 ，。) )r o o d ( 1 6 ，5 ) ( ( 8 ，o ) ，( 1 3 ，) ，( 4 ，2 1 ，( 1 2 ，1 ) ，( t o ，o ) ，( 2 ，o 。) )r o o d ( t 6 ，5 ) ( ( o ，3 ) ，( 0 ，0 ) ，( 9 ，4 ) ，( 5 ，3 ) ，( 1 0 ，4 ) ，( 1 ，4 ) )r o o d ( 1 6 ，5 ) 易验证，g ，) 是一个组型为( 1 6 6 ) 的( u ，g 6 ，1 ) f