（基础数学专业论文）两个六点九边图的填充和覆盖设计.pdf

摘要 设a 凰是a 重口点完全图，其任二不同顶点z 和问都恰有a 条边f z ，y 相 连对于有限简单图g ，图设计g g d ( ) ( 图填充设计g p d ( ) ，图覆盖设计g g d ( u ) ) 是一个序偶( x ，8 ) ，其中x 是虹，的顶点集，层为k ，中同构于g 的子图 的族( 称为区组族) ，使得中每条边恰好( 至多，至少) 出现在层的a 个区组中 一个填充设计( 覆盖设计) 被称作是最大( 最小) 的，如果不再存在同阶数的其它填 充( 覆盖) 设计含有更多( 更少) 的区组本文主要研究两个六点九边图的最大填充 设计和最小覆盖设计问题在统一的构作方法下，对于所有可能的 和a 给出了它 们相应的最大填充设计和最小覆盖设计 另外，本文还讨论了线性不定方程。+ o + 6 z = n 的非负整数解的计数问题，给 出了统一的计数公式，并对其中n6 的情形给出了简洁的表达 关键词：图填充设计，图覆盖设计，线性不定方程 河北师范大学硕士论文 a b s t r a c t ac o m p l e t em u l t i g r a p ho fo r d e rua n di n d e xa ，d e n o t e db ya k 0 ，i sa nu n d i r e c t e dg r a p h w j t h ”v e r t i c e 8 ，w h e r ea n yt w od i s t i n “v e r t i c e s 茁a n d 可a r ej o i n e db y e d g e s 扛，可) l e t gb ea 丘n i t e8 i m p l cg r a p hag r a p hd e s 遮hg - g d 扣) ( g r a p hp a c k i n gd e s i g ng p d a ( ) ， g r a p hc o v e r i n gd e s i g ng a d ( ) ) o f 入，i sap a i r ( x ，8 ) w h e r exi st h ev e r t e xs e to fk ， a n d 口i sac o l l e c t i o no f8 u b g r 印h so f 。f “，c a u e db l o c k s ，s u c ht h a te a c hb l o c ki si s o m o p h i ct o ga n da n yt w od i s t i n c tv e r t i c e si nk ，a r ej o i n e de x a c t l y ( a tm o s t ，a “e a s t ) i nab l o c k so f b ap a c k i n g ( c o v e r i n g ) d e s i g ni ss a i dt ob ei n a x i m u m ( m i n i m u m ) i fn oo t h e rs u c hp a c k i n g ( c o v e r i n g ) d e s l g no ft h es a m eo r d e rh a sm o r e ( f e w e r ) b l o c k si nt i l i sp a p e r ，t h em a _ ) ( i m u m p a c k i n gd e s i g na n dt h em i n i m u nc o v e r i n gd e s i g no ft w og r a p h sw i t hs i xv c r “c e 5a n dn i n e e d g e sa r er e 8 e a r c h e d b ya nu n i f i e dm e 幽o d ，w es o l v et h ep r o b l e m so ft h em a x i m u m p a c k i n gd e s 培na n dt h em i n i m u mc o v e r i n gd e s i g nf o ra up o s s i b l e 口a n da i na d d i t i o n ，t h ee n u m e r a t i o np r o b l c mf o rn o n n e g a “v ei n t e g e rs o l u t i o n so ft h ee q u a _ t i o no + o 掣+ 6 z = 礼i sd i s c u s s e d a | l dt h eu n i 6 e de n u m e r a t i o nf o r m u l a sa r eo b t a i n e d f u t h e r m o r e ，ab r i e fd e s c r i p t i o no ft h ef o r m u l a sf o rt h ec a s en 1 6i sg i v e n k e y 、o r d s ：g r a p hp a c l 【i n gd e s 培n ，g r 印hc o v e r i n gd e s i g n ，l i n e a ri n d 胡n i t ee q u a t i o n 河北师范大学硕士论文 1引言 本文共分为两部分，第一部分研究了两个六点九边图的填充设计和覆盖设计，第 二部分主要讨论了一类线性不定方程非负整数解的计数问题 1 设g 是一个由n 个顶点和e 条边组成的简单图a 凰是a 重 点塞全堕，其 任二不同顶点z 和f 问都恰有 条边 z ，相连( 因本文不涉及有向边，边和，g ) 也可记作( z ，) ) 所谓的里塑g g d ( ”) ( 塑垫查堡盐g p d ( ”) ，里壅堇堡塑g - g _ d ( ) ) 是一个序偶( x ，8 ) ，其中x 是蜀，的顶点集，b 为凰，中同构于g 的子图 的族( 称为区组族) ，使得中每条边恰好( 至多，至少) 出现在目的 个区组中 显然，存在g - g d ( 口) 的必要条件为； ；瑟 三0 ( 黜 其中d 表示g 中各顶点度数的最大公因数一个填充设计( 覆盖设计) 被称作是 最大( 最小) 的，如果不再存在同阶数的其它填充设计( 覆盖设计) 含有更多( 更少) 的区组最大的填充设计( 最小的覆盖设计) 的区组数称为填充数( 覆盖数) ，记作 p ( ，g ， ) ( c ( ，g ，a ) ) 显然， p ( ”，g ，a ) su ( ”，g ，a ) = l 每爱崭j f 高等蟊* 1 = y ( ”，g ， ) c ( 。，g ， ) ( + ) 这里h ( m ) 分别表示满足g z ( 。) 的最大( 最小) 整数本文称填充 数为u ( ”，g ，a ) 的填充设计( 覆盖数为y ( ，g ，a ) 的覆盖设计) 为正则的，简记为 0 尸风( ) ( 0 g d ( ) ) 显然，图设计g g d ( ) 存在当且仅当p ( ，g ， ) = c ( u ，g ，a ) 因此，一个图设计g g d ( ”) 可看成是一个正则的填充设计或正则的覆盖设计 填充设计g p d ( ) = ( k p ) 的余边图厶( p ) 是a 凰的子图，其边集是p ( 填充 设计中各区组所对应子图的多重并) 在a 凰中的补当_ p 最大时，ll ( p ) i 称为此 填充设计的余边数，记作h ( ) 类似地，覆盖设计g g d ( ”) = ( k c ) 的重边图风( c ) 也是a 凰的子图，其边集是a 凰在c ( 覆盖设计中各区组所对应子图的多重并) 中 的补当c 最小时，i j h ( c ) l 称为此覆盖设计的重边数，记作n ( ) 为简便，l ) 与f ( ) 通常简记为三 与h ，而r ( c ) 与n ( ”) 则简记为r 与n 称a ，m ，一m = ( 鱼置，e ) 为一个生童童全塑，其中诸墨两两不交，置l = m ，且v $ 五，暑，玛，边扣， 在曰中出现a 次( 当i j 时) 或不出现( 当 河北师范大学硕士论文 i = j 时) 图g 的型为t = n n j n 的鲎塑堕堡! 指的是a m 。，m 的一个分 拆，所分拆成的各子图均与g 同构为方便，带洞图设计的型t 常被表达为指数 形式，例如n f l n 铲n 静表示n l 长洞出现1 次，n 。长洞出现次这样的 带洞图设计常记为g 一日d 口) 或g 一日d ( n f l n ；2 n 静) 一个g - 日d ( 1 ”一” 1 ) 称为 不完全的图设计，记为g j d ( ”，w ) = 渺，w ，4 ) ，其中i v i = 口， w l = w ，且w c v 为 简洁，当a = 1 时，符号g d ，h d ，d ，o p d ，0 g d 的下标a 均可省略 国内外对图填充设计和图覆盖设计的研究已有相当一段时间，主要涉及的图有 蚝，甄，飓，五点图，六点困等文献【1 7 l 解决了不超过四点的完全圜的填充和覆 盖设计问题1 9 9 4 年，殷剑兴教授解决了困凰的填充设计问题1 9 9 9 年，葛根 年教授解决了加一条悬边的五点星图的填充设计问题对于六点简单图的填充和覆 盖设计问题，我的导师康庆德教授和我的师兄、师姐们进行了研究文献f 4 ，8 】已 对全部六点七边图的困设计、图填充和覆盖设计问题给出了系统完整的解决文献 f 1 0 ，1 4 1 对全部六点八边图的图设计问题给出了完整的解次，而对填充和覆盖设计 的研究也已开始文献 9 ，1 1 已对全部二十个不合孤立点的六点九边图中九个图的 图设计问题给出了系统完整的解决，文献f 6 l5 完全解决了其中四个图的填充和覆 盖设计 本文第二章和第三章则对如下两个六点九边图g 和日的填充和覆盖设计进行 研究，分别构作了其最大填充设计和最小覆盖设计为方便，作为设计中的区组， 它们按照各点的标注分别被记为( o ，6 ，c ，d ，e ，) ， ! ! 。哥 图g 引理1 1 【9 】存在g g d ( u ) 仁争 引理1 2 9 j 存在盯g d ( 口) 聿专 图h a u ( u 1 ) 三0 ( m o d1 8 ) ，”6 fu 6 ； a 。( 一1 ) io ( m o d l 8 ) ； 【( ， ) ( 1 ，9 ) 本文将在此基础上研究它们的填充设计与覆盖设计 2 河北师范大学硕士论文 2 当t 2 时，形为n l 。1 + n 2 。2 十+ 啦规= n 的整系数方程称为垡：堡丕窒查墨， 又称为丢番图方程，如何确定它的非负整数解个数的问题是组合计数理论研究的一 个课题迄今为止，人们已经对于 0 1 + 0 2 + - - + 规：n ， z + 2 馨+ 3 名= n ， o + 2 可+ 4 z = 钆， z + 2 + 5 名= n ， z + 3 可+ 4 z = n ， 等有限个不定方程给出了简洁的计数表达式( 见 7 】) 本文将在此基础上进一步讨论 形为z + o f + 如= 的线性不定方程非负整数解的计数问题，并给出了较一般的简 洁计数公式 3 河北师范大学硕士论文 4 2图g 的填充和覆盖设计 以下，在构作日d ，d ，d p d ，0 g d 的区组集时，常应用循环群或循环群的直积 作为自同构群对于基区组b ，当自同构群为时， 且m o dm 表示区组族 b + t ：i z m ) 而当自同构群为z m 磊时，以缩写记号 b m o d ( m ，n )表示区组族f b 十( i ，j ) ：i z 。，j 磊) ， 口m o d ( m ，一)表示区组族 口+ ( z ，o ) ：t ) ， b m o d ( 一，n )表示区组族 b + ( o ，j ) ：j 况) 至于设计的点集中不属于此自同构群的元，则在自同构群作用下保持不变，它们通 常被记为o 。或o 。t 本章将涉及以下的图： 个顶点的路最，个悬点的星图k l m 个顶点的圈瓯， 图g 和图日的不交并g u 日，n 个图g 的不交并n g 2 1 填充与覆盖设计的一般构作方法 引理2 1 对于图g 和正整数 ，u ，若存在有g 一儿) ( + w ，u ) 和g 一0 p _ d ) ( g d g d ) ) 则存在有g d 尸d ( + 叫) ( g d e d ( + u ) ) ，且它的余( 重) 边图与前者一致 证明：设已知有g 一，d ( 九+ u ，u ) = ( 磊u z l ，。2 ，z 。 ，廖) 及g 一0 尸d ( u ) = ( p t ，z 2 ， ，。 ，) ，则( z i u z l ，z 2 ，。) ，8 u 8 7 ) 即为所需要的g d p d + u ) 显然， 它的余边图与g o p d ) 是一致的类似可说明g 一0 g d ( + u ) 的存在性 口 引理2 2 【4 】对于图g 和正整数 ，“j ，m ，a ( m22 ) ，若存在有g 一日d ( ”) 和g j d ( h + ，u ) ，月i j ( 1 ) 当g 一0 p d ) 或g * 0 p d ( h + u ) 存在时，g - 0 p d ( m + “j ) 亦存在 ( 2 ) 当g 0 e d ) 或g - 0 g d ( + u ) 存在时，g 一0 g d ( m + u ) 亦存在 引理2 ，3 【4 j 对于图g 和正整数口，a ，弘，设x 是一个u 元集， ( 1 ) 若存在g d p 巩( ) = ( x ，p ) ，它的余边图二 ( p ) cg ，则存在有g 一0 g 仇( ) ， 其重边图为g 厶伊) ( 2 ) ，若存在g ，0 p _ d ( ) = ( x ，p ) 和g o 尸d p 如) = ( x ，p ) ，它 门的余边图分别为 厶 ( p ) 和l 。( p 7 ) ，如果l 二 ( p ) f + i l p ( p 7 ) i = f + p ，贝l j 存在有g o 尸d + 卢扣) = ( x ，p u p ) ， 河北师范大学硕士论文 它的余边因为三 ( p ) u 三。( p ，) ( 3 ) 若存在g 一0 g d ( ) = ( x ，c ) 和g 。o g 巩( u ) = ( x ，c ，) 其重边图分别为风( c ) 和q 。( ) ，如果i r ( c ) j + l r p ( c 川= r + p ，则存在有g - 0 g d + p ( ) = ( x ，c uc ) ，其重 边图为月 ( c ) u r 。( c ，) ( 4 ) 若存在g 一0 p d ( ) = ( x ，p ) 和g - o g d 。( ) = ( x ，c ) ，它们的余边图和重边图 分别为三 伊) 和r 。( c ) ，如果l ( p ) 3 吼( c ) 且l l ( p ) i i r 。( c ) l = f + ，则存在有 g 一0 p d + 。如) = ( x ，p u c ) ，它的余边图为l ( p ) r “( c ) ( 5 ) 若存在g - o a d ( ) = ( x ，c ) 和g 0 p d 。( ) = ( x ，p ) ，其重边图和余边图分 别为r ( c ) 和“垆) ，如果地( c ) “( p ) 且i 嘞( c ) l i “( p ) i = n + p ，则存在有 g 一0 e d + 。( ) = ( x ，p u c ) ，其重边图为r ( c ) l “( p ) 引理2 4 对给定的阶数u ，设a = a o 是使得g g d ( ) 存在的最小正整数若对 15s o 一1 ，g 一0 p 风( ) 和g - 0 g 风( ) 皆存在，则对于任意的正整数a ，g 一 0 p d ( ) 和g 一0 g d ( ) 都存在 证明：设g g d 。( 口) = ( x ，b ) va o ，令a ；s ( m o da o ) ，其中o 5sa o 一1 由 已知，对于1 茎s 茎a o 一1 ，存在g 0 p d 。( ) = ( x ，p ( s ) ) 及g - d g d 。扣) = ( x ，c ( s ) ) 则： 当s o 时， ( x ，( 絮8 ) u p ( s ) ) 即是一个g o p 仇( ) ， ( x ，( 每孑日) u c ( s ) ) 即是一个g d c d 扣) ， 当s = o 时， ( x ，砉8 ) 即是g g d ( ) ，它亦是g - o ，p d ( 口) 和g d g d ( ) 口 对于本文所讨论的图g 和图日，由引理1 1 ，1 2 和2 4 可以确定出我们需要讨论 的 和a 的范围应满足； ( 1 ) 当 ；3 ，4 ，6 ，7 ( m o d9 ) 且u 6 时，a o = 3 ，仅需对a = 1 ，2 构作； ( 2 ) 当 ；2 ，5 ，8 ( m o d9 ) 且u 6 时，a o = 9 ，仅需对l a 8 构作； ( 3 ) 对于图日，由于日一g d ( 9 ) 不存在，需单独给出 = 9 ，a = 1 时的最大填充设 计和最小覆盖设计 2 2a = 1 的填充和覆盖 引理2 5t 3 且t 8 时，存在g 一日d ( 1 8 4 ) 及g 一日d ( 9 ) 证明：( 1 ) 在点集z 1 8 蜀上构作g 一日d ( 1 8 4 ) ，区组集由以下基区组i n o d ( 1 8 ，4 ) 构 5 河北师范大学硕士论文 成 5 1 兰二谚翼： 二 1 3 2 它还可以应用上节所述标注，用代数式简洁地表达为： ( 0 0 ，1 2 1 ，1 7 0 ，3 2 ，1 1 l ，8 2 ) ，( 5 l ，0 3 ，6 1 ，1 3 2 ，9 l ，6 0 ) ，( 2 1 ，0 2 ，1 0 ，0 3 ，1 1 i ，o ) m o d ( 1 8 ，4 ) 本文以下均用此简洁的形式表达，这里最后的区组中点。在下标模4 时依次取为 0 0 ，0 l ，9 2 ，9 3 ( 2 ) 由【9 知，t 3 且t 6 ，8 时，存在g h d ( 9 。) ， 下面在点集玩z 6 上构作g 一日d ( 9 6 ) = ( z 9xz 6 ，4 ) ，它的1 3 5 个区组由以下1 5 个基区组m o d9 产生； ：( o o ，0 l ，1 2 ，8 3 ，1 4 ，5 5 ) ，( 6 5 ，0 0 ，1 l ，0 2 ，0 3 ，8 4 ) ，( 2 4 ，8 5 ，o o ，2 1 ，6 2 ，7 3 ) ， ( 7 3 ，7 4 ，7 5 ，0 0 ，3 l ，5 2 ) ，( 1 2 ，0 3 ，5 4 ，4 5 ，o o ，4 i ) ，( 5 l ，1 2 ，5 3 ，8 4 ，0 5 ，0 0 ) ， ( 3 2 ，o l ，6 3 ，8 5 ，7 2 ，4 4 ) ，( 2 5 ，0 0 ，6 4 ，3 2 ，l o ，6 3 ) ，( o o ，6 1 ，7 3 ，5 4 ，2 0 ，4 3 ) ， ( 1 0 ，8 1 ，0 0 ，8 2 ，2 0 ，6 2 ) ，( o o ，1 3 ，l o ，2 4 ，7 0 ，1 5 ) ，( 8 1 ，3 3 ，o o ，0 4 ，3 1 ，6 5 ) ， ( 1 1 ，2 5 ，0 l ，3 3 ，3 l ，8 4 ) ，( 0 2 ，4 5 ，4 2 ，8 4 ，3 2 ，6 3 ) ，( 0 4 ，2 5 ，5 3 ，0 2 ，7 5 ，7 1 )m o d ( 9 一) 口 引理2 6 当u = 2 ，3 ，8 ，1 1 ，1 2 ，1 3 时，存在g 一，d ( 9 + w ，) 证明；每个g j d ( 9 + ，u ) 含w + 4 个区组 世兰：( 邑历) u z 1 ，z 2 ) ； ( o o ，2 l ，2 2 ，l o ，1 2 ，z 1 ) ，( o o ，2 2 ，1 2 ，吼，1 l ，。2 )m o d ( 3 ，一) 世：函u 茹l ，2 ，茹3 ) ； ( 2 ，4 ，3 ，o ，6 ，7 ) ，( o ，l ，2 ，z 2 ，3 ，茁1 ) ，( 4 ，5 ，6 ，z 1 ，7 ，。2 ) ，( 3 ，2 ，l ，8 ，。2 ，6 ) ， ( 5 ，o ，7 ，8 ，4 ，z 3 ) ，( 8 ，6 ，4 ，1 ，7 ，z 3 ) ，( 1 ，3 ，7 ，5 ，2 ，茁3 ) 型三垒：z 9 u ( z 1 ，z 2 ，z 3 ，z 4 ) ； ( 0 ，1 ，2 ，$ 2 ，3 ，z 1 ) ，( 4 ，5 ，6 ，。l ，7 ，z 2 ) ，( o ，2 ，3 ，z 4 ，1 ，z 3 ) ，( 4 ，3 ，7 ，1 ，6 ，o ) ， ( 4 ，2 ，z l ，8 ，z 2 ，6 ) ，( 8 ，3 ，z 3 ，5 ，茁4 ，6 ) ，( 4 ，7 ，6 ，茁3 ，8 ，z 4 ) ，( 0 ，7 ，2 ，5 ，l ，8 ) 型壹：z 9 u 茁1 ，。2 ，- ，。5 ； ( 0 ，l ，6 ，3 ，2 ，。1 ) ，( 7 ，。3 ，o ，5 ，z 5 ，4 ) ，( 6 ，7 ，o ，。5 ，8 ，z 1 ) ，( 8 ，6 ，z 3 ，2 ，o ，z 2 ) 6 塑些堑至盎堂塑主堡圭 7 ( 1 ，2 ，7 ，。2 ，3 ，z 5 ) ，( 1 ，4 ，z 2 ，5 ，3 ，z 4 ) ，( 1 ，8 ，2 4 ，7 ，3 ，2 3 ) ，( 5 ，。4 ，o ，6 ，4 ，2 ) ， ( 3 ，4 ，o ，8 ，5 ，z 1 ) 型剑：曷u 0 1 ，0 2 ，一，z 6 ； ( 0 ，l ，4 ，5 ，2 ，z 1 ) ，( 3 ，4 ，o ，z 6 ，5 ，。1 ) ，( 6 ，7 ，0 ，z 5 ，8 ，。1 ) ，( 0 ，2 ，石6 ，8 ，5 ，z 2 ) ， ( 3 ，1 ，z 5 ，2 ，4 ，茹2 ) ，( 6 ，8 ，z 4 ，4 ，7 ，。2 ) ，( 1 ，8 ，3 ，7 ，2 ，z 3 ) ，( 3 ，5 ，7 ，z 3 ，4 ，。5 ) ， ( 3 ，0 ，$ 3 ，6 ，5 ，4 ) ，( 1 ，6 ，2 ，。4 ，7 ，z 6 ) 世三z ：局u ( z l ，。2 ，一，z 7 ； ( 0 ，1 ，罩7 ，6 ，2 ，嚣1 ) ，( 3 ，4 ，6 ，z 6 ，5 ，z 1 ) ，( 6 ，7 ，o ，z 5 ，8 ，卫1 ) ，( 5 ，1 ，。5 ，3 ，6 ，z 2 ) ， ( o ，2 ，3 ，茁2 ，4 ，。7 ) ，( 1 ，8 ，。2 ，7 ，z 6 ，2 ) ，( 5 ，6 ，。4 ，8 ，4 ，。3 ) ，( 8 ，0 ，3 ，茁3 ，1 ，茁6 ) ， ( 4 ，2 ，。3 ，7 ，5 ，。5 ) ，( 7 ，3 ，8 ，。7 ，5 ，嚣4 ) ，( o ，4 ，1 ，z 4 ，2 ，5 ) 型三墨：z 9 u 1 ，z 2 ，- ，z 8 ； ( 0 ，1 ，8 ，z 5 ，2 ，z 1 ) ，( 3 ，4 ，2 ，。7 ，5 ，z 1 ) ，( 6 ，7 ，o ，z 8 ，8 ，z 1 ) ，( 3 ，5 ，o ，。2 ，7 ，。5 ) ， ( 8 ，2 ，z 6 ，5 ，6 ，z 2 ) ，( 7 ，1 ，茁2 ，4 ，8 ，茁7 ) ，( 1 ，2 ，7 ，z 3 ，4 ，z 8 ) ，( o ，6 ，。5 ，4 ，5 ，茁3 ) ， ( 7 ，3 ，z 3 ，8 ，o ，z 6 ) ，( 1 ，z 4 ，7 ，5 ，z 8 ，3 ) ，( 8 ，6 ，l ，z 6 ，4 ，。4 ) ，( 3 ，2 ，。4 ，0 ，2 7 ，6 ) 型三! ! ：玩u z 1 ，z 2 ，。1 1 ) ； ( o ，l ，2 ，z 2 ，3 ，z 1 ) ，( 4 ，5 ，6 ，。l ，7 ，$ 2 ) ，( z l o ，2 ，茁l ，8 ，嚣2 ，6 ) ，( 2 ，4 ，1 ，。9 ，6 ，。6 ) ， ( 5 ，7 ，1 ，z 6 ，3 ，。8 ) ，( 4 ，0 ，。6 ，8 ，5 ，z 7 ) ，( 7 ，6 ，3 ，z 7 ，8 ，茁3 ) ，( z l l ，6 ，z 5 ，4 ，z 8 ，8 ) ， ( 1 ，8 ，9 ，3 ，2 ，卫5 ) ，( 1 ，6 ，o ，z 8 ，2 ，茁4 ) ，( 4 ，7 ，8 ，z 4 ，5 ，茁1 0 ) ，( z 1 1 ，7 ，2 ，0 ，z 4 ，3 ) ， ( z l l ，5 ，z 3 ，2 ，z 7 ，1 ) ，( o ，5 ，3 ，z 5 ，7 ，。9 ) ，( 0 ，3 ，4 ，。3 ，l ，茁l o ) 型三1 2 ：面u z l ，。2 ，0 1 2 ) ； ( 0 ，l ，2 ，z 2 ，3 ，z 1 ) ，( 4 ，5 ，6 ，z l ，7 ，z 2 ) ，( z l l ，2 ，z 9 ，5 ，z l o ，0 ) ，( 2 ，7 ，5 ，z 4 ，0 ，z 3 ) ， ( 6 t4 ，8 t z 3 ，3 ，。4 ) ，( 3 ，5 ，z 3 ，l ，。4 ，8 ) ，( 1 ，8 ，o ，。6 ，6 ，z 5 ) ，( 岔1 2 ，4 ，。i i ，3 ，z 7 ，1 ) ， ( 茁1 2 ，o ，z 5 ，5 ，z 6 ，7 ) ，( 4 ，0 ，3 ，z 8 ，2 ，。7 ) ，( 6 ，7 ，8 ，z 7 ，5 ，嚣8 ) ，( 3 ，6 ，0 ，z 9 ，1 ，。l o ) ， ( 7 ，4 ，2 ，。i o ，8 ，z 9 ) ，( 。1 2 ，2 ，z 1 ，8 ，z 2 ，6 ) ，( 6 ，。l l ，7 ，l ，z 8 ，8 ) ，( 2 ，3 ，7 ，z 5 ，4 ，z 6 ) 鲍三! 墨：z 9 u 茁1 ，z 2 ，一，。1 3 ) ； ( 5 ，7 ，茁4 ，8 ，l ，z l o ) ，( 4 ，5 ，6 ，。l ，7 ，茁2 ) ，( z 1 3 ，2 ，茹1 ，8 ，z 2 ，6 ) ，( 5 ，o ，7 ，z 1 2 ，1 ，z 7 ) ， ( 6 ，3 ，l ，z 3 ，2 ，。1 2 ) ，( 。9 ，8 ，。3 ，o ，z l l ，3 ) ，( 6 ，l ，7 ，z l l ，5 ，。4 ) ，( 2 ，3 ，4 ，z 4 ，0 ，8 ) ， ( o ，1 ，2 ，。2 ，3 ，。1 ) ，( 1 ，5 ，3 ，z 6 ，7 ，z 1 3 ) ，( 5 ，2 ，7 ，茁5 ，l ，z 9 ) ，( z 1 3 ，o ，z 5 ，3 ，嚣1 0 ，4 ) ， ( 6 ，7 ，3 ，z 7 ，4 ，。9 ) ，( z 5 ，6 ，卫8 ，8 ，茁1 2 ，4 ) ，( 。1 l ，4 ，。6 ，2 ，z 7 ，8 ) ，( 7 ，4 ，l ，z 8 ，5 ，z 3 ) ， ( 6 ，o ，2 ，z l o ，8 ，z 6 ) ，口 河北师范大学硕士论文 弓i 理27 当= 5 ，8 时，存在g f d ( 1 8 + u ，u ) 证明：每个g - ，d ( 1 8 + u ，u ) 含2 + 1 7 个区组 世虫：( z g z 2 ) u l ，z 2 ，z 5 ； ( 1 0 ，0 0 ，。t ，o i ，。2 ，3 0 ) ，( 4 上，3 h z 3 ，0 0 ，。4 ，1 1 ) ，( 4 0 ，5 l ，3 0 ，l l ，z 5 ，o 。) m o d ( 9 ，一) 笪三里：( 历玩) u 。l ，z 2 ，z 8 ； ( o o ，z 1 ，2 2 ，2 3 ，z 2 ，o l ( 0 3 ，z 4 ，o o ，0 5 ，3 ，2 l ( 0 1 ，0 7 ，2 3 ，0 5 ，z 8 ，1 2 ( 0 0 ，z 2 ，1 2 ，1 5 ，z 1 ，0 4 ) ， ( 0 2 ，z 5 ，0 5 ，1 4 ，卫6 ，1 3 ) ， ( 1 3 ，茁8 ，1 l ，0 0 ，。7 ，0 4 ) ， ( 0 0 ，。3 ，2 3 ，2 4 ，石4 ，0 2 ) ( 2 5 ，。6 ，2 2 ，o l ，躬，0 0 ) ( o o ，2 2 ，1 3 ，l o ，2 4 ，2 1 ) ( 0 l ，l l ，2 5 ，0 3 ，1 3 ，2 4 ) ，( 0 2 ，0 4 ，1 4 ，1 5 ，0 5 ，1 2 )m o d ( 3 ，一) 口 引理2 8 当u = 6 ，7 ，8 ，7 8 ，7 9 时，存在g 一0 p d ( u ) 和g o c d ( w ) 证明：仅需对每个u 给出g 。d p d ) ，它包含【亟寄皿j 个区组至于相应的g o g d ) 可由引理2 3 ( 1 ) 得到，因诸g 一0 p d ( ) 的余边图l 1 均为g 的子图( 注：以下引 理2 9 和2 1 1 中给出的0 尸d 构造亦满足此条件，均不再赘述) 脚：z 6 ； ( 0 ，1 ，2 ，3 ，4 ，5 ) ； l 1 = ( o ，2 ) ，( 2 ，5 ) ，( 3 ，5 ) ，( 1 ，4 ) ，( o ，4 ) ，( 2 ，4 ) ) 丛三一王：z 7 ； ( o ，l ，2 ，3 ，4 ，5 ) ，( 0 ，2 ，5 ，6 ，1 ，4 ) ； l l = “3 ，5 ) ，( 3 ，6 ) ，( 4 ，6 ) ) 。 幽：磊； ( o ，i ，2 ，3 ，4 ，5 ) ，( 1 ，4 ，0 ，6 ，5 ，7 ) ，( 6 ，7 ，0 ，2 ，5 ，3 ) ； 工l = ( 2 ，4 ) ) 笪三z 曼：( z 3 7 z 2 ) u z 1 ，z 2 ，茁3 ，茁4 ) ； 令 缸= ( 5 l ，3 0 ，3 h 1 0 l ，0 2 ，1 4 0 ) ，尬= ( 0 0 ，1 5 0 ，1 0 ，2 5 l ，8 0 ，2 6 l 慨= ( 8 l ，o o ，1 6 l ，1 2 0 ，。4 ，9 1 ) ，m 4 = ( o o ，1 2 l ，3 6 0 ，2 0 l ，l l ，3 2 螈= ( 0 0 ，1 0 ，3 0 ，7 0 ，1 2 0 ，2 0 0 ) ，慨= ( 4 0 ，2 0 0 ，7 0 ，2 6 l ，1 1 0 ，3 4 坼= ( 0 1 ，3 l ，1 2 l ，2 5 1 ，4 1 ，1 4 1 ) ，慨= ( o o ，1 l ，1 3 0 ，3 0 ，。3 ，5 1 ) = ( 9 0 ，3 l ，4 0 ，1 1 ，z h o o ) i 则0 尸d ( 7 8 ) 的区组集为尬+ z ，i 1 ，2 ，9 ) ，z 毛7 ，其中+ o 中 的1 4 0 与蝎+ o 中的。3 对换，m l + 1 中的z 1 与坞+ 1 中的6 1 对换 8 河北师范大学硕士论文 五1 = ( z 1 ，z 2 ) ，( z l ，z 4 ) ，( 。2 ，工4 ) ，( z 2 ，1 4 0 ) ，( 。3 ，z 4 ) ，( z 3 ，6 1 ) ) 型三z 坌：( z 1 9 z 4 ) u 。1 ，z 2 ，z 3 ) ； ( o o ，1 6 1 ，0 2 ，9 0 ，1 2 ，1 0 1 ) ，( o o ，5 l ，o l ，3 3 ，2 2 ，6 2 ) ，( 1 l l ，3 2 ，o o ，7 0 ，0 3 ，7 3 ) ， ( 0 0 ，2 1 ，2 2 ，4 0 ，3 2 ，1 1 ) ，( 0 2 ，1 2 ，1 2 2 ，7 3 ，2 3 ，6 2 ) ，( 4 0 ，0 1 ，6 0 ，1 3 2 ，5 0 ，1 8 2 ) ， ( 0 1 ，3 l ，1 5 1 ，1 0 3 ，8 l ，1 6 3 ) ，( 8 0 ，。2 ，0 3 ，1 2 ，4 2 ，0 1 ) ，( 0 2 ，黝，9 1 ，0 0 ，1 3 ，2 3 ) ， ( 5 0 ，0 1 ，4 l ，9 2 ，3 1 ，4 3 ) ，( 0 0 ，0 3 ，2 0 ，8 3 ，1 3 0 ，1 0 3 ) ，( 0 0 ，9 3 ，1 7 0 ，5 3 ，6 l ，1 5 3 ) ， ( 0 l ，1 6 2 ，0 0 ，8 1 ，2 0 ，7 2 ) ，( 0 2 ，5 3 ，o l ，1 2 2 ，1 6 l ，8 3 ) ，( 2 3 ，0 0 ，1 2 ，4 3 ，1 0 2 ，8 0 ) ， ( 0 3 ，z l ，7 0 ，o l ，2 l ，0 2 ) ，( o l ，1 4 2 ，1 6 2 ，6 3 ，1 5 2 ，1 2 3 ) ，( o o ，1 0 ，3 0 ，6 d ，9 1 ，0 1 ) m o d ( 1 9 ，一) ； 三l = ( z l ，z 2 ) ，( 。2 ，。3 ) ，( l ，z 3 ) ) 口 引理2 9 当“= 2 ，3 ，4 ，5 时，存在g o p d ( 9 + “) 和g - 0 g d ( 9 + “) 证明；每个g o p d ( 9 + ) 应包含u + 4 + l 掣j 个区组 垃三上：此时的g o p d ( 9 + 2 ) 即为引理2 6 给出的g j d ( 9 + 2 ，2 ) ，而l 1 = ( 。l ，z 2 ) ) 堂三上：z 1 2 ； ( 0 ，1 ，2 ，3 ，4 ，5 ) ，( 0 ，2 ，4 ，6 ，l ，7 ) ，( o ，4 ，l ，8 ，2 ，9 ) ，( 1 ，9 ，3 ，l o ，o ，1 1 ) ， ( 2 ，5 ，3 ，1 l ，4 ，1 0 ) ，( 3 ，7 ，5 ，8 ，1 l ，6 ) ，( 8 ，6 ，5 ，9 ，7 ，1 0 ) ； l 1 = ( 4 ，7 ) ，( 7 ，1 1 ) ，( 1 0 ，1 1 ) ) 垡三：z 1 3 ； ( 0 ，1 ，2 ，3 ，4 ，5 ) ，( 3 ，6 ，5 ，8 ，7 ，1 1 ) ，( 0 ，4 ，1 ，8 ，2 ，9 ) ，( 0 ，1 0 ，1 ，l l ，2 ，1 2 ) ， ( 3 ，5 ，2 ，1 0 ，4 ，7 ) ，( 0 ，2 ，4 ，6 ，l ，7 ) ，( 7 ，6 ，9 ，1 0 ，8 ，1 2 ) ，( 5 ，1 1 ，8 ，9 ，l ，1 2 ) ； l l = “3 ，9 ) ，( 7 ，9 ) ，( 4 ，1 1 ) ，( 4 ，1 2 ) ，( 3 ，1 2 ) ，( 9 ，1 2 ) k j 三：z 1 4 ； ( 8 ，1 2 ，l l ，5 ，9 ，6 ) ，( 1 0 ，8 ，3 ，1 3 ，1 2 ，7 ) ，( o ，4 ，l ，8 ，2 ，9 ) ，( o ，1 0 ，1 ，l l ，2 ，1 2 ) ， ( 1 ，9 ，3 ，1 2 ，4 ，1 3 ) ，( 2 ，5 ，3 ，1 0 ，6 ，1 3 ) ，( 3 ，6 ，5 ，7 ，1 3 ，1 1 ) ，( 7 ，1 1 ，8 ，9 ，1 0 ，4 ) ， ( o ，l ，2 ，3 ，4 ，5 ) ，( o ，2 ，4 ，6 ，l ，7 ) ； 三1 = ( o ，1 3 ) ) 口 引理2 1 0 当u = 6 ，7 ，8 ，1 1 ，1 2 ，1 3 时，存在g 一0 p d ( 9 + u ) 和g - 0 g d ( 9 + u ) 证明，由引理2 6 知存在g - f 口( 9 + u ，u ) ，而由引理2 8 和2 9 ，存在g - 0 p d ( w ) 和 g 一0 g 口( u ) ，再由引理2 1 知存在g - d 尸d ( 9 + u ) 和g 一0 g d ( 9 + u ) 口 引理2 1 1 当u = 5 ，6 ，7 ，8 时，存在g 一0 p d ( 1 8 + ) 和g - 0 g d ( 1 8 + u ) 证明：每个g o p 口( 1 8 十w ) 应包含+ 1 7 + 【业铲j 个区组 河北师范大学硕士论文 娅生：( 勿历) u 茁l ，茹2 ) ； ( 0 0 ，1 l ，2 0 ，3 2 ，0 2 ，。1 ) ， ( 0 0 ，6 2 ，5 l ，0 1 ，3 l ，0 2 ) 三1 = ( z 1 ，$ 2 ) ) 垒l 三：扬ou 。l ，z 2 ，z 3 ，z 4 ) ； ( o ，l ，z 2 ，1 2 ，茁1 ，5 ) ，( 6 ，1 ( 1 ，2 ，z 2 ，1 3 ，1 6 ，6 ) ，( 7 ， ( 2 ，3 ，。2 ，1 4 ，。1 ，7 ) ，( 8 ，： ( 3 ，4 ，2 ，1 0 ，。1 ，8 ) ，( 9 ，： ( 4 ，0 ，0 2 ，儿，0 1 ，9 ) ，( 5 ，一 ( 0 ，1 0 ，1 1 ，1 7 ，1 6 ，2 ) ，( 5 ( 2 ，1 2 ，1 3 ，1 9 ，1 8 ，4 ) ，( 7 ( 4 ，1 4 ，1 0 ，1 6 ，1 5 ，1 ) ，( 9 ， ( 0 0 ，2 2 ，0 2 ，2 l ，l l ， m o d ( 7 ，一) ； 3 ，z l ，1 5 ，z 2 ，0 3 ) ， l ，l ，1 6 ，茁2 ，8 ) ， 2 ，z l ，1 7 ，z 2 ，9 ) ， 3 ，z 1 ，1 8 ，z 2 ，5 ) ，( 4 ，茁l ，1 9 ，茁2 ，6 ) ，( ，8 ，0 ，1 6 ，1 9 ，1 4 ) ， ，5 ，2 ，1 8 ，1 6 ，1 1 ) ， 7 ，4 ，1 5 ，1 8 ，1 3 ) ； z 2 ) ，( 0 0 ，6 0 ，2 1 ，4 0 ，1 1 ，4 2 ) ， ( 1 2 ，5 ，z 4 ，l o ，z 3 ，1 5 ) ，( 1 4 ，1 8 ，z 4 ，0 ，7 ，6 1 3 ，6 ，z 4 ，1 l ，z 3 ，。1 ) ，( 1 0 ，1 9 ，。4 ，l ，z 3 ，7 1 4 ，7 ，。4 ，1 2 ，。3 ，1 7 ) ，( 1 l ，1 5 ，嚣4 ，2 ，z 3 ，8 1 0 ，8 ，z 4 ，1 3 ，。3 ，1 8 ) ，( 1 2 ，1 6 ，z 4 ，3 ，茁3 ，9 1 1 ，9 ，z 4 ，1 4 ，。3 ，1 9 ) ，( 1 3 ，1 7 ，z 4 ，4 ，z 3 ，5 ( 1 ，1 1 ，1 2 ，1 8 ，1 7 ，3 ) ，( 6 ，9 ，l ，1 7 ，1 5 ，1 0 ) ( 3 ，1 3 ，1 4 ，1 5 ，1 9 ，0 ) ，( 8 ，6 ，3 ，1 9 ，1 7 ，1 2 ) l l = ( z 1 ，z 2 ) ，( 七l ，嚣4 ) ，( z 2 ，。4 ) ，( z 2 ，7 ) ，( z 3 ，嚣4 ) ，( z 3 ，1 6 ) ) 垒l 三z ：( z 1 1 z 2 ) u 茁l ，0 2 ，z 3 ； ( 1 0 ，0 0 ，。1 ，0 1 ，1 1 ，3 0 ) ，( 1 1 ，o o ，。2 ，3 l ，9 l ，4 0 ) ，( o o ，7 lj 。3 ，5 0 ，o l ，4 1 )m o d ( 1 l ，一) ； 工l = ( z 1 ，。2 ) ，( z 2 ，z 3 ) ，( z 1 ，茁3 ) ) 熊三堕：由引理2 7 ，存在g 一，d ( 1 8 + u ，“j ) ；由引理2 8 ，存在g 一0 p d ( u ) 和g 一0 g d ( “j ) ； 进而由引理2 1 知存在g 0 p d ( 1 8 + u ) 和g 一0 g d ( 1 8 + u ) 口 定理2 1 2 当2 u m o d958 且 6 时，存在g 一0 尸d ( u ) 和g o g d ( u ) 证明：令 = 9 + u ，下面对t 分情况讨论，其中u = 2 ，3 ，8 = 0 时，由引理2 8 给出； t = l 时，由引理2 9 ，2 1 0 给出； = 2 时，对于u = 2 ，3 ，4 ，由引理2 1 0 给出；对于u = 5 ，6 ，7 ，8 ，由引理2 1 l 给出； t 3 且8 时，由引理2 2 可知，其中g 一日d ( 9 ) ，g j d ( 9 十，u ) 及g - 0 p d ( 9 + u ) ( g d g d ( 9 + u ) ) 分别由引理2 5 ，26 及2 9 ，2 1 0 给出； t = 8 时，对于w = 2 ，3 ，4 ，由引理2 2 可知，其