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

独创声明 本人声明所呈交的学位论文足本人在导师指导f 进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示谢意。 学位论文作者签名 孝姒锄虢湫 引雉辄矽7 k 学位论文版权使用授权书 本学位论文作者完全了解当塑有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权堂蕉可以将学位论文的全部或部分内容编入有天数据库 进行搜索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。( 保密的学位论文在解密后使用本授权书) 学位论文作者签名 季级 铈躲高救刷程名南伊陬 签字目期：2 0 0 6 年歹7 拥日签字目期：2 0 0 6 年( 阳a j | j 山东师范大学硕士学位论文 下整和图与排斥下整和图 李敏 ( 山东师范大学数学科学学院：济南，山东，2 5 0 0 1 4 ) 中文摘要 本文所用图论基本术语与符号遵循文献f l j 1 9 9 0 年h a r a r y 2 1 提出和图的概念1 9 9 4 年h a r a r y 3 提出整和图的概念 令n ( z ) 表示正整数( 整数) 集，n ( z ) 的非空有限子集j 5 r 的和( 整和) 图g + f 印 是图( s ，e ) ，其中“o e 当且仅当u + u s一个图g 称为和( 整和) 图， 若它同构于某个scn ( z ) 的和( 整和) 图，我们说s 给出了g 的一个和( 整 和) 标号，并且将顶点与其标号不加区分g 的和数( 整和数) 。( g ) ( ( ( g ) ) 是使得 g u n k - 是和图( 整和图) 的非负整数礼的最小值 1 9 9 0 年b o l a n d 4 等人提出模和图的概念模和图是取sc 1 ，2 ，m 1 ) 且所有算术运算均取模m ( 三l s l + 1 ) 的和图由此，2 0 0 2 年s u t t o n 5 1 等人 提出了模和数的概念一个图g 的模和数p ( a ) 是使得g u p k l 是模和图的 非负整数p 的最小值 2 0 0 3 年m i l l e r 6 等人提出排斥图的概念图g u 礼k 1 的( 整) 和标号s 称 为排斥的( e x c l u s i v e ) ，若对每条边“w e ( g ) ，u + 乳矿( g ) 图g 的排斥和 数( g ) 是使得g u 扎z 有排斥和标号的非负整数n 的最小值 2 0 0 4 年赛文卿【7 提出模整和图的概念，模整和图是取sc o ，1 ，2 ，： p 1 ) 且所有算术运算均取模m ( l s l ) 的和图一个图g 的模整和数妒( g ) 是使 得g u 砂k l 是模整和图的非负整数妒的最小值 从实用的观点来看，各种和图标号都可用作图的压缩表示，即表示图的数 据结构当利用输入图的压缩表示来工作时，数据压缩不仅可以节省内存，还 可以加快某些图算法的运算速度 本文提出如下定义： 用l 。j 表示不超过实数z 的最大整数( 称为z 的下整数) ，q + 表示正有理 数集q + 的非空有限子集s 的下整和图g + ( s ) 是图( s ，e ) ，其中u 口e 当且 仅当h + j s 一个图g 称为下整和图，若它同构于某个scq + 的下整和 图我们说s 给出g 的一个下整和标号：并且顶点与标号不加区分下整和数 山东师范大学硕士学位论文 口( g ) 是使得g u n k l 是下整和图的非负整数n 的最小值 如果两条边有一个公共的端点，则我们称这两条边是邻接的在g u 盯7 ( g ) k 1 的一个下整和标号中，对于一个顶点w ，如果存在某条边“”，使得w = i u + uh 则称叫为工作顶点显然、工作顶点均为整数点对于边u u ，如果有 札十u v ( a 1 ，则称这条边是工作的 假设s 是图g 的下整和标号，且整数点均为工作顶点则称s 是图g 的 标准下整和标号 图g u n k l 的下整和标号s 称为排斥的( e x c l u s i v e ) ，若对每条边u u f ( g ) ：l u + j 乳y ( g ) 图g 的排斥下整和数5 ( g ) 是使得g u n k l 有排斥 下整和标号的非负整数几的最小值 下整和标号与排斥下整和标号是图的新的压缩表示 在本文的第一章中，我们主要介绍( 下整) 和图的“些概念，术语，符号；第 二章给出下整和图与排斥下整和图的一些结构性质；第三章确定了几类图的 下整和数与排斥下整和数，并给出确定某些图类下整和数的一种方法：第四章 讨论了几类图的下整和性与排斥下整和性：第五章指出了有待研究的内容 若集合s = z 。【1si n ) ，则令s l s = 甄一l 甄j l l 茎i 佗) ，且刘实 数七，令南l s j + s = 后l x i j + z 。 l i 曼札 ，s + 七= z 。十南1 1sisn ) 我们主要得到如下结果 定理2 5 设图g = ( k e ) 为非空下整和图，则 a ) 不存在点v 2 ，v 4 满足一1 j = l v 4 j ，l v 2 j = l 3 j ，v l v 2 ，v 3 v 4 岳e ，v l v 3 ：u 2 7 2 4 e b ) 不存在点啦( 1 i 5 ) ，满足0 仇一。5 1 ( 1 i 茎4 ) ， v 5 + w 1 = l 口5 + ? 2 4 j ，v 5 7 2 1 ，? 2 5 7 2 4 ) 7 2 i v 3 ，? 2 2 v 4 e ，7 2 1 v 2 ，7 2 3 v 4 乒e c ) 不存在点7 2 i ( 1 i 6 ) ；满足h j = a ( 1sis3 ) ，7 2 1 u 4 ，v 2 7 2 4 ，7 2 1 7 2 5 ， 0 3 7 2 5 ；7 2 2 v 6 ， v 3 v 6 e ，u 37 ) 4 ，7 2 7 ) 5 ，7 2 1 7 2 6 芒e d ) 不存在点v i ( 1 i 6 ) ，满足h j = k ( 1 茎i 3 ) ：u l ? 2 4 ，? 2 2 2 2 4 ，7 2 2 v 5 ，u 2 ，f 3 7 2 6 e ，q j 3 0 4 ，2 j 1 u 5 ， 0 3 u 5 ，7 2 1 0 6 硭e e ) 不存在点仇( 1si 曼6 ) ，满足h j = k ( 1 i 曼3 ) ， i v 4 ，u 2 v 4 ，? 2 2 7 2 5 ，v 1 7 2 6 e ，v 3 v 4 ，u 1 v 5 ，? 2 3 v 5 1v 2 7 2 6 ，? 2 3 7 2 6 e f ) 不存在点饥( 1si 6 ) ，满足h j = k ( 1 墨i 3 ) ，? 2 3 7 2 4 ，? 2 2 7 2 5 ，7 2 1 v 6 2 山东师范大学硕二 学位论文 f ，矶蛳，u 2 v 4 ， 1 啦) 啦u 5v 2 v 6 v 3 v 6 岳且 定理2 6 设图g 为下整和图，s 是g 的下整和标号且m a x ( s 一1 s | 1 ；k 是非负整数，则kj s j + s 也是g 的下整和标号 定理2 7 没图g l ，g 2 无孤立点，& 是g 。u 盯( g ；) 甄的下整和标号，口( g 。) 1 ，且m a x ( s | 一l & ) ；，g 是& 中的工作点集( i = 1 ，2 ) ，且c 2 中存在一点 与竹2 , a x c l 互质，贝0 口( g 1u g 2 ) 口。( g 1 ) + 口( g 2 ) 一1 定理2 8 设图g 无孤立点，s = s 1 u 岛为g u 口( g ) 甄的下整和标号，其 中s - 为g 的标号集，岛为孤立点的标号集，且m i n ( s 1i s l l ) i 1 ，k 为非负 整数，则k ( 1 纠+ 1 ) + s 为g u d7 ( g ) 塌的下整和标号 定理2 9 对任意下整和图g ，v ( c ) = 忱i o i n l ，若1 j 0 1 ) 。e ( 1 i 4 ) ： l 2 ， u 3 y 4 e ，1 2 1 u 3 ，u l m ，v 2 v 4 e ，则图g 的工作点数大于1 在定理21 0 2 1 3 中我们得到下面结果： 下整和图若包含g ，g ，k 2 卫2 或再作为其导出子图，则： 作点数大于1 3 1 节主要证明m 凰，珥，。，一e ( 珥) ，u 墨，。，硒，是下整和图： ，m ( m ，他，q 2 ) 的下整和数为2 ，c 5 ，g u 的下整和数为1 3 2 节主要证明m 1 ( 2 ，耳，。，u 坼m k ：一e ( 墨) ( 1 茎rsn 1 ) ，k 如 的排斥下整和数为1 ，( m ，n ，q 2 ) 的排斥下整和数为2 3 3 节给出确定图类下整和数的一种方法，并以，( m ，礼，q 2 ) ，巧，。 为例介绍了这种方法这种方法可让我们由一类下整和图构造出无数多类下 整和图，也可由一类图的下整和数确定出另一类图的下整和数的界需要用到 对称点的定义和定理3 3 1 峨，v j 称为图g 中的对称点，如果对图g 中任意不同于口。，u ，的点仇，都满 足7 ) i y k e ( g ) 当且仅当v j r 女e ( g ) 定理3 3 1 设u l ，u 2 为图g 中的两对称点，g 1 = g + v 1 。2 ( 若u 1 抛e ( g ) ，则 g l ：g ) ，g 2 = g 一1 j v 2 ( 若1 ；1 v 2 隹e ( g ) ，则g 2 = g ) ，则m i n ( g 。( g l ) ，o - ( g 2 ) ) 墨 盯7 ( g 一 1 ) 41 节讨论图g 研3 ) ，e ( m 尬) ( 2 茎2 msn ) ，瓦( n 3 ) ，巧，。一 e ( m k 2 ) ( r ，s m ) ，( n 3 ) ，r ( n 2 ) ，一e ( p m ) ( n m ) 在什么条件下是 下整和图主要有下面结果： 3 堕塑堕查堂堡主堂堡丝奎 定理4 1 1g ( 佗3 ) 为f 整和图当且仅当n = 3 或r 4 定理4 1 2 一e ( m 恐) ( 2 2 ms 扎) 是下整和图当且仅当 # l 或2 定理4 1 3 瓦( n 3 ) 为下整和图当且仅当n ：3 或4 定理4 1 4k 一e ( m k 2 ) ( r ，s m ) 是下整和图当且仅当m = l ，2 或3 定理4 1 5 ( n 3 ) 为f 整和图当且仅当n = 3 或4 定理4 1 6b m 2 ) 为f 整和图当且仅当n = 2 ，3 或4 定理4 1 7 k 。一e ( 厶) ( n m ) 为下整和图当且仅当l m 5 4 2 节讨论图e ；( n 2 ) ，3 ) ，坼，。一e ( m 尬) ( r ，s 7 n ) ，一e ( m k ，) ( 2s 2 ms7 。) ，玩一e ( p m ) ( 佗m ) 在什么条件下排斥下整和数为1 主要有下面结 果： 定理4 2 1 ( r ) = 1 2 ) 当且仅当n = 2 ，3 定理4 2 2e ( w j ) = 1 23 ) 当且仅当n = 3 定理4 2 3 ( 珥，。一e ( m k 2 ) ) = l ( r ，s 芝m ，。：s 2 ) 当且仅当m = 1 ，2 定理4 2 4 。( 凰一e ( m 辽) ) = i ( 2 2 msn ，n 2 ) 当且仅当m = 1 或 2 定理4 2 5e ( 一e ( p m ) ) = 1 ( 礼m ，m 不同时为1 , 2 ，3 ) 当且仅当 m = 12 ，3 或礼= m = 4 5 关键词：( 排斥) 下整和图；( 排斥) 下整和数；( 排斥) 下整和标号 分类号：0 1 5 7 5 4 山东师范大学硕二 学位论文 一一 l o w e ri n t e g r a ls u mg r a p ha n de x c l u s i v e l o w e ri n t e g r a ls l l mg r a p h 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 8r e 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 2 1p 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 h a r a r y 3 】p r e s e n t e d t h ec o n c e p to fi n t e g r a ls u mg r a p hi n1 9 9 4l e tn ( z ) d e n o t et h es e to fa l lp o s i t i v e i n t e g e r s ( i n t e g e r s ) t h e ( i n t e g r a l ) s u n lg r a p hg + ( s ) o f an o n e m p t yf i n i t es u b s e t scn ( z ) i st h eg r a p h ( s ，e ) w i t h “勘ei fa n do n l yi fu + s ag r a p h gi ss a i dt ob ea nf i n t e g r a l ls u mg r a p hi fi ti si s o m o r p h i ct ot h e ( i n t e g r a l ) s u m 盯a p ho fs o m escn ( z ) w cs a i dt h a tsi so n eo ft h e ( i n t e g r a l ) s u ml a b e l i n g ：a n d w ec o i r a i d e rt h ev e r t i c e sa n dl a b e l i n g sa st h es a m et h e ( i n t e g r a l ) s u l y in u m b e r 口f g l f ( f g ) ) i st h es m a l l e s tn u m b e ro fi 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 og r e s u l t e di na n ( i n t e g r a l ) s u mg r a p h r f h ec o n c e p to ft h em o ds l l l t ig r a p hw a si n t r o d u c e db yb o l a n d 4 】i l l1 9 9 0 a r o o ds u mg r a p hi sas n mg r a p hw i t hsc o a n da l ta r i t h m e t i cp e r f o r m e d m o d u l o7 nw h e r em l s l + 1 t h e n ，s u t t o n 5 】p r e s e n t e dt h ec o n c e p to fm o d 8 l i r a n u m b e rt h em o ds u i nn u m b e rp ( c ) o fg i st h el e a s tn u m b e rpo fi s o l a t e dv e r t i c e s p k ls u c ht h a tg up k ii sa r o o ds h i ng r a p h m i l l e r 6 1p r e s e n t e dt h ec o n c e p to fe x c l u s i v eg r a p h i n2 0 0 5as u ml a b e l i n gs i sc a l l e da ne x c l u s l v es u ml a b e l i n g ，i fu + u s v ( c ) f o ra n ye d g e 缸封e ( g ) t h ee x c l u s i v es u mn u m b e r ( g ) o fg i st h el e a s tn u m b e r o fi s o l a t e dv e r t i c e s c k ls u c ht h a tg ue k li sa l le x c l u s i v es u l t ig r a p h d o l l f 7 1p r e s e n t e dt h ec o n c e p to fm o di n t e g r a ls u n lg r a p hi n 2 0 0 4 ar o o d i n t e g r a ls l i mg r a p hi s a8 u r ng r a p hw i t hscz ma n da l la r i t h m e t i cp e r f o r m e d m o d u l omw h e r em i s l t h em o di n t e g r a ls u mn u m b e r 妒( g ) o fgi st h el e a s t n u m b e r 砂o fi s o l a t e dv e r t i c e sc k ls u c ht h a tg u c k l i sar o o di n t e g r a ls u m g r a p h f r o map r a c t i c a lp o i n to fv i e w ，s u n lg r a p hl a b e l l i n gc a nb eu s e da sac 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 ni si m p o rr a n tn o to f i l yf o rs a v i n gm e m o r ys p a ，c eb u ta l s of o r s 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 n e wc o n c e p t sa r ep r e s e n t e di nt h i st h e s i sa sf o l l o w s ： l e tl 。d e n o t et h el a r g e s ti n t e g e rw h i c hi sn o tl a r g e rt h a nt h er e a lx ，q + d e n o t et h es e to fa l lt h ep o s i t i v er e a l s t h el o w e ri n t e g r a ls u i ng r a p hg + ( s ) o fa n o n e m p t yf i n i t es u b s e tscq + i st h eg r a p h ( s ，e ) w i t hu u e i fa n do n l yi f l u + v j sag r a p hg i ss a i dt ob ea nl o w e ri n t e g r a ls u m g r a p hi f i ti si s o m o r p h i c t ot h el o w e ri n t e g r a ls u mg r a p ho fs o m escq + t h el o w e ri n t e g r a ls n l nn u m b e r o - ( g ) ) i st h es m a l l e s tn u m b e ro fi 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 og r e s u l t e d i nal o w e ri n t e g r a ls u mg r a p h av e r t i c e 叫i sc a l l e daw o r k i n gv e r t i c e i ft h e r ee x i s t sa ne d g e 口w i t h h + u j s u p p o s et h a tsi st h el o w e ri n t e g r a ls u ml a b e l i n go fg ，a n da l li n t e g r a lv e r t i c e s a r ew o r k i n gv e r t i c e s ，t h e nw es a yt h a tsi sas t a n d a r dl o w e ri n t e g r a ls u ml a b e l i n g al o w e ri n t e g r a ls u n ll a b e l i n gsi sc a l l e da ne x c l u s i v el o w e ri n t e g r a ls u p 2 1 l a b e l i n g ，i fl u + u j s v ( c ) f o ra n ye d g eu e ( c ) l o w e ri n t e g r a ls u ml a b e l i n ga n de x c l u s i v el o w e ri n t e g r a ls u ml a b e l i n ga r e a n o t h e rw a y su s e da sc 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 t h ef i r s tc h a p t e ro ft h i st h e s i s g i v e sab r i e fi n t r o d u c t i o na b o u tt h eb a s i c c 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 e so f ( 1 0 w e ri n t e g r a l ) 8 1 2 1 1 1 g r a p h i nt h es e c o n d c h a p t e rw eg i v es o m ep r o p e r t i e so f ( e x c l u s i v e ) l o w e ri n t e g r a ls u l t ig r a p hi nt h e t h i r dc h a p t e r ，w ed e t e r m i n e ( e x c l u s i v e ) l o w e ri n t e g r a ls u mn u m b e ro fs o m eg r a p h s ，a n dg i v eam e t h o do fd e t e r m i n i n gt h el o w e ri n t e g r a ls u mn u m b e ro fc e r t a i ng r a p h i nt h ef o u t hc h a p t e r ，w ed i s c u s st h e ( e x c l u s i v e ) l o w e ri n t e g r a ls u mp r o p e r t i e so f s o m eg r a p h sa tl a s t ，i nt h ef i f t hc h a p t e rw ea d v a n c et h et h i n g st ob ed i s c u s s e d i nt h i st h e s i sw eo b t a i nt h ef o l l o w i n gr e s u l t s t h e o r e m2 5 s u p p o s et h a tg i san o n e m p t yl o w e ri n t e g r a ls n n lg r a p h 、 t h e n a ) t h e r ee x i s tn ov e r t i c e sw 1 u 3 v 4 硭e ， u l v 3 ，u 2 m e v 2 ：u 3 ，v 4 ，s a t i s f y i n g 1 j = l v 4 ，l v 2 j = h j ，v l v 2 6 山东师范大学顶士学位论文 b ) t h e r ee x i s tn ov e r t i c e sv i ( 1 茎i 茎5 ) ，s a t i s ( y i n g0 u i v 5 1 ( 1 is 4 ) ：l v 5 + ”lj = i v 5 + v 4 j ，v 5 v l ，廿4 v i v a ，v 2 v , 1 e ，v 1 7 ) 2 ，7 ；3 v 4 岳e c 1t h e r ee x i s tn ov e r t i c e s 嘶( 1 曼i 6 ) ，s a t i s f y i n gl v i j = k ( 1s 。s3 ) ，u l v 4 ，v 2 v 4 1 w 5 ，v 3 y 5 ， u 2 v 6 ，v 3 v 6 e ，? ；3 u 4 ，v 2 7 ) 5 ，v l v 6 岳e d ) t h e r ee x i s tn ov e r t i c e s ( 1 is6 ) ，s a t i s f y i n gl 地j = k ( 1 i 3 ) ，7 ) 1 u 4 ，7 ；2 7 ；4 v 2 y 5 ，v 2 v 6 ，可3 u 6 e ，7 ) 3 t 1 4 ， u l v 5 ) u 3 v 5 ，钉1 e e ) t h e r ee x i s tn ov e r t i c e s 仇( 1 is6 ) ，s a t i s 毋i n gl v i j = k ( 1si 3 ) ，v l w 4 ，7 7 2 7 ) 4 ， u 2 u 5 ) 7 ) 1 v 6 e ，7 ) 3 u 4 ；7 ) t 7 ) 5 ：u 3 郇5 ，_ 1 1 2 7 ) 6 ，7 ) 3 7 ) 6 隹e f ) l h e r ee x i s tn ov e r t i c e sv i ( 1sis6 ) ，s a t i s f y i n gl 仉j = k ( 1 曼i 墨3 ) ，v 3 v 4 ，_ ? j 2 v 5 ， 7 ) 1 7 ) 6 e j l 口4 ，7 ) 2 7 ) 4 ，v l v 5 ，7 ) 3 v 5 ： d 2 7 ) 6 ，u 3 ”6 e t h e o r e m2 6 s u p p o s et h a tg i sal o w e ri n t e g r a ls u mg r a p h ，si sal o w e r i n t e g r a ls u ml a b e l i n g ，a n dm a x ( s l s j ) r 2 为 2 n 一4 ，s u t t o n m i l l e r 1 1 1 证明v v ( n 5 ) 的和数当札为奇数时为n ：礼为偶数 时为；+ 2 窦文卿【7 】证明凡( n 5 ) 和数当扎为偶数时为3 ，竹，为奇数时为 4 ；，。一e ( n k 2 ) 的和数为2 n 一3 m i l l e re t a l 1 2 证明酒会图岛，。= 元瓦( n 2 ) 的和数为4 n 一5 m i l l e r 证明完全图甄( n 4 ) 的排斥和数为2 n 一3 ，( n 5 ) 的排斥和 数为礼，r ( 礼三5 ) 的排斥和数为n ，酒会图凰，。= 一n k 一。( n 2 ) 的排斥和数为 4 n 一5 王海棠 1 3 证明k r ，。( 2srss ) 的排斥和数为r + s + 1 , k r ，。一e ( r k 2 ) 的排斥和数当s r = l 时为s l ，当s r 2 时为s + r 一3 ，而对 n 5 ，一e ( 珥) 的排斥和数当r = 几时为0 ，当r = 礼一1 时为扎一l ，当 2sr k ，所以l n 。4 - b jj s 1 综上，s 1 为g u m k 。的下整和标号，即g u m k l 是下整和图 由定理1 2 1 ，可给出图的下整和数这个有意义的概念图g 的下整和数 a f f g ) 是使得g u m k 。是下整和图的非负整数，n 的最小值显然，一( g ) 玉o ( g ) ， 因而用下整和标号表示图比用和标号更节省内存 在g u 0 - ( g ) 风的一个下整和标号中，对于个顶点w ，如果存在某条边 u ”，使得1 1 2 = l i t + t 叱则称w 为工作顶点显然，工作顶点均为整数点对于 边伽，如果有l u + w l y ( g ) ，则称这条边是工作的 假设s 是图g 的下整和标号，且整数点均为工作顶点，则称s 是图g 的 标准下整和标号 定理1 2 2 下整和图一定存在标准下整和标号 1 2 山东师范大学硕士学位论文 证令s = u u 矿u w 7 是图g 的下整和标号，其中u = h 为工怍顶 点1v = f 0 i h 为整数非工作顶点) ，w = u j 。5 讪为非整数非工作顶点) ，k = m z n j ( 1 一( 7 ) i 1 u i j ) ) 1 、0 。一1 7 1 i j ) 1 w i w ) ，v = v + ，下证s = u u vu w 为图g 的下整和标号 1 ) s 中各元素互异且s c q + 2 ) 由于l v i + k + v j + 纠二【仇+ v j j ，l 碗+ 南+ j = 1 + 码j ，l v i + 七+ j = 奶+ i j + l k + w j1 jj = u 。+ 爿= h + 屿j ，所以在标号s 。下，任意两 顶点之间有边当且仅当在标号s 下有边 综上，s 为图g 的下整和标号由标准下整和标号的定义可知，s 。为图g 的标准下整和标号 推论1 2 3 图g 存在下整和标号当且仅当图g 存在标准下整和标号 定理1 2 4 若g l jm k l 有一个排斥的下整和标号，则对任意自然数q ，g u ( m + q ) k 、也有一个排斥的下整和标号 证设s o = s u f 训l ，7 1 ) 2 ，7 1 j 。) 为g u ? 7 7 , k i 的一个排斥下整和标号，其中 s = f o ：l l5 isn 是g 的标号，令k = m a z l a i j ( 1si n ) ，7 1 j 1 ，叫2 ，7 1 7 m ，q k i 的标号为s = 吼= + 1 + 上7 + 1 l l 。q ) ，s l = 岛u s ，易证下面论断成立： 1 ) s 。中元素互异且s 。 q + 2 1 在标号s o 中存在的边在s - 中仍然存在：在标号岛中不存在的边在标 号s l 中仍然不存在，且对任意的让 ee ( g ) ，h + j s 1 v ( g ) 3 ) 任取两点6 ：s 7 ，b j s ，l b i + b i j = l k + l + 南+ + 1 + 彘j = 2 k + 2 簪s 1 ； 任取两点c ，es ，b jes 7 ，b + b jj k ，所以l c i + b i j 岳s 1 综上，马为g u ( m + q ) k ，的一个排斥下整和标号 由定理12 4 ，有理由定义图g 的排斥下整和数图g 的排斥下整和数 e ( g ) 是使得g u n k 。有排斥下整和标号的非负整数礼的最小值显然，盯。( g ) e ( g ) 4 c ) 若图g 无孤立点，则( g ) 1 1 3 些查堡里奎堂塑主堂笪笙奎 第二章 下整和图与排斥下整和图的结构性质 下整和图与排斥下整和图的结构性质具有普遍性，而且对确定下整和数与 排斥下整和数有重要意义，本章先予于讨论 定理2 1 设g = ( ve ) ，8 为g 的下整和标号，则 a ) 设最大整数标号为6 ，5 ，= 。：i b n 。e ) ，则n 。 。1 1 设s 2 = 矧b n j e ) ， 则嘶l b ) 设c ，。：s ，c 为整数， 1 ，则 e ， c ) 若a s 2 非空，则b 2 d ) 设g ( s 1 非空，啦，q s l 若。i a j e ，则k a 。+ 。，= 1 s ；若。0 7 聋e ， 则l ( l i + 0 j = 0 e ) 品中任三点吼，吼，若满足吼。j e ，n ：岳e ：，e ，则啦 0 5 g ) s i 中不存在点n ，( 1 i 茎5 ) ，满足毗。2 e ，0 1 0 3 隹e ，0 2 n 3 硭e ，( 1 3 g 4 e ：a 3 a 5 e ，a 4 a 5 e 证 a ) 若如1 ，则s 弓【6 十n 。6 + 1 ，与b 为最大整数标号，矛盾：若a j i ， 则l b + 唧j = b ，b a j e ，矛盾 b ) 显然 c ) 由题设知存在点o 。，s 2 ，a i a j 日，由a ) 得毗1 ，。，1 ，所以 b 2j a 。+ o ， 2 n 2 + 凸， l n z + n k 1 o j + o k 1 1 4 ( 1 ) ( 2 ) ( 3 ) 若胪q d 0而 或如 o = 吁吼 1_4贝 目 以幻所呵 - ：嘶 s 7 0 l 1 = “叫 0 卜 得h 得 a则由 由e 由 町 血 坐堕奎兰堡主堂垡堡窭 亨? 。o 5 ，由( 1 ) 式得。j o5 ，由( 2 ) 式得d o 5 ，所以+ 吼 l ，与 ( 3 ) 式矛盾，所以啦 o5 ( 4 ) ( 5 ) ( 6 ) 6 所以+ i ：与( 6 ) g ) 若存在上述性质的点，因为a l a 2 e ，l 。3 隹e ，o , 2 a 3 譬e ，由e ) 得 a 3 0 5 ，矛盾 定理2 2 设图g = ( k e ) 没有孤立点，口( g ) 1 ，则在g u 盯7 ( g ) 甄的下 整和标号中，最大标号点为孤立点，g 的标号都大于等于1 ，孤立点均为工作顶 点，孤立点的标号均大于等于2 此论断显然 定理2 3 设图g = ( v 曰) 没有孤立点，则e7 ( g ) 三i 在g u ( g ) 凰的排 斥下整和标号中，最大标号点为孤立点，g 的标号都大于等于l ，孤立点均为工 作顶点，孤立点的标号均大于等于2 此论断显然 定理2 4 设图g = ( k e ) 没有孤立点且为下整和图，s 为g 的下整和标 号，最大标号d 不为整数，d = k - t - c ( ：i d l ) 则 a ) 芝1 b ) 粤q - = o ；j d 凸。e ) ，9 2 = ( j d 弓甓e ) ，则吼 1 ，七q 2 ，d o g ( d ) s d e g ( k ) c ) 若g f q l 非空，则1 q 2 ，c o ，5 d j 在c ) 的条件下，c q ：n ( ) 为完全图 证a 1 显然 b ) 由于图g 无孤立点，故q l 西因为l d + 啦j2 七，d 为最大标号，所以 【4 + o 刈= s 由于l d + 。d = + 【c + 啦j = 七，所以毗 i ，进而七q 2 由 吼 l 可得k a e ，即d 的邻点均为的邻点，所虬d 印( d ) sd 叼( ) 1 5 山东师范大学硕士学位论文 c ) 在g 0 l j 中取边吼n ，：则l n 。十j 大于等于o5 ，不妨设为n 。因为d , a 。四 c + 啦 1 ，而。，0 5 ，所以c 1 ，。+ b j = 1 ，所以6 如，e ，所以g q 2 n ( k ) 为完全图 定理2 5 设图g = ( k e ) 为非空下整和图，s 为g 的下整和标号，则 a ) 不存在点v 2 ：地，v 4 满足一1 j = l 4 j ，l 2 j = h j ，v t 奶，忱u 4 譬e ，u 1 3 ： 2 u 4 e b ) 不存在点仇( 1s 1 + t j 4 j ，1 j 5 u 1 ，砜，”1 如 c ) 不存在点矾( 1 。6 ) ，满足h = k ( 1 is3 ) ：u l 4 ，v 2 v 4 ，口l 5 ，如， 2 现u 6 e ，7 ) 3 v 4 ， u 2 5 ) 口1 u 6 e