（系统理论专业论文）裂变图的顶点标号.pdf

原创性声明 本人郑重声明：所里交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：蓝筮到日期：2 9 吐，互：! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：商敛& l 导师签名： 日 期：套2 q 生：缱 山东大学硕士学位论文 裂变圈的顶点标号 高敏剐 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) 中文摘要 图的染色理论是图论中的重要课题，它既有着广泛的实际应用背景，又是极 有趣味的数学课题，对它的研究已经有一百多年的历史了许多图论中的理论都 是围绕着它展开的，图的标号问题就是图的染色问题的推广，本文所讨论的裂变 图的顶点标号就是其中的一个推广 图的顶点标号的研究背景是频率分配问题此问题最早是1 9 8 0 年由h a l e 在 文献【1 】中提出的，h a l e 给出了这样的定义：给定些无线电发射台。要求对每 个无线电发射台分配一个频率使得相互干扰的无线电发射台所分配的频率的间 隔在允许的范围之内后来他将此类问题归结为图的t 一染色问题，图的丁一染 色问题在过去十几年里被广泛地加以研究( 见【2 , 3 ，4 ，5 】) 文献【6 】6 中指出r o b e r t s 提出了在几个不同地点的无线电发射台有效地分配无线电频率。频率用非负整 数表示。使得相近的地点分配到不同的频率，相邻的地点分配的频率至少相差 2 ，从而使得这些频率不会相互干扰 g e r a r dj c h a n g h 和d a v i dk u o 于1 9 9 6 年 在f 6 1 6 中更精确地提出图g 的l ( 2 ，1 ) 一标号的概念，他们还给出了解决一般图 g 的l ( 2 ，1 ) 一标号问题的算法。2 0 0 0 年g e r a r dj c h a n g ，w ，t k e ，d k u o ，d d 一 f l i u 和r k y e h 1 l j 将图的l ( 2 ，1 ) 一标号问题推广到图的l ( d ，1 ) - 标号问题， 图g 的( d ，1 7 一标号是指一个从顶点集g ) 到非负整数集的函数，( u ) ，使得 若d ( u ， ) = 1 ，则i y ( u ) 一，( ”) i d ：若d ( u ，”) = 2 ，则i ，扣) 一，( ”) i 1 图的一个 k l ( d ，1 ) 标号是图的一个l ( d ，1 ) 一标号，使得所有标号都小于等于k 并且至少 有个达到k 图g 的上( d ，1 ) 一标号数是一个使得g 有一个k 一五似1 ) 一标号 的最小数k ，记作k ( g ) g r i g g s 和y e h 【6 1 于1 9 9 2 年证明了对一般图的l ( 2 ，1 ) - 标号问题是p 一完备问题作为推广，工( d ，1 ) - 标号至少是n p - 完备问题。 从而，要直接给出一般图的比较好的l ( d ，1 ) 一标号的困难性可想而知，因此， 人们转而研究某类图的l ( d ，1 ) 标号数的上界。以此来间接解决实际问题近 几年，图的标号问题又被推广到图的l ( d 1 ，如) 一标号图的。一标号以及图的 l ( d t ，如，d 。) 一标号( 参考文献【1 9 】) 本文讨论的裂变图的顶点标号是标号问题的又一推广文章共分为三章： 1 、第一章引言，给出顶点标号相关背景和预备知识 2 、在第二章，本人将染色理论推广到赋权图的l ( d a ) 一标号，引入了一类 新图( 即裂变图) ，借助该类瓤图，给出了一般图的裂变图的l ：) 一标号数的上 山东大学硕士学位论文 界，并给出了几类图的裂变图的l ( 籍) 一标号 其主要结果如下： 定理2 1 1 设图g 是最大度为的一般图，则其裂变图g 满足 吲0 , 1 ( g ) n o a + d n 。一d ，令凡一i 。蜀) i 定理2 1 3 一般图g 的裂变图g 满足磕i ( g ) = x ( c ) 一1 3 、在第三章，本文将文献 1 9 】中图的z ( d ：1 ) 标号推广到赋权图的工( d 0 , 正1 , 2 1 ) 一 标号，给出了一般图的裂变图的工( d 0 1 d a , 2 。) 一标号数的上界，并证明了赋权图的 l ( “0 , 1 , ，2 。) 一标号是图的l ( d ，1 ) 一标号的推广，给出了图g 的裂变图的l ( 0 1 嚣) 一标 号数与图g 的2 一色数的关系，而且给出了几类重要图的裂变图的l ( 矬：) 一标 号数的上界，并以推论形式给出文献【l9 】中的一些重要结论 其主要结果如下： 定理3 1 1 图g 是最大度为的一般图，其裂变图d 满足 a d 0 a 正, 2 i ( g ) sn o a 。+ ( d 一1 ) n o a d ( 珊一1 ) 引理3 , 2 1 对一般简单图g ，其裂变图g 满足 a d 0 , d 1 , 2 l ( g ) ) b ( g ) + ( d 一1 ) x ( g 。) 一d 定理3 , 2 4a 0 d - d - , i , 2 l ( g ) d n o x 2 ( g ) 一d 定理3 2 5a d 0 ，, d 1 , 2 l ( g ) d n o ( 麟d ( 日) ) + d ( n 。一1 ) 定理3 3 1 对最大度为的二般平面三角剖分图g ，对于其裂变图g 有 a d 0 , 矗1 , 2 l ( g ) sn o a 2 十( d 一3 ) n o 一d ( n o 一1 ) 定理3 , 5 2 对最大度为的r 一单位球图g r ( r 2 ) ，其裂变图g 满足 必( g ；) 黼苦n o a 2 + d n o a + d ( 旷t ) 本文的主要创新点： 1 、引入一类新图，借助此类新图可以更好的研究标号问题 2 、将染色问题推广到图的l ( d 0 ，, 1 1 ) 一标号 3 、将图的l ( d ，1 ) - 标号推广到裂变图的( d 0 d , 1 , 2 1 ) 一标号 关键词： 染色；裂变图；l ( 4 ，1 ) 一标号；l ( ：j 欠标号；l ( ：嚣) 、号 2 山东大学硕士学位论文 t h el a b e l i n go nf i s s i l eg r a p h s g a o m i n g a n g ( i n s t o fm a t h & s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ) a b s t r a c t t h et h e o r yo fg r a p hc o l o r i n gi sav e r yi m p o r t a n tp r o b l e mi ng r a p ht h e o r y i t i sav e r yi n t e r e s t i n gm a t h e m a t i c a lp r o b l e ma n di t sa c t u a la p p l i c a t i o nb a c k g r o u n d i s v e r yb r o a d t h es t u d yo ft h et h e o r yc a nb et r a c e dt o o v e ro n eh u n d r e dy e a r s a g o m a n yt h e o r i e sa b o u tg r a p ha r ed e v e l o p e da r o u n di t i t i sag e n e r a l i z a t i o n o ft h ec o l o r i n gp r o b l e m sa n dt h el a b e l i n gw h i c hi ss t u d i e di nm yp a p e ri sj u s to n e g e n e r a l i z a t i o no ft h ec o l o r i n gp r o b l e m s t h e s t u d yb a c k g r o u n do fg r a p hl a b e l i n gi st h ef r e q u e n c ya s s i g n m e n tp r o b l e m w h i c hw a sf i r s t l yp u tf o r w a r db yh a l ei n i l 】i n1 9 8 0 ，t h ed e f i n i t i o ng i v e nb yh a l e w a sa sf o l l o w s ：t h ef r e q u e n c ya s s i g n m e n tp r o b l e mi st oa s s i g naf r e q u e n c yt oe a c h r a d i ot r a n s m i t t e rs ot h a ti n t e f e r i n gt r a n s m i t t e r sa r ea s s i g n e df r e q u e n c i e sw h o s es e p - a r a t i o ni sn o ti nas e to fd i s a l l o w d es e p a r a t i o n s h a l ef o r m u l a t e dt h i sp r o b l e m i n t ot h en o t i o no ft h et - c o l o r i n go fag r a p hw h i c hh a sb e e ne x t e n s i v e l ys t u d i e d o v e rp a s td e c a d e ( s e e 2 ，3 ，4 ，5 】) i n 【6 】r o b e r t sp r o p o s e dav a r i a t i o no ft h ec h a n n e l a s s i g n m e n tp r o b l e mi nw h i c h ”c l o s e l l t r a n s m i t t e r sm u s tr e c e i v ed i f f e r e n tc h a n n e l s a n d ”v e r yc l o s e ”t r a n s m i t t e r sm u s tr e c e i v ec h a n n e l st h a ta l ea tl e a s tt w oa p a r t i n 1 9 9 6g e r a r dj c h a n ga n dd a v i dk u od e f i n e dt h el ( 2 ，1 ) - l a b e l i n gp r e c i s e l yi n 【6 j a n dg i v e dt h ea l g o r i t h mt ol a b e lag e n e r a lg r a p h ，i n2 0 0 0g e r a r dj c h a n ga n d w t k ee t cg e n e r a l i z e dl ( 2 ，1 ) - l a b e l i n gt ol ( d ，1 ) 一l a b e l i n g t h el ( d ，1 ) - l a b e l i n g i saf u n c t i o n ，( u ) f r o mt h ev e r t e xs e t i ? ( g ) t ot i l e s e to fa l ln o n n e g a t i v ei n t e - g e r s s u c ht h a t i ，( t ，口) i d i fd ( u ， ) = 1a n d ，( “， ) ii f d ( u ) = 2 a k l ( d ，1 ) - l a b e l i n gi s a nl ( d ，1 ) - l a b e l i n gs u c ht h a tn ol a b e li s g r e a t e rt h a nk ， t h el ( a ，1 ) 一l a b e l i n gn u m b e ro fgd e n o t e db ya ( g ) ，i st h es m a l l e s tn u m b e rks u c h t h a tgh a sa 女一l ( d ，1 ) - l a b e l i n gi n1 9 9 2g r i g g sa n dv e h 6 】p r o b v e dt h a tt h e l ( 2 1 1 一l a b e l i n gp r o b l e mi s p c o m p l e t ef o rg e n e r a lg r a p h s a st h eg e n e r a l i z a t i o n o ft h el ( 2 ，1 ) - l a b e l i n gp r o b l e m ，t h el ( d ，1 ) - l a b e l i n gp r o b l e mi sa l s o p c o m p l e t e f o rg e n e r a lg r a p h ，s oi t i sd i f f i c u l tt os t u d yt h ep r o b l e m d i r e c t l y h e n c er e s e a r c h e r s t u r n e dt os t u d yt h eu p p e rb o u n d so ft h el ( a ，1 ) - l a b e l i n gn u m b e r so fs o m ec l a s s e s o fg r a p h sa n dt r yt os o l v et h ea c t u a lp r o b l e m i nr e c e n ty e a r st h el a b e l i n gp r o b l e m h a db e e ne x t e n e dt ot h el ( d l td 2 ) - l a b e l i n gp r o b l e m ，t h el n - l a b e l i n gp r o b l e ma n d 3 山东大学硕士学位论文 t h el ( d l ，d 2 ，靠) - l a b e l i n gp r o b l e m ( s e e 1 9 】) ， t h el a b e l i n go nf i s s i l eg r a p h si nt h i sp a p e ri sa n o t h e rg e n e r a l i z a t i o no fl a b e l i n g p r o b l e m t h i sp a p e ri sd i v i d e di n t ot h r e ec h a p t e r s ： 1 i nt h ef i r s t c h a p t e rw eg a v e t h eb a c k g r o u n do fl a b e l i n ga n dt h er e l a t i v e k n o w l e d g e 2 i nt h es e c o n dc h a p t e r ，t h et h e o r ) o f c o l o r i n gw a se x t e n e dt ot h el ( “0 , 1 ) 一l a b e l i n g o fw e i g h t e dg r a p h s ，a n dac l a s so fn e wg r a p h s ，c a l l e df i s s i l eg r a p h s ，w a sg i v e n t h e u p p e rb o u n do ft h e ( 0 d 1 , z ) 一l a b e l i n gn u m b e ro ft h eg e n e r a lf i s s i l eg r a p h sw a sg i v e n a n dt h e 工( “0 , 1 ) 一l a b e l i n go ns e v e r a lc l a s s e so ff i s s i l eg r a p h s - t h em a i nr e s u l t sa r ea sf o l l o w s ： t h e o r e m2 1 1f o rt h eg e n e r a lg r a p h so f m a x i m u md e g r e e ，t h el ( d 0 1 1j i a d e 儿g n u m b e ro ft h e i rf i s s i l e 口a p h s 嗡0 , 1 ( g ) sn 。+ d n 。一d ，n ”l 。m 1 s 】的k 一距离稳定集s + 由定义知，如果我们认为非赋权图的边权为单位 1 ，那么一距离稳定集就等价于k 一稳定集，可见，k 一距离稳定集是k 一稳定 集在赋权图中的推广 定义1 2 7 f 1 2 j 图g 的一个k 顶点2 一着色是指k 种颜色1 ，2 ，k 对于g 的 各顶点的一个分配称顶点2 一着色是正常的，如果任意两个距离小于等于2 的 顶点都分配到不同的颜色当g 有一个正常的顶点2 一着色时，就称g 是顶点 可2 一着色的为方便起见，我们把”正常的顶点2 一着色”简称为2 一着色， 而把”正常k 顶点2 一着色”简称为k 一2 一着色，类似地把”k 顶点可2 一着色 1 简称为k 可2 一着色显然，一个图是k 可2 一着色的当且仅当它的基础简单 图是k 可2 一着色的因此在讨论2 一距离着色时，可以只限于讨论简单图g 的2 一色数x 2 ( g ) 是指使得图g 为k 可2 一着色的数k 的最小值若x 2 ( g ) = k ， 则称g 是k 一2 - 色的 定义1 2 8 【1 2 | 赋权图g 的顶点 的9 一度畦( ”) 是指g 中与 的距离小于 等于2 的点的数目用如( g ) 和：( g ) 分别表示g 的顶点的最小2 一度和最大 2 一度 本文中所说的一般图都是指一般简单图，其它相关术语参考文献 1 2 l 另外 一些概念，将在必要时予以阐述 8 第二章 赋权图的l ( d 0 , 1 1 ) 一标号 在第二章，本人给出了赋权图的l ( ：；：；) 一标号的概念，从而推广了图的标号 问题，并给出了几类图的工( 正0 , 1 ，) 一标号赋权图的( d 0 , ，1 ) 一标号实际上是图的一 般染色的推广 标号问题以往研究的都是一个地点或无线电发射台仅分配一个频率的情况， 在我们的图论模型中对应的是每个点需要一个标号的情况然而我们实际多数 情况下，需要给同一个地点或无线电发射台分配多个频率例如，同一地区往往 会有多个通讯公司，不同通讯公司要从频率管理部门申请不同频率，这些频率之 间耍相互区分，而且，这个区分越大不同通讯公司的信号相互干扰才会越小，他 们的用户手机信号才会越稳定随着手机用户的急剧增加，要想满足用户手机使 用，而且保证信号的正确稳定，各个通讯公司和频率管理部门就不得不考虑频 率的合理分配问题这样，以往的研究就有一定的局限性了，并不能为所有实际 问题给出合理解决方法为此，我们在本章第一节引入了一个新图，借助这个新 图，我们来研究图的标号问题 2 1 赋权图的l ( d o , 1 1 ) 一标号 对于每个顶点需要多个标号，我们考虑将以往研究的图的每个顶点”裂变 1 ，使得每个顶点满足，需要几个标号就”裂变”成几个新的顶点，然后，我们按 照一定规则给它们连边在此思想基础上，假设图g = ( v ，e ) 的每个点q 需要 n 。个标号，我们引入下面的新图： 定义2 1 1 图g = ( u e ) 的裂变圈g 。= ( 1 j ，e 。，) 是如下定义的赋权图： 顶点集i = u i i ，一，u l n l 一，t 。m r m 一，v w l l ，q l | n j 边集e = u i k 嘞：或者i = ，和1se lsn 藏者1 冬i js | ，1 女曼 7 l 。1 f 茎n j 和u v j e ) ， 边权 i = j ，1sk fsn 5 寸， 1si js j v 1s ks 啦，1szs 唧，吨码e 时 其中，1 1 7 i 是图g 的顶点数 令k = v i l ， 。) ：1 墨i 旷i ，我们会发现每个k 与图g 中的仇对应， 而且每个k 在裂变图g7 中的点生成子图是完全图 _ i 我们不难想象，图g 的 9 山东大学硕士学位论文 每个顶点q 需要m 个标号的问题，就转化为了每个顶点集 j 需要m 个标号的 问题，即裂变图g 的每个顶点需要一个标号的问题下面我们将不带权图的标 号推广到赋权图的标号， 定义2 1 2 对任给的“， r 和非负整数d ，赋权图g = ( 1 ：e ，w ) 的l ( 猫) 一 标号是指一个顶点集r 到非负整数集f 0 、1 ，女) 的函数 ( ) ，使得若d ( u ，u ) = 0 ， 则j ( “) 一，o ( ”) f2 础若d ( “，) = 1 ，则 ( “) 一 ( f ) f 1 赋权图的女一三( d 0 , 。1 ) 标号 是赋权图的一个l ( ：；) 一标号，使得至少有一个顶点取到 赋权图g = ( 1 ，e ，w ) 的l ( 驻) 一标号数是使得g 有一个k 一( ： ) 标号的最小数，记作a 。o , ；( g ) 当赋权图的边权均为1 时，令n o = l l l a x 啦) = 1 | 裂变图中不同顶点之 l 三连卜j f 间距离都大于0 不难想象裂变图的基础图与原图同构，赋权图的l ( d 0 , 】t ) 一标号等 价于图的染色，这一点也可以通过定理2 1 3 及5 2 2 的定理及推论得到验证 下面我们给出一般图的裂变图的l ( 嚣) 一标号数的一个上界： 定理2 1 1 设图g 是最大度为的一般图，则其裂变图g 满足 a d 0 , 1 1 ( g7 ) 7 2 0 立+ d n 。一d 令，n 05 l 。要黟( g ) l m j 证明：考虑如下标号方案：开始时所有顶点未得到标号，令s d + - = s d + 2 = = s l = 曲对i = 01 ，2 当s “s d 忆，最一t 确定且还有未标号的 顶点时，令 一l e = 如t ( c 。) ：。未标号且对所有的：z us j d ( “t ) 2 1 ) i - d - rl 选取只的极大1 一距离稳定子集s 。，即s 是只的1 一距离稳定子集但s 不 是丘的任何1 一距离稳定子集的真子集，注意若f l = 曲即对任意的未标号顶点 卜一l t h i 存在某个顶点u 昌，使得d u ，“f ) 1 时，有强：( 砭) = d n o d 或a d o ，, 1 l ( 只) = d n o d + l ，并且两类值 均有图取到 证明：( 1 ) 不失一般性，我们假设路b 的顶点按照u 。”2 ：，u 。的顺序排列， 取n l 十n 2 = ，m a ，x m + ”州一1 ) 由于i j 与k 的所有点生成予图是完全图 1 = 二“ 虬：+ 故 础( 群) ) ( ( 巧) 一1 x ( 机) 2 n i + n 2 1 。m a 。x 。 n t + + 1 1 ) 下面我们给出一种标号，其标号数至多为m a ，x m + n i + 1 1 ) 首先给k 和 k 以标号，= 0 ：1 ，、一，n l + 凡2 1 ( n i 用，中的数给h 和k 中的点标号) ，然后 我们按照下面的规则给其它顶点集标号，当点集k 已给出标号厶垦，( 非负整数 集合) 而k + l 未标号时，由于啦+ n 。n ：+ n 2 因此我们可以用，一的子集 给k 标号，直到所有点集都给出标号故有a 跗( ) 畏黑( n 。+ 7 t i + l 一1 - 从 而定理成立 ( 2 ) 令 j l = 0 ，d d n o d ， 如= 1 ，d + 1 一，d n o d + 1 设k 是具有n o 个点的点集，因为我们给l j 标号时。至少要用n o 个数，我 们可以用，l 给k 标号，所以，我们有a o d , 。i l - 瑶) 2d n o d ，下面我们考虑用，和 如给群标号，显然这两个数集中均有n o 个数，所以我们可以交替用 的子集 和1 2 的子集( 均包括本身) 给k i ；l 标号，从而得到赋权图砭的( o d , 1 。) 一 标号因而，a 0 d , l i ( 巧) sd 伽一d + 1 ( n ) 不存在相邻点集k 和k 使得n ，= n ：= 礼。时，显然我们可以先用 ，。或如给诸1 ；标号，然后用厶的子集卡口，z 的子集给e 中其它点集标号，这 时有a 0 “a ( e ) = d n o d ( b j 存在相邻点集1 7 ；和k + 1 使得n = “= “o 时，我们对相邻点集k 和 l ；+ - 至少应该用，- 和如标号，这时有a ：i ( e ) = d n o d + 1 推论2 2 1 【l ：2 jr 是有n 个顶点的路，其色数( r ) = 2 证明：由定理2 2 1 ( 2 ) ( b ) 知，当r t i = n 0 = 1 ( 对所有的1sisn ) 时，对应 l ( ： ) 一标号即为图的一般染色，且色数为d n o d + l + 1 = 2 推论得证 定理2 2 2 对于有九个顶点的圈c j 其裂变图c 二满足 ( 1 ) 当n 为偶数时，有a 氍( 嘭1 = 。m 。a x 。 n t + ? l i + l 一1 ) - ( 2 ) 当n 为偶数时，有q 0 , 1 1 ( c ：) = 2 n o 一2 或2 m 一1 ，并且两类值均有裂变图 取到 ( 3 ) 当d = 0 或d 23 时，有d n o d s 0 “, 1 ( 暖) d n o d + 2 ，并且三类值均 有裂变图取到 证明：( i ) 类似定理2 2 1 ( 1 ) ，我们先给k 和以标号i = o ，1 ，n l + n 2 一 1 2 山东大学硕士学位论文 1 ) ，其中n l + r t 22 忍黑 啦+ h i + l ，然后我们按照定理2 2 1 中的规则给其它点 集标号 ( 2 ) 令 i l = 0 ，2 ，2 n o 一2 ) ， 如= 1 ，3 ，2 m l 设k 是具有“o 个顶点的点集，同定理2 , 2 1 中的标号规则，我们有2 伽一2s a 2 0 , 。1 ( 暖) s2 n o 一1 ，并且两类值均有裂变图取到 ( 3 ) 令 ，l = o ，d ，：d n o d ) ， 厶= l ，d + l ，一，d n o d 十1 ) ， ，3 = 2 ，d + 2 ，d n o d + 2 ) 设k 同上，同定理2 2 1 ，我们有a d 0 ，, 1 l ( ) d n o d ，当n 为偶数时我们可 以依次用z 的子集和2 的子集给眨中的点集k 标号；当n 为奇数时，我们依 次用 的子集和厶的子集给矗中的点集k 标号，直到剩下最后一个点集，我 们此时可以用厶给它标号所以有a “0 , 1 ( 暖) d n o d + 2 ( n ) 不存在相邻点集k 和k 使得，h = n i + 。= n o 时，我们可以先用，l 给 k 。标号，然后用厶的子集和，- 的子集给c ：中k 。左右的其它点集标号( 特殊 情况是当n 为奇数时，最后一个点集我们用厶一f d n o d + 2 ) 给它标号) 此时 有a ：( c 毫) = d n o d ( b ) n 为偶数且存在相邻点集i j 和k 十1 1 使得n ；= “t + l = n o 时或者n 为奇 数且存在i k ，满足m n o 时。我们可以用，i 和厶给c ：中的点集标号，此 时，有a d 0 , 1 l ( ) = d n o d + 1 ( c ) n 为奇数且吼= 珊( 对所有i ) 时，我们至少要用 和如依次给暖 中的点集标号，直到剩下最后一个点集为标号，我们用如给它标号，此时，有 a d o 1 l ( ) = d n o d + 2 推论2 2 2 【1 2 】对于有n 个顶点的圈c n ，当n 为偶数时，x ( g ) = 2 ；当n 为 奇数时，( c k ) = 3 证明：同推论2 2 1 ，由定理2 2 2 ( 3 ) ( b ) 知，当n 为偶数时，x ( g ) = 2 由定 理2 2 2 ( 3 ) ( c ) 知，当n 为奇数时，x ( g ) = 3 定理2 2 3 对有n 个顶点的树b 其裂变图满足 ( 1 ) 当d = 1 时，有砖：j ( 矗) 3 。m a 。x 。 h i 十“ ，一1 ) ，其中，n i 和n i ，对应的地 和”r 在图乃中相邻 ( 2 ) 当d l 时，有a 0 1 , l i ( ) = d d 或d n o d + 1 ，两类值均有树的裂变 图取到 证明：( 1 ) 类似定理2 2 1 ( 1 ) 中考虑k 及i ，+ - 一样考虑中的k 及其儿子 点集( 与之相邻的点集) 巧，从而得到a 0 , 1 ( ) = 。m a 。x 。 n | i + 礼b 一1 ) 由东大学硬士学位论文 ( 2 ) 令 1 1 = 0 ，d ，d n o d ) ， 1 2 = 1 ，d + 1 ，t ，d n o d + 1 依次用，- 和1 2 给树的裂变图中的父亲点集和儿予点集( 即相邻点集) 标号 从而得到了砭的一个l ( 2 i ) 一标号同定理2 2 1 ，可以证明本定理 推论2 2 3 【12 j 对有n 个顶点的树l ，其色数满足x ( 瓦) = 2 定理2 2 4 对有扎+ m 个顶点的完全二分图琢其裂变图砭。满足 ( 1 ) 当d 。1 时，有a 错( 砭，。) = 1 m 。a 。x 。 r k + “，一1 ) 其中m 与n ，对应的仇 和”。，在图编。中为邻点 ( 2 ) 当d 1 时，有a 正0 , 1 1 ( 。) = d n o d 或d n o d + 1 ，并且两类值均有图 取到 证明：( 1 ) 首先给u 和k 以标号，= o ，1 ，n l + 竹2 + l ，其中n l + n 2 = l ( m ；a 。x 。 h i + 礼，j ) ，然后，按照定理2 2 1 中的规则给其它点集标号即可得到裂变图 的标号数为m a 、x 。 n t + n 一1 ) 的二0 i ) 一标号 ( 2 ) 同定理2 2 1 定义，l ，2 ，以，1 和，2 分别给二分图的两部分标号，就得到 了裂变图的l ( d 0 , 】1 ) 一标号类似定理2 2 1 ，可证明本定理 定义2 2 1 【1 3 3 种一格图g 。是这样一个图，它的顶点集是所有有序n 整数组 ( i l ，i z ，i 。) ，其中两个顶点相邻当且仅当它辩有一个坐标不同且其差为l ， 它在无线电工程中有着广泛的应用 1 4 1 r 定义2 2 2 n b 一格图口。( n 2 ) 是这佯一个图它以n 一格图g 为支 撑子图，且加上边如下： ( i l ，i 2 ，k ) 与( ，岛+ 1 ：i o + 1 ) ；一i 。- ，t ) ，( 岛一1 ，i ( j + 1 ) ：一1 ，t t ) ，j = 1 2 ，礼，相邻，其中 r lj + 1 ，j 棚寸 0 + 1 ) l = i 1 j = 衙 对这两类图的裂变图我们有下面的定理； 定理2 2 5 对1 l 一格圈g k ，当d 3 时，其裂变图g ：满足a 爱；( g 0 = 一d 或d n o d + 1 ，两类值均有树的裂变图取到 证明：令 i l2 o ，d ，d n o d ) ， 是= 1 ，d + 1 ，一，d n o d + l 假设k 同上，同定理2 2 1 ，我们有a 嚣( g ：) d n o d 我们以札一格图g 。的 左下角顶点( 0 ，0 ，0 ) 为原点，以n 一格图的刻度为单位l ，建立直角坐标系，使 得点( i ，2 2 ，i 。) 即表示n 一格图g 。上该点的直角坐标在新裂变图中我们将 1 4 山东大学硕士学位论文 点集k 整体考虑，对应的有k 。的坐标为n 一格图g 。中的点( i 。，i 2 ，一，i 。) 的坐标我们按照以下规则标号；当。l + z 2 + q - i 。为偶数时，用 给k 。，：。 标号；当i i + i 2 十+ i 。为奇数时，用屯给k 。，。标号( 因为，- 和如中均有 n 0 个顶点，所以这种标号是可行的) 从而有砖：( g ：) d n o d + 1 ( n ) 不存在相邻点集k 和k + ，使得2 i = n = n o 时，可以先用 a ! y 2 或 给诸k 标号，然后用如的子集和，1 的子集给h 。的两种情况( i - + i 2 q - + 。 为奇数和偶数) 分别标号，这时有心 ( g ：) = d n o d ( b ) 存在相邻点集k 和i ，+ l ：使得n ：= “州= 7 l o 时，我们对相邻点集k 和 l ：，至少应该用1 1 和如标号，这时有畦：( g ：) = d n 0 一d + 1 推论2 2 5 ( ”】对n 一格图g 。，其色数满足x ( g 。) = 2 定理2 2 6 对与n 一口一格图玩( n 2 ) ，当d 3 时，其裂变图聪满足 d n o d a 盛( 或) d n o d - t - 2 ，并且三类值均有裂变图取到 证明：，l = o ，d ，d n o d ) ， 1 2 = 1 ，d + 1 ，d n o d + 1 ) ， 1 3 = 2 dq - 2 ，d n o d + 2 ) ， 假设l 同上，类似定理2 2 1 我们有砖：( b ：) 2d n o d 同定理2 2 5 建立 坐标系按照下面的规则给裂变图标号：当i 1 + i 24 - + i 。三0 ( r o o d 3 ) 时，以 ，i 给k m ，_ 。标号；当i l - b i 2 + + i 。! l ( r o o d 3 ) 时，以厶给k 一”，妇标号； 当i l + 屯+ ，- + i 。三2 ( r o o d 3 ) 时，以厶给k ， ：，一h 标号( 因为，l ，厶，厶中均有n o 个数，所以这种标号是可行的) 从而有a ：( 眨) sd n o d + 2 ( ) 不存在相邻点集k 和1 j 使得n ：= n ，= n o 时，可以先用 给k 标号，然后依次用如的子集， 厶的子集和，i 的子集给k 。，：。的三种情况 ( i l + i , 2 + + i n 三o ( m o d 3 ) ，i l + i 2 + + i 。三1 ( m o d 3 ) ，i l + i 2 + + i n 三2 ( r o o d 3 ) ) 分别标号，这时有a ：! ：( 瑗) = d n o d ( 6 ) 仅存在两个相邻点集k 和l j ：使得n ：= q = n o 时，至少应该用，l 、如 和如中的两个给k 和k 标号，此时有a ：i ( 口：) = d n o d + 1 ( c ) 存在三个相邻点集k 、i j 和k 使得n = n j = “ = n o 时，至少应该 用1 ，1 2 和厶给k 、l j 和k 标号，这时有a ：i ( 口：) = d 伽一d + 2 推论2 2 ，6 【1 2 】对与n b 一格图b 。，其色数满足x ( b 。) = 3 ， 第三章 赋权图的l ( d o , d 1 , 2 1 3 一标号 在这一章里，本人将标号问题进一步推广到赋权图的工( d 0 、, d 1 ，, 2 。) 一标号，并给出 t - - 般图的裂变图的l ( d 0 矗, 1 , 2 。) 一标号数的上界以及几类裂变图的l r 、o d l , d 1 , 2 i 、一标号数 上界 3 1 赋权图的l ( 矬；) 一标号 定义3 1 1 图抒= ( ：e ，w ) 是赋以非负整数边权的图，对任一非负整 数d 和v u ，口图h 的( ：篇卜标号是指一个顶点集i ，到非负整数集 0 1 k ) 的函数h ( v ) 使得若d ( “，t j 1 ，则i ( u ) 一 ( u ) l d ；若d ( u ， ) = 2 ， 则； ( u ) 一 ( ”) i 1 赋权图的k 一( “0 1 2 。) 标号是赋权图的一个l ( 黔j ) 一标号。 使得至少有一个顶点取到赋权图的l 、o , 1 2 。, ，、一标号数是使得图h 有k 一( d 0 正, 1 1 2 1 ) 标号的最小数 ，记作磺描( h ) 当n o = l 时，裂变图中不同顶点之间距离都大于0 ，不难想象裂变图的基础 图与原图同构，裂变图g 的l ( 并) 一标号就等价于原图g 的( d ，1 ) 一标号，所 以我们说赋权图的( 。0 , d 1 , 2 ，) 一标号是图的( d ，1 ) 一标号的推广 下面我们给出一般图的裂变图的( 数i ) 一标号数的一个上界： 定理3 1 1 图g 是最大度为的一般图，其裂变图g + 满足 a d 0 正, 1 , 2 l ( g ) s 珊2 + ( d 1 ) 住。一d ( n o 1 ) 证明：考虑如下标号方案：开始时所有顶点未得到标号，令s d + i = s d + z = = s - l = 咖对i = 0 ：l ，2 ，当& 一d + 1 s ；一d + 2 ：，& 一l 确定且还有未标号的 顶点时，令 卜- l r = v ( c 。) ：u 未标号且对所有的u us ，d ( u ) 2 ) t d + l 选取只的极大2 一距离稳定子集s 即s 是曩的2 一距离稳定子集但s ：不 是的任何2 一距离稳定子集的真子集，注意若e = ，即对任意的未标号顶点 i i q “，存在某个顶点u 【j 毋，使得d ( t ，h i ) 2 ，则= 西无论只= 曲与否， i d + l 标记s 中的顶点为i ，然后i = i + l ，直到所有的顶点得到标号假设k 是所用到 的最大标号并选取一个标号为的顶点f 、令 ，1 = i ：0 i 一l 且对某个u s 。d ( u ，v h l ) s1 ) ， 如= f f ：0si k 一1 x 对某个“s d ( u 吼1 ) 2 ) ： 1 6 山东大学硕士学位论文 1 3 = i ：0 i5k l 且对所有u s ，d ( u ，t ! h 1 ) 23 ) ， 显然有i 如l + i 厶i = k 我们考虑g 。的结构，可得到与顶点”州距离小于等于l 的顶点个数至多 为( g ) s ( + 1 ) n o l ；而与c 距离为2 的顶点个数至多为( 一1 ) n o ：= n o 2 一n o ，故有 i 如lsn o & 2 一r 如+ ( + 1 ) n o 一1 ， 另外，任给i 1 3 ，r a t e 只；否则s 。uv h l 是只的2 一距离稳定子集，这与s 的选取矛盾即存在u 。i - 一。t + 。岛中的某个顶点“，有d ( u ，u h t ) 1 ，也就是存在j ，满 足i d + 1sj i 一1 ，使得j ，l ，通过i 到这样的个j 的映射，从而定义了 一个从厶到，。的函数，则每个j ，t 是厶中至多d 一