（应用数学专业论文）六点十二边图的图设计及其应用.pdf

摘要 设局是一个v 个点的完全图，g 为k 的一个不含孤立点的简单子图凰的一个g 设计，常记为( v ，g ，1 ) 一g d ，是指一个二元组功，其中x 为蜀的顶点集，召是凰的一 些子图( 亦称为区组) 构成的集合，使得每一个区组与g 同构，且凰的任何一条边恰出现 在男的一个区组中本文讨论了5 个六点十二边图g f ( f = l ，5 ) 图设计的存在性问题 业务疏导足光网络研究中的一个前沿和热点问题它足指将低速信号打包成高速流， 以降低设备成本在w d m 光网络中，成本主要用于叫做分插复用器( 简称a d m ) 的电子 终端节点数上我们考虑疏导率为c 的无向环网时，业务疏导问题用图论的术语可叙述为 将业务请求构成的图分解成最多含c 条边的子图，并使所有子图的顶点总数最少对于某 些特定的疏导率，利用图论和设计的理论已经得到了最优构造本文利用六点十二边图 图设计的结论，研究c = 1 2 的业务疏导问题，并得到了a d m 数的最小值 关键词：图设计可分组设计带洞设计业务疏导 i i i a b s t r a c t l e tk b eac o m p l e t eg r a p hw i t hyv e r t i c e s ，a n dgas i m p l es u b g r a p hw i t h o u ti 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 d b y ( y ，g ，1 ) 一g d ，i sap a i r 陇助，w h e r ex i st h ev e r t e x s 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 局，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 ，a n da n ye d g ei n 凰o c c u r si ne x a c t l yo n eb l o c k t h e r ea r ef i v en o n i s o m o r p h i c g 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 dt w e l v ee d g e s i nt h i sp a p e r ，w ew i l ld i s c u s st h e e x i s t e n c ep r o b l e m so f ( v ，g i ，1 ) 一g df o ri = 1 ，5 t r a f f i cg r o o m i n gi so n eo ft h em o s ti m p o r t a n ta n dp o p u l a ri s s u e si nt h ea r e ao fo p t i c a l n e t w o r k s i tr e f e r st og r o u p i n gl o wr a t es i g n a l si n t oh i g h e rs p e e ds t r e a m s ，i no r d e rt or e d u c e t h ee q u i p m e n tc o s t i nw d mn e t w o r k s ，t h i sc o s ti sm o s t l yg i v e nb yt h en u m b e ro fe l e c t r o n i c t e r m i n a t i o n s ，n a m e l ya d d - d r o pm u l t i p l e x e r s ( a d m sf o rs h o r t ) w ec o n s i d e rt h eu n d i r e c t e d r i n gw i t hag e n e r i cg r o o m i n gf a c t o rc ，a n di nt h i sc a s e ，i ng r a p h - t h e o r e t i c a lt e r m s ，t h et r a f f i c g r o o m i n gp r o b l e mc o n s i s t si np a r t i t i o n i n gt h ee d g e so far e q u e s tg r a p hi n t os u b g r a p h sw i t ha t m o s tce d g e s ，w h i l em i n i m i z i n gt h et o t a ln u m b e ro fv e r t i c e so ft h ed e c o m p o s i t i o n f o rs o m e g r o o m i n gf a c t o r s ，u s i n gt h eg r a p ha n dd e s i g nt h e o r y ，w eo p t i m a l l ys o l v et h ep r o b l e m b a s e d o nt h er e s u l t so f g - d e s i g nw i t hs i xv e r t i c e sa n dt w e l v ee d g e s ，w ec o n s i d e rt h ep r o b l e mo f t r a f f i c g r o o m i n gw h e nc = 1 2a n dg e tt h em i n i m u mn u m b e ro fa d m s k e yw o r d s ：g 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 n h o l c yd e s i g n t r a f f i cg r o o m i n g i v 学位论文原创性声明 本人所提交的学位论文六点十二边图的图设计及其应用，是在导师的指导下， 独立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人 和集体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：易砀j 谴 指导教师确认( 签名) ： e ；| 年6 旯兰b 年具b 学位论文版权使用授权书 署锄k 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 论文作者( 签名) ：了乞缃使 9 甲年石月j 日 指导教师( 签名) ：缴扎 听每6 其孓日 n 绪论 1 图设计的研究背景及本文的主要结论 组合数学是研究离散对象在给定约束条件下如何进行安排( 或配置) 的数学分支它 的渊源可以追溯到公元前2 2 0 0 年我国的大禹治水时代，但该学科进展一直很慢直到二 十世纪4 0 年代电子计算机诞生后，它开始振兴，并以前所未有的速度发展和壮大起来， 而且在计算机科学、数字通讯，实验设计及现代企业管理等方面的应用越来越广泛组 合设计是组合数学的一个主要分支，而平衡不完全区组设计是其中最重要的一类： 定义1 设v ，k 是正整数，若有限关联结构d = ( 置8 ) ( 其中集合x 中的元素叫作点， 集合易中的元素叫作区组) 满足以下条件： ( i ) 凶= v ； ( i i ) 对任意b 召，都有l b i = 七； ( i i i ) x 中任意两个不同的元素恰在8 的1 个区组中出现， 则称d 为一个平衡不完全区组设计，简称区组设计或b i b 设计，记作b ( 织l ；v ) 根据定义容易得到口 ，l ；y ) 存在的必要条件为： ( i ) ( 1 ，一1 ) 三0 ( r o o d ( k 1 ) ) ， ( i i ) “1 ，一1 ) 兰0 ( r o o d k ( k l ” 若g 是一个a b e l 群，其运算为加法，占l ，岛，既是易中的部分区组，如果满足： 当= u 至l 岛+ gg g ) 则称每一个毋( i = l ，2 ，历) 为初始区组( 或基区组) 特别地，当 g = 乙时，我们常把男简记为：b f ( r o o d 刀) ( i = 1 ，2 ，所) 定义2 设图g 有v 个点，若其任意两个不同点x ，y 之间均恰有一条边 工，y 相连，则 称其为v 点完全图，简记为凰 在平衡不完全区组设计b ，1 ；d 中，每一个区组实际上就是一个k 点完全图h e l l 和 r o s a 用任意图结构代替区组，从而推广了区组设计的概念，这些设计就称为图设计( 简称 g - 设计) 在这篇文章中，我们讨论的图都是有限、无向、不含孤立点的简单图与图和设 计相关的术语，读者可参考著作【l 一3 】 定义3 设g 是一个不含孤立点的简单图，凰的一个g 一设计，记为( v ，g ，1 ) 一g d ，是 指一个二元组( x 功，x 为凰的顶点集，男为凰的一些子图( 也称为区组) 构成的集合， 使得任一子图均与图g 同构，且墨的任意一条边恰在当的一个子图中出现 特别地，当图g 为完全图时，一个g - 设计恰为一个b i b 设计 j c b e n n o n d 等在文章 4 1 4 中给出了g 一设计存在的必要条件，即若图g 有k 个顶点， e 条边，且各顶点度的最大公因子为d 时，( 1 ，g ，1 ) 一g d 存在的必要条件是： ( 1 少七， ( i i ) “y 1 ) 三0 ( r o o d 2 e ) ， ( i i i ) v l 三0 ( r o o d 回 关于各种图的g - 设计的存在性，近年来有着广泛的研究： ( 1 ) 当图g 的顶点数后4 时，j c b e r m o n d 等在文献【5 】中证明了上述条件也充分 ( 2 ) 当图g 的顶点数k = 5 时，j 。c 。b e r m o n d 等在文献【4 ，6 】中亦几乎给出了完全解 ( 3 ) 当图g 的顶点数k = 6 时：殷剑兴等首先在文章【7 】中讨论了3 d g ) 6 的情况，并 给出了存在谱对于e ( g ) = 7 的情形，田子红等在文章【8 】中讨论了两个图的图设计存在 性，其中g = 如3 + p 这一问题的完全解是由徐爱庆在文章【9 ，1 0 中给出的对于d g ) = 8 的情形，除一些子图外，刘重阳等在文章【l l 】中已基本解决对于“6 3 = 9 的情形，赵红 涛等在文章【1 2 】中讨论了部分图的存在性关于图设计的综述，读者可参见文献【1 3 ，1 4 】 出于研究疏导率c = 1 2 时环上业务疏导问题的需要，本文讨论七= 6 且“g ) = 1 2 的情形，即5 个六点十二边图g io = 1 ，2 ，5 ) 图设计的存在性问题。根据这5 个图的结 构，把它们分为如下三类：第一类图g l ，第二类图g 2 ，g 3 ，g 4 及第三类图g 5 ，均简记为 0 ，b ，c ，矾e ，力，如下图所示 9 川穆川e 回e 印川ec 回厂e 易知这些图的图设计存在的必要条件如下： ( 1 x v , g i ，1 ) 一g d 存在的必要条件为：y 兰1 ，9 ( r o o d2 4 ) 且v 9 ； ( 2 ) o ，g j ，1 ) 一g do = 2 ，3 ，4 ，5 ) 存在的必要条件为： ，兰0 ，i ，9 ，1 6 沏o d2 4 ) 且 ，9 本文得到如下结论： 定理1 ( 第一类图) 当v 兰l ，9 ( r o o d2 4 ) 且v 2 5 时，似g 1 ，1 ) 一g d 存在 定理2 ( 第二类图) 对i = 2 ，3 ： ( i ) 当v 三1 仰d d2 4 ) 且v 2 5 时，( v ，g f ，1 ) 一g d 存在； ( i i ) 当v 三9 咖o d2 4 u ) 且v 9 时，对任意正整数z ，除可能例外的v = 8 i ，1 5 3 ， ( v ，g 2 ，1 ) 一g d 存在；对甜三l ，2 ，3 ( r o o d4 ) ，除例外的v = 9 及可能例外的1 ，= 1 5 3 ，1 7 7 ， 似g 3 ，1 ) 一g d 存在，对“三0 ( m o d4 ) ，若存在( 1 0 5 ，g 3 ，1 ) 一g d ，则除可能例外的v = 2 2 0 1 ，2 9 7 ，似g 3 ，1 ) 一g d 存在； ( i i i ) 当v 兰1 6 o d2 4 u ) ，l f 三l ，6 ( r o o d2 0 ) 且v 1 6 时，( ，g ；，1 ) 一g d 存在； ( i v ) 当v 三0 ( r o o d2 4 ) 时，若存在( 2 4 ，g ，1 ) 一g d 及( 4 8 ，g i ，1 ) 一g d ，则除可能例外 的 ，= 7 2 ，似g i ，1 ) 一g d 存在 对i = 4 ： 当y = 1 6 时，( v ，g 4 ，1 ) 一g d 不存在，当y = 9 ，2 5 ，4 0 ，4 9 ，5 7 ，7 3 时，一，g 4 ，1 ) 一g d 存在 若还存在g 4 一h g d ( 8 4 ) 和g 4 一h g d ( 6 5 ) ，则此图图设计的存在性与图g 2 的完全一样 定理3 ( 第三类图) ( i ) 当v 兰l ( r o o d 2 4 u ) ，越兰0 ，l 如甜5 ) 且材5 及，= 2 5 ，4 9 ，7 3 时，( v ，g 5 ，1 ) 一g d 存 在； ( i i ) 当1 ，三0 沏o d2 4 u ) ，材三0 ，1 ( r o o d5 ) 且5 时，若存在( 2 4 ，g 5 ，1 ) 一g d ，则 ( v ，g 5 ，1 ) 一g d 存在； ( i i i ) 当 ，= 9 ，1 6 时，( 1 ，g 5 ，1 ) 一g d 不存在，当，= 5 7 时，( 1 ，g 5 ，1 ) 一g d 存在 2 业务疏导问题的研究背景及本文的主要结论 i n t e r n e t 的迅猛发展极大地推动了光网络研究的进展近几年来，随着波分复用( w d m ) 技术的应用，单根光纤可承载更多波长，而每个波长又可通过时分复用( t d m ) 的方式容纳 许多低速业务流在这样的系统中，限制光网络潜在容量得到充分发挥的主要因素已不再 是光纤的带宽，而是网络终端的复用器、交换机和路由器等电子设备的处理速度所带来的 瓶颈效应业务疏导( t r a f f i cg r o o m i n g ) 技术的出现为解决这些问题提供了一种有效途径 业务疏导研究的就是如何通过有效地复用、解复用及交换处理，将不同速率、不同类型的 低速业务流打包成高速数据流，复用到一个波长上，以实现各种特定的设计目的，进而提 高网络资源的利用率，降低网络成本， 对于每个节点，我们可以通过业务疏导，利用波长分插复用器( w a d m ) 把节点所需 的波提取出来，而对其它不需要的波长进行光学旁路，从而减少节点处网络设备的信息处 理量由于每个波长复用很多的低速业务流，对于每个波长我们必须利用一个分插复用器 ( a d m ) 对其所带的低速业务流进行上厂f 分路因此a d m 的数量随光网络所用的波长数 的增加而呈增加的趋势由于a d m 的费用占整个网络费用相当大的份额，而通过业务疏 导，不仅可以使得波长资源得到充分的利用，也能大幅减少a d m 的使用量，从而降低网络 成本 根据网络的型，常有很多变量需要考虑，如使用的容量和最优化的参数等，这引出了许 多有趣的设计问题( 如图分解) 我们用一个v 点图g 来表示一个光网络给定一个业务矩 阵，它足用图j 来表示全部要求形成的图，每两个点间的要求数确定了它们之间的边数当 每两个点间恰存在一个要求时，则，= 墨每两个点问的要求是由g 中分配一个波长的路 径实现的。若一个要求在一个波长上只能使用带宽的l c 通过它的路径，则此c 称为疏导 率或者说，对于g 中每一条边e 和每一个波长w ，w 上至多存在c 条包含边e 的路 对于某些疏导率c ，利用图论和组合设计理论已经得到了最优的构造0 4 特别地，当 c = l 时，每个子图都是l 条边，没有降低成本的可能当c = 2 时，每个子图至多包含2 条 边，由于凰线图是欧拉图，在每个欧拉圈上用连续的点可以降低成本，因此，得到最低成 本是r 三等坐1 1 5 1 对疏导率c = 3 1 6 1 ，c = 4 【1 7 , i s ，c = 5 【1 9 1 ，c = 6 【1 5 】等环上的业务疏导 问题也已经解决本文将利用六点十二边图图设计的结论，并结合多图分解的理论，研究 无向w d m 环网中疏导率c = 1 2 的业务疏导问题， 文中我们用a ( c ，v ) 表示一个具有1 ，个点的疏导率为c 的无向w d m 环网中所用a d m 数的最小值 本部分得到的主要结论如下： 定理4 当1 ，兰0 ，l ，9 ，1 6 ( r o o d2 4 ) 且1 ，9 时，a 0 2 ，d = ! 必4 4 1 递推构造方法 所谓递推构造方法足指利用一些已知的淮往是阶数较小的) 设计来构造一些新的( 往 往是阶数较大的) 设计，从而获得一些具有新的参数的设计的方法本章将引入本文所用 的递推方法以及与其相关的定义、引理及其证明 1 1 基本定义 定义1 1 设1 ，为正整数，k 与m 均为正整数集设d = 缪，功为有限关联结构， 其中x 是一个v 元点集，多是x 的个划分，其元素叫作组，易是x 的个子集簇，其元 素叫作区组，若满足下述条件： ( i ) 对任意g 够，都有l g i 尬 ( i i ) 对任意b 男，都有i b i k ； ( i i i ) 对任意g 缪和任意b 8 ，都有i gnb l l ； ( i v 中任意一对属于不同组的元素恰同时包含在易的1 个区组中， 则称d 为一个可分组设计或g d d ，记作g d d ( k , l ，尬力特别地，当k = ，m = 所) 时，记作g d d ( k ，l ，坍；v ) ，简记为七一g d d ，并称其为均匀可分组设计若9 包含岛个大小为 协的组，f = l ，2 ，研，则称d 是个型为瑶1n 缸2 玎智的g d d ，记作后一d ( 刀：1 刀 刀鲁) 定义1 2 如果一个图具有顶点集x = u l s 勘五和边集占，且满足以下两个条件： ( i ( 1 f 所) 是两两互不相交的集合，其中i = n i ，= 至1 订j ； ( i i ) 对任意x x ，y 与，当f ，时，边 x , y l e ，而当汪j 时 边k y l 豇 则称其为完全多部图，记作为m 特别地，当胁= 刀( f = l ，2 ，m ) 时，常简记为如期 定义1 3 给定一个图g ，设x 为。虎，的点集，侈= 五，局，】是x 的一个划 分( 每个亦称为洞) ，召为与g 同构的边不交子图( 亦称为区组) 构成的集合，若毛m 。加 可分拆成若干个与g 同构的边不交的子图的并，则称d = 多，劢为带洞g - 设计或 h g d ，记作g h g d 若参包含岛个大小为珞的组，i = l ，2 ，m ，则称d 是一个型为 刀：1n 赶2 刀勿的h g d ，记作g h g d ( n ： 砖刀鲁) 易知，当图g 为完全图时，一个h g d 恰为一个g d d 特别地，g h g d ( 1 ”“1 0 1 ) 也称为不完全g 一设计，记为( u ，；g ，1 ) 一i g d 易知，一 个( u ，g ，1 ) 一g d 也是一个g h g d ( i ”) 或是一个( u ，山；g ，1 ) 一i g d ，其中山= 0 或1 1 2 相关引理 本文在递推构造时，将用到下面这些引理，读者可参考文献【1 4 】 引理1 1 设g ，甜为正整数，3 一g d d ( g ) 存在的充要条件为： 5 ( i ) g 三l ，5 ( r o o d6 ) ，甜兰l ，3 ( r o o d6 ) 且u 3 ，或 ( i i ) g 兰2 ，4 ( r o o d 6 ) ，“兰0 ，l ( m o d3 ) 且甜3 ，或 ( i i i ) g 兰3 ( r o o d6 ) ，兰l ( m o d2 ) 且”3 ，或 ( i v ) g 兰o ( m o d 6 ) 且u 3 引理1 2 设g ，m ，u 为非负整数，3 一g 肋铲m 1 ) 存在的充要条件为下列同时满足： ( i ) g 0 且材3 ，或甜= 2 且朋= g ，或“= 1 且肌= 0 ，或甜= 0 ， ( i i ) ，”甙“一1 ) ，或g u = 0 ， ( i i i ) g ( u 1 ) + m 三o ( m o d 2 ) ，或g u = 0 ， ( i v ) 言o ( m o d 2 ) ，或m = 0 ， ( v ) 矿 一1 ) + g u m 童o ( m o d 3 ) 引理1 3 设脚，甜为正整数，4 一g d d ( i 。所1 ) 存在的充要条件为： ( i ) m 三l ，7 ( r o o d1 2 ) ，兰0 ，3 ( m o d1 2 ) 且2 m + l ，或 ( i i 砌兰4 ，l o ( m o d1 2 ) ，”三0 ，9 ( r o o d1 2 ) 且材2 m + 1 引理1 4 设m ，材为正整数，4 一g d d ( 3 ”所1 ) 存在的充要条件为： ( j ) 所兰0 ，6 ( r o o d1 2 ) ，甜三0 ，l ( m o d 4 ) 且甜( 2 m + 3 ) 3 ，或 ( i i ) m 兰3 ，9 ( r o o d1 2 ) ，扰兰0 ，3 ( r o o d 4 ) 且甜( 2 m + 3 ) 3 引理1 5 设m ，甜为正整数，4 一g d d ( 4 “m 1 ) 存在的充要条件为： ( i 砌= 4 且甜= 3 ，或 ( i i ) 研兰l ( m o d 3 ) ，三o ( m o d3 ) 且l 1 7 1s2 ( u 1 ) ，u 之6 引理1 6 设所，甜为正整数，4 一g d d ( 5 ”m 1 ) 存在的充要条件为： ( i ) ，刀量5 ( r o o d6 ) ，甜兰3 ( r o o d1 2 ) 且55m ( 5 u 一5 ) 2 ，或 ( i i 砌三2 ( r o o d 6 ) ，u 兰9 ( m o d1 2 ) 且2 m ( s u 一5 ) 2 ，或 ( i i i ) m 三2 ( r o o d 3 ) ，u 三o ( m o d1 2 ) 且2 m ( 5 u 一8 ) 2 引理1 7 设蜀“为正整数，5 一g d d ( g u ) 存在的充要条件为： ( i ) g 三o ( m o d 2 0 ) 且甜5 ，或 ( i i 塘三o ( m o d 4 ) ，甜兰0 ，l ( m o d5 ) 且”5 ， 除了旷f 2 5 ，2 ，3 5 ，6 勺及可能的g = 3 ，g 三2 ，6 ，1 0 ，1 4 ，1 8 ( r o o d 2 0 ) 中的一些例外 威尔逊基本构造o v f c ) ：设彦，囝为一个g d d ，其中缪= ，局，x ) ，若存在 一个映射山：x 叶n ，对任意b = x 1 ，x 2 ，砍) 写，都存在一个k g d d ( w ( x 1 ) ，“船) ) ， 则存在k a ，d ( 删j “功，础u ( 工) ) 将上述著名定理简单改造，易得到如下图设计的引理： 引理1 8 若存在七一g 肋( 玎：t l 赶2 疗磬) 和g 一脚( 矿) ，则存在g h g d ( ( n n l ) 幻( 朋2 ) 七2 6 0 刀。) ) 引理1 9 若存在g h g d ( n ：刀 刀勿) 和( g ，1 ) 一g d ( f = l ，2 聊) ，则存在 ( 翟ln i k i ，g ，1 ) 一g d 引理1 1 0 若存在g - h g d ( n ：1 甩 刀鲁) 和( 聊+ l ，g ，1 ) 一g d ( f _ l ，2 所) ，则存在 ( 1 + z t - _ l 刀f 奶，g ，1 ) 一g d 7 2 三类六点十二边图的图设计 本章将讨论六点十二边图g ，( f = 1 ，5 ) 图设计的存在性问题我们首先直接构造出 一些小阶数的设计，然后运用递推构造法得到这些图设计存在的充分条件 2 1 第一类六点十二边图g 。的图设计 b c f p 图g l 引理2 1 不存在( 9 ，g l ，1 ) 一g d 证明：令点集x = a o ，a l ，a 8 l ，若存在( 9 ，g l ，1 ) 一g d ，则其区组集由b = 芋书= 3 个区组构成因为局的每个点均为8 度，而g l 的每个点都为4 度点，所以局中的每 个点仅由一种型构成，即2 个4 度不妨设其中一个区组为( 口o ，g i ，a s ) ，我们考虑点口。 与a 3 ：此区组中不含边 g o ，r n 3 l ，而边 研，a j l ，i = 0 ，3 ，j = 1 ，2 ，4 ，5 各出现一次，所以边 l a f ，a j l ，i = 0 ，3 ，j = 6 ，7 ，8 必同时出现在另一个含有边 a o ，a 3 l 的区组中，但在g i 中与任 意一条给定边的两端点同时相连的点仅有2 个，所以边( 口f ，a ) ，i = 0 ，3 ，j = 6 ，7 ，8 不可能 同时出现在含边 口o ，l 一个区组中，因此不存在( 9 ，g l ，1 ) 一g d 口 引理2 2 存在似g l ，1 ) 一g d ，其中1 ，= 2 5 ，4 9 证明：当 ，= 2 5 时，取x = z 玉，可定义区组集如下： 贸i ：( o ，1 ，3 ，9 ，1 8 ，1 4 ) ( r o o d 2 5 ) 易验证贝1 ) 是一个( 2 5 ，g l ，1 ) 一g d 当v = 4 9 时，取x = 2 匆，可定义区组集如下： 贝l ：( o ，l ，3 ，7 ，1 5 ，2 0 ) ( r o o d 4 9 ) ( o ，7 ，2 3 ，4 5 ，1 4 ，2 4 ) ( r o o d4 9 ) 易验证仪贝1 ) 是一个( 4 9 ，g l ，1 ) 一g d 口 引理2 3 存在( 1 ，g l ，1 ) 一g d ，其中 ，= 3 3 ，5 7 ，8 1 证明：当1 ，= 3 3 时，取x = z l i z 3 ，可定义区组集如下： 贝l ：( ( 0 ，0 ) ，( 0 ，1 ) ，( 1 ，1 ) ，( 2 ，0 ) ，( 8 ，o ) ，( 5 ，1 ) ) ( r o o d11 ) 8 ( ( 0 ，o ) ( o ，2 ) ，( 1 ，2 ) ，( 5 ，0 ) ( 9 ，0 ) ，( 2 ，2 ) ) ( ( 0 ，1 ) ，( 0 ，2 ) ，( 4 ，2 ) ，( 5 ，1 ) ，( 3 ，1 ) ，( 8 ，2 ) ) ( ( 0 ，0 ) ，( 6 ，1 ) ，( 1 0 ，o ) ，( 4 ，2 ) ，( 9 ，2 ) ，( 2 ，1 ) ) 易验证j 1 1 ) 是一个( 3 3 ，g l ，1 ) 一g d 当1 ，= 5 7 时，取x = z 1 9xz , 3 ，可定义区组集如下： 贝l ：( ( 0 ，0 ) ，( 0 ，1 ) ，( 1 ，1 ) ，( 2 ，0 ) ，( 4 ，0 ) ，( 6 ，1 ) ) ( ( 0 ，o ) ，( 3 ，1 ) ，( 5 ，1 ) ，( 11 ，0 ) ，( 1 4 ，o ) ，( 7 ，1 ) ) ( ( 0 ，0 ) ，( 2 ，2 ) ，( 4 ，2 ) ，( 1 6 ，0 ) ，( 6 ，0 ) ，( 9 ，2 ) ) ( ( 0 ，0 ) ，( 1 0 ，2 ) ，( 1 3 ，2 ) ，( 1 8 ，o ) ，( 7 ，0 ) ，( 1 5 ，2 ) ) ( ( 0 ，1 ) ，( 3 ，2 ) ，( 9 ，2 ) ，( 1 4 ，1 ) ，( 1 1 ，1 ) ，0 3 ，2 ) ) ( ( 0 ，1 ) ，( 1 2 ，2 ) ，( 1 ，2 ) ，( 1 6 ，1 ) ，( 9 ，1 ) ，( 1 6 ，2 ) ) ( ( 0 ，0 ) ，( 9 ，1 ) ，( 1 ，0 ) ，( o ，2 ) ，( 1 ，2 ) ，( 1 4 ，1 ) ) 易验证陇贝1 ) 是一个( 5 7 ，g l ，1 ) 一g d ( r o o d1 1 ) ( r o o d1 1 ) ( r o o d1 9 ) ( r o o d1 9 ) ( r o o d1 9 ) ( r o o d1 9 ) ( r o o d1 9 ) ( r o o d1 9 ) ( r o o d1 9 ) 当1 ，= 8 1 时，取x = z 2 7x 历，可定义区组集如下： 舅l ：( ( 0 ，0 ) ，( 0 ，1 ) ，( 1 ，1 ) ，( 2 ，o ) ，( 4 ，0 ) ，( 6 ，1 ) ) ( r o o d 2 7 ) ( ( 0 ，o ) ，( 3 ，1 ) ，( 5 ，1 ) ，( 9 ，0 ) ，( 1 0 ，o ) ，( 1 7 ，1 ) ) ( r o o d2 7 ) ( ( o ，0 ) ，( 9 ，1 ) ，( 1 2 ，1 ) ，( 2 5 ，0 ) ，( 2 0 ，0 ) ，( 1 3 ，1 ) ) ( r o o d2 7 ) ( ( o ，o ) ，( o ，2 ) ，( 2 ，2 ) ，( 3 ，0 ) ，( “，0 ) ，0 5 ，2 ) ) ( r o o d 2 7 ) ( ( 0 ，0 ) ，( 8 ，2 ) ，( 1 l ，2 ) ，0 8 ，o ) ，( 1 5 ，0 ) ，0 3 ，2 ) ) ( r o o d 2 7 ) ( ( o ，0 ) ，( 9 ，2 ) ，( 5 ，2 ) ，( 2 2 ，0 ) ，( 1 3 ，0 ) ，0 6 ，2 ) ) ( r o o d2 7 ) ( ( 0 ，1 ) ，( 0 ，2 ) ，( 1 4 ，2 ) ，( 3 ，1 ) ，( 1 2 ，1 ) ，( 1 9 ，2 ) ) ( m o d 2 7 ) ( ( o ，1 ) ，( 4 ，2 ) ，( 1 3 ，2 ) ，( 5 ，1 ) ，( 2 2 ，1 ) ，( 2 5 ，2 ) ) ( r o o d2 7 ) ( ( 0 ，1 ) ，( 5 ，2 ) ，( 1 5 ，2 ) ，( 9 ，1 ) ，( 2 0 ，1 ) ，( 2 1 ，2 ) ) ( r o o d 2 7 ) ( ( o ，o ) ，( 1 0 ，1 ) ，( 2 1 ，o ) ，( 0 ，2 ) ，( 1 ，2 ) ，( 1 8 ，1 ) ) ( r o o d 2 7 ) 易验证仪贸1 ) 是一个( 8 l ，g l 1 ) 一g d 凸 引理2 4 存在g l h g d ( 4 3 ) 证明：取x = z 4xz 3 ，其组集为够= z 4 f ) if z 3 ) ，可定义区组集如下： 舅l ：( ( 0 ，0 ) ，( o ，1 ) ，( 0 ，2 ) ，( 1 ，o ) ，( 1 ，1 ) ，( 1 ，2 ) ) ( ( 0 ，0 ) ，( 2 ，1 ) ，( 2 ，2 ) ，( 1 ，o ) ，( 3 ，1 ) ，( 3 ，2 ) ) ( ( 2 ，o ) ，( 0 ，1 ) ，( 2 ，2 ) ，( 3 ，o ) ，( 1 ，1 ) ，( 3 ，2 ) ) ( ( 2 ，0 ) ，( 2 ，1 ) ，( o ，2 ) ，( 3 ，0 ) ，( 3 ，1 ) ，( 1 ，2 ) ) 9 易验证贝1 ) 是一个g l h g d ( 4 3 ) 凸 引理2 5 对任意正整数u 3 ，存在( 2 4 u + l ，g l 1 ) 一g d 证明：令点集x = ( z 0xz 4 ) u o o j 由引理1 1 知，当g = 6 且甜3 时，存在 3 一g o d ( 6 ”) = ( z 0 ，u 0 ：0 j f 甜一l 】，彩，其中乃= 6 j , 6 j + l ，町+ 5 ( 0 js1 , g 1 ) ， 由引理2 2 和2 4 知，存在以下设计： ( i ) ( 4 哟i + l ，g l ，1 ) 一g d = ( 2 5 ，g 1 ，1 ) 一g d = ( a 0 z i ) u o o ，夕b ) ，y x j ，0 - ，甜一l ； ( i i ) g l h a d ( 4 3 ) = 俾z 4 ，“j xz 4 ：工j 6 f l ，c b ) ，v b 男，i b i = 3 设q = ( u 丑e $ c b ) u ( u 矧乃) ，则由引理1 8 和1 1 0 ，易知( 置固是一个( 2 4 u + l ，g i ，1 ) 一 g d ，其中甜之3 口 引理2 6 对任意正整数“4 ，存在( 2 4 u + 9 ，g i ，1 ) 一g d 证明：令点集x = ( 2 & 铲1 ) x 五) u ( a l ，口2 ，a 8 xz 4 ) u j 由引理1 2 知，当g = 6 ， 所= 8 且”4 时，存在3 一g o d ( 6 - 1 8 1 ) = ( 2 & 卜1 ) u a l ，a 2 ，嘲l ， 乃：0 j h 1 ) ，固， 其中乃= i “町+ l ，町+ 5 j ( o5 _ ，u 一2 ) ；x , - i = a i ，a 2 ，a 8 l ，由引理2 2 ，2 3 和2 4 知，存在以下设计： ( i x 4 f + 1 ，g i ，1 ) 一g d = ( 2 5 ，g i ，1 ) 一g d = ( 0 0 7 4 ) u o o ，夕b ) ，y x j ，0 j 甜一2 ； ( i i ) ( 4 阢一i i + l ，g l ，1 ) 一g d = ( 3 3 ，g i ，1 ) 一g d = ( 伐，ix2 ：i ) u f ) ，巩一i ) ； ( i i i ) g l h g d ( 4 3 ) = px7 4 ， 工l z 4 ：工b ，c b ) ，y b 易，l b i = 3 设q = ( u 日e 8 c b ) u ( u 蜀羁) ，则由引理1 8 和1 1 0 知仪锄是个( 2 4 u + 9 ，g i ，1 ) 一g d ， 其中甜4 口 定理2 1 当，兰l ，9 沏o d2 4 ) 且y 2 5 时，( 1 ，g l 1 ) 一g d 存在 证明：由引理2 1 ，2 2 ，2 3 ，2 5 及2 6 ，该定理很容易得证 口 2 2 第二类六点十二边图g 2 ，g 3 ，g 4 的图设计 1 0 c 口口口 图g 2图g 3图g 4 引理2 7 存在( v ，g f ，1 ) 一g d ，其中扛2 ，3 ，4 ，= 2 5 ，4 9 ，7 3 证明：当 ，= 2 5 时，取x = z 2 5 ，可定义区组集分别如下： 舅2 ：( o ，1 ，3 ，7 ，2 0 ，1 1 ) ( m o a 2 5 ) 凡：( o ，1 ，3 ，11 ，7 ，2 0 )咖o d 2 5 ) 乳：( o ，1 ，3 ，8 ，1 2 ，1 8 ) ( r o o d 2 5 ) 易验证陇丑) 为( 2 5 ，g f ，1 ) 一g d ( i = 2 ，3 ，4 ) 当v = 4 9 时，取x = z 4 9 ，可定义区组集分别如下： 凫：( o ，1 ，3 ，7 ，1 2 ，2 0 ) ( r o o d 4 9 ) ( o ，9 ，3 5 ，2 2 ，4 3 ，2 5 ) ( r o o d 4 9 ) 凡：( o ，1 ，3 ，7 ，1 2 ，2 7 ) ( r o o d 4 9 ) ( 0 8 ，2 l ，4 0 ，2 6 ，1 6 ) ( r o o d 4 9 ) 乳：( o ，1 ，3 ，7 ，1 2 ，3 9 ) ( r o o d 4 9 ) ( 0 ，1 5 ，3 5 ，1 7 ，4 3 ，1 9 ) ( r o o d 4 9 ) 易验证仪贝i ) 为( 4 9 ，g f ，1 ) 一g d ( f = 2 ，3 ，4 ) 当，= 7 3 时，取x = z 7 3 ，可定义区组集分别如下： 凫：( o ，1 ，3 ，7 ，1 2 ，1 8 ) ( r o o d 7 3 ) ( 0 ，8 ，2 1 ，4 9 ，3 0 ，4 6 ) ( r o o d7 3 ) ( 0 ，2 3 ，5 9 ，2 0 ，6 4 ，3 3 ) ( r o o d7 3 ) 巩：( o ，1 ，3 ，7 ，1 2 ，2 0 ) ( r o o d7 3 ) ( 0 ，9 ，3 8 ，5 7 ，4 3 ，1 7 ) ( r o o d7 3 ) ( o ，1 8 ，4 i ，6 3 ，4 2 ，2 7 ) ( r o o d 7 3 ) 凡：( 0 ，1 ，3 ，7 ，1 2 ，1 8 ) ( r o o d 7 3 ) ( o ，1 3 ，4 6 ，2 l ，5 6 ，3 2 ) ( r o o d7 3 ) ( o ，1 6 ，4 5 ，1 9 ，5 3 ，2 2 ) ( r o o d7 3 ) 易验证( 五贝f ) 为( 7 3 ，g f ，1 ) 一g d ( f = 2 ，3 ，4 ) 引理2 8 存在g f h g d ( 6 5 ) ，其中f = 2 ，3 证明：取x = z 6 z 5 ，其组集为醪= f 磊 f l if z 5 l ，可定义区组集分别如下： 爿2 ：( ( 0 ，0 ) ，( 0 ，2 ) ，( 0 ，3 ) ，( o ，1 ) ，( 1 ，3 ) ，( 0 ，4 ) ) ( ( 0 ，1 ) ，( 2 ，3 ) ，( 4 ，4 ) ，( 3 ，2 ) ，( 5 ，4 ) ，( 3 ，0 ) ) ( ( o ，2 ) ，( 3 ，4 ) ，( 4 ，o ) ，( 2 ，3 ) ，( 5 ，0 ) ，( 0 ，1 ) ) ( ( 0 ，3 ) ，( 4 ，0 ) ，( 2 ，1 ) ，( 4 ，4 ) ，( 3 ，1 ) ，( 1 ，2 ) ) ( ( 0 ，4 ) ，( 0 ，1 ) ，( 1 ，2 ) ，( 3 ，o ) ，( 2 ，2 ) ，( 5 ，3 ) ) ( r o o d 6 ) ( r n o d 6 1 ( r o o d 6 ) ( r o o d 6 ) ( r o o d 6 ) 口 贸3 ：( ( o ，o ) ，( o ，3 ) ，( 0 ，2 ) ，( o ，1 ) ，( o ，4 ) ，( 1 ，2 ) ) ( ( o ，1 ) ，( 2 ，4 ) ，( 3 ，3 ) ，( 5 ，2 ) ，( 1 ，o ) ，( 4 ，3 ” ( ( o ，2 ) ，( 4 ，0 ) ，( 0 ，4 ) ，( 3 3 ) ，( 2 ，1 ) 。( 1 ，4 ) ) ( ( o ，3 ) ，( 1 ，1 ) ，( 4 ，0 ) ，( 2 ，4 ) ，( 4 ，2 ) ，( 5 ，0 ) ) ( ( 0 ，4 ) ，( 4 ，2 ) ，( 2 ，1 ) ，( 1 ，0 ) ，( 5 ，3 ) ，( 3 ，1 ) ) ( r o o d 6 ) ( r o o d6 ) ( r o o d 6 ) ( r o o d 6 ) ( r o o d 6 1 易验证( x , 3 1 i ) 是一个g f h g d ( 6 5 ) ( f = 2 ，3 ) 口 引理2 9 存在( 1 4 5 ，g ，1 ) 一g d ，其中i = 2 ，3 证明：令点集x = ( z 2 4 z 6 ) u 由引理1 7 知，当g = 4 且豁= 6 时，存在 5 一a d d ( 4 6 ) = ( z 2 , t ，：0 歹s5 j ，动，其中恐= l 劬4 j + l ，句+ 2 ，彭+ 3 j ( 0sj 5 ) ，由 引理2 7 和引理2 8 知，存在以下设计： ( i ) ( 6 i + l ，g i ，1 ) 一g d = ( 2 5 ，g i ，1 ) 一g d = ( q 0 z ；) u l ，为) ，v 玛，0 js5 ； ( i i ) g t h g o ( 6 5 ) = ( 占z 6 ，“x 7 - 6 ：工召j ，c b ) ，y b 易，i b i = 5 设q = ( u b 臼c b ) u ( u 贝，) 则由引理1 8 和1