（应用数学专业论文）关于模和图与有向和图.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。掘我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 鬲、印久 导师签字： 学位论文版权使用授权书 匆嘎 本学位论文作者完全了解堂撞仃关保留、使用学位论文的舰定。有权保尉并向 团家仃天部门或机构送交论文的复印件和磁船，允许论文破查f ； j 平借阅。本人授权堂 奠w 以将学位论文的伞部或部分内存编入| 彳哭数拼：阼进行检索，可以采用影印、缩印 或扫描等复制手段保存、j r ：编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作存签名：节铷弧 导州i 签： 签声| i j j ：2 0 0 7 年珥jj ) d签引j ：2 。7 年渺j 必1 山东师范大学硬士学位论文 关于模和图与有向和图 陈玲 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 本文所用图论符号及术语遵循文献 1 】 1 9 9 0 年h a r a n t f 2 】提出和图的概念1 9 9 4 年h a l a r y 【提出整和图的慨 念令( z ) 表示正整数( 整数) 集， r ( z ) 的非空有限子集s 的和( 整和) 图g + ( s ) 是图( s e ) 其中一当且仅当“+ r s 一个图g 称为和 ( 整和) 图，若它同构于某个sc ( z ) 的和( 整和) 图我们说s 给出了g 的一个和( 整和) 标号，并且将顶点与其标号不加区分g 的和数( 整和 数) 一( g ) ( ( ( g ) ) 是使得g u t z 是和图( 整和图) 的非负整数n 的最小值 1 9 9 0 年b o l a n c l 等人l l l 提f l ；模和图的慨念模和图是取5 t c 1 2 m 一 1 且所有算术运算均取模，儿( 俐+ 1 ) 的和图南此，2 i 】( ) 2 年s t i t - 等人 【5 l 提f f 了模和数的慨念一个图g 的模和数p ( g ) 是使得g u p i 是模和 图的非负整数p 的最小值 2 州) 3 年、“l l c - 等人提f ；排斥图的慨念图g u ，n 的( 整) 和标号s 称为排斥的( l i n ，) 若对每条边w t ( g m + r 趴l ，( g ) 图g 的排斥和 数! 【g ) 是使得g u ，。有排斥和标号的非负整数”的最小值 2 ( ) ( 1 了年窦文卿等人提_ f 模整和图的慨念模整和图是取s c 0 1 2 ，儿一l 且所有算术运贸：均取模m ( 旧j 的和图一个图g 的馍整和数t ( g r j 是使得g uc t 凡是模整和图的非负整数c ，的最小值 从实用的观点来看，计钾：饥可将图的( 各种j 和图怀号作为图的压缩 l l j 东师范大学硕士学位论文 表示当利用输入图的压缩表示来工作时，数据压缩不仅能节省存储空 间，还可以加快某些图算法的运算速度 本文提出如下定义： 有向图g = ( v e ) 称为有向和图，正整数集的非空有限子集s 的有 向和图否+ ( s ) 是图( s ，e ) ，其中赢e 当且仅当“一口s 一个图g 称为有 向和图，若它同构于某个sca r 的有向和图我们说s 给出了g 的一个 有向和标号，并且将顶点与其标号不加区分g 的有向和数秽( g ) 是使 得g u n - 是有向和图的非负整数n 的最小值显然才( g ) o 图g u n k - 的有向和标号s 称为排斥的( “c l u s i v c ) ，若对每条边甜 ( g ) n w 吼y ( g ) 图g 的排斥有向和数? ( g ) 是使得g u n i 有排斥有 向和标号的非负整数，z 的最小值 在本文的第一章中，我们主要介绍了文章中所涉及的一些慨念、术 语和符号以及前人关于和图的一些重要研究结果；在第二章中我们给出 关于模和图的一些结构性结果；第三章中，我们定义了两类图一扇星 与轮星，并证明了这两类图不是模和图；第四章中，我们定义了有向和 图，并给_ l ：了有关有向和图的些结构性质以及几类特殊有向图的( 排斥 ) 有向和数；第五章指 l ：了有待研究的问题 在本文中，我们主要得到如下定理： 定理2 1 1 模和图至多含一个饱和点 推论2 11 含有饱和点的，阶模和图的饱和点标号形如0 ，巾一1 ) 其 中为模， - 1 2 ，一2 定理2 2 i 含有饱和点的图饱和度为大j ：等j ：3 的质数时，只有星和 h l “是模和图 定理2 3l 和图与模和图的并是模和图， 定理2 矗2 设模和图g h 的模和标号集分别为s - s 2 模分别为：1 珏 2 山东师范大学硕士学位论文 若( 轧勿) = l ，则g u h 是模和图 定理2 4 1 若单位图g 的次大标号点不邻。j 二最小标号点，则g 为模和 图 定理2 4 2 单位图g 上一定存在一点，使得在该点上粘星的中心所得 的图为模和图 定理2 4 3 若g 是模和图，且其模和标号使得任意不相邻点的标号和 不等于模m ，则。v g 是模整和图 定理2 4 4 对任意正整数r ，存在r 一正则模整和图 定理3 1 1 扇星不是模和图 定理3 2 1 轮星不是模和图 定理4 1 1 设图g 是有向和图，则对任意自然数m g u ”z - 是有向和 图 定理4 1 2 若g u ，n 。有一个排斥的有向和标号，则对任意自然数 q g u ( n t + 口) k - 也有一个排斥的有向和标号 定理4 2 3 对任意有向图g 1 g 2 若亨f g lj 万f 岛) 存在，有了( g lu g 2 ) 才( g 1 ) + 才( g 2 ) 推论4 2 3 若g - 岛是有向和图，则g - u 也是有向和图 定理4 3 1m 羁是有向和图 定理4 3 2 有向路是有向和图 定理4 3 3 有向路的排斥有向和数是1 定理4 3 4 有向幔配的排斥有向和数是i 关键词：模和图；模和数；模和标号；扇星；轮星；有向和 图；有向和数；有向排斥和图；有向排斥和数 分类号； 0 1 5 7 5 坐奎堕整盔兰堡主堂垡堡茎 t h em o ds u mg r a p ha n dd i r e c t e ds u mg r a p h c h c nl i n g s i l a n d o n gn o 咖a lu n i v c r s i 毗j i n a n ，s l l a n d o ng 2 5 0 0 1 4 p c o p l c sm p u b l i co fc h i n a a b s t r a c t h a r a r y 【研p r c s c n t e dt h cc o n c c p to fs u mg r a p h i n1 9 9 0 h a r a r y i 司p r c s c n t c dt h c c o n c c p to fi n t c g r a ls u mg r a p hi n1 9 9 4 l e t r ( z ) d c n o t et h es c to fa np o s i t i 、c i n t c g c r s ( i n t c g c r s ) t h c ( i 1 1 t c g r a l ) s u mg r a p hg + ( s ) o f an 0 1 1 c l n p yf i l l i t cs u b s p t s c 7 ( z ) i st h cg r a p h ( s 层) w “ i “u i fa n ( io n 妒i f “+ s a g r a p l ig j s s a i dt ob ca n ( i l l t c g r a l ) s u l ug r a p hi fi t i si s o i n o r p l l i ct ot h c ( i l l t c 苫r a l ) s l l mg r a p ho f s o l l l esc ( z )、0s a 、，t l i a tsi sa n ( i 1 1 t c g r a l ) s l i l nl a b o l i l l g a 1w cc o l l 硝d c rt h c w r t i c c sa 1 1 d1 a b c l i l l 尉a st l l ps a j l l o t l l c ( i i l t c g r a l ) s l l l i li l l l l l l l ) c r 盯( g ) ( ( ( g ) ) 拓t l w s m a l l c s tl l t m 山c ro fi s o l a t “l 、t r t i ( 心w l l i c l lw h c l la ( 1 ( 1 c ( 1t ogr o s l l l ti 1 1a 1 1 ( i i l t c g r a l ) s l m lg r a p h t i l cf o l l ( - 叩to f t l l pl l l o ds l l l i lg r a l ) hw 蹦i i l t l 0 【1 1 i f c wb o l n i l ( 1c t 甜l | i 1 11 9 9 0 a1 1 1 0 【1s l m lg l a l ) l li sa l l lg l a l ) hw i t l lscz ，。 o m l ( 1a l l 盯计l l i j l n i cp p r f o l l l l c ( 1 l l l o ( 1 l l l omw l l p r em i s i + 1 t h c n s u t t o l lc t a l h l ) r 始c l l “、( i “ ( o l l ( 0 1 ) to fl l l ( ) ls l l n l 1 1 1 l i l l b e r t l l cn l o ds u l l l1 1 i i m i ) p r ，( “) 【) f “批t h cl p a s ti l t i l l l l j ( ，lp j fi 斯j l 1 t r ( 1v p r t i 。( s p ，、，ls l i c l l l a t ( ；u p ikai i i o lm l l ng i a p h 、i i l l c rc t a l 【qp i r s c i l t y lil l c 【( 儿l 1 ) t ，fr x ( l u 西、c9 1 a 1 ) l li i l2 【j f ) 3 am u l ll l b 、l i n g s 伽f a l i p la i lr x ( 一l i l s i w 州l l ul n l ，( - l i l l g i f “+ f s v ( g ) f ( j ra l i ) 。p ( 1 9 、f ( g ) t l l ce x ( ，1 1 l s i s l l l l l i l l l m l ) p i 三f ( ? ) ) f “h | l l t ，1 e a s t1 1 1 1 1 1 1 1 ) r l _ 三o f 幽) 抽t ( ，( 1w l t n s 三，、1 州l ( 1 j “l h “u 三 + 】“a n ( ，x ( l i i 硝( s 川ng l 甜f j h 山东师范大学硕士学位论文 d o ua n ( 1g a o 【刀p r c s c n t c dt h cc ( 儿l c c p to f1 1 l o di 1 1 t c g r a lm u l lg r a p hi n2 0 0 7 a m o di n t c g r a ls u mg r a p l li sas l l l l lg l a p hw i t l lsc 互。a i l ( 1a l la r i t l l i i i c t i cp o r f o n n c d n l o d l l l omw h c r cm 1 s 卜t h pn l o di n t o g r a ls u mn t l n l b c l 驴( g ) o fgi st l i el c a s t 1 1 u m b c r 砂o fi s o l a t e dv e r t i c e s 妒1s u c ht 1 1 a tgu 砂k 1i sa 1 l l o ( 1i l l t c g r a ls u mg r a p h f r o map r a c t i c a lp o i n to fv i c w ，s i l mg r a p hl a b c l l i i l gc a l lb cu s c da sac o m - p r c s s c dr c p r c s e n t a t i o no fag r 印h ，ad a t as t r u c t u r cf b rr c p i c 唔c l l t i n g t l l cg r a p h d a t ac o m p r c s s i o ni s i m p o r t a n tn o to n l yf o rs 撕i l gm c n l o r ys p a c eb l l ta l s 0f o r s p c c d i n gu ps o m eg r a p ha i g o r i t h m sw h c na d a p t c dt ow o r kw i t ht h cc o m p r c s s e d r c p r c s c n t a t i o no ft h ci n p u tg r a p h n c wc 0 1 l c c p t sa r cp r c s o l l t c di l lt l l i st h 隅i sa sf o l l o w s ： t h c ( 1 i r c c t c ds l l mg r a p hg + ( s ) o fan o l l c l n p t yf l l l i t cs u l ) s p tsc i st h c d i g r a p h ( s ，e ) w i t l l 赢ei fa i l ( 1o l l l yi f “一t s ，ad i g r a l ) hg ks a i dt ob ea ( 1 i r c t c ds u n lg r a p hi fi t i si s 0 1 n o r p l l i ct ot h ( 1 ( 1 i l c r t c ( 1s u l l l9 1 + a p ho fs o n l csc t 1 1 cd i r c c t c ds u mn t l m b c r 孑f g ) i st 1 1 rs m a l i ，s t1 l l l i n b c ro fi s o l a t 州w r t i c c sw h i c h w 1 1 c na d ( 1 e dt ogr c 吼1 1 ti na ( 1 i l c r t c ( 1s i l l l ig r a l ) 1 1 a ( “r c c t “ls i i l l li a b e l i i l gsk ( n l l e 1a l l ( ，x f h l s i 、c l i r p c t c ( 1s h l i ll a l ，( 1 i i l g i fu u s 7 ( g ) f o ra l j yr ( 1 斟石7 f f ( n d i r r ( 。t 蜘1 1 1 ll a l ) r l i l l g i i l f l ( ，x l i l s | 、1 i i r p ( t t lm m ll 1 b ( ，l i l l ga 1 - pa l l u t l l c l w a y si l s c ( 1 a s ( 儿1 1 1 ) r ( * s ( y lr ( ，1 ) r e l l t a t 汕io fa l ig l n l ) 1 i t l l ( h ( 1 i a l ) t p i o “i 瓜1 ) ( 1 rg i 、( sa b r i ( fi l l t l “i l ( t i o l lh 1 j ( ，1 l tt l l r1 ) a s 衍c 0 1 卜 “- p i s t ( l i l l i l l o l o g i 雌a 1 1 ( 1s 1 1 l j j l 咻u + l l i 1 l 州r1 l s ，( i i l lt l l “i ) a 1 ) ，r ：l l lt l l ( ，s o i l ( if l l a l ) t c r 、坩g i y ps o l l i ( 、s t l 1 l ( t 1 1 a i “- 州1 l l s l ii l l o r l 刚i l “g l + n i ) l l h ：i l lt l l 、t l l m l 】l t l l ) t c r w r ( i c t c r - l l l i l i pat y l ) p ) fg l n p l l hw l l i h 埘l l ( 计l 王l ( j ( 1 蚓l l ng ln 1 ) l l ：i 量it i r 1 “l ( l m l ) t pr 、r c i 儿r l y i f i ( r h ( ，( 1 0 f l “，p hf ，ff l i “y “y i s i l i g i n p j ln l ( 气( l l l s h i f f j i h 、“v ls l i n lg l a l “1 a i i ( i ( 1 t ，“、l l l l i l l ct l l r ( ( 1 i r ( t t ( 1 x “l i s j 、( t l i “，( t t ，f 1 ) 蝌i l l li 1 l l l l j f t ru fh j l i l e ( 1 i g r n p h ：a t l n s t 1 lt n f f l l l m i ) t p r 、t l n d 、i l 。，f l l l l l i i l 削t l ，m s i i 州“ i i it h hp a l r 、w l i ：l v 【f l 时r ( j 、- i l gf l i ( t j l 儿s 5 山东师范大学硕士学位论文 t h e o r e m2 1 1t 1 1 cm o f l 默l mg r a p hl l a sa t1 1 1 0 s to l l es a t u r a t c dp o i 王l t c o r l l a r y2 1 1 t h cs a n l r a t c dv e r t c xo fm o ds u l ng r a p hgw i t ho r d o rnc a n b oo x p r c s s c db y 七，n ( n 1 ) ，w h c r cl 七sn 一2a 1 1 d ，ni st 1 1 0i n o ( 1 l l l o t h e o r e m2 2 1i ft 1 1 cs a t u r a t 砌v c r t c xo fg r a p hgw i t hs a t u r a t c dd c g r c ci s p r i m ca n dm o r ct h a n2 ，t h c ngi sn o tam o d 吼m 1g r a p hc x c c p tt h cs t a ra n d ，1 3 + e t h e o r e m2 3 1t h cu n i o n0 fas u mg r a p l la n dam o ds u mg r a p hi sam o d s u m g r a p h t h e o r e m2 3 2t h cu n i o no ft h em o ds u mg r a p hg ，hw i t hm o d1 a b c l l i i l g s 1 ，s 2a n dt h em o d u l u s2 l ，勿，( 。l ，却) = 1 ，t h c ng u i sam o ds u mg r a p h t h e o r e m2 4 1u i l i ts t l i ng r a p hgj sam o d 鳅h ng i a p h ，i fi t ss c c 研l dl a b d i si l o ta d j a c c n tt oi t sl l l i l m l ml a b c l t l l c l lg t h e o r e m2 4 2t h c r em i l s tb caw r t “i nt h c1 1 1 1 i ts u l l lg r a p hw i t l l 、订l i c h w h c ni d c n t 讯c das t a r1 ( 喁i l l t si l lai l l o ( 1s u n lg la p h t h e o r e m2 4 3i ft l l cs 1 1 l no fa l 埽t w oi l o l i a ( 1 j a c c l l tl a b o l so ft l l c1 1 1 0 ( 1g r a p h “i sl l o tt h cm o d l l l l l s t l l c i l iv g 缸al l i o ( i “l t 鸭l a is u mg r a i ) i l t h e o r e m2 4 4t l l r r ci l l l i s t1 ) ca ，一r c g l l l n rl l l o ( 1 蛳1 l l lg r a l ) l lr ) ra 1 1 、，1 ) o 如t i 、c i l i t r 群r r t h e o r e m3 1 1 f l 诋l l o tai l l o ( 1s u l l lg l a i ) 1 1 t h e o r e m3 2 1i l ：，t 缸l l ( ) ta1 1 1 f ( is i l l i lg l 1 1 t h e o r e m4 1 1i f ( j fi sn 1 i r ( y 叶r ( 1 州mg l a l ) 1 1 t l l c n ( ? u 川，、1 诂af l i u y t ( 1 m l l i l9 1a i l it o o ，f o ra l i y ，i l t h e o r e m4 1 2 i f ( ? u ，7 ，、，l l m s ；l l i x ( l i 、t ( 1 i “( t c ( 1 州i l ll a j j t i i l g t l l ( 、i l f ? u ( 川+ q ) il l ；协a i i i i lt x ( l l l 前、【( “r t l ( t “l 蛳l l nl n l ) ( l i i l l gt o o ，f o ra n yq t b e o r e i n4 2 3h b d t b 方( g 1 ) n i j ( j 万( g 2 ) c x 鲥t j h y 】7 ( g l u g ? ) 5 万( d i ) + 6 山东师范大学硕士学位论文 才( g 2 ) t h e o r e m4 3 1m 玄i sad i r c c t c ds t l i ng r a p h t h e o r e m4 3 2t h ed i r c c t c dp a t l l mi sad i r e c t c ds u mg r a p h t h e o r e m4 3 3 7 ( 。) ：1 t h e o r e m4 3 4 言( m 兹) = 1 ， k e yw o r d s ： m o ds u mg r 印h ；m o ds u mn u i n b o r ；m o ds u ml a b d l i n g ：f a n s t a r ； w h e c l s t a r ；d i r c c t e ds 呦芦a p h ；d i r c c t c ds u mn l l m b e “d i r c c t e de x c l u s i v cs u mg r a p l l ； d i r o c t o dc x c l u s i v cs u mn u i n b c r c l a s s i 矗c a t i o n ：0 1 5 7 5 7 山东师范大学硕士学位论文 第一章预备知识 1 9 9 0 年h a r ”y 1 2 | 提出和图的概念1 9 9 4 年h a r a r y l 3 l 提出整和图的概 念令( z ) 表示正整数( 整数) 集，( z ) 的非空有限子集s 的和( 整和) 图g + ( s ) 是图( s ，e ) ，其中u ”e 当且仅当“+ t s 一个图g 称为和 ( 整和) 图，若它同构于某个sc ( z ) 的和( 整和) 图我们说s 给出了g 的一个和( 整和) 标号，并且将顶点与其标号不加区分g 的和数( 整和 数) a ( g ) ( ( ( g ) ) 是使得g u n k - 是和图( 整和图) 的非负整数n 的最小值 a ( g ) = 1 时，g 叫做单位图 1 9 9 0 年b o l a n c l 等人【。l 提f ：模和图的慨念模和图是取sc 1 ，2 ，m 1 ) 且所有算术运算均取模m ( + 1 ) 的和图由此，2 2 年s u t t o n 等人 | 5 】提出了模和数的慨念一个图g 的模和数p ( g ) 是使得g u p k 。是模和 图的非负整数p 的最小值 2 0 0 3 年、i i l l c i 等人提f j ；排斥图的慨念图g u ，t 硒的( 整) 和标号s 称为排斥的( c x c l m i v c ) 若对每条边，( 8 ) “+ l 乳v ( g ) 图g 的排斥和 数= ( g ) 是使得g u ”凡有排斥和标号的非负整数n 的最小值 2 0 0 7 年窦文卿等人川提模整和图的概念模整和图是取sc o ，1 2 ，一 ，儿一1 ) 且所有麴：术运钎：均取模，( 蚓) 的和图一个图g 的模整和数r ( g ) 是使得g uo ，k ，是模整和囹的非负整数c ，的最小值 2 0 0 6 年，李敏等人川提】l i ：下整和圈的慨念用q + 表示正有理数集 q + 的非空有限子集s 的下整和图g ，( s ) 是图( s ) 其中m e 当且仅当 h + 叫s ， 不难看_ i l ：，对j ：任意图g 有( ( ( ；! ) s 一( o ( o ) sp ( g ) 一( g ) = ( g ) s 口( g ) 从实用的角度来看，计钎：饥可将各什和圈环号作为图的压缩表示 8 山东师范大学硕士学位论文 当利用图的压缩表示来】：作时，数据压缩不仅可以节省内存，还可以加 快某些图算法的运算速度 1 9 9 1 年，h a r “y 等人i - q 定义了实和图实和图取s 为正实数集他 们证明每一个实和图是和图 1 9 9 2 年，b e r g s t r a n d 等人i - - 】提出积图的概念令1 表示不包括l 的 正整数集，l 的非空有限子集s 的积图g ( s ) 是图( s ，e ) ，其中“r e 当 且仅当“。es 一个图g 称为积图，若它同构于某个scm 的积图 【l l 】中证明每一个积图是和图，每一个和图是积图 一般说来，确定一个图的( 模，整，排斥，模整，下整) 和数是非常困 难的s l l t t o n 等人i s l 猜测确定图的模和数是一个p 一难的问题 目前对和图的研究主要集中在两个方面： 一方面研究图的( 模整，模，整，排斥，下整) 和数与其它图参数，图结 构的联系，这方面的结果已有很多与所有点都有边相联的点称为饱和 点h “r a r y 【中指f i ；除虬外，和图一定不存在饱和点c l m 、州证明了除 硒外的整和图至多含两个饱和点；n 阶整和图g 恰禽两个饱和点当且仅 当g 兰g + ( 卜1 o 1 ，2 ) 并证明了任何一个整和图都是某个连通图的 导子图窦文卿等人l ? l 给；若 j 3 有n = n + n in + q _ 1 则虮一。；q - 1 _ 其中j 一1 一1 与归纳假设矛盾 所以a = “6 _ n 1 n 2 是g 的一组模和标号由因为n + n ， a 6 n 2 ，n p 否则若n + 唧in 则叶5o 矛盾若n + 郇i6 有+ 唧5 n + 则唧5n i 矛盾若“+ in l 有6 + n l + 唧5 则6 + 唧5o 与6 是饱和 点矛盾若n + p = n 2 t 有n + 5n + b 则唧56 矛盾若n + 唧5n 其 中j = 3 4 p ，有n + “pen + n “则f l ，j5q 。其中j l p 矛盾所以 n + 不在模和标号集 中，与n 是饱和点矛盾 情形3分两种子情形讨论 子情形3 1n + b i r 2 6 + r l 兰“n + 丁l 兰r 3 对j ：江3 ，4 ，p 因为n 是饱和点，所以6 + 以( t 卅，1 ) s ：因为b + ，。；m 所以b + ，。( r o d ，1 ) n ：因为r 2 + r ，兰( “+ 6 ) + t ，兰n + ( b + i ，) s f 而 j l + 啦三“+ 6 + z i 三( n + ，1 ) + 厶三厶十，：i s 所以对i = 1 3 4 p j 2 ，i e ( g ) 又因为2 ，_ i ! u _ 2 e ( g ) 所以l 2 是g 的饱和点，口= 2 + “r 2 十6 ，r 2 + 1 3 山东师范大学硕士学位论文 z 2 + z 3 ，耽+ t 2 + 是g 的模和标号但z 2 n ；若z 2 + nin 则 z 2 三o ，矛盾；若z 2 + b 三n ，有勋+ 扫三6 + r l ，则z 2 兰j 1 ，矛盾；若z 2 + z j 三o 有n + 6 + ；n 则6 + q ；o ，与6 是饱和点矛盾，所以n 不在b 中，矛盾 子情形3 2n + 6 兰z l ，6 + z l 三z 2 ，口+ z 1 三z 3 因为6 是g 的饱和点，所以g = 6 ，6 + o ，6 + z 1 6 + z 2 ， 6 + 唧 是图g 的 模和标号所以存在使得b 十z ；。考虑n ，6 ，z 组成的甄若n + z = 6 ， 则转化为子情形2 2 若n + z k = z j ，j l ，则转化为子情形3 1 t 青形4n + 6 三z 2 6 + z 1 三z 3 ，n + z l 三z 4 考虑n ，6 砌组成的肠，即可转化为情形l ，2 1 。32 中的一种 综上所述，模和图至多含一个饱和点 推论2 1 1 含有饱和点的n 阶模和图的饱和点标号形如m ( ，z 一1 ) 其 中h l 为模，k 1 ，2 ，l 一2 ) 证明设图g 是含有饱和点的n 阶模和图，摸为一由上述定理知， g 只含有一个饱和点设s = t ，m 一 是图g 的一组模和标号， 其中z 是g 的饱和点，则 卫+ z l 三丁，( ”l o d ”z ) j = 1 2 儿一1 其中h ，z 。r 。， = h ，。，。- j 上述式子相加得( ”一1 ) r ；o 所以 存在 l ，2 n 一2 ) 满足z = h 。巾l 一1 ) 注1 南一j ：除心外的树都是模和图它是星时恰含一个饱和点，否 则不含饱和点，故定理的结果是最好可能的 注2 由j ：轮= c 。v 凡，( ”4 ) 不是模和图州、恰含一个饱和点， 而。一e ( n 虬j ( 7 l 6 ) 的模和数为，t 一2 、不禽饱和点，因此定理2 1 1 的条件不是充分的 山东师范大学硕士学位论文 2 2 含有饱和点图的模和性的描述 目前，知道含有饱和点的模和图有，- + 1 个顶点的星。以及5 个顶 点的轮矾，对于其他含有饱和点的州pl 阶图是不是模和图还没有确切地 证明本节研究了饱和度是大于等于3 的质数的图g 的情况，并证明了 这种图除了所。以及k 。，s + e 都不是模和图记饱和点的度为m 饱和点 称为中心，标号为c ，且模为m ，令v = y ( g ) = n - ，o ：，c ) 除饱和点外 的点称为缘点，缘点与缘点之间的边称为缘边本节的标号运算是在模 m 下进行的 引理2 2 1 i i | n 2 时，星虬。都是模和图 下面仅考虑除星之外的图g 引理2 2 2n = 2 时，图g 不是模和图 证明n = 2 时，除星之外含有饱和点的图仅有盹但地不是模和图 引理2 2 3 ，z = 3 时，仅有g = 1 ：l + r 是模和图 证明由定理2 1 1 知，模和图至多含有一个饱和点所以n = 3 时， 可能为模和图的仅有g = ，、。，+ f 下证g = ，3 + c 是模和图 给j i ：g 的一组标号集s = 1 23 5 ) 取h t = 6 易验证g = ，1 3 + c 是模 和图 引理2 2 4在g 的一个模和标号中，如果所有的辐都是j ：作的，则 “卜n 2 一n 。 = “l + nr 心+ 九，f ，+ r ， 证显然+ n 啦+ n m + f 是 1 2 m l 中的n 个不同的标 号，m 所有的辐都足i ：作的即得结论 引理2 2 5 在g u ，。的一个模和标号中，如果所有的辐都是c 作 1 5 山东师范大学硕士学位论文 的，则缘顶点的标号可被剖分成等长度f 的集合使得每个集合中的元素 在加”c ，下成 一圈 证 选取集合月= 和z ，2 ，n f l + 1 ，“州 中的最小标号( 模嘲， 设为n l ，从只中移出它，并把它作为代表第一个剖分的新集合的第一个 标号，由引理2 2 4 可知，必存在一个标号q r ，使得n j = n i + c ，从r 中 移出q ，并把它放在第一个剖分中，继续此过程直到该序列中的下一个标 号不在r 中，由引理2 2 4 可知，该标号曾出现在最先的集合中，故该标 号已被选入第一个剖分中，而且必为n f 这样就完成了第一个剖分集合的 选取。 如果兄廿则重复该过程选取第二个剖分，重复这个选取过程直到 曰= p 这样我们就得到了r 的一个剖分假设第i 个剖分集合包含“个 标号且第一个标号是啦则u ，+ f 。c 一即f 。r = o 且j c o ，j = 1 2 ，“一l j 因此所有的圈必是等长度的，引理得证 注此时被刮分成的_ 圈的圈数小1 二m ( 因为圈数等于，t 时，则被 剖分成n 个圈，此时的圈长为1 所以有“。= n ，+ c 则c = o 矛盾) 本章中我们称这些剖分集合为圈，其怀号形成卜圈g 的顶点用 n 1 1 岫，蚴来表示 引理2 2 6 一个，一圈中的任两个顶点的标号之和不能等于同一，一 圈中的顶点的标号 证 假设存在f j 1 2 ， 且j f 满足“。+ “= f l ，则 z 己竭品= f n ，j + ( f 1 ) f j + f r ，i + ( j 1 ) r 4 右端= n ，l + ( 一1 ) f 所以“，i = 川 j2 ， 所以存在某个s l 。2 使得，= n 矛盾，引理成立 引理22 7 当，t 为质数，中心不是r 怍顶点时，g 不是模和图 1 6 山东师范大学硕士学位论文 证假设g 是模和图，由于n 为质数，缘点只能被剖分成一个圈 由引理2 2 6 知，缘边之和不等于缘点，所以缘边之和必等于中心标号， 与中心不是工作顶点矛盾 引理2 2 8 当n 为质数，中心是工作顶点时，g 不是模和图 证假设g 是模和图，由于n 为质数时，缘点只能被剖分成一个圈 由引理2 2 6 知，缘边之和一定不等于缘点标号，所以必等于中心标号 不妨设n ，+ n z = c ，则至少满足以下三种情形中的一种： 情形一，n l + n 2 = c ，c + 毗= n 2 ，c + d 2 = n 1 ，c + 奶= o 缸，c + o h = n “，其中 0 = 3 ，4 ，m j = 3 ，4 ，n 由第二、第三个等式得c = 等，由推论2 1 1 知， c = 訾，其中l n l 因为n 是质数，所以c 不可能是c = 等矛盾， 情形二、n l + 0 2 = c c + n 1 = n 2 c + n 2 = 幻，c + n 3 = n ，c 十n 。= 口 。，其 中巧= 1 4 n ，j = 3 ，4 n 由第一、第二个等式得a t = 警，则其他缘点 标号为 c 一考的形式，又因为g 是模和图，则应该存在一个耙一等；等 得耙；o ，由推论2 1 1 知，c = 警，其中1 ，z 1 则有i 警= o 又因为 i ， n 而n 是质数，所以i 簪o 。与，z 是质数矛盾 情形三、n 1 + n 2 = + “i = n 3 r 十n 2 = n i ( f + = n 1 i ( + n ”= n “其 中0 = 1 2 5 ，6 ，1 j = 3 4 棚不妨设n 1 = ，则恤= p r o = 行一t o k = ，c + z 其中j = 3 ，4 ，m 江2 3 ，z 一2 因为图g 是模和图，则必存在一 点满足下列四种情形中的一种： i c f = r j r + r = c r ( 1 ) i c z = c j j r + r = ，( 2 ) f c 一r = 卫，j r z = ( 一( 3 ) i r j = ( | 一，j c z = r ( 4 ) 由( 1 ) 得，衍= 2 j ( 1 一j ) r = 2 所以i ( t = ( 1 一j ) r ，( ，+ 一1 ) c = o 所以 ( h j 1 ) n l ，一o 因为j + j 1 k n 因为 因为j n ( 2 ) 若对任意的f t t w e ( g ) 则存在“，s i _ 满足u + ”= 玑所以 ”+ t - ；”( m 谢p ) 即w ，( o u j 若对任意的l f r 5 ，2 一e ( h ) ，则存在 满足l j + f 三“( ，j l 耐：) 所以2 f ，+ 2 ，l 口三2 小叫( m 洲p ) 即“u e ( g uh ) 所以g 日中原来有边的仍有边。 f 3 ) 若对任意的f r 一一g 引o ) 因为，+ f 2 m # 与 “一口 u ，有+ 2 m 。= 2 m ( 一 ) 2 m 2 ，“ o 矛盾当 口，有u = 2 m ( 一”) + 2 m 2 = 2 m m u + 2 ) 2 m ，与“ m 矛 盾所以“”ge ( g u 日) 所以g ，日原来无边的仍无边 综上，s 是g