（应用数学专业论文）和图与整和图.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者虢彭祆 撕粹翮极 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保宦f 劳向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 t 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩e 或扫描等复刹手段保存、汇编学位论文。( 保密的学位沦文在解密后适用本授权书) 学位论文作者签名：岛狄 导师签字： 毒莎饭 签字f 1 期：2 0 0 年缸月7 五日 签字r 期：2 0 0r 年牛月f 2 日 山东师范大学坝士学位论文 和圈与整和图 彭敬 ( 山东师范大学数学科学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 从实用的观点来看，和图标号可用作图的压缩表示，即表示图的结构当利用输 入图的压缩表示来工作时，数据压缩不仅可以节省内存，还可以加快某些图算法的运 算速度 和图的概念是f h a r a r y l 9 9 0 年提出的设g = ( 矿( g ) ，( g ) ) 是一个图，其中v ( g ) ， e ( g ) 分别表示g 的顶点集和边集，简记为v 和e 令( z ) 表示正整数( 整数) 集 ( z ) 的非空有限子集s 的和图g ( s ) 是图( s ，e ) ，其中u v e 当且仅当“+ v s 对 于图g ，若存在sc ( z ) ，使得g 兰g + ( _ s ) ，则称图g 是( 整) 和图对于任意图g 若存在最小的非负整数盯= 盯( g ) ( f = f ( g ) ) 使得g u a ( o k 。为( 整) 和图，称此数 为g 的( 整) 和数，即：o - = o - ( g ) = m i n s ：j s c n ，使得g us k l 兰g + ( s ) ，其中s2 0 j ( f = f ( g ) = r a i n s ：3 s c z ，使得g t p s k l 三g + ( s ) ，其中s o ) 显然对任意的图g 有 f ( g ) s 盯( g ) 为了更好地理解和图与整和图的定义，许多作者又给出了f 整) 和标号的定义： 图g 的一个标号是y ( g ) 。( z ) 的一映射l 如果存在图g 的一个标号满足：对 矿( g ) 。p 的任意两个互异顶点“和v ，“v e ( g ) 当且仅当存在w 矿( g ) 使得 1 4 u ) + ( v ) = l ( u ，) ，则称此标号l 为图g 的一个( 整) 和标号为了方便，在本文中， 如果没有特殊说明，顶点的( 整) 和标号与顶点可以不加区分 自1 9 9 0 年h a r a r y 提出了和图的概念，开始了对和图的研究目前对和图的研究 主要是从一些特殊图类着手，确定它们的和数、整和数迄今为止，已经知道一些简 单图类的和数与整和数，如：完全图k 。，n c 一路只，二分图k ，轮吼，扇f ， 酒会图i 瓦等但是对和图整和图性质的研究却不是很多 山东师托大学硕士学位论文 在本文的第一章，我们主要介绍了文章中所涉及的一些概念、术语和符号： 在第二章中，我们讨论了整和图的性质；在第三章中，分别确定了图。一e ( n k ：) 与 图g 的和数，定义了新图只。、。并给出了和数的上、下界，定义了一类新的不可 兼图c ：在第四章中，利用粘合的方法证明了又点距离至少为2 且每个叉点上有一 个距离为2 的路的树为整和图 在本文中，主要得到以下定理： 定理2 1 拧阶( ”4 ) 整和图g 至多有两个i i l 度顶点：g 含两个”l 度顶点当 且仅当g 兰g + ( 一l ，0 ，l ，2 ，r t 一2 ) 定理2 、2 设g 为一个 阶( 仃4 ) 图，有以下结论： ( 1 ) 若6 ( g ) f 爿+ 1 ，则g 不是整和图：且界不可以改进 ( 2 ) 令盯! 垒m j n s + s ：s s e s , s s 甚e ，若盯：2 f 兰1 + 2 ，则g 不是整和图：且界不可 以改进 定理2 3 设g 是一个”阶( 4 ) 图，如果( g ) 蔓r t 一2 ，那么有以下结论 ( 1 ) 若艿( g ) l 兰j + l ，则g 不是整和图：且界不可以改进 他若口! 2 l 兰j + 2 ，则g 不是整和图 定理3 1 1 对 5 ，c r ( k 。，一e ( n k 2 ) = 2 ，一3 定理3 2 1 对 23 ，c r ( g 。) = 2 + 1 定理3 3 2 2 n c r ( p o j ) s2 n + 2 山东师范大学硕士学位论立 定理3 4 3n 3 时，2 蔓仃( t ) 3 定理3 5 对n 5 ，c 。是不可兼图 定理4 2 叉点距离至少为2 且每个叉点上有个距离为2 的路的树为整和图 关键词( 整) 和图；( 整) 和数：( 整) 和标号 分类号0 1 5 7 6 山东师范大学硕士学位葩文 t h es u mg r a p ha n dt h ein t e g r als u mg r a p h j i n gp e n g s h a n d o n gn o r m a lu n i v e r s i t y ，j i n a n ，s h a n d o n g ，2 5 0 0 1 4 p e o p l e sr e p u b l i co fc h i n a a b s t r a c t f r o map r a c t i c a p o i n to fv i e w ，s u mg r a p h l a b e l i n gc a rb e u s e da s a c o m p r e s s e dr e p r e s e n t a t i o no fag r a p h ，ad a t as t r u c t u r ef o rr e p r e s e n t i n gt h e g r a p h d a t ac o m p r e s s i o nisi m p o r t a n tn o to n l yf o rs a v i n gm e m o r ys p a c eh u ta l s o f o rs p e e d i n gu ps o m eg r a p ha l g o r i t h m sw h e na d a p t e dt ow o r kw i t ht h ec o m p r e s s e d r e p r e s e n t a t i o no ft h ei n p u tg r a p h t h e c o n c e p to fs u mg r a p hw a sin t r o d u c e db yf h a r a r yin 】9 9 0 l e t g = ( 矿( g ) ，( g ) ) b eag r a p h ，w h e r ev = v ( g ) a n de = e ( g 1d e n o t et h ev e f e x s e ta n d t h ee d g es e to fgr e s p e c t i v e l y l e tn ( z ) d e n o t et h es e t o fa 1 1 p o s ir i v ei n t e g e r s ( i n t e g e r s ) t h es u mg r a p hg + ( s ) o faf i n i t e s u b s e t s 仁n ( z ) l st h eg r a p h ( s ，e ) w l t h “v e1 fa n do n l yi fh + y s ag r a p h giss a i dt ob ea ( a ni n t e g r a l ) s u mg r a p hi f ili sis o m o r p h i et ot h es u mg r a p h o fs o m es cf l ( z ) - t h e ( i n t e g r a l ) s u mn u m b e r o - = 盯( g ) ( f = f ( g ) ) o fgi s t h e s m a l1 e s tn u m b e ro f i s o l a t e dv e r t i c e sw h i c hw h e na d d e dt 。gr e s u l t ina ( a n i n t e g r a i ) s u m g r a p h ， i ，e 口= a ( g ) = m i n s ：3 s c n ，s u c h t h a t g u s k f 兰g + ( s ) ， a n ds 0 j ( f = f ( g ) = m i n s ：3 s c z ， s u c hth al gus k e 兰g + ( s ) ，a n d ，0 ) i t i so b v i o u s l yt h a t f ( g ) 盯( g ) f o ra n y g r a p h g t ob e t t e ru n d e r s t a n dt h en o t i o n so ft h es u mg r a p ha n d t h ei n t e g r a ls u m g r a p h ，s o m ea u t h o r sg i v eu st h ed e f i n i t i o n so ft h e ( i n t e g r a l ) s u ml a b e l i n g a ( a ni n t e g r a l ) l a b e l i n go fg r a p h gi sao n e o n em a p p i n g ：矿( g ) 斗| v ( z ) a ( a ni n t e g r a l ) l a b e li n glo fgi sc a l l e da ( a ni n t e g r a l ) s l i ml a b e l i n gi f f o r 5 山东师范大学硕士学位论文 e v e r yp a i ro fd i s t i n c tv e r t i c e s u a n dv o fg ，柳e ( g ) i fa n do n l yi ft h e r e e x i s t sw 矿( g ) w i t h三( “) + 己( v ) = 三( w ) ，f o rc o n v e n i e n c e ，t h r o u g h o u tt h i s p a p e rw em a ya s s u m et h a tt h ev e r t i c e so f ga r ei d e n t if i e dw i t ht h e i rl a b e l s s i n c ef h a r a r yp r e s e n t e dt h ec o n c e p to fs u mg r a p hi n1 9 9 0 ，t h er e s e a r c h w o r kh a sb e e na i m e da td e t e r m i n i n gt h es u mn u m b e r ，i n t e g r a ls u mn u m b e ro fs o m e g r a p hc l a s s e s u pt on o wt h e ( m o d ，i n t e g r a l ) s u mn u m b e r so fs o m ep o p u l a rg r a p h s s u c ha sc o m p l e t e g r a p h sk n ，c y c l e sc 。，p a t h s 只，b i p a r t i t eg r a p h sk 。 w h e e l s 峨，f a n s 只a n dc o c k t a i lp a r t yg r a p h s h 2 。h a v eb e e no b t a i n e d ，b u tt h e r e s e a r c h e st ot h ep r o p e r t yo ft h es u mg r a p ha n dt h ei n t e g r a ls u mg r a p hh a v e b e e nig n o r e d t h ef i r s tc h a p t e ro ft h i sp a p e rg i y e su sab r i e fi n t r o d u c t i o na b o u tt h e b a s i cc o n c e p t s ，t e r m i n o l o g i e sa n ds y m b o l sw h i c ha r eu s e di nt h i sp a p e r i n t h es e c o n dc h a p t e rt h ep r o p e r t i e so fi n t e g r a ls u mg r a p h sa r ed i s c u s s e d i n t h et h i r dc h a p t e rw ed e t e r m i n et h es u mn u m b e r so fg r a p h 瓯。a n d k 一e ( n k 2 ) r e s p e c t i v e ya n dd e f i n ean e wg r a p h 三。a n db o u n di t ss u mn u m b e r an e wk i n d o fe x c l u s i v eg r a p h si sa l s od e f i n e d i nt h el a s tc h a p t e rw ed e t e r m i n ean e w k i n do fi n t e g r a ls u mt r e e sb yi d e n t i f i c a t i o n i nt h i sp a p e rw eh a v et h ef o l l o w i n gt h e o r e m s t h e o r e m2 1f o rn 4 i n t e g r a ls u mg r a p hgh a sa tm o s tt w on o t e sw i t h 一ld e g r e e s ：gh a st w on o t e sw i t hn ld e g r e e si fa n do n l yi f g 兰g + ( 一1 , 0 12 - 一，n 一2 ) t h e o r e m2 2f o r ”4 c ，t r 占c g ，f 三1 + ，t n e n gi sn o ta ni n t e g r a ls u ms r a 。n ：t h eb o u n di sn e s t p o s si b l e c z ，。e t 盯：r a i n t s + s ：scs e s , s s 芒e ，t r 盯：z f 三1 + 2 ，t h e n gt sn 。ta i n t e g r a ls u mg r a p h ：t h eb o u n di s b e s tp o s s i b l e 6 山东师范大学硕士学位论文 t h e o r e m2 3f o rn 4 ，( g ) 一2 ， z f 郧，匕j 十l ，t n e n g 。tai n t e g r a ls u m 鲫叭呲o u n a i s 慨t p o s s i b l e ： c z 盯：4 舟2 ，t n e n g 。ta ni n t e g r a ls u mg r a p h , t h e o r e m3 1 f o rh 5 c r ( k 。一e ( n k 2 ) = 2 n 一3 t h e o r e m3 2 1 f o r 3 ，盯( g 。) = 2 n + 1 t h e o r e m3 3 3 2 n s 口( 只。) 2 n + 2 t h e o r e m3 4 3f o r 盯3 ，2 盯( 。) 3 t h e o r e m3 5f o rn 5 ，c 。i se x c l u s i v e t h e o r e m4 2t r e e sw i t ha t lf o r k sa t1 e a s td i s t a n c e2a p a r ta n de v e r yf o r k c o n t a i n sap a t hw i t hl e n g t h2a r ei n t e g r a ls u mg r a p h s k e yw o r d s ( i n t e g r a l ) s u mg r a p h ；( i n t e g r a l ) s u mn u m b e r ：( i n t e g r a l ) s u m l a b e l i n g c l a s s i f j c a t i o n0 1 5 7 6 7 山求师范大学硕士学位论文 第一章预备知识 本文仅讨论有限无向简单图，相关的主要概念和记号如下： 和图的概念是由h a r a r y 0 1 提出的从实际应用来看，图的( 整) 和标号可以作 为该图的压缩表示。即表示图的数据结构当利用输入图的压缩表示来工作时，数据 压缩不仅可以节省内存，还可以加快某些图算法的运算速度所以，给出图的( 整) 和标号，确定或估计图的( 整) 和数是很有实用价值的 令( z ) 表示正整数( 整数) 集，( z ) 的非空有限子集s 的和图g + 岱) 是图 ( s ，e ) ，其中“v e 当且仅当“+ v s 对于图g ，若存在s c n ( z ) ，使得g 兰g + ( s ) ， 则称图g 是( 整) 和图对于任意图g ，若存在最小的非负整数仃= 盯( g ) ( f = f ( g ) ) 使得g u 盯( f ) k 为( 整) 和图，称此数为g 的( 整) 和数，即： 仃= 盯( g ) = m i n s ：3 s c n ，使得g u s k ，兰g + ( s ) ， 其 中 s o ) ( f = f ( g ) = m i n s ：3 s c z ，使得g u s k ，兰g + ( s ) ，其中s d ) ) 显然对任意的图g 有 f ( g ) 仃( g ) 为了更好地理解和图与整和图的定义，许多作者。1 又给出了( 整) 和标号的定义： 图g 的一个标号是v ( g ) j n ( z ) 的一一映射l 如果存在图g 的一个标号l 满足：对 v ( g ) 中的任意两个互异顶点h 和v ，“v e ( g ) 当且仅当存在w v ( o ) 使得 l ( u ) + l ( v ) = 工( w ) ，则称此标号为图g 的一个( 整) 和标号为了方便，在本文中， 如果没有特殊说明，顶点的( 整) 和标号与顶点可以不加区分 在图g u m k ，的( 整) 和标号中，个顶点“称为工作顶点，若存在一条边掣， 使得 = x + y ：否则，称“为非工作顶点如果g u m k 的任意边的两端点( 标号) 之和都是孤立点，称g 为不可兼( e x c l u s i v e ) 图；否则，称g 为可兼图 确定图的和数与整和数，是h a r a r y l 9 9 0 年提出来的，由于难度较大，迄今为止， 经过许多作者的研究只确定了一些简单图类的和数与整和数，如：圈c “1 ，路p 。“3 ， 二分图k ，3 1 州1 “，轮w 。”，扇f 。叫，树，酒会图h 2 m 州侧等等；在 1 0 中z h i b oc h e n 山东师范大学硕士学位论文 用粘合( i d e n t i f i c a t i o n ) 的方法证明了某特殊的树t 是整和图 与本文相关及有用的结果如下： 剃，油娜i 掣吲邺。 定理”“：酒会图h ：。是不可兼图 定理“：完全二分图k 。，f ( 世。) = o - ( k 。) = 2 n - 1 定理“1 ：路只，f ( 只) = 0 定理：盯( g 。) = 0 ：f ( g 。) = 0 定理：除k 外，o - ( t ) = 1 定理”。3 ：叉点距离至少为4 的树是整和图 定理“3 1 ：立方体e3 是非整和图 9 山东师范大学硕士学位论文 第二章整和图的性质 和图或整和图性质的研究却是很少的我们仅有： 趔渺一棚瑚榔私掣 本章给出一个图是整和图的必要条件 引理“”非平凡整和图g ，0 s 当且仅当g 的最大度a = r 一1 定理2 1n 阶( 4 ) 整和图g 至多有两个扮一1 度顶点：g 含两个n 一1 度顶点当 且仅当g 兰g + ( 一1 , 0 ，1 ，2 ，n 一2 ) 证明设g = g + ( s ) 记s + = s s ：s 0 ) ，s = s s ：s 0 ( 1 ) 当 s + i 22 时，设s 。= m a x s ：s s + ) 则对任意的s s + 一 s o ，有 j + 芒s 所以有d ( j ) o ) 则对任意的s s 一 一所o ，都有5 + ( 一掰) s 不妨设 s = 一m 0 n l ( 一m ) + a 4 _ l = 0 山东师范大学硕士学位论文 ( 一m ) + ( f 一1 ) m = ( f 一2 ) m = a ，2 ，所以( 一m ) + 口。= 口，一1 = ( i - 1 ) m ，得口。= i m ( f = 1 ， h 一2 ) 故s = 一m ，0 ，m ，2 m ，( h 一2 ) m ) ，g 兰g + - 1 0 1 ，一，n 一2 充分性显然 定理2 。1 褥证 ( 1 ) 若d ( g ) f 爿+ 1 ，则g 不是整和图：且界不可以改进 ( 2 ) 令盯：垒m i n 扣+ s s s ，d 硅毋，若盯，2 r 訇+ 2 ，则g 不是整和图：且界不可 以改进 证明假设g 是整和图( s ，e ) 不妨设1 s + l 1 s l ，因有1 s + 1 + i s l ”一1 ，则 p + l l 三j ，( n 2 ) 设s t , s 2 分别为s + 中的最大元与次大元对任意的s e _ s + - - 溉 ，都 有s 十s 1 s i ，所阻s s l 仨e ，特别的有s 2 s 1 茌e ( 1 ) 出以上叙述知，6 蔓d ( 啪n p + i n l 到= f n 2 1 t 里条件矛盾，故g 不 是整和图 下图举例说明界不可以改进 2 ( 2 ) 由以上叙述可知：对任意的s s + 一“，s 2 ，都有s + s 2 s 2 所以船2 e 当且 山东师范大学硕士学位论文 仅当s = s 一s ：所以有c r 2 - d ( ) + d ( 占：) 伽一p + 9 + m p l + 1 ) 可纠+ 1 与定理条 件矛盾，故g 不是楚和图 h a r a r y 在 1 中定义的整和图g 。= k 。v ( g 。v g 。) 恰好表明了此界是最好可能 定理2 2 得证 定理2 3 设g 是一个n 阶( h 4 ) 图，如果( g ) r t 一2 ，那么有以下结论： ( 1 ) 若j ( g ) l 到+ l ，则g 不是整和图：且界不可以改进 ( 2 ) 若c r 2 2 l 兰j + 2 ，则g 不是整和图 证明假设g 是整和图( s ，e ) 不妨设p + ；1 s 1 设$ d s 2 分别为s + 中的最大元与 次大元因为”4 ，九一2 ，由弓1 理知，。匹s 所以p + l f 纠，2 ) ( 1 ) 万d ( _ ) n p + l 匕与定理条件矛盾，故g 不是整和图 下图c ，说明界不可以改进 图 ( 2 ) q d ( 啪+ d ( s ：) 2 。一p + 9 + 1 2 l 到+ l 与定理条件矛盾，所以g 不是整和 定理2 3 得证： 山东师范大学硕士学位论文 第三章几类图的和数 本章我们主要讨论了图k 。e ( n k ：) 与图瓯。的和数，定义了新图只，、l ，并 给出了它们的和数的上、下界，定义了一类新的不可兼图c 。 3 1 五。一e ( n k ：) 的和数 h a r a r y 在 1 中提出了问题：确定k 。一e ( n k 2 ) 的和数本节回答此问题。 由于”= 1 时，k i i e ( k 2 ) = 2 k 1 ，n = 2 时，k 2 ，2 一e ( 2 k 2 ) = 2 k 2 ， n = 3 时， k 3 3 一e ( 3 k 2 ) = c 6 ，n = 4时， k 4 4 一e ( 4 k 2 ) = q 3 ， 故 f o ，咒= 1 ； 眠，川蚂) = 岂三 在本讹仅考虑剜的髋 1 3 , 4 或5 ，n = 4 令g = k 。一e ( n k 2 ) ，( 一，占) 是g 的二分类，a = 如l ，日2 ，d 。 ，b = 蛾，6 ：，6 。 v = a u b 设m = 仃( g ) ，s 是g u m k ，的和标号集顶点与其标号不加区分不妨 谚 6 ，= m a x v ：v 矿) ， 日l 口2 一 d 。，e ( n k 2 ) = 盯j 6 1 ：i = 1 ，2 ，一，玎) 引理3 1 1 对任意i r ，_ ，f ，o i + 6 lga ( 5 ) 证明若存在p t 、q ，使得口。+ 6 ，a ，不妨设口p + 6 ，= 口，则对任意的，、 p ，有拜，+ 6 1 = ( 口，+ 6 1 ) + 6 p s ，故拜p + 抚e a u 协p ，由口p 十6 le s y 知f = r ， 即口，+ 6 ，= q 故对任意的_ ，p 、f ，d ，+ 6 i k 。，6 ， ，月兰4 ，与竹5 矛盾结 山东师范大学硕上学位论文 论成立 引理3 1 2 假设存在口p + 6 ，c = s v 则对任意的i ，、q ，盘+ 6 p c ( 疗5 ) 证明对任意的i q ，d ，+ ( a ，+ 钆) = ( q + 6 q ) + a p 萑s ，故q + 6 p 4 u 协f u c 由 引理3 1 1 ，对任意的f q 、f 。a ，+ 6 ，札 u c 若存在r g 、f ，使盘，+ 6 。= 6 ， 则对任意的k p 、q 。a k + 6 ，= ( 吼+ 屯) + ，s ，故嘶+ 6 ，口u k ， ，敌对任意的 k p 、q 、f ，吼+ 钆 6 ， ，故n 4 ，与h 5 矛盾结论成立 引理3 1 3 假设存在，+ 6 。b ，则对任意的i q ，d ，+ b 。b ( 月5 ) 证明设口p + b q = b ，则对任意的i r 、q ，a + 6 ，= ，+ ( a ，+ 6 q ) s ，故 c l ，+ 6 。b u k ， ，由引理3 1 1 知：对任意的f r 、q 、f ，有日，+ 6 。b t t f _ i = ， ，时，也有口，+ b 。b ( 1 ) 若存在，q 使d ，+ b q c ，则由引理3 1 2 知，对任意的i f 、q d ，+ b v c ， 故对任意的i ，、q 、，q 十钆b u k ， n c = 中，故盯4 ，与盯5 矛盾 ( 2 ) 只需再汪f _ ，、t 时，日，十6 a 若吼+ 6 。a ( = ，或r ) ，设吼+ b q = d ， 则对任意的q 、s ，q + 口j = ( d ，+ 6 。) + q 硭s ，故q + 屯au 溉) u c 由引理 3 1 ，1 及上述论述知，对任意的，q 、s 、t 有口，+ 6 。 6 。 ，故 茎4 ，与 25 矛盾结 论成立 5 i 理3 1 4 盯( k 。e ( n k 2 ) ) 2 n 一3 ( n 5 ) 山东师范大学硕士学位论文 证明我们分两种情形讨论 情形1 存在p f 、q ，使a ，+ 6 9 甚c 由引理3 1 1 知“，+ 6 。b ； 由引理3 1 3 ， 对任意的f g a c + b q b b = 札，n 1 + 6 u ，d 2 + 6 q ，d q i + ，d q + 1 + 6 q ，一，a 。+ ，这样6 ，= 盘。+ 6 u 翠f 于是列歹g ，i ，有球，+ b ，证b ，这样a ，+ b j c ，i t ，j g 、i 下分两种情况证明珥+ b s c ，j # q 、t ( 1 ) 若对任意的g 、t 有- a , + 6 ，g c ，则由上述论述，啦+ 6 ，a ，q 、f 则k ，+ 6 ，q + b 2 ，q + 钆) 一h + ，a t + 包j 爿，由于q ，故q + b 不妨设 + 6 q = b ，则对任意的，、r b ，+ 6 ，= ( q + 6 ，) + 茌s ，故日，+ 6 ，bw a q u c 这 样对任意的j r 、f 、q 有q 十6 ，协。 ，故”s 4 ，与 5 矛盾 ( 2 ) 存在，q 、，使日，+ 6 ，c ，则对任意的j t ，( 。+ 6 ，) + 6 ，= ( 口，+ 6 ，) + 6 ，gs ， 故q 十6 ，b u a 。 u c 故对，、q ，q + 6 j 仁， u c t i i e a 。+ 6 ，诺k ， ，j f 、 g 若存在q + 玩= 口，则对口r 、，有日，+ 屯= ( q 十) + 6 ，sr 故 ，+ 溉) u 月故对q ，、，q + = 6 ，出- y - n 5 ，所以存在1 使得l r 、 q 、r 、s ，且。，+ b j = ( 。，十b j ) + b 、s ，这与q + 6 l c 矛盾 上面已证，对，f 、q ，口r + 6 ，c 这样，对任意的，q 、i t d ，+ 6 ，c 故 口1 + 6 1 ，“l + b 3 ，口l + b q i ，a i + 6 “+ l ，口l + b n ) 2 ( 2 日1 + o 矿口1 + 口2 + 气，a l + 订川+ 6 q ，q + 口+ i + 6 q ，q + a 。+ 易q ) c ，而且 口1 + 缸，。一，q 一1 + 6 f ，口f + 1 + 6 l ，c l 。+ 包 c 又a q + ( 口j + 6 q ) = a l + q + 6 q c ，且 2 a f + 气 q + 口2 + 口i + c l q l + 盯l + d q + b q a t + d q + l + 6 q i + a 。+ b q 些垄塑蔓查兰堡圭兰焦笙壅 一 一 d 。+ 6 ， - 口i - l + 6 f f + 1 + 6 r 口。+ 6 f 故盯( k 。一e ( n k 2 ) ) 2 n 一3 情形2 对任意的i f ，i ，口，+ 6 ，c 当r 1 时，口l + b 2 ，盘l + b 3 ，一，a l + 以，a 2 + 6 i ，口，- l 十包，口f + 1 + h i ，吼+ 6 f 是s v 中互异的2 n 一3 个点：当，= 1 时，a 2 + b 3 ，盯2 + b 4 ，口2 + b n ，口2 + 乜 码+ 6 l ，口。+ 6 1 是s v 中互异的2 ”3 个点故盯( k 。，一e ( n k 2 ) ) 2 行一3 ( n 5 ) 日i 理3 。1 5 盯( k 。一e ( n k 2 ) ) 兰2 一3 ( 2 ) 证明对( k 。一e ( n k ：) ) 给出如下标号 口，= 8 i + 1 ，f = 1 , 2 ，一- ，”； 6 = 8 j + 3 ，j = 1 , 2 ，h ：8 k + 4 ，= 2 , 3 ，t 一，n 一1 ，n + 1 ，2 n 1 ； t i i e s ： 。f 一，d 。，b l ，岛，“2 ，+ 1 ，“2 h 是( k 。一e ( n k 2 ) ) 的和标号 n ，+ 订= 8 ( i + ，) + 2 诺s b ，+ b ，= 8 ( i + ，) + 6 仨s l i p + l l 。= 8 ( p + q + 1 ) 芒s 订，十z ，女= 8 ( i + k ) + 5 芒s ， 6 。+ z k = 8 ( j + 七) + 7e s ， ( f ，+ 6 ，= 8 ( i + ) + 4 ，当i + jn , 2 行时，口，+ 6 = “。，s ，1 f ， ，即 a t b 。l ，口2 e m ，a 。b 。，a n b n 茌s ，共有n 条匹配边被去掉故s 正是k 。e ( n k 2 ) 6 山东师范大学硕士学位论义 的和标号 据引理3 1 4 和3 1 5 ，得定理： 定理3 1 1 对n 5 ，。k 。一e ( n k 2 ) = 2 n - 3 3 一g 。的和数 h a r a r y 在 1 中提出来了“一类有用的和图g 。”：令n 。= 1 , 2 ，n ) g 。= g + ( n 。) 显然，如果用( = l ，2 ，阳) 给其标号，当且仅当3 ，+ j s l l 时，i 与 j 连边 n q 1 又定义了整和图g 。，k v ( g 。v g 。) 本节将确定g 。的和数 令g = g 。，设= 仃( g ) ，s 是g u m k 的和标号集顶点与其标号不加区分令 k i = c ) ；a = d l ，口2 ，a ，b = b i ，6 2 ，。b 表示两个g 。的顶点 集v = a u b v o c ，c = s v 定理3 2 1 对 3 ，盯( g 。) = 2 n + 1 先证明o - ( g 。) 2 n + 1 情形1 c = r r l a x q ，口2 ，d b l ，6 2 ，v ，b ，c 刁i 妨设b ，= m i n a i , d 2 ，- 一，。，b t , b 2 ，- ，b 。) 贝0 c + 口i ，c + d 2 ，c + d 。，c + 6 i ，c + 6 2 ，c + b 。 c 下面证明6 ，+ a j c 山东师范大学硕士学位论文 若存在p 使得玩+ 口。a ，不妨设6 f + a p 2 口，则口，+ c 。( 6 ，+ c ) + 口p s ，这 与b ，+ c c 矛盾 若存在g 使得轨+ d 。b ，不妨设以+ a 。= 巩则以+ c 。( 6 j + c ) + 口。s ，这 与b ，+ c c 矛盾 所以6 。+ 疗，c u c 因为拧3 ，至少存在一个口，使得6 ，+ 口，c 这样， c + 口i ，c 十口2 ，c + 口。，c + b i ，c + 6 2 ，c + b 。，b f + 口j c 故盯( g ”) 2 n + l 情形2c 不是y 中最大者，不妨设6 。= m a x a 。，口：，。，6 i ，6 ：，屯，c ) ，则 6 。+ a n ，b 。+ a 。，6 。+ c ) c ，有以下4 个结论： ( 1 ) 对任意的，- ，口，+ b ，诺a 事实上，若存在p 、q 使得疗，+ 6 。a ，不妨设d p + 6 q = 口，则 d 。+ 6 。，= ( 6 。+ 口p ) + 6 q s ，与b 。+ 口p c 矛盾 ( 2 ) 对任意的f ，口+ b ，c 事实上，若存在p ，q 使得口p + 6 v = c ，则c + 6 。= ( 6 。+ 口p ) + c s ，与6 。+ 口，c 矛盾 ( 3 ) 对任意i ，a ，+ c 茌a 事实上，若存在g 使得d 。十c a ，不妨设a g + c = 口，则口，+ b 。= ( 口q + 6 m ) + e s 与口。+ 6 。c 矛盾 ( 4 ) 若存在七使得d + c b ，则对任意的口，有口。+ c b 事实上，若存在使得a 。+ c b ，不妨设吼+ c = 缸，则对任意的n 。， 山东师范大学颂七学位论文 a + b ，= ( 日，+ c ) + 吼s 口，+ c v ；由( 3 ) 知：对任意的口，有a ，+ c b 子情形2 1 日，：m i n q ，a 2 ，a n , c ) ，此时有 ( a ) 对任意的i ，+ b ，茌b 事实上，若存在p 使得d ，+ 6 ，b ，不妨设d ，+ 6 ，= b ，则对任意的口，有 a i + b ，2 ( n + b p ) + d ，s ，有口，十6 p v ；由( 1 ) 、( 2 ) 知：a i + 6 ，诺a 且口+ b ，f ， 故对任意的日，q + b ，v a 一 c ) = b 这样 6 p ，q + 6 p ，+ 6 p 占，与蚓= 疗矛 盾 ( b ) 对任意的i ，a ，+ 玩c 若d 。+ c c ，则 6 。+ 口l ，6 。+ 。，b 。+ c ，a + 6 l 。，a 。+ “，口。+ c ) c a ( g 。，) 2 n + l 若存在p 使得n + c = b 。，出( 4 ) 知：对任意的a ，有矗，- f c 雪即 b = f ( 1 l + f ，口。+ c - 若6 。b ”因为，7 3 ，有6 p + 氓= ( 矗、+ 6 1 ) + c s ，与( h ) 矛 盾所以6 。= 缸，即d 。+ c = b ，由d 。的最小性知：b 是b 中最小者设6 。，= “，+ c ， 则d ，足ac p 最大者；设6 l = 口，+ c ，因为啪”，n b 。+ b i = ( d ，+ c ) + ，+ f ) c 山 ( b ) 及l 一述论述： 6 。+ a i ，一，b 。+ 盯。，b 。+ c ，a ，+ 6 l ，一，a 。+ 6 。，b 。十b l 3 口，+ c + “i ，+ c + d 2 ， c 十口 口。+ ( n 【+ c ) ，。+ ( d 2 + c ) ，一，口，+ ( d 。十c ) ，( j + c ) + ( 口，+ c ) ) c ， o - ( g 。，) 2 n 十1 子情形2 2c = m i n a 1 ，。2 ，口。，c 山东师范大学顿士学位论文 此时有：对任意i ，6 。+ 印5a 否则，若存在q 使得6 。+ c a ，不妨设6 q + c = 口， 则口，+ b ，= ( c 十6 。) + b 。s ，与c + b 。c 矛盾 女口果对任意的i ，以。+ c c ，贝u b 。+ 口i ，一，b 。+ 口。，b 。，+ c ，4 l + c ，口。+ f c ， 仃( 瓯。) 2 n + 1 否则，由( 3 ) 与( 4 ) ，b = b + c ，口2 + c ，d 。+ c ；其中设