（运筹学与控制论专业论文）复合图gkk的l（21）标号.pdfVIP

摘要 图的l ( 2 ，1 ) 一标号来自于频道分配问题：某一区域有若干电台，不同的电台要使用无线 电波发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置较 近的电台要使用有一定相差的频道。将频道分配给电台，目标是在保证电台互不干扰的前 提下使用最少的频道资源。图的l ( 2 ，1 ) 一标号是一个从点集y ( g ) 到非负整数集的函数，满足条 件：( 1 ) 当“口e ( g ) 时，l ，( 一，( 删2 ；( 2 ) 当d ( u ，口) = 2 时，l ，( t ) 一，( ”) i 1 。图g 的l ( 2 ，1 ) 标 号数定义为：沁，1 ( g ) = m i n im a x f ( ”) ：口y ( g ) ) ，即图g 的所有l ( 2 ，1 ) 一标号中最大标号的 最小值。 考虑下面的实际问题：在同一个地区，有很多电台，通常情况下每个电台有多个频道。 本文考虑了每个电台都需要k 个频道的情况，为了防止频道之间的相互干扰，同一个电台 的k 个频道要相互区分，每两个都至少要相差2 ，如果两个电台v o 和”1 距离为1 ，电台v o 的每个 频道和电台口l 的每个频道都至少要相差2 ，如果两个电台v o 和 l 距离为2 ，电台v o 的每个频道 和电台”l 的每个频道都至少要相差1 ，这实际上是图g 的一个k 重l ( 2 ，1 ) 一标号问题。图g 的一 个k 重l ( 2 ，t ) - 标号问题等价于复合图g t k k 的l ( 2 ，1 ) 标号问题，其中甄是k 个顶点的完全图。 文章的第二章首先引用复合图g 【日】的定义，然后给出当日为完全图j 靠时，复合图的一 些基本性质。文章的第三章研究了一些基本的图类与完全图玩的复合图的l ( 2 ，1 ) 一标号。对 于n 个顶点的路r ，得到t p k k 的l ( 2 ，1 ) 一标号数。对于任意的树t ，给出了t 暇刈的l ( 2 ，1 ) 一标 号数的上下界，即( + 2 ) k 一1sa ( t k k ) ( + 2 ) k + 4 。最后，当g 为n 个顶点的圈g 时，我 们得到了部分结果。 关键词：频道分配问题；l ( 2 ，1 ) 标号；l ( 2 ，1 ) - 标号数；复合图。 a b s t r a c t l ( 2 ，1 ) - l a b e l i n g so ff a p h 8a r o s ef r o mt h ec h a n n e la s s i g n m e n tp r o b l e m s u p p o s ean u m b e r o fb r o a d c a s t i n gs t a t i o n sa g i v e n t h e s es t a t i o n sn e e dt r a n s m i ti n f o r m a t i o nb yr a d i o i no r d e rt o a v o i dt h ei n t e r f e r e n c e ，a n yt w o v e r yc 1 0 8 e s t a t i o n sm u s tu s ec h a n n e l sa p a r te n o u g h ，a n da n yt w o c l o s e s t a t i o n sm u s tu d i f f e r e n te h a m a e l s w ew a n tt o1 l s et h el e a s tc h a n n e lr e f l o l l l r o bt oa s s i g n 曲a n e l 8t oe a c hs t a t i o ns u c ht h a tt h ei n t e r f e r e n c ei sa v o i d e d a nl ( 2 ，1 ) 一l a b e l i n go fag r a p hg i s a s s i g n m e n tf t m e t i o n ，f r o mt h ev e r t e xs e tv ( c ) t on o n n e g a t i v ei n t e g e r s ，s a t m y i r t g ：( 1 ) i ，( “) 一，( ) i 2 ，i f 刀( g ，；( 2 ) l f ( u ) 一，( 口) i 1 ，i fd ( ，f ) = 2 t h el ( 2 ，1 ) 一l a b e l i n gn u l n b e r o fag r a p hg ，d e m o t e db ya ( g ) 抽m i n ，m 戤 ，( ) ：们y ( g ) ) c o n 日i d e rt h ep r a c t i c a lp r o b l e m ：s u p p o s et h e r ea r em a n yr a d i os t a t i o n si nt h ea r 蚀e a c hs t a t i o n m a yh a v em o r et h a no n ec h a n n e l s w es t u d yt h es i t u a t i o nt h a te a c hs t a t i o nh a 8 c h a n n e l s i n o r d e rt or e d u c et h ei n t e r f e r e n c e a n yt w ot i n s e l sw h i c hc o m ef r o mt h ef l a m es t a t i o n sm u s tb e a p l t l 吨a tl e a s t2 ，a n di ft w os t a t i o n s a n d ”la r ea d j a c e n t ，t h e nt h ed i f f e r e n c eb e t w e e ne a c h d 衄n e lw l a i e hc 咄f r o mt h es t a t i o n st j 0a n de 眺c h a n n e lw h i c hc 0 脚f r o mt h es t a t i o n s 盯lm u s t b ea tl e a s t2 ；i ft w os t a t i o n s 咖a n d 砚a r e 砒d i g t 心t w o ，t h ed i f f e r e n c eb e t w 蝴e a c hc h a n n e l c o m i n gf r o mt h es t a t i o nv 0a n de a c hc h a n n e lc o n l i n gf r o mt h es t a t 妣v lm u s tb ea tl e a s t1 he _ h p t e r2 ， s t u d yt h eb l l l d ep r o p e r t i e so fc o m p o s i t eg r a p hg i 风】i nc h a p t e r3 ，w e d e t e r m i n et h el ( 2 ，1 ) 一l a b e l i n gn u m b e ro fr 【讯】，w h e r er i 8t h ep a t ho nnv e r t i c e s t h e n p r o v et h a t 五叫a n yt r e et ，( + 2 ) 七一1 a ( t 【凤】) ( + 2 ) 七+ 4 ，w h e r e i s t h em a x i m u m d e g r e eo ft f i n a l l y , o b t a i n mr e s u l t sf o rt h e - n a m b e r so fg 陬】，w h e r egi st h ec y c l e o nnv e r t i c e s k e y w o r d s ：d m n e la 镕i 孕m l e n tp r o b l e m , l ( 2 ，1 ) 一l a b e l i n g ，l ( 2 ，1 ) 一l a b e l i n gn m n b e r ，e o m l x b - i t eg r a p h 一、学位论文独创性声明 东南大学学位论文 独创性声明及使用授权的说明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸 质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理 签名：导师签名：日期： 第一章引言 近年来，对于图论中各个方向的研究都得到了极大的发展。其中图的着色问题研究作 为图论研究中的一个重要分支，近年来也受到了广泛关注，图的着色问题从最早的点着色、 边着色和面着色发展到现在的圆着色、分式着色、列表着色等等各种着色。但这些新的定义 往往来自于现实中为了描述某个问题而建立的抽象模型。下文我们研究的( 2 ，1 ) 一标号就是 对频道分配问题的一种抽象描述。 1 1 标号着色的背景和定义 频道分配问题【1 】( f r e q u e n c ya s s i g n m e n t ) 是讨论如何最优地给不同的电台分配有限个 频道的问题假如在某一个地理区域内有多个电台，每个电台都要利用无线电波发送自己的 信号。但是，如果不同的电台使用了相同的或者相近的频道时，就可能产生相互干扰，所以 各个电台要避免使用可能产生干扰的频道。另外，地理位置也会影响频道的分配，如果两个 电台相距的足够远，那么即使使用了相同的频道也不会影响其正常工作。但是，如果两个电 台的地理位置接近的话，仅仅不同的频道是不够的，还必须使用相差足够远的频道才能保 证互不干扰。将频道分配给电台，目标是在保证电台互不干扰的前提下使用最少的频道资 源。 事实上描述频道分配问题的模型很多，w k h a l e 1 用图论 t - c o l o r i n g 的概念来描述 和研究过频道分配问题，最先把该问题转化为图的着色问题1 9 8 8 年，f s r o b e r t s 用标号 的概念描述过这个问题，即相隔很近的电台使用的频道至少相差2 ，相隔较近的电台必须使 用不同的频道。j r g r i g g s 和rk y e h 将此问题转化为不同于t - - c o l o r l n g 的另一种图着色 问题，并且考虑了更一般的情形，他们引入了工( d ，1 ) 一标号的概念。给定一个图g 和正整数d ， 图g 的一个l ( d ，1 ) 一标号是定义在y ( g ) 上的非负整数函数，满足：i 0 ) 一f c v ) i d 若d ( u ，口) = 1 ；l f ( u ) 一，( ) i l 若d ( u ，口) = 2 ；定义图g 的l ( d ，1 ) 标号数k ，1 ( g ) = m i n f m o 口 f ( v ) ：口 y ( g ) ) 。x d ，1 ( g ) 也可记作知( g ) 。当d = 2 时，l ( d ，1 ) 一标号就是l ( 2 ，1 ) 标号，x d c c ) 即为l ( 2 ，1 ) 一标 号数a ( g ) 。 下文不加说明的话，图g 的一个a ( g ) l ( 2 ，1 ) 标号指的是图g 的一个最大标号不大于a ( g ) 的l ( 2 ，1 ) - 标号。图g 的一个扛( 2 ，1 ) 一标号指的是图g 的一个最大标号不大于t 的l ( 2 ，1 ) 一标号。 奎查奎堂堡圭耋堡丝塞 2 在同一个地区，有很多电台，通常情况下每个电台有多个频道。本文考虑了每个电台都 需要女个频道的情况，为了防止频道之间的相互干扰，同一个电台的k 个频道要相互区分，每 两个都至少要相差2 ，如果两个电台v o 和口1 相邻，电台如的每个频道和电台口l 的每个频道都至 少要相差2 ，如果两个电台v 0 和”l 距离为2 ，电台v o 的每个频道和电台 1 的每个频道都至少要 相差1 ，这实际上是图g 的一个重l ( 2 ，1 ) 标号问题。图g 的一个k 重l ( 2 ，1 ) 一标号问题等价于复 合图g 【凤l 的l ( 2 ，1 ) - 标号问题，其e e k k 是k 个顶点的完全图。 复合图g 阻】定义：设g ( g ) ，e ( g ) ) 和h c v ( h ) ，e ( 日) ) 是两个简单图，图g 和图日的复合图g 【明 有顶点集合v ( g ) y ( 日) ，g h i 中任意两个顶点( z ，) 和( 一，矿) 相邻当且仅当：z = $ ，y y e ( 日) ，或者7 e ( g ) 图的l ( 2 ，1 ) 一标号数和l ( d ，1 ) 一标号数曾在过去十几年里得到了广泛研究，并且有了很多 结果。 。 定理1 1 1 囟对任意的图g ，a ( g ) 2a + 1 定理1 1 2 国令r 为包含n 个顶点的路则a ( p 2 ) = 2 ，x ( p 3 ) = 3 ，a ( 且) = 3 ，a ( r ) = 4 ，vt l 5 定理1 1 3 【2 】令g 为包含n 个顶点的圈则有a ( g ) = 4 定理1 1 4 【2 1 若t 是最大度a 1 的树，则a ( t ) = + 1 或+ 2 定理1 1 5 【2 】若图g 的最大度为，则a ( g ) 2 + 2 a c h a n g 和g u o 对这个结果作了改进，得到下面的定理： 定理1 1 6 1 3 】若图g 的最大度为，则a ( g ) a 2 + a 最近，这个结果再次被改进为： 定理1 1 7 1 4 若图g 的最大度为，则a ( g ) 2 + a 一1 g r i g g s 和y e h 对一般图做了如下猜想： 猜想1 1 8 【2 】对任意最大度a 2 的图g ， ( g ) 2 下面是有关l ( d ，1 ) 标号的一些基本结果： 定理1 1 9 1 5 对任何最大度为的树t ，+ d 一1 k ( t ) m i n + 2 d 一2 ，2 a + d 一2 ) 定理1 1 1 0 【6 1 令r 为包含n 个顶点的路则有知( 恳) = d ，k ( p 3 ) = d + 1 ，k ( 只) = d + 2 ，k ( r ) = d + 2 ，v n 5 定理1 1 1 1 1 6 令g 为包含n 个顶点的圈则有 椒，= 睫a ， 定理1 1 1 2 【1 0 】对任何最大度为的树t ，a + d 一1 h ( 曼m m ( a + 2 d 一2 ，2 a + d 一2 1 2 关于多重l ( d ，1 ) - 标号已有的一些结果 文献【7 】研究了复合图g 阻】的l ( 2 ，1 ) 标号情况，其中日是有个点且其补图是有哈密尔顿 路的简单图。得到了下面几个定理： 定理1 2 1 【7 1 令r 为包含n 个顶点的路，则有 ( 0 a ( p 2 h i ) = 2 k ； ( i i ) a ( 1 3 旧) = a ( 4 【卅) = 3 k ； ( f ) a ( r 【明) = 3 k + l ，n 5 定理1 2 2 7 ，t 是一棵最大度为的树，则有 口p 司) = ( + 1 ) 或( + 1 + 1 。 定理1 2 3 1 7 】令为包含n 个顶点的圈_ 贝有 ( i ) a ( c k 旧) = 3 k + 1 ，t 1 ； ( n ) a ( q 卅) = 4 k ； ( i i i ) ( c 5 【明) = 5 k 一1 ； ( i v ) a ( 岛l 明) = 4 k l ； ( v ) a ( 岛i j 翊) = 8 ； ( v i ) a ( c 二【明) = 3 k + 1 ，若n 足够大时 文献 8 】研究了一类裂变图的工( 燃) 标号数，对于每个顶点需要多个标号的情况，将每个 顶点“裂变”，使得每个顶点满足，需要几个标号就“裂变”成几个新的顶点，由文献给出的 裂变图的定义可以看出，如果图g 每个顶点都裂变成个顶点，则图g 的裂变图的l ( ：瑶) 标号 数就是复合图g 【玩】的l ( d ，1 ) 标号数 定理1 2 4 【8 】对最大度为的任一无风。的简单图g ，其裂变图g ，满足 媸0 , 正1 , 2 l ( g ，) 鱼掣+ d 如+ d ( 伽一1 ) ， 其中，n o = m a x l c l v ( g ) l n 推论1 2 5 1 8 1 对最大度为的任一无硒。3 ) 的简单图g ，复合图g 酶】的l ( 2 ，1 ) 一标号 数满足 奎查奎耋堡圭耋堡垒塞 4 a ( g ) s 哔+ 2 a k + 2 k 一2 1 3 本文的主要工作 本文考虑复合图g l 】的i ( 2 ，1 ) 标号问题，其中是凰是个顶点的完全图，即研究了 图g 的k 重l ( 2 ，1 ) 一标号问题。据本文作者所知，目前有关图g 的k 重l ( 2 ，1 ) 一标号的文章很少。 本文第二章首先引用复合图g 阻】的定义，然后给出当日为完全图凤时，复合图g g k l 的 一些基本性质。文章的第三章考虑了一些基本的图类与完全图甄的复合图的l ( 2 ，1 ) 标号情 况。对于n 个顶点的路r ，完全确定t p k k i 的l ( 2 ，1 ) 一标号数，即a ( p l l 】) = 2 k 一2 ，a ( p 2 瞰1 ) = 船一2 ，a c p 3 i k k i ) = a ( p 4 l 】) = 4 k 一1 ，当n 5 时，a ( r 【玩】) = 4 k 。对于任意的树t ，给出 了t 陬】的l ( 2 ，1 ) 标号数的上下界。当为偶数时，( + 2 ) k 一1 a c t 阢j ) ( + 2 ) + 1 ， 并且上界和下界都是可达到的：当为奇数时，( + 2 一1 s 入( 死【凰i ) ( + 2 ) + 4 。最 后，当g 为t 1 个顶点的圈g 时，得到了以下结果：a ( c 3 g k l ) = 6 k 一2 ，当t l 时，a ( c k 【玩】) = 4 女，a ( i 【】) = 5 k 一1 a 当t 2 ，k 2 时，4 k a c c s t k k ) 5 k 一1 4 a c c 5 t + 4 i k k ) 5 一1 , 4 k a ( c 毗l k k ) 5 k 一1 文中未加说明的符号以及未加定义的概念参见文献【9 】 第二章基本定义和一些性质 首先给出几个相关定义： 定义2 h 设a 是一个非负整数集合，如果a 中的任意两个数相差至少为2 ，则称a 是2 分 离的；将a 中的数按由小到大的顺序排列，如果相邻的两个数相差都为2 ，则称a 是最优2 分 离集。 o ，6 是两个整数，且。曼b ，下文不加说明的话，【n ，6 】表示整数集合f n ，o + 1 ，o + 2 ，b 一 1 ，6 ) 。 a 是一个集合，川表示集合a 的基数，即a 中元素的个数。 定义2 2 ：设a 是【0 1 刈的一个2 - 分离子集，定义a = 0 + l p a ， a ) u a 一1 1 1 a ，i o 。 定义2 3 ：设g ( y ( g ) ，e ( g ) ) 和日( y ( 日) ，e ( 日) ) 是两个简单图，图g 和图日的复合图g 【日】有 顶点集合v ( e ) y ( 日) ，g 旧中任意两个顶点( z ，) 和( z 7 ，) 相邻当且仅当： = 一，y y e ( 日) ，或者e ( g ) 。g 旧中与g 中顶点口对应的子图日记为e k ，v z y ( g ) ，z k = ( 口，口) 旧y ( 日) ) 。 设，是g 【凤】的一个l ( 2 ，1 ) 一标号，口y ( g ) ，凰的标号是指凰中每个顶点的标号的集合 根据l ( 2 ，1 ) - 标号的定义，显然l ( h v ) 是2 分离集。 本文研究当e 为完全图风时，复合图g 【j “】的标号情况。下文不加说明的话，g g k 与g 中顶点仇对应的子图记为风。 由复合图的定义可得以下结论： ( 1 ) 如果图g 有n 个顶点，则复合图g 【j “】有l m 个顶点。 ( 2 ) 如果图g 有d 条边，n 个顶点，则复合图g 陬】有胪d + n 嚷条边。 ( 3 ) 如果图g 的最大度是g ，则复合图g 【j “】的最大度是g + 。 5 第三章复合图g 凰 的l ( 2 ，1 ) 一标号数 本章主要研究图g 分别为路，树，圈的情形。 3 1r 【磁】的l ( 2 ，1 ) - 标号数 e j i 理3 1 1 囟g 是最大度为的简单图，若a ( g ) = a + 1 ，则在g 的任何一个 ( g ) 工( 2 ，1 ) 一标 号中，最大度点”的标号是0 或+ 1 。 定理3 1 2g 是最大度为的简单图， 是g 的一个最大度点，若x ( g 【风】) = ( a + 2 ) k 一1 ，则 在g 【凤】的任何一个( a + 2 ) k - 1 一l ( 2 ，1 ) 标号中，存在8 【o ，捌，使得凰的标号为 o ，2 ，4 ，2 s - 2 ，a k + 2 s + 1 ，a k + 2 s + 3 ，( + 2 ) k 一3 ，( a + 2 ) k 一1 ) 。 证明：最大度点和它的个邻点形成的图是凰，因为复合图硒，【凰】是有( + 1 ) 个点 的直径为2 的图，所以这( + 1 ) 个点的标号都不同。用完全图凰代替最大度点v 0 以后的图 设为z 玷。设r 0 的标号为山，假设山不是( o ，2 ，4 ，2 s 一2 ，a k + 2 s + 1 ，+ 2 s + 3 ，a k 一 3 ，a k 1 ) ，则i 粕i k + 1 ，因为【o ，( a + 2 ) k 一1 】共有( + 2 ) k 个标号，在给凰的个邻子图标 号时有2 + 1 个标号不能用，所以还剩下a k 1 个标号，这些标号不够给日0 的个邻子图标 号，因此假设错误，从而该定理得证。 由此定理可得： 推论3 1 3 若g 中存在3 个最大度点，这3 个最大度点中任两点的距离都小于等于2 ，则a ( g 陬1 ) ( + 2 ) 七。 将r 的顶点依次记为砚，v 2 ，t 1 3 ，则复合f 虱p k k l f i 个子图可记为历，凰，凰，日。， 不妨设它们的标号为a l ，也，如，厶。 定理3 1 4 ：令r 是一个具有n 个顶点的路，那么 ( ) a ( p 1 陬】) = 2 k 一2 ； ( ) a ( 恳【虬】) = 4 k 一2 ； ( i i i ) a ( 恳【放】) = a ( 4 【玩】) = 4 女一1 ； ( i v ) x ( p 【凤】) = 4 k ，t i 5 证明：当n = l 时，p l l 】_ j 如，因此x ( e 1 i k k l ) = x ( k k ) = 2 k 一2 当t n = 2 时，p 2 i k k i = k 啦，因此a ( p 1 陬1 ) = a ( j 幻k ) = 4 k 一2 。 奎查奎耋堡圭兰堡丝塞 7 当n = 3 时，存在一个4 b l l ( 2 ，1 ) 一标号，标号方法如下：令a 1 = 2 k ，2 k + 2 ，4 k 一2 ) ，a 2 = o ，2 ，2 一2 ) ，a s = 2 + 1 ，2 k + 3 ，4 一1 ) ，因此a ( 马【凤】) 4 k 一1 由于i 钙l k ，又 因为a 1 ，也，也，钙两两不交，所以a ( p 3 【玩】) 4 k 一1 。从而a c p s 【j “1 ) = 驰一1 a 当n = 4 时，存在一个4 b 1 l ( 2 ，1 ) 一标号，令a 1 = 2 ，2 k + 2 ，4 k - 2 ，a 2 = o ，2 ，2 k - 2 ) ，a 3 = 2 k + 1 ，2 k + 3 ，驰一1 ) ，a 4 = l ，3 ，2 一1 ) 。因此a ( 且【甄】) 4 k 一1 又因 为b 【凰】是只【凰】的子图，所以a ( 且【凤】) a ( 马【甄】) 4 k1 ，从而a ( 且f j “1 ) = 4 k 一1 。 当n = 5 时，存在一个4 k - l ( 2 ，1 ) 标号，令a l = 2 k ，2 k + 2 ，4 一2 ，a 2 = o ，2 ，2 k - 2 ) ，a 3 = 【2 k + 1 ，2 k + 3 ，4 k - 1 ，a 4 = 1 ，3 ，2 k - 1 ，a 5 = 2 + 2 ，2 k + 4 ，4 k 一2 ，4 k 即a ( 岛陬】) 4 k 。又由推论3 1 3 可知，a ( 尸5 【j “】) ( + 2 ) k = 4 j c ，因此a ( p s k k ) = 4 k a 当t l 6 时，存在一个4 k - l ( 2 ，1 ) 一标号，标号方法为：令a 1 = 2 k + 2 ，2 k + 4 ，4 k ，a 2 = o ，2 ，一，2 k 一2 ，a s = 2 k + l ，2 k + 3 ，一，4 k 1 ) ，山= t l ，3 ，一，2 k - 1 ，当口5 时，令厶= a ，l 。o d4 ，即入( r 暇d ) s4 k 。又因为p 5 l 】是r 【k 一的子图，所以 ( r 【k d ) 入( p 5 【k d ) = 4 k ， 从而a ( r 【凰】) = 4 k 。 3 2复合图t 【k d 的工( 2 ，1 ) 标号数 我们下面来讨论复合图t 陬】的l ( 2 ，1 ) 一标号数 下面给出一些标记： ( 1 ) 当为偶数时，对t = 0 ，2 ，4 ，定义： a = 珠，t + 2 ，( t + 2 ) 一2 ， a + l = ( t k + l ，如+ 3 ，( t + 2 ) k 一1 ) ( 2 ) 当为奇数，女为偶数时，对t = o ，2 ，4 ，a 一1 ，定义： a i = t 女，t k + 2 ，o + 1 ) k 一2 ) ， 钟= ( t + 1 ) k ，( t + 1 ) + 2 ，( t + 2 ) k 一2 ) ， a l l = 拙+ 1 ，t 鼍+ 3 ，一，( t + 1 ) k 一1 ) ， a l l = + 1 ) k + 1 ，( t + 1 ) + 3 ，( t + 2 ) k 一1 ， a x + l = ( + 1 ) k ，( + 1 ) k + 2 ，( + 2 ) 一2 ) ， 以+ 1 = ( + 1 ) 七+ 1 ，( a + 1 ) k + 3 ，一，( + 2 ) 七一1 东南大学硕士学位论文8 ( 3 ) 当为奇数，为奇数时，x c t = 0 ，2 ，4 ，a 一1 ，定义 a = t ，t k + 2 ，o + 1 ) k 一3 ) ， 所= o + 1 一1 ，( t + 1 ) + 1 ，( t + 2 ) k 一2 ) ， 趣+ l = 姥+ 1 ，伽+ 3 ，( t + 1 ) k 一2 ) ， a l l = o + 1 ) k ，o + 1 ) k + 2 ，0 + 2 ) k 一1 ) ， a k + 1 = ( + 1 ) ，( + 1 ) k + 2 ，- 一，( + 2 ) k 一3 ，( a + 2 ) k 一1 ) ， a 盖+ l = ( + 1 ) k + 1 ，( + 1 ) k + 3 ，( + 2 ) k 一2 可以看出：对口= o ，1 ，2 ，a - 2 ，标号以有6 手个元素，名有w - 个元素，a x + 1 中有5 笋个 元素，以+ l 有8 笋个元素。 给出一个标号的方法如下： s t e p l 选择原来树的一个最大度点v o ，用完全图取代它之后的子图设为日o 。 s t e p 2 给子图日0 标号，给凰的个相邻子图标号。 s t e p 3 选择一个已经标好号的子图风。 s t e p 4 给已经选出的子图的所有未标号的相邻子图进行标号。 s t e p 5 如果还存在没有标号的子图皿，就进行s t e p 3 ，如果都标好了就结束 引理3 2 1 ：对于任意的树t ，复合图t 【玩1 的l ( 2 ，1 ) 一标号数满足：x ( t k k ) ( a + 2 ) k 一1 。 证明：因为树甄是任意树的子图，所以下面先考虑树t 为甄t 的情况，对于树r 为凰， 复合图r 陬】是有( + 1 ) k 个点的直径为2 的图，所以所有的点的标号都不同，用完全图甄代 替最大度点t j o 以后的图设为z 而，设凰的标号为山，则i 尚l 女，所以至少有个标号不能用， 即 口【j “1 ) 2 ( + 1 ) k l + k = ( + 2 一1 。因此对于任意的树t ，a ( r 陬1 ) ( + 2 ) 一1 定理3 2 2 ：对任意的只有一个最大度点的树t ，x c t k 女 ) = ( + 2 ) k 一1 。 证明：由引理3 2 1 可知a ( t 【凤j ) ( + 2 ) 一1 。下面只需考虑满足这样条件的树t ：除了 叶子外，t 有一个最大度点，且其余点的度都是一1 ( 5 ) 。要证明定理结论，只需找到复 合图t 【j “的一个( + 2 ) 一1 - l ( 2 ，1 ) 一标号。 ( 1 ) 当为偶数时，使用本节刚开始给出的标号的方法，具体进行s t e p 2 和s t e p 4 的方法 如下： 奎室奎耋塑圭耋堡垒塞 9 s t e p 2 给子图凰标号山，给凰的个相邻子图分别标号为a 2 ，a 3 ，a + 1 s t e p 4 设凰为选择的已标好号的子图，设其标号为a ，给凰的相邻子图标号，根据标号顺序可 知：凰有且只有一个已经标好号的相邻子图，设为兄，设其标号为工( 风) 而且是先标好凰，然后 才标好了凰的由标号方法可知：工( 凰) = 厶，8 o ，1 ，2 ，+ 1 ) 在给风的a 一2 个相邻子 图标号时由于不能用标号也一l ，a ，a + 1 ，a ，所以可用山，a 1 ，a 一2 ，a + 2 ，a + 3 ，a a + l 中 不是也的那些标号给凰的相邻子图进行标号，可以看出，剩下的这些标号集合的个数共 有+ 2 4 个，即一2 个。 ( 2 ) 当为奇数时，使用本节刚开始给出的标号方法，具体进行s t e p 2 和s t e p 4 的方法如下： s t e p 2 给子图日0 标号山，给日0 的个相邻子图分别标号为：如，也，如- 2 a - l ， a x u a x + l ，a 客u a 各+ 1 此处的a t = a 2 _ u 智，t = 0 ，1 ，2 ，a 一1 当为偶数时，a x ，a x + 1 以，a 盖+ 。各有个元素当女为奇数时，a x 和以4 - 1 各有2 手个元 素，a 盖，a k + l 各有拳个元素，因此a xua x + l ，舷u 以+ 1 各有个元素 s t e p 4 设凰为选择的已标好号的子图，设其标号为l ( h t ) ，给凰的相邻子图标号时，根据 标号顺序可知：凰有且只有一个已经标好号的相邻子图，设为风，不妨设其标号为三( 吼) ，而 且是先标好也，然后才标好凰的因此凰最多还有一2 个相邻子图需要标号 首先将偶数集合a 孓墙，鸽，鸽，以一1 ，以一l ，a x + l 按照这个顺序捧成一捧，再将奇数 集合a ， i ，鸽，a ；，a x ，以，以+ 。按照这个顺序排成一排其次将偶数集合按照上面排的 顺序称为凰，噩，墨_ 1 五，置+ l ，五，x + 1 ，将奇数集合按照上面排的顺序称为确，m ， 硷，m 一1 ，m ，k + l ，y - + l ，+ 1 可以看出：偶数集合中只要两个集合的元素总个数为k 个，就可以放在一起给一个顶点 标号；奇数集合中也只要两个集合的元素总个数为k 个，就可以放在一起给一个顶点标号。 因为m i n 五) 与m “ k 1 ) 相差为1 ，所以不能放在一起给一个顶点标号。 下文中两个集合能“放一起”的意思是由这两个集合构成的一个集合是禾分离集下 文不加说明的话，都假设，i + 1 由s t e p 2 可以看出已经标好号的子图的标号形式是五u 玛，五u 巧，k u 巧形式。 c l a i m l ：趣的标号形式是五u 玛形式，或恐u y ；形式，或k u 巧形式，它的a 一1 个邻子 图都可用【o ( a + 2 ) k 一1 】中标号标好，而且标号也是这三种形式。 证明：下面根据凰的标号分三种情形来讨论。 c a s e l ：皿的标号为墨u x f 形式 首先，在标号集合铂，鹰，a ，钟，以，a 盖，a x + l ，以+ l 中去掉置，玛，k ，巧，m 一1 ，巧一1 ， 如果j = i + 1 , 贝, j y j 一1 = k 。因为总共有+ 2 个偶数集合，去掉2 个偶数集合，还剩下个偶数 奎室奎兰堡圭兰堡墼塞 1 0 集合；总共有a + 2 个奇数集合，最多去掉4 - f 奇数集合，所以至少还剩下a 一2 个奇数集合 其次，在剩下的这个偶数集合中任意选择一个偶数集合，然后在剩下的这一2 个 奇数集和和中选择一个能与之“放一起”的奇数集合l j ，用凰u m 给甄的一个邻点标号。 最后剩下的这一1 个偶数集合可以给犁个邻子图进行标号；剩下的这一3 个奇数集 合可以给学个邻子图进行标号。因为1 + 垒+ 垒= 一1 ，而凰还有一1 个邻子图需要标 号所以此种情况下证明成立。 c a s e 2 ：玩的标号为置uk 形式 在标号集合鸽，鸽，a ，钟，a k ，以，a x + l a 盖+ 1 中去掉蜀，巧，k 一1 ，k ，乃，玛+ - 中标号， 因为总共有+ 2 个偶数集合，去掉3 个偶数集合，还剩下一1 个偶数集合，可以给学个邻 子图进行标号；总共有+ 2 - f 奇数集合，去掉3 个奇数集合，还剩下一1 个奇数集合，可以 给垒个邻子图进行标号。因为垒+ 垒= 一l ，而凰还有一1 个邻子图需要标号所以此 种情况下证明成立。 c a 3 ：风的标号为kuk 形式 首先，在标号集合舶，鬈，a i ，重，a x ，以，4 盖+ 1 ，以+ 1 中去掉m ，巧，墨，玛，x i + l ，x j + b 如果j = i + 1 ，则五十1 = 局。因为总共有+ 2 个偶数集合，最多去掉4 个偶数集合，还剩 下一2 - t - 偶数集合；总共有+ 2 个奇数集合，去掉2 个奇数集合，还剩下个奇数集合。 其次，在剩下的这一2 个偶数集合中任意选择一个偶数集合凰，然后在剩下的这个 奇数集合中选择_ 二个能与之“放一起”的奇数集合m ，用凰um 给日t 的一个邻点标号。 最后剩下的这一3 个偶数集合可以给牮个邻子图进行标号；剩下的这一1 个奇数集 合可以给垒个邻子图进行标号。 因为l + 垒乒+ 垒= 一1 ，而日t 还有一1 个邻子图需要标号所以此种情况下证明成立。 c l e d m 2 ：如果风的标号形式是玉u 冯形式，或玉u 巧形式，或k u 巧形式，它的邻子图凰的 另外一2 个邻子图也可用【o ( + 2 ) 一1 】中标号标好，而且标号也是这3 种形式之一。 证明：下面根据巩和凰的标号分8 种情形来讨论。 c a s e l ：l ( 凰) = 凰u 五，l ( 日t ) = x i u x j 形式 因为风是先按照c l s i m l 中c a s e l 的方法给它的最多一1 个邻子图进行标号的，其中包 括凰，在给凰的一2 个邻子图进行标号时， 首先，在所有的标号集合中去掉墨，玛，m ，巧，k 一1 ，巧一1 ，x k ，五，如果j = + 1 ，则巧一1 = k 。 因为总共有+ 2 个偶数集合，所以去掉4 个偶数集合后，还剩下a 一2 - f 偶数集合。因为总共 有+ 2 - f 奇数集合，最多去掉4 个奇数集合，所以至少还剩下一2 个奇数集合 其次，在剩下的这一2 个偶数集合中任意选择一个偶数集合兄，然后在剩下的这一2 个 东南大学硕士学位论文 1 l 奇数集合中选择一个能与之“放一起”的奇数集合k ，用兄uk 给衄的一个邻点标号。 最后剩下的这一3 个偶数集合可以给学个邻子图进行标号；剩下的这一3 个奇数集 合可以给垒个邻子图进行标号。 因为1 + 垒+ 垒= 一2 ，而风还有一2 个邻子图需要标号所以此种情况下证明成立。 c a s e 2 ：l ( h j ) = 凰u 蜀，工( 凰) = 五u 巧形式 因为玩是先按照c l a i m l 中c a s e l 的方法给它的最多一1 个邻子图进行标号的，其中包 括日，在给风一2 个邻子图进行标号时， 首先，在所有的标号集合中去掉五，巧，k 一1 ，k ，玛，玛+ 1 ，托，蜀，因为总共有a + 2 个偶数 集合，去掉5 个后，还剩下一3 个偶数集合，可以给单个邻子图进行标号，总共有a + 2 个奇 数集合，去掉3 个后，还剩下一1 个奇数集合，可以给掣个邻子图进行标号。 因为垒+ 垒= 一2 ，而日t 还有一2 个邻子图需要标号所以此种情况下证明成立。 c a s e 3 ：工( 玩) = x k u 蜀，工( 凰) = m u 巧形式 因为巩是先按照c l a i m l 中c a s e l 的方法给它的最多一1 个邻子图进行标号的，其中包 括凰，在给凰一2 个邻子图进行标号时， 首先，在所有的标号集合去掉k ，巧，五，玛，五+ 1 ，玛+ 1 ，凰，蜀如果j = i + i ，则脚1 = 玛。 因为总共有+ 2 个偶数集合，最多去掉0 个偶数集合，所以至少还剩下一4 个偶数集合；因 为总共有+ 2 个奇数集合，去掉2 个奇数集合，所以还剩下个奇数集合。 其次，在剩下的这a 一4 个偶数集合中任意选择一个偶数集合咒，然后在剩下的这个 奇数集合中选择一个能与之。放一起”的奇数集合k ，用五uk 给风的一个邻点标号。 最后剩下的这一5 个偶数集合可以给学个邻子图进行标号；剩下的这一1 个奇数集 合可以给垒善个邻子图进行标号。 因为1 + 垒+ 垒= 一2 ，而皿还有一2 个邻子图需要标号所以此种情况下证明成立。 c a s e 4 ：l ( 风) = 飘u l j ，工( 日t ) = 蜀u 乃形式 因为也是先按照c l a i m l 中c a s e 2 的方法给它的最多一1 个邻子图进行标号的，其中包 括凰，在给凰一2 q 邻子图进行标号时， 在所有的标号集合中去掉置，玛，k ，巧，k 一1 ，巧一1 ，凰，i ，如果j = i + l ，则巧一1 = k 。因为 总共有+ 2 个偶数集合，去掉3 个偶数集合，所以还剩下一1 个偶数集合，可以给垒个邻子 图进行标号。因为总共有+ 2 个奇数集合，最多去掉5 个奇数集合，所以至少还剩下一3 个 奇数集合，可以给华个邻子图进行标号。 因为垒丢+ 垒碧= 一2 ，而凰还有一2 个邻子图需要标号所以此种情况下证明成立。 c a s e s ：l ( 风) = 甄u m ，工) = k u 巧形式 东南大学硕士学位论文 1 2 因为风是先按照c l a i m l 中c a s e 2 的方法给它的最多一1 个邻子图进行标号的，其中包 括凰，在给凰的一2 个邻子图进行标号时，在所有的标号集合去掉l ；，巧，玉，玛，墨+ 1 ，x j + 1 ，m ， 如果j = i + 1 ，则x j = 置+ 1 。因为总共有+ 2 个偶数集合，最多去掉5 个偶数集合，所以至 少还剩下一3 个偶数集合，可以给垒个邻予图进行标号；因为总共有+ 2 个奇数集合，去 掉3 个奇数集合后，所以还剩下一1 个奇数集合，可以给单个邻子图进行标号。 因为垒+ 垒軎= 一2 ，而凰还有一2 个邻子图需要标号所以此种情况下证明成立。 c a s e 6 ：l ( h