（应用数学专业论文）完全t（k1k）三元系的存在性.pdf

河北师范大学硕士学位论文 摘要 设g 是舐的子图在g 的每边外添加一点，将该边扩展为一个3 长圈：且所添加 的点两两不同，均异于g 的诸顶点，这样得到的图形被记为t ( g ) 如果3 的边能够分 拆成与t ( c ) 同构的一些子图 峨) 。，则称这些子图构成一个n 阶的? ( g ) 三元系记每 个皿中与g 同构的子图为五，若2 “的边也能够分拆成 z 。则称这个t ( g ) 三元系是 完全的对于甄的任意子图g ，在b i l l i n g t o n ，l i n d n e r , k n g n k e i 埘和r o s a 等人近期的一些 文章中已经完整地解决了完全t ( g ) 一三元系的存在性问题本文第一部分将对于星图 k 1 ，女讨论同类问题特别，当是素数幂时，我们完整地解决了完全t ( k l ，k ) 一三元系和完 全t ( k i2 k ) 一三元系的存在性问题 设a 甄，是a 重”点完全图，其任二不同顶点问都恰有a 条边相连对于有限简单图 g ，图设计g g d ( v ) ( 图填充g p d ( u ) ，图覆盖g g d ( ) ) 是一个序偶( x ，廖) ，其中x 是 凰的顶点集，且为甄，中同构于g 的子图( 称为区组) 的族，使得凰中每条边恰好( 至多， 至少) 出现在8 的a 个区组中一个图填充( 图覆盖) 被称作是最大( 最小) 的，如果不再存 在同阶数的其它图填充( 图覆盖) 含有更多( 更少) 的区组本文第二部分给出了两个六 点八边图的全部最大填充和最小覆盖 关键词t ( g ) ，f ( g ) 一三元系，完全的r ( g ) 一三元系，星图，图填充，图覆盖 a b s t r a c t l e tgb eas u b g r a p ho f 蚝t h eg r a p ho b t a i n e df r o mg b yr e p l a c i n ge a c he d g ew i t ha3 - c y c l e w h o s et h et h i r ；dv e r t e xi sd i s t i n c tf r o mo t h e rv e r t i c e si nt h ec o n f i g u r a t i o ni sc a l l e da t ( g ) 一t r i p l e a n e d g e d i s j o i n td e c o m p o s i t i o no f3 k i n t oc o p i e s 凰) o ft ( g ) i sc a l l e dat ( g ) t r i p l es y s t e mo f o r d e rn t h ec o p yo fg i n 甄i sc a l l e d 噩，i ft h e s e 正) tf o r ma ne d g e - d i s j o i n td e c o m p o s i t i o no f 玩，t h e nt h et ( g ) 一t r i p l es y s t e mi ss a i dt ob ep e r f e c t r e c e n tp a p e r sb ya u t h o r si n c l u d i n gb i l l i n g t o n 。 l i n d n e r , k i i q f i k q i f e ia n dr o s ah a v ec o m p l e t e l ys o l v e dt h ee x i s t e n c ef o rp e r f e c tt ( g ) 一t r i p l es y s t e m 。 w h e r egi sa n ys u b g r a p ho fk 4 t h ef i r s ts e c t i o no ft h i sp a p e rw i l ld i s c u s st h es a m ep r o b l e mf o rt h e s t a rg r a p hk 1 k e s p e c i a l l y , f o rp r i m ep o w e n ，w eh a v ec o m p l e t e l ys o l v e dt h ee x i s t e n c eo fp e r f e c t t ( k 1 ，) a n dp e r f e c tt ( k z 2 k ) ac o m p l e t em u l t i p l eg r a p h so fo r d e r 口w i t hi n d e xa ，d e n o t e db ya j l ，i s 卸u n d i r e c t e dg r a p h w i t h v e r t i c e s w h e r ea n yt w od i s t i n c tv e r t i c e sa r e j o i n e db yae d g e s l e tgb eaf i n i t es i m p l eg r a p h a g r a p hd e s i g ng g d x ( v ) t g r a p hp a c k i n gg p d x ( v ) ，g r a p hc o v e r i n gg c d x ( v ) ) o fa 甄i s ap a j r ，层) w h e r ex i st h ev e r t e xs e to fj la n dgi sac o l l e c t i o no fs u b g r a p h so fj 0 ，c a l l e db l o c k s ，s u c h t h a te a c hb l o c ki si s o m o r p h i ct oga n da n yt w od i s t i n c tv e r t i c e si nk va r ej o i n e di ne x a c t ( a tm o s t ， a tl e a s t ) ab l o c k so f8 ag r a p hp a c k i n g ( c o v e r i n g ) i ss a i dt ob em a x i m u m ( m i n i m u m ) i fn oo t h e r s u c hg r a p hp a c k i n g ( c o v e r i n g ) w i t ht h es a m eo r d e rh a sm o r e ( f e w e r ) b l o c k s t h es e c o n ds e c t i o no f t h i sp a p e rd i s c u s st h eg r a p hp a c k i n ga n dt h eg r a p hc o v e r i n go ft w og r a p h sw i t hs i xv e r t i c e sa n de i g h t e d g e s k e y w o r d s ：t ( g ) ，t ( g ) t r i p l es y s t e m ，p e r f e c tt ( g ) t r i p l es y s t e m ，s t a rg r a p h ，g r a p hp a c k i n g ， g r a p hc o v e r i n g 学位论文原创性声明 本人所提交的学位论文完全t ( k m ) 一三元系的存在性，是 在导师的指导下，独立进行研究工作所取得的原创性成果。除文中已 经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已 在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：幻阀- 曰 刎年年月7 日 学位论文原创性确认书 学生型园园所提交的学位论文完全丁( 墨) 一三元系的存在 性，是在本人的指导下，由其独立进行研究工作所取得的原创性成 果。除文中已经注明引用的内容外，该论文不包含任何其他个人或集 体已经发表或撰写过的研究成果。 鹰 、笈 、抒 名i ，p 鹳钥 师年 教呷 导 似 指 河北师范大学硕士学位论文 1 l 弓l 言 在j k 中。连接顶点z 和y 的边记为鲫( 或班) ，顶点是毛y ，z 的3 长圈记为( 毛y ，z ) 或，) 设g 是j 厶的子图，定义t ( g ) = ( 口，b ，c ) ：曲e ( g ) ) ，满足： ( i ) 若( 口 b ，c ) t ( g ) 并且a b e ( g ) 。则c 垡y ( g ) ， ( i i ) 若( q ，6 i ，c 4 ) t ( g ) ， = 1 ，2 ，a l b l ，a 2 6 2 e ( g ) ，则c 1 c 2 对于一个t ( g ) 来说，g 的顶点和边被称为其内部，而t ( g ) 一g 的顶点和边被称为其外 部t ( g ) 亦可看作是一个3 长圈( 三元组) 的族 一个n 阶t ( g ) 三元系，记为t ( g n ) ，是一个序偶( x ，b ) ，其中x 是j 靠的顶点集， b 是一旅边不相交的r ( g ) ，它们恰构成了3 j “中所有边的分拆进而，若b 中诸t ( g ) 的内部边( 构成同构干g 的子图) 恰构成x 上j “所有边的分拆，则称此t ( g ，札) 为n 阶完全? ( g ) 三元系，完全丁( g ) 三元系的存在谱即是使得n 阶完全t ( g ) - 三元系存 在的所有正整数n 的集合丁( g ) ，t ( g ) 三元系和完全r ( g ) 一三元系的概念首先是被 s k 吣d 吣i 趣i 和c c l i a d n e r 在文献1 1 3 1 申引进的 带m 个h 长洞的带洞完全t ( g ) - 三元系t ( g ，危”) 是一个序偶( s 1 ，s 。) ，4 ) ，其 中每个s l 都是一个h 元集( 称为勤，诸s t 两两不交，而a 是一族边不相交的丁( g ) ，它们 构成了不同洞的点之问所有联边的分拆定义在集合x y 上的不完全t ( 日) - 三元系 t ( h ，口：h ) 是一个三元组( x ，y ，c ) ，其中yc x ，l x l = 口 y = h ，而c 是一族边不相交的 t f g ) ，它们构成了x y 内及x 与y 间所有边集的分拆 k f i n 砖峨i ，l i n d n e r ( 见【1 3 1 ) 解决了完全r ( 伤) 一三元系的存在谱：l i n d n e r r o s a ( 见【1 4 1 ) 解决了完全t ( k 4 ) 三元系的存在谱；b i l l i n g m n ，l i n d e r 和r o s a ( 见1 ) 解决了完全t ( c 4 ) 一 三元系的存在谱；2 0 0 6 年，b i l l i n g t o n ，l i , d c r ( 见1 2 1 ) 解决了当g 是甄的其它剩余子图时， 完全r ( g ) 三元系的存在谱；康庆德教授和张艳丽，侯英涛( 见【8 】) 解次了当g 是的 边数不大于6 的子图时，完全t ( g ) 三元系的存在谱迄今为止，当g 是j 囊或蚝的子图 且边数不大于6 时，完全的t ( g ) 一三元系的存在谱已经被完全解决本文2 一3 主要研究 的是星图甄，( 见下图k 讨论完全t ( k l ) 一y - 9 。系的存在性 2 完全t ( 研) - 三元系的存在性 设g 是一个由n 个顶点和e 条边组成的简单图 k ，是入重 点完全圈，其任二 不同顶点z 和y 间都恰有a 条边 ，口) 相联( 可简记为x y ) 所谓的图设计g - g d x ( v ) ( 图填充g - p d ( v ) 圈覆盖g c h ( ) 是一个序偶( x ，8 ) ，其中x 是j 0 的顶点集，日为j 0 中同构于g 的子图( 称为区组) 的族，使得凰中每条边恰好( 至多，至少) 出现在8 的a 个区组中显然，存在g g d ( 口) 的必要条件为： 口n ，a v ( v 一1 ) 0 ( m o d2 e ) ，a ( 口一1 ) 1 0 ( r o o d d ) ， 其中d 表示g 中各顶点度数的最大公约数一个圈填充( 囤覆盖) 被称作是最大( 最小) 的， 如果不存在同阶数的其它图填充( 图覆盖) 含有更多( 更少) 的区组最大的图填充( 最小 的图覆盖) 的区组数称为填充数( 覆盖数) ，记作p ( 口，g ，a ) ( c ( 口，g ，a ) ) 显然， p ( 弘g ，a ) 扣，g ，a ) = i 苗鲁斟fsl 寄篱崭l ：y ( 玑g ，a ) sc o ，g ，a ) ( ) 这里h ( f z l ) 分别表示满足y 茹( y 。) 的最大( 最小) 整数y 将填充数为【，( ，g ，a ) 的图填充( 覆盖数为y ( 口，g ，a ) 的图覆盖) 称为正则的，记为o p d ( v ) ( o g d ( 口) ) 显然， 图设计g g d ( v ) 存在当且仅当p ( v ，g ，a ) = c ( v ，g ，a ) 因此，一个图设计g - g d ( v ) 亦是 一个正则的图填充及正则的图覆盖 图填充g p d ( ) = ( v p ) 的余边图厶伊) 是a 墨，的子图，其边集是p ( 图填充中各 区组所对应子图的多重并) 在a k ，中的补当p 最大时，【l x ( p ) 【称为此图填充的余边数， 记作“( ) - 类似地，图覆盖g c d ( 口) = ( e c ) 的重边图r ( c ) 也是a k ，的子图，其边集 是 j 0 在c ( 图覆盖中各区组所对应子图的多重并) 中的补当c 最小时，5 凡( c ) i 称为此 图覆盖的重边数，记作n ( 口) 为简便，以( p ) ，“( 口) 与如( c ) ，n ( 口) 通常可简记为l h h 与 而，r a 本文中对应于图g 。的r a ，h ，厶，凡分别记为r l ，暖，幺，磁 称a ，m ，n t = ( u 墨，e ) 为一个垒重塞全兰塑里，其中f x , l = 礼t ，诸x 两两不交， 且妇五，掣托，边 z ，f 在e 中出现a 次( 当i j 时) 或不出现( 当i = j 时) 图g 的型 为t = n i n 5 n ；的堂塑里矍! 指的是a 。：，m 的一个分拆，所分拆成的各子图均与 g 同构为方便，带洞图设计的型t 常被表达为指数形式，例如n ：1 n 争表示n l 长 洞出现k 1 次，n 。长洞出现次这样的带洞图设计常记为g h d a ( n - 磅) 一个g h d ( 1 v - - w z 0 1 ) 称为不完全的图设计记为g j d ( ， ) = ( v ，w ，一4 ) ，其中i v l = 口，l w f = ，且wcv 为简洁，当a = 1 时，符号g 巩，h d a ，仇，0 p 巩，o c d j , 的下标 a 均可省略 国内外对图填充和图覆盖的研究已有相当一段时间，主要涉及的图有飓，垃，确， 五点图，六点图等y r o d i t t l y ( l 1 7 1 ) 完全解决了不超过四点的完全图的填充和覆盖问 河北师范大学硕士学位论文3 题；1 9 9 4 年，殷剑兴教授解次了完全图j r 5 的填充问题；1 9 9 9 年，葛根年教授解次了加一 条悬边的五点星图的填充问题；文【1 1 】已对全部六点七边图的图设计、图填充和图覆盖 问题给出了系统完整的解决；文【6 ，7 。1 6 1 完全解次了六点九边图中六个图的填充和覆 盖问题文【l o 。1 8 1 已砖全部六点八边图的图设计问题给出了基本完整的解决，但它们 的图填充与图覆盖问题尚未研究 本文将在4 对如下两个六点八边图g l 和g 2 的图填充和图覆盖进行研究，分别构 作了其最大图填充和最小图覆盖 图g 1图g 2 河北师范大学硕士学位论文 5 2 完全丁( k 1 k ) 三元系的存在性 为了代数地表达区组t ( z q ) ( 见下边左图) 。我们将采用右边的两种形式： ( 0 ：a t ，a 2 ，氐；岛，b 2 ，b k ) 小0 ata 2 ：a 风k ) a s 本文中，完全t 旧) 一三元系的构造主要用的是差方法对于整数a sb 。定义 f 0 ，6 】= o ，a + l ，b 一1 b ； - a ，6 | = - a ，一( d + 1 ) ，一，一( 6 1 ) ，一6 ； 陋，6 l = m n + t ，b t ，6 ，其中a ib m o d t ； 一陋，6 】c = 一n ，- ( a + t ) ，- ( b 一) ，- b ，其中a eb m o d t 而在磊中，有序差为 0 ，1 ，2 ，n 一1 ) ，无序差为 l ，2 ，字) 或 1 ，2 ，字湾) i 理2 1 给出了从一些有序差集a 到对应的无序差集b 的等价转变a b ， 引理2 1 设n 为正整耗则 ( 1 ) 在z 4 。或z 4 2 中， 1 2 n ，2 n 一3 j 4 一【1 ，2 n 一1 】2 【3 2 n ，2 礼一l 】4 一1 1 ，2 一1 】2 ( 2 ) 在五。+ 2 中，f 2 ，轨一2 】4 一【2 ，2 n 2 ，【4 ，4 n 】4 一【2 ，2 n 2 , ( 3 ) 在z 6 n + 4 中，当n ；0 m o d4 时：i l 一3 n ，3 n 一3 1 4 一f 1 ，3 n 一1 1 2 ， 当n 车2 r o o d4 时：【- 3 n 一1 ，3 n l 】4 一【1 ，3 n + l 】2 ； ( 4 ) 在乃。+ 1 中，若15a n ，则当d 为奇数时：陋，2 n 一口】2 一陋，叫， 当8 为偶数时：1 8 ，2 n + 2 一口】2 一【8 1 ，】 引理2 2 设日是一个有e 条边的简单图若存在完全t ( h ，”) ，则2 e p 扣一1 ) 且 是奇托 特别地口 1 m o d2 e 和 壬e m o d 2 e 阳奇j 满足必要条作 珏i 递归构造 定理2 3 设日是一个e 边简单图如果存在完全t ( h ，3 e ) ，完全t ( h , 5 e ) ，完全t ( h ，矿) 和完全t ( h ，3 e ：e ) 。则对任意正整数m ，存在完全t ( h ，2 m e + e ) 构造令顶点集为x = ( z 咖u ) 磊则完全t ( h ，2 m e + e ) 的区组集由( 2 m + 1 ) 垒学个区组构成由【4 】知，当m 3 ， 3 十( m 一2 ) 时，存在3 - g d d ( 2 , n ) = ( z 2 m ， g j：0 j t n 一1 ，8 ) 。其中 g j = 2 j 十1 ，2 j + 2 ，0 s j m 一1 ： 3 1 ( m 一2 ) 时，存在3 - g d d ( 2 m - 2 4 1 ) = ( 历。， q ：0 冬j m 一2 ，b ) ，其中 g o = l ，2 ，3 ，4 ，g j = 勿+ 3 ，巧十4 ，1 sj m 一2 对于组g o ，令( ( g 0 u o 。 ) 磊，山) 是完全t ( h ，3 e ) ( 3 f ( m - 2 ) 时) 或完全t ( e5 e ) ( 3 1 ( m 一 2 ) 时) 对于每个组q ，j 0 ，存在完全t ( h ，3 e ：e ) = ( ( ( 岛u ( ) 磊， o 。) z e ) ，山) 而对于每个三元组b 嚣，存在完全t ( h ，e 3 ) = ( “n ) 磊：口b ) ，c b ) 则 q = ( u 白) u ( u 心) 构成x 上的完全t ( h ，2 m e + e ) 的区组集，其中s = m 一1 ( 3 t ( m 一2 ) 时) 或8 = m 一2 ( 3 1 ( m 一2 ) 时) 证明首先，我们有以下计数： 川= 攀鞣墨n 仆牮= 4 e - l ( j # 0 ， 旧= 翠堑母型嵩 墨扣学一s e ， 吲_ 挲之。+ 掣+ ( 4 似e - 1 ) 叫( m - 。1 ) ，邛，掣 则i n i 恰是t ( h ，2 m e + e ) 中应含区组总数而且， v i 1 7 厶，“o 。，f ) ( 。，i ，) 出现在a 0 的三个区组中； v x 如。，存在包含z 的g j v i ，f 厶， ( z ，z ) ，( o o ，i ，) ) 出现在心自d s - 个区组中； v ( z ， ) ( 一，i 7 ) 2 m 厶，。g j ，。g j ， 若j j ，则q b b ，其中z ，$ 7 b ，则 ( z ，z ) ，( z 7 ， 出现在的三个区组中： 若j = j 7 ，则z ，g j ； ( 七，。) ，( 一， 出现在 的三个区组中，其中均恰有一 条边在内部 口 2 2 主要构造 定理2 4 对任意正整数m 1 和k 1 ，存在完全t ( 所，2 k i n + 1 ) 构造点集z 2 k 州1 上完全t ( 凰k ，2 k i n + 1 ) 的区组集由以下m 个基r ：x 组模2 k i n + 1 构成： 河北师范大学硕士学位论文 7 岛= ( 0 ：觚+ 1 ，k i + 2 ，舡+ ；- ( k i + 1 ) ，一( 航+ 2 ) ，一( 艇+ ) ) ，0 is 竹t 一1 证明基区组马的内部差为：k i + 1 ，k i + 2 ，航+ k ，故所有基区组b | ( 0 t m 一1 ) 的内部差恰覆盖了整敷段1 1 ，m 】而基区组最的外部差为 觚+ 1 ，k i + 2 ，一，航+ k 和2 ( k i + 1 ) ，2 ( k i 羊2 ) ，2 ( k i + ) ， 故所有基区组最( osi m 一1 ) 的外部差恰覆盖了整数段【1 ，k m 和【2 ，2 k 1 2 = 【1 ，k i n ， 见引理2 1 口 定理2 5 对任意奇数k ，存在完全t ( k 1 ，3 ) 构造取点集为况x 忍，则完全t ( k 1 , k ，轳) 的3 k 个区组由以下基区组模( ，3 ) 构成： b = ( 0 0 ：( k 一1 ) 1 ，0 i ，1 1 ，- ，( 一2 h ；( k 一1 ) 2 ，( k 一2 ) 2 ，( k 一3 ) 2 ，2 2 ，1 2 ，0 2 ) 证明，在b 中内部( 0 ，1 ) 混差恰覆盖了整数段1 0 ，k 一1 】而b 模( 一，3 ) 祷得到具有相同 值的( 1 ，2 ) 和( 2 ，o ) 混差在b 中的外部混差为： ( 2 ，o ) 一混差：一i o ，k 一1 】= 【o ，k 一1 】； ( 1 ，2 ) 混差： f 一一2 一i ) ：i 磊 = 2 i + 2 ：i z ；) = o ，k 一1 】 而b 模( 一，3 ) 可得到具有相同值的( 0 ，1 ) 一，( 1 ，2 ) 一混差及( 2 ，o ) 一，( 0 ，1 ) - 混差， 口 定理2 6 对任意奇数k ，存在完全t ( k 1 m 3 k ：k ) 构造k = 1 时，完全t ( k i , 1 , 3 ：1 ) 即是完全t ( k 1 ，1 ，3 ) ，它可由以下3 个区组构成： o 二_ 二1 iq 2 二= 02 二二l 当k 23 时，取顶点集为z 铀u o o o ，o o k 一1 ) ，其中 。o o ，o o k 一1 是一个k 长凋而区 组集由以下的4 k 一1 个区组构成：a ，b i ，倒( 0 i k 一1 ) 和a ：( 1 i k 1 ) 以。=(o。t【十0，,2k一-21+2。)，a：=(mt啤+十1,2，k-一112k 2 i3 k2 12 i3 k 1 + 。司。) ， 【十，一+ 2 q 2 啤+ 十，一+ 2 司2 ，k + 2 i 【1 + 2 i ，k 一2 + 2 i 2 【2 十2 i ，k 一1 + 2 i 2 、 耻l 瓤0 0 0 阶，。睾盼1 恼舡2 矧2 z 一2j 、0 0 1 ，睾 降十l 十窃 z 芹一z 十 ， ，o o o【2 + 2 i ，k 一1 + 2 i 2 【3 + 2 i ，k + 2 司2 剜2 i1 + 嚣k + 1 + 2 i 。州，o o k 一1 啤十2 + 2 i ，2 k 一1 懈j 七+ + o o 量土呈，一啤十+ ， 一十2 t j i ， 证明色。合o 。的对子如下： 璺 墨全! ( 丝! ：1 2 ：三垄垒鱼查垒丝 ! ! 立“= 0 ) ：【o i2 k 一2 】2 u t l + 2 i k ：- o i = f o 2 k l 】。在a o 和所有的层中； ( i 0 ) ：【o ，2 k 一2 j 2 u 【1 ，2 k l 】2 = | 0 ，2 k 一1 l ，在所有的哇。和4 ：中 ! 上竖弘= o ) ：降，3 k 一2 】2 u 勿打k = - o i u 七+ 2 2 j = o u 后+ 1 + 勿。乃k = - 0 1 = 2 ( 陋，3 k 一2 1 2 u 【o ，2 k 一2 1 2 ) e 2 【0 ，2 k 1 1 ，在a o 和所有易，b ：中： ( 1 l k 一1 ) ：f k + 2 i ，3 k 一2 + 2 i 2 u 陋+ l + 2 i ，3 k 一1 + 2 i 2 = f k + 2 i ，3 k 一1 + 2 i e 扣，2 k 一1 】，在所有的a 和卅中； ( 1 i s 学) ： 幻) 凳磊u 巧十2 i i ，k ：- 3 = i o ，2 k 一2 j 2 u 【2 t 一1 ，2 i + 2 k 一3 】2 ii o ，2 k 一1 1 ，在所有的b ，中： ( 学s k 一1 ) ：( 1 + 勿 譬：u 2 i + 2 j k + 1 k ，：- o i = f 1 ，2 k 一1 1 2 u 【2 i 一+ l ，2 i + k l j 2 【0 ，2 k 一1 】，在所有的b ：中 差【田= “z ，z + d ) ：z 忍，1 d k 。的出现如下： 立童( d = ) ： 2 i ，2 i + 寄在所有的b t 中： ( 1s d s 一2 ，d 奇) ： 2 i ，2 i + d ：d 【1 ，一2 1 2 譬在所有的b z 中， “i + 2 i ，1 + 2 i + d ：d f 1 ，k 一2 】2 譬在所有的耳中： ( 2 d k 一1 ，d 偶) ：“2 i ，2 i + d ) ：d 【2 ，k 一1 】2 譬在所有的b 中， l + 2 i ，l + 2 i + d ：d 【2 ，一l j 2 。k ：- o i 在所有的研中 丛查( d = ) ： 2 3 ，2 d + ；三ju 1 + 2 i ，1 + 2 i + 譬在a o 和所有的联中； ( 1sd 一2 ，d 奇) ： 2 j ，巧十k + 2 2 ；蓦在全部的a 。中，i 0 ， “l + 2 j ，1 + 巧+ + 2 z ) ) ? ；在全部的a ：中，i 0 ，其中 d + 2 i 譬? = 陋+ 2 ，3 k 一2 】2 2 【1 ，k 一2 1 2 ； ( 2sd k 一1 ，d 偶) ：“2 i ，2 。+ d 譬在所有的且中， “l + 2 i ，l 十2 i + d 譬在所有的掣中，其中 d 陋+ 1 ，2 k 一2 1 2 - 【2 ，k l 】2 ： “+ 2 2 十1 2 j ，k + 2 i 一1 + 巧”舌在所有的鼠中， “十2 i + 2 2 j ，k + 2 i + 巧 高在所有的耳中，其中 d 4 j 一2 ) 苫= 1 2 ，2 k 一4 1 4 ，【2 ，一l 】2 口 定理2 7 对任意正整数i1m o d 4 , 存在完全? ( 硒，3 七) 构造首先，定理2 6 中给出了完全t ( 凰1 1 3 ) 以下，令= 4 t + 1 ，t 0 取顶点集为 ( z 6 t + l x z = ) u o o 区组集由以下3 个基区组模6 蚌l 构成，其中整数段【o ，6 】= n o ，的 1 - ，- 】= 0 1 ，6 1 河北师范大学硕士学位论文 9 o o f 5 t + 1 ，6 t 】 3 t + 1 ，4 t 4 t + 1 ，5 t 1研，翮、 石一【i 讯，硐一【r ，习一 s t + l ，6 t 一隔丽，硐 b 2 ：f 百。 【l j 】1 2 t “3 t 】吼翮 n - + - i 阎1 ， 0 一【4 t + 1 ，5 t 一【1 ，q一瞄+ 1 ，3 t 1 一偈f 干1 ，硐， 岛：f 西。 陬+ 1 6 t 】1 4 t + 1 别【t + 1 2 埘匝习 1 o o - s t + 1 ，6 t 】一 3 t + 1 ，4 t i- f f ，习一吼习 证明显然，含o o 的对子的出现满足条件以下表格中列出了z 6 f + 1 汤中的内部差和 外部差其中，( f ， ) 一p d 代表( i ，t ) 一纯差，i = 0 ，1 ( 0 ，1 ) 一m d 代表( o ，1 ) 混差 基区组b t ，1 i s3 ，的内部差 ( 0 ，0 ) 一p d( 1 ，1 ) 一p d( 0 ，1 ) m d b 11 1 ，3 t j 1 2 f + 1 ，3 t 】 b 2【t + 1 ，2 吼【2 t + 1 ，3 t 】 【5 t + 1 ，6 乩【3 + 1 ，耻1 b 3 【1 ，t 】【4 t + 1 ，5 珠【o ，2 t 】 基区组最，1 i 3 ，的外部差 ( 0 ，o ) - p d( 1 ，1 ) p d( 0 ，1 ) 一m d 【1 ，】【t + 1 ，2 洲5 t + i ，6 t l ，【0 ，t l 日1f t + 1 ，3 t l 】2 【t + 2 ，3 t 2 i t + 2 ，3 t 2 ，【t + 1 3 一l j 2 【1 ，2 t l k 1 1 ，t 1阻+ l ，5 】，【0 ，t 】 b 2 【2 t + 1 ，3 t l【2 t + 1 ，3 t 】【2 t + 1 ，3 t 】，【3 t + 2 ，5 t 2 【2 ，2 t 2【l ，乩f t + l ，2 t 】1 5 + 1 ，6 叱【3 t + 1 ，4 t j b 3 【t + 1 ，3 t l 】2【t + 2 ，3 t j 2【3 t + l ，5 + l 】2 定理2 8 对任意的正整数e3 m o d4 ，存在完全t ( k 1 k ，3 ) 构造令膏= 4 t + 3 对于基区组b 爿区组b + i ，我们用以下的表示法： rn 、一j ( ；) 0 i 3 t + 1 ； f ，口( 6 ) 、一j ( ：) 0 s i 3 t + 1 ； u ( d ) i ( 笳3 t + 2 i 6 t + 3 c i ( 93 t + 2 i s6 t + 3 ( 瑙) = e ) 0 s i 曼i 3 t ， g ) 学曼i 3 t + 1 ； ( ：) 3 t + 2 i 6 t + 3 t = 0 时，定义在顶点集忍x 历上的完全t ( k 1 3 ，9 ) 口 ! ! 一一一 完全t ( k l三元系的存在性,k)- ( 0 0 ：l o ，0 1 ，1 1 ；2 0 ，2 2 ，1 2 ) ，( 0 1 ：1 1 ，1 2 ，2 2 ；2 1 ，i o ，o o ) ， ( 0 2 ：1 2 ，0 1 ，0 0 ；2 2 ，2 0 ，2 1 ) ，( o o ：2 1 ，1 2 ，2 2 ；0 2 ，1 1 ，0 1 ) ，m o d ( 3 ，一) t = 1 时，定义在顶点集( z l o z 2 ) u 上的完全? ( 硒，7 ，2 1 ) ： ( 0 ：7 ，9 ，6 ，8 ，百，o 。，5 ( 石) ；l ，2 ，亏，互，互，石( 5 ) ，5 ) ， ：7 ，9 ，6 ，8 ，3 ，。，o ( 5 ) ；t ，趸，4 ，2 ， ，5 ( o ) ，5 ) ， ( 石：瓦吾，2 ，4 ，5 ，百，亍；8 ，9 ，3 ，1 ，o 。，吾，_ r ) ，m o d ( 1 0 ，一) t = 2 时，定义在顶点集? ( k l ，i i ，3 3 ) 上的完全( z 1 6 z 2 ) u o 。 ： ( 0 ：8 固，o 。，1 ，2 ，4 ，6 ，亍，丽，3 ，5 ，7 ；1 2 匝】，1 5 ，1 1 ，瓦1 3 ，1 4 ，5 ，6 ，豇，碡，丽) ， ( 石：吝【8 1 ，o o ，i i ，0 ，2 ，4 ，6 ，5 ，7 ，i ，瓦砭【1 2 】，1 0 ，两，7 ，5 ，3 ，1 ，1 4 ，1 5 ，覆，两) ， ( 巧：t ，趸，1 4 ，一2 ，1 ，5 ，玩1 0 ，1 2 ，1 3 ，1 5 ；4 ，o 。，2 ，丽，g ，丽，互，8 ，6 ，甄，两) ，m o d ( 1 6 ，一) 以下讨论t23 的情况取顶点集为( z 6 t + 4xz 2 ) u o o ) ，区组集由以下3 个基区组 模( 6 t + 4 ，一) 构成 t 为奇数且t23 时： 耻( 玩= ( 耻( 0 0 3 t + 2 ( 石) 1 3 t + 4 ，f i t + 3 1 2 3 t + 3 ，6 t + 2 1 2 隔丽，舀e 。干司2 瞄z 。干1 ，五e 。干1 2 、 0 ( 3 t + 2 ) 蕊1 1 , 学l 浮，丽】阿，羽旺，鹗， o 。 o ( 5 i 。干互) f 3 + 4 ，6 t + 3 j 2f 3 t + 3 ，6 t + 2 j 2陋+ 2 ，2 t + 1 1 2x lm 、 3 t + 2 ( 0 ) 3 t + 2 f r ，藿尹l【2 ，3 t + 1 1 i 厦丽，萼马尥k 。 3 t + 2 【i 再习，硐2f 2 ，3 t + i 2z l 】、 o o ( 丑笋，6 t + 3 l l ，3 芒l i z 2 w 2 ， 其中当t i1 m o d 4 时 x t = f 面2 。踊1 2m = 芦乒，翮：z l - 呼，蕊1 2m = ( 歪尹，i 邢l ： 髓= f 平，平j 蚝= 【萼噩，硐历= 【平，羽奶= 【平，平】 当t = 3 m o d 4 时 蜀= i 孚，丽j 。m = 降，觋z i = 浮，确k = 洋，i 硼： 施= 萼噩，飘托= 【马亘，硐磊= ( 平，鹦= i 平，羽 t 三2 i l l o d 4 且t 6 时： 3 - 7 - 4 忑 3 t + 2 】o o 4 t + 3 率l 学3 学一5 t + 3 【0 ，3 t 2哆，雨l 。f 再瓦翮。、 l ，3 t + 1 】；i 墼笋，f i t + 3 l 西丽，踊】， 3 t + 2 犀司o o 12 4 t + 5 学嘲6 t + 3 学平厕 【4 ，3 i 2 【l 硝，i 再诵2f 5 再了，i 讯1 2 【3 ，3 t4 - 1 1 2 、 【学灏十2 1 阿，飘浮，习浮，万硼 一o 0 一 ，一，一 = = 鼠 岛 河北师范大学硕士学位论文 1 1 b 3 ：凡1 2 1i 半6 2 】z 1 3 t + 4 ，学k 忍 学丽功【2 ，学】i 【学，3 t + 窃i 学，蔚硐 【1 ，2 t 一3 1 2 3 3 t 一1 4 t + 5 ，6 t + 3 b 、 岳币，刁o o2 铲瞬丽，6 丽】 t i o m o d 4 且t 4 时： 耻( 。 3 + 2 零f 干习 12c o 1 4 ，3 t 2 f 3 ，3 t 一3 b 学阐学互乒6 t + 3 【学，o r + 2 1 【擎，翮 厣，吼3 t + 53 t + 35 雨警4 洋丽，瓣1 2 、 f 5 丽，学1 ji 3 t + 1 监学蓐糯，学1 。一3 t - 蕊 3 t + 2 1 3 t + 16 干1 【1 ，2 铲】2【4 学，3 t 一1 】2 【4 ，t 1 2 岛= l 0 ”二 l学【学】学o o 【韭笋，6 t + 晰【3 t + 3 ，学j i 嘲 口丽，5 习26 丽0 t + 2 【2 t ，3 t 2 【3 t + 4 ，警】21 2 鼍堡，乳+ 2 1 2 、 【半，f i 】学丽可旺，鞠【掣，鞠l 学，学】， 风：fd 。0 o 2 【3 5 6 3 k 1 21 厕2 臣卿21 学夏可一11 3 t + 4 o t + 2 ef 学，夏瓢lf 韭笋丽霜 i 学，瓤+ 1 】， 证明当f = 0 ，1 ，2 时，构造显然满足条件当t 4 时，包含o 。的对子的出现满足条件以 下考虑磊。4 历中的内部差和外部差其中，符号5 再j 代表纯差3 t + 2 轨道的一半， 符号6 代表对于混差0 轨道的一半当为偶数时，在b l ，b 2 中，有符号( 删) ： ( 。3 霉篱) 或( a 雩别 不难验证由基区组且，岛生成的所有区组在这部分的外部边恰是差为( o ，o ) p d 掣， ( 1 ，1 ) 一p d 譬。( o ，i ) m di 学和( o ，1 ) m d 盟笋的所有边当t 为偶数时，除了以上4 个外， 其余的外部混差被列在下面的表格中 t 为奇数且t 3 时的内部差 ( 0 ，0 ) - p d( 1 ，1 ) - p d( 0 ，1 ) - m d 【1 ，3 啪【5 + 4 ，6 + 3 】2 口l f 2 ，3 t + 1 j 2 ，5 痢 【3 t + 4 ，4 t + 1 1 2 , 6 徜 b 2 【学，2 t 一1 】2 【学，3 t bt i l ( 4 ) 【l ，3 t b ，【2 3 t + l k 【f 塾笋，2 t + 1 1 2 ，1 5 等，3 q 2 t i3 ( 4 ) 【4 t + 3 ，5 t + 2 k ，0 【2 ，3 t + z 2 【孔+ 3 ，6 t + 2 1 2 岛 f 1 ，型尹川2 + 1 ，星笋】2t 三1 ( 4 ) 3 t + 2 i1 1 ，3 学；2 ， 恐+ 3 ，5 字j 2 i 3 ( 4 ) t 为奇数且t 3 时的外部差 ( o ，0 ) 一p d ( 1 ，1 ) - p d( 0 ，1 ) 一时d 【掣，3 t + 1 1 l a 。 2 - 掣1 ，5 五飞 【学，2 + 1 1 , 3 t - t 靶p + 1 ，学1 b a i 2 宇，3 t + 1 】i 学，3 t + 1 l 1 1 ，字】，0 ，3 t + 2 阻+ 3 ，2 学】 面花，f 1 ，墼笋坤t + 2 ，警3 1 【2 1 6 t 4 一f 2 ，3 t + l | 2 j 【学，学】，| 竿，学】t ；l ( 4 ) 【3 + 3 ，6 + 2 k b 2l 半，擎j ，【学必2l 旧3 ( 4 ) i 学3 t + 1 l 3 + 2 i 警，t l jf 1 ，孕l ， 峨坦，3 t + l ；l ( 4 ) o ，嚣+ 2 【1 ，宁j ，【半产，3 t + 1 jt 3 ( 4 ) f 学，韭尹j ，【字，t t + l lt = l ( 4 ) f 1 ，2 笋】 【( 墅控4 ，韭笋】，【半，孚j t 3 ( 4 ) b 3【- 3 t ，3 t 一2 1 4 一【1 ，3 t 1 2 【3 + 4 ，6 - 3 1 2 l 学，学j ，【擎，卫学jt l ( 4 ) 【f 学，学j ，i 学旦弘j 据3 ( 4 ) 【学。6 t + 3 j t ；0 m o d 4 ，t24 时的内部差 ( 0 ，o ) 一p d ( 1 ，1 ) | p d( 0 ，1 ) - m d 3 t + 2 ，1 ，2 3 t 一1 3 t + l 5 确，3 t + 1 ，学 b 1 【4 ，3 t 2 ，f 3 ，3 t 一3 j 21 4 ，f 1 2 4 t + 6 ，5 t4 - 2 】2 f 学，6 t + 3 川3 t + 5 ，学1 2 b 2莉，3 p + 4 ，2 t 1 2 ，1 3 t + 3 ，i 5 t 十4 6 t 2 ，2 1 3 t + 4 ，4 t + 4 j