（运筹学与控制论专业论文）复合树的l（21）标号研究.pdf

摘要 图的距离二标号来自频道分配问题：某一区域有若干电台，不同的电台要使用无线电 波发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置较近 的电台要使用有一定相差的频道将频道分配给电台，目标是在保证电台互不干扰的前提 下使用最少的频道资源图的l ( 2 ，1 ) 一标号是一个从点集v ( v ) 到非负整数集的函数，满 足条件：( 1 ) 当让”e ( g ) 时，i f ( u ) 一，( 口) l22 ；( 2 ) 当d ( u ，口) = 2 时，i f ( u ) 一，( 。) l 1 图g 的l ( 2 ，1 ) 一标号数定义为：a 2 ，1 ( g ) = m l l f m a x f ( v ) ： y ( g ) ) ，即图g 的所有l ( 2 ，1 ) 一标号 的最大标号的最小值 在第二章中，我们对复合树t k c 的l ( 2 ，1 ) 一标号数进行研究对于任意一棵树，g r i g g s 和y e h 已经证明了a ( 丁) = a + i 或者a + 2 ，而复合树t k g 】的标号数也被证明等于( + 1 ) n 或者( + 1 ) n + 1 。本文将结合多重l ( 2 ，1 ) 。标号，给出在最大度等于3 时，该复合树标号数为 ( + 1 ) 札的充分条件，并且将进一步讨论当n = 2 时，t j 标号数为( + 1 ) n 的充分条件 在第三章中，我们讨论另一类复合树的标号问题，即t 【】的l ( 2 ，1 ) 一标号首先给出 最大度等于奇数且n = 2 和礼= 3 时该复合树的标号数的上界，最后对最大度等于偶数且大 于等于4 的情形，给出引1 的标号数的上界 关键词：频道分配问题，l ( 2 ，1 ) 一标号，复合树，多重l ( 2 ，1 ) 标号 a b s t r a c t t h el ( 2 ，1 ) 一l a b e l i n go fag r a p hi sm o t i v a t e db yas p e c i a lk i n do fc 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 ro fb r o a d c a s t i n gs t a t i o n sl t x eg i v e n t h e s es t a t i o n sn e e dt ot r a n s m i ti n f o r m a t i o n o nc h a n n e l s i no 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 o v e r yc l o s e s t a t i o n sm u s tr e c e i v ec h a n n e l s a 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 tr e c e i v ed i f f e r e n tc h a n n e l s w ew a n tt ou s et h e l e a s tc h a n n e lr e s o u r c et oa s s i g nc h a n n e l st 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 l ( 2 ，1 ) 一l a b e l i n go fag r a p hg i sa na s s i g n m e n tf ，f r o mt h ev e r t e xs e tv ( a ) t on o n n e g a t i v ei n t e g e r s ， s a t i s f y i n g ：( 1 ) j f ( u ) 一，( 口) j 2 ，i f “口e ( g ) ；( 2 ) i ，( “) ，( u ) j 1 ，i fd ( u ， ) = 2 t h el ( 2 ，1 ) 一 l a b e l i n gn u m b e ra 2 ，1 ( g ) o fg i sd e f i n e da sm i n fm a x f ( v ) ：口y ( g ) ，i e ，t h em i n i m u mo fs p 品 ( f ) o v e ra l l 及2 ，1 ) 一l a b e l i n g so fg i nc h a p t e r2 ，w ei n v e s t i g a t et h el ( 2 ，1 ) 一l a b e l i n gn u m b e ro ft h ec o m p o s i t et r e e 丁 k af o ra t r e e ，g r i g g sa n dy e hp r o v e dt h a ta ( t ) = a + io ra + 2 ，a l s ot h el ( 2 ，1 ) 一l a b e l i n gn u m b e ro f 丁【蟛】 h a sb e e np r o v e dt ob e ( a + 1 ) no r ( a + 1 ) n + 1 ，i nt h i sp a p e r ，f o rat r e etw i t hm a x i m u md e g r e e 3 ，w eg i v eas u f f i c i e n tc o n d i t i o nf o rt 蟛】t oh a v el ( 2 ，1 ) 一l a b e l i n gn u m b e r ( a + 1 ) n e s p e c i a l l y , f o rt h ec a s en = 2 ，w eg i v es u f f i c i e n tc o n d i t i o n sf o rt k 舜t oh a v el ( 2 ，1 ) 一l a b e l i n gn u m b e r8 i nc h a p t e r3 ，w es t u d yt h el ( 2 ，1 ) 一l a b e l i n go ft 【1f o rt r e et f i r s tw eg i v et h eu p p e rb o u n d f o ri t sl ( 2 ，1 ) 一l a b e l i n gn u m b e rw h e nt h em a x i m u md e g r e ei so d da n dn = 2o r3 t h e nw eg i v et h e u p p e rb o u n df o rl ( 2 ，1 ) 一l a b e l i n gn u m b e ro ft i k 7 jw h e nt h em a x i m u md e g r e ei se v e na n da tl e a s t4 k e y w o r d s ：c h a n n e l s i 孕l l e n tp r o b l e m l ( 2 1 ) 一l a b e l i n g ，c o m p o s i t et r e c b m u l t i p l el ( 2 1 ) 一 i i 一、学位论文独创性声明 独创性声明及使用授权的说明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他入已经发表或撰写 过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 二、关于学位论文使用授权的说明 签名：日期： 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存沦文本人电子文档的内容和纸 质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阌，可以公布l 包 括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办理 签名 第一章引言 图的着色是图论研究中的一个重要问题它所涉及的范围十分广泛，例如点着色、边着 色、圆着色、列表着色等等这些不同的着色概念往往来自于现实世界中为了描述菜个问题 而建立的抽象模型。距离二标号问题最初来自于上世纪九十年代的频道分配问题，它实际 上可以被看成图的顶点着色的一个推广最近十几年来，图的距离二标号研究已经有很多 结果 驵1距离二稼号的定义和背景 距离二标号问题最早来自于频道分配问题【1 1 ( r b a i o c h a n n e lf r e q u e n c ya s s i g n m e n t ) 的 研究。所谓频道分配问题是讨论如何最优地给某一地区的不同电台分配有限个频道的问题。 假设在某一个区域内有多个电台，每个电台都要利用无线电波发送自己的信号。但是如果 不同的电台使用了相同或相近的频道，就可能产生信号干扰，所以各个电台要避免使用可 能产生干扰的频道另一方面，地理位置也会影响频道的分配。如果两个电台相距足够远， 即使用了相同的频道也不会影响其正常工作。而对于地理位置接近的电台，只要保证使用 的频道有一定的相差。对于地理位置十分接近的电台，就必须要求使用相差足够远的频道 才能保证互不干扰。将频道分配给电台，目标是在保证电台互不干扰的前提下使用最少的 频道资源 描述频道分配问题的模型有很多，w k h a l e 曾用图论中t c o l o r i n g 的概念来描述和研 究这个同题。1 9 s $ 年，f s ，r t m c l 提出了标号的慨念，这可以看成是对图的着色问题的一 种演变。他提出相隔很近的电台使用的频道至少相差2 ，相隔较近的电台必须陡用不同的频 道。j ，r g r j g 黔和rk y e l l 将此问题转化为更一般的情形，他们引入了l d ( 2 ，1 ) 标号着色： 定义1 11 f 糊对于简单图g ( v e ) ，对于任意给定的实数d 0 ，图的l d ( 2 ，1 ) 标号是一个 非负函数f ：v ( a ) 一 0 ，。c ) ，满足条件： ( 1 ) i f ( u ) 一，( 口) i22 d ，若“u e ( g ) ； ( 2 ) f f ( u ) 一，( ) f d ，若d ( 弘口) = 2 若，是图g 的一个l d ( 2 ，1 ) 一标号，我们就称f l d ( 2 ，1 ) ( g ) 每个点在，下的象称为该 点的标号，定义f t f ( a ) l f = m “ ，( 口) ：口y ( g ) ) ，则图g 的标号数( l d ( 2 ，1 ) 一l a b e l i n gn u m b e r ) 定义为：a ( g ，d ) = m i n il ，( g ) 扎 这里图g 中的点表示电台，如果两个电台十分接近，则在g 中代表这两个电台的点 1 东南大学硕士学位论文 铂v 相邻；如果两个电台比较接近，则用4 ( u ，。) = 2 表示，扫) 用来代表电台使用的频道， 根据上述定义就可以保证各电台之间不会相互干扰我们的目标就是在保证电台互不干扰 的前提下使用最少的频道资源 g r i g g s 和y e h 继续在这个问题上进行了研究，他们发现上述定义是建立在实数的基 础上，使厢起来十分不方便经研究发现，实数值标号l d ( 2 ，1 ) 1 a b e l i n g 可以和整数值标号 l 1 ( 2 ，1 ) 一l a b e l i n g 建立联系 从而，关于图l d ( 2 ，1 ) 一l a b e l i n g 问题的研究只须考虑d = 1 的情形为了简便，我们将 l 1 ( 2 ，1 ) 一l a b e l i n g 简记作l ( 2 ，1 ) 一l a b e l i n g 对于一个给定的图g ，它的l ( 2 ，1 ) 一l a b e l i n g ( l ( 2 ，1 ) 标 号) 是定义在y ( v ) 上的非负整数函数，满足条件；( 1 ) 若u ”e ( g ) ，l f ( u ) 一，( ) l 2 ；( 2 ) 若d ( “，口) = 2 ，l ，( ) 一，( 圳21 相应的我们将l 1 ( 2 ，1 ) ( g ) 记作l ( 2 ，1 ) ( g ) ，a ( g ，1 ) 。记作 a ( g ) 证一l ( 2 ，1 ) 一l a b e l i n g 表示最大标号不大于k 的l ( 2 ，1 ) 1 a b e l i n g 。 1 9 9 8 年，h e u v e l ，l e e s e 和s h e p h e r d1 1 9 】在l ( 2 ，1 ) 一标号的基础上提出了圆标号的定 义，图g 的一个m 一( j ，峥圆标号是这样的一个函数f ：v ( g ) 一 o ，l ，2 ，m 一1 且满 足；当“和v 相邻时，j ，( 叻一f ( v ) l 。歹；当”和”距离为2 时，i f ( u ) 一f ( v ) l 。，这 里：吲。= m i - l 。 ，m 一 。g 所拥有的m 一( 曩七) 一圆标号中的最小的m 称之为g 的盯j 护数， 记之为。谁( g ) 。 关于圆标号的产生以及它与n ( 2 ，1 ) 一标号的关系，将在下面的篇章中具体讲述 1 2 囝的n _ 重n ( 2 ，1 ) 标号 上一节我们介绍了标号问题的产生。近些年来许多作者在标号这个问题上做了深入的 研究，概话起来主要有以下几个方面：首先是研究各种图的环号数，包括找到了凡娄常用图 的标号数或者上下界：有路，圈，立方体，树，弦图以及乘积图等；其7 欠屉对于l ( 2 。lj 标号 问题的推广，例如研究l ( j k ) 标号。圆标号等。这篇文章主要讨论了复合树的l ( 2 1 ) 标号， 涉及到了树的l ( 2 ，1 ) 标号，n 重n ( 2 ，1 ) 标号及圆标号的一些的概念和结论，下面就简单介 绍一下 定理1 2 1 【蠲若t 是最大度a 1 的树，则入( 丁) = 十1 或+ 2 定义1 2 1 称树是一类树当且仅当它的l ( 2 ，1 ) 标号数等于+ 1 假设n 和d 是两个正整数，我们接下来考虑这样的频道分配问题如果某个区域有多 个电台，每个电台要发射n 个不同的电波频率，为了避免信号的干扰，任意两个位置非常 接近的信号至少要相距d 个频率，而位置比较接近的信号只要频率不同就可以了类似的， 用标号的思想来考虑这个问题。就可以把它看成是图的n 一重( 砖l 标号 2 东南大学硬士学位论文 首先规定：对于任意两个整数集合i 和j ，它们之间的距离定义为d ( ，j ) = m i n l i j f ： j ，j 以 定义1 2 2 3 1 l 对于一个给定的图g ，它的n 重l ( d ，1 ) 标号是一个非负整数集函数 ，v ( a ) 一非负整数集的所有佗子集合的集合对于任意点口，i ( v ) c z + 且含有n 个元素， 这里z + 是非负整数集满足条件：f i ，若伽e ( g ) ，则d ( ，( 乱) ，( ) ) d f 到若“与u 的 距离为2 ，则d ( ，( u ) ，( 口) ) 1 定义( g ) = i i f i n f f ( v 1 ) u ，( 2 ) u u ，( 口。) 中最大的元素 如果令d = 2 ，就是我们要研究的n 重l ( 2 ，1 ) 标号，具体的定义见下文关于树的n 重 l ( d ，1 ) 标号，主要有以下几个结果 定理1 2 2 1 3 1 l 对于任意一个最大度为的树，满足( + 1 加+ d 一2 ”( t ) m i n ( a + 1 ) n + 2 d 一3 ，2 a n + d 一2 ) 当d = 2 时，很自然可以得到下面的定理1 2 3 。 定理1 2 3 1 ”l 当t 为树时，t f 蟛 的l ( 2 ，1 ) 标号数为( + 1 ) n 或( + 1 ) n + 1 注解：为下文的叙述方便，若复合树的l ( 2 ，1 ) 标号数等于( + 1 ) n ，则称该树是一类树。 定理1 2 4 【3 1 1 对于任意一个最大度为的树，满足暖( 丁) = ( a + 1 如+ 2 d 一2 1 3 本文的主要工作 本文主要研究的是复合树的5 ( 2 ，1 ) 标号。在实际论证中我们发现研究复合树的z ( 2 ，1 ) 标号其实就是研究树的n 重l f 2 ，1 ) 标号。由于复合树的结构十分复杂，这样做就可以减少 对结构的研究，转而直接研究树的n 重l ( 2 ，1 ) 标号。 在第二章中，我们先研究复合树丁 焉 这里如果n = 1 就是我们所说的树因此可以 把这个问题看成是对树的推广。王维凡，- 隹他的论文中给出了判定讨为一类附的充分条 件，即任意两个最大度点的距离不等于l ，2 或4 ，这课树就是一类树。对于这个结论能否推 广到r f 蜂 上，或者又有什么变化这足我所考虑的问题结合树枝理论把树进行拆分和拼 接，最后得出结论：若树t 的最大度= 3 ，且任意两个最大度点u ，v 的距离d ( u ，v ) 5 ，则 可以判定这是一类树 在第三章中，我们将研究另一类复合树t 【 ，它的结构明显要比? 【j 复杂很多，不过 仍然用n 重标号的思想来分析，就可以省去对结构的研究。首先我将给出在最大度等于奇数 且n = 2 和n = 3 时该复合树的标号数的上界，其次对最大度等于偶数且大于3 的情况下， 界定出r ( 西。j 的标号数上界。现有的结论是a f 瞄m ( + 2 ) n + 1 ，我利用团标号的思想， 把这个结论的上界减少到( + 2 ) n 文中未加说明的符号以及未加定义的概念参见 1 4 j 3 第二章t 霹 的l ( 2 ，1 ) 标号研究 在本章中，我们首先对t 【蟛 进行讨论，它的l ( 2 ，1 ) 标号数已经被证明等于( + 1 冲或 者( + 1 m + 1 【蝴在第二节中将给出一个充分条件判定其为一类树，此外对于t 【2 锈 ，将在 第二节的基础上进一步分析，得出更多的充分条件判定其标号数 2 1 复合树及其相关概念 前面已经介绍了l ( 2 ，1 ) 标号的概念，最早g r i g g s 和y e h 证明了a ( t ) = a + i 或者+ 2 王维凡【1 5 】在他的论文中给出判定树为一类树的充分条件，即任意两个最大度点的距离不等 于1 ，2 或4 ，这棵树就是一类树对于一棵复合树而言，我们也希望能找到判定其为一类树 的充分条件 。 定义2 1 1 图g 具有顶点集v = 1 ，v 2 ，口m ) ，图凰t 有个顶点，1 m ，1sj m 图g 和凰1 ，凰一，风。的复合图g 凰1 ，- ”2 ，凰m 定义为。由 凰1 ，矾2 ，日。分别代替g 中的点u 1 ，口2 ，：一，且满足：若图g 中点和相邻，那 么凰。中的每个点都与勘中的每个点相邻，把这样的图称为复合图。 例2 1 1 复合图忍 蟛】，它是由蟛代替p 2 中的点得到，如下图j 注解1 ：如果图g 中有m 个顶点，图h 中有n 个顶点，那么根据复合图的定义g 【日 有 m n 个顶点 注解2 ：如果图g 有d 1 条边m 个顶点，图h 有d 2 条边n 个顶点，则复合图g 日 有 n 2 d 1 - t - r o d ：条边 注解3 ：当凰1 ：凰2 一一凰。时，图g 【凰1 ，曼2 ，凰m 1 可以记为g 日t 扎简记 为g 【日1 特别的，当风l ：风2 一一凰。= 坛时，图g h 0 1 ，4 , j 2 ，凰m 可以记为 东南大学硕士学位论文 5 v i a g 注解4 ：本章主要讨论的是最大度等于3 的复合树，该复合树是由树与n 个点的完全图 的补图复合产生的，简记为t 【磁1 对于任意两个整数集合i 和j ，它们之间的距离定义为d ( i ，j ) = m i n 伸一j l ：i j ，j 以 定义2 1 2 对于一个给定的图g ，它的礼重l ( 2 ，1 ) 标号是一个非负整数集函数， v ( c ) 一非负整数集的所有哆子集合的集合对于任意点仉i ( v ) cz + 且含有礼个元素，这 里z + 是非负整数集满足条件：r j j 若u 口e ( g ) ，则d ( ，( ) ，( 口) ) 2 ；f 剀若与u 的距 离为2 ，则d ( ，( “) ，厂( 口) ) 1 定义遐1 ( q = m i n ， ，( 口1 ) u ，池) u u ，( ) 中最大的元素) 注解：根据t 【蟛l 的结构，它的l ( 2 ，1 ) 标号其实与t 的n 重l ( 2 ，1 ) 标号等价，在标号 过程中不仅要满足l ( 2 ，1 ) 标号的性质，并且要求每个点的n 个标号互不相同。为方便起见， 以下的讨论就以n 重l ( 2 ，1 ) 标号为基础 + 定义2 1 3 树中的一条路y o v l y k l v k ，其中d ( v o ) = d ( v k ) = 3 ，d ( ) = 2 ( 1 i k 1 ) ，称这样的路为树枝，记为鼠，且树枝的长度规定为k 记v o 是树枝的0 号位，也称 作起点，让是树枝的i 号位( 1 isk 一1 ) ，v k 是树枝的k 号位，也称作终点。 注解1 ：为方便起见，以下都用口表示3 度点，用o 表示2 度点和1 度点 注解2 ：把只有一个3 度点的路，即r o y l y k ，其中d ( v o ) = 3 ，d ( v i ) = 2 ( 1 i k 1 ) ， d ( v k ) = 1 ，也看成是特殊的树枝，记为b o 。，段长规定为无穷大此外把v o v l ，其中d ( v o ) = d ( v 。) = 3 ，即口一口的形式也定义成树枝，记为b 1 定义2 143 度树中的树枝的连接是指2 个或3 个树枝共用一个3 度点 注解：当两个树枝连接时，它们的连接方式和树枝中点的号位如下图所示 例2 12 假设两个树枝晚1 和b l ? ，b k ：和日! 的连接方式如下，简记为b l + b ? ； 口一。一。一一0 一口 ( b k l ) ol2k l - 1k t 口一。一。一一。一口 ( b k 2 ) 0l2k 2 - 1k 2 口一。一一。一口一。一一。一口 ( b k l + b k 2 ) o1k l - 1k lk 1 1k 1 + k 2 1k l + k 2 东南大学硕士学位论文 6 定义2 1 5 用f ( i ，k ) 表示当树枝的长度是k 时，j 号位标号集为j 的所有4 n - l ( 2 ，1 ) 标号中第k - 1 号位的标号集的集合；f ( i ，k 1 ，k 2 ) 表示k 1 长度的树枝与2 长度的树枝连接 时，1 号位标号集为j 的所有4 n l ( 2 ，1 ) 标号中第k 1 + k 2 1 号位的标号集的集合 定义2 1 6 称点u 与树枝鼠关联是指t 是该树枝的起点或终点。 2 2t k g 的l ( 2 ，1 ) 标号 下面开始具体介绍判定t 【j 锈】为一类树的充分条件由定理1 2 3 得知，( + 1 ) n a ( t i k , ：j ) s ( + 1 n + 1 显然当树的最大度= 3 时，4 n a ( t i k , ：i ) s4 n + 1 ，但a ( 丁蹶】) 在什么条件下等于4 n ，仍然不得知，以下就着重研究这个问题 定理2 2 1 若t 的最大度= 3 ，且任意两个最大度锄口的距离d ( u ， ) 5 ，则 a ( t 【j ) = 4 n 为了证明这个定理，先介绍几个相关的引理 引理2 2 1 若入( 丁 蟛】) ；4 n ，则对于每个3 度点，它的标号只能是 0 ，1 ，n 1 ) 或者 3 n + 1 ，3 n + 2 ，4 n 证明：利用反证法；若3 度点u 的标号不是 0 ，1 ，n 一1 ) 也不是 3 n + l ，3 n + 2 ，轨 ， 由l ( 2 ，1 ) 标号的定义以及a ( t j 锈】) = 4 n ，至少有n + 2 个标号不能给u 的邻点使用，贝u 的邻点能使用的标号数量最多有3 n 一1 个，但总共有3 n 个邻点。所以一定存在u 的两个邻 点使用了相同的标号，这与l ( 2 ，1 ) 标号的定义相矛盾。证毕。口 引理2 2 1 说明了在r 焉】标号数等于4 n 情况下，最大度点的标号也可以确定那么 对于讨的其他部分，标号又如何呢? 引理2 2 a 将说明这个问题 引理2 22 令p ，是一条具有m 个顶点的路，那幺( 1 ja ( be 凡；：j = 2 n ；f 2 ja ( b ：k ：j = a ( p 4 麟 ) = 3 n ；( 3 ) a ( e 蟛1 ) = 3 n 一1 ( m 5 ) 。 引理2 2 3f ( i ，k l ，k 2 ) cf ( i ，七l + 2 ) 证明：f ( i ，k 。，k 2 ) 是表示树枝1 号位标，时，且第k 号位的标号限制为 o ，1 ，乱一1 或f 3 + 1 ，3 n + 2 ，4 n 所有第女l + 2 1 号位的标号集合，而f ( i ，七1 + k 2 ) 的定义对第k 号位的标号无限制所以前者f ( j ，k 1 ，k 2 ) 的标号方式均是后者f ( ，h + 2 ) 的标号方式，即 f ( z ，1 ，如) c f ( z ，k l + k 2 ) 。口 一棵树t 其实可以看成是由多个树枝拼接而成。如图所示，该树可以看成是由b 1 ，曰2 ，b 5 这五个树枝拼接而成，其中口1 ，b 2 ，岛共用v o 点；岛，玩，昆共用啦点 东南大学硕士学位论文 7 v 0 口o o ，口_ ( 卜口， b 1 b 2b 3 ， b 4b 5 研究树的4 n l ( 2 ，1 ) 标号，主要是考虑树枝的4 n l ( 2 ，1 ) 标号。当分散的树枝拼接成 树时，拼接处距离为2 的点的标号要满足l ( 2 ，1 ) 标号的性质 令：e o = n 十1 ，n + 2 ，2 n ， 2 曝+ 1 ，2 n + 2 ，3 n ， 3 n4 - 1 3 竹+ 2 ，4 n ) ) 。 e 1 = n + 1 ，礼+ 2 ，2 礼 。 岛= 2 礼+ 1 ，2 n + 2 ，3 n e 3 = 3 n + 1 ，3 n + 2 ，4 n ) 定义2 2 1 称树枝鼠可e 标号( i = 1 ，2 ，3 ) 是相该树枝的号位标蜀时，按 4 n l ( 2 ，1 ) 标号可标完此树枝且f ( 蜀，k ) e o 注解l ：由于最大度点可标 o ，1 ，咒一1 ) 或 3 n + 1 ，3 n + 2 ，4 n ) ，而以上定义是在最 大度点标 0 ，1 ，n 一1 ) 下规定的。若在标号过程中遇到最大度点标 3 n + 1 ，3 n + 2 ，4 n 时，则该最大度点的邻点的标号按4 取补。这时规定e o = “o ，1 ，n - l ， n ，n + l ，2 n - 1 ，( 2 n ，2 n + i ，3 n 一1 ) ，e i = 2 m2 n + 1 ，3 n 一1 ) ，岛= n ，n + 1 ，2 n 一1 ，岛= 0 1 ，n l 。显然彰= 丘，这里i = 1 ，2 ，3 。 注解2 ：若树饺的起点标号是f 0 ，1 ，n l ，终点标号是 3 “_ l ，：3 “一2 ，4 ，噍树 枝b 在取补意义下可e ，标号f i = 12 3 ) 是指该树枝的1 号位标e 时，按轨一l ( 2 - 1 ) 标 号可标完此树枝且f ( 历，k ) e o 。类似若树枝的起点标号是 3 n + 1 ，3 n + 2 ，4 n ，终点标 号是 0 ，1 ，n 一1 ) ，树枝仇在取补意义下可e ：标号( i = 1 ，2 ，3 ) 是指该树枝的1 号位标 e 时，按4 n n ( 2 ，1 ) 标号可标完此树枝且f ( e ，k ) e o 注解3 ：若树枝起点和终点的标号都是 3 n + 1 3 n + 2 ，4 n ) ，只要把这个树枝的所有 点的标号按4 n 取补，树枝鼠可标号等价于树枝风可易标号。 性质2 2 1b 2 可e 1 标号，口3 可e l ，易，局标号，鼠可岛，玩标号 证明：b 2 的标号如下： o ，1 ，佗一1 ) 一 2 n ，2 n + 1 ，3 n 一1 ) 一 3 n4 - 1 ，3 n + 2 ，4 n ) ，在取补的意义下可 东南大学硕士学位论文8 e 1 标号； 玩的标号如下： o ，1 ，n 一1 ) 一 礼+ 1 ，n + 2 ，2 礼) 一 3 n + 1 ，3 n + 2 ，4 几 一 o ，1 ，n 一1 ，显然 可取，岛标号； b 3 的e 2 标号如下： o ，1 ，7 1 一1 ) 一 2 n + 1 ，2 n + 2 ，3 n 一 n ，n + 1 ，2 几一1 ) 一 3 n + 1 ，3 n + 2 ，一，4 n ， 在取补的意义下可局标号； b 4 的标号如下： o ，1 ，一，礼一1 卜 3 几+ 1 ，3 n + 2 ，4 凡) 一 几，礼+ 1 ，一，2 礼一1 ) 一 2 几十1 ，2 n + 2 ，- - ，3 n ) 一 o ，1 ，n 一1 ) ，显然可砀，e 3 标号口 引理2 2 4 对任意的i25 ，b i 可e 1 ，易，e 3 标号 证明；首先对岛进行标号，如t o ，1 ，一，n 一1 - ( n + 1 ，n + 2 ，2 n - 3 n 3 n + l ，一，4 n 一1 卜 o ，1 ，n 一1 - - 2 n ，2 n + 1 ，3 扎一l 卜一 3 器+ 1 ，3 n + 2 ，4 拈 ，在互补的意义下b 5 可f l 标号 o ，1 ，一，钆一1 ) 一 2 礼4 - 1 ，2 n + 2 ，3 n 一 n + 1 ，n + 2 ，一，2 n 一1 ) u 4 礼) 一 o ，1 ，n 一 1 一 2 n ，2 n + 1 ，3 礼一1 一 轨+ 1 ，3 n + 2 ，4 n ) ，在互补的意义下岛可易标号 o ，1 ，一，n 一1 卜 3 n + t ，3 n + 2 ，4 n ，一 n ，n + 1 ，2 几一1 ，一 2 n + 1 ，2 n + 2 ，3 n 一 o ，1 ，n 一1 一 3 n + 1 ，3 n + 2 ，4 n ，在互补的意义下岛可岛标号。 对于b 6 进行标号，如下： o ，l ，一，n 一1 - n + 1 r z + 2 ，2 n 卜 3 n ，3 r l 十1 ，4 n l 卜 o ，1 ，r n 一1 卜 2 m2 “+ 1 - - 3 n 一1 一 3 n 1 3 n 。2 一，4 ”) 一 0 1 ，一n 一1 ，b 可l 标号。 o 1 ：- ，n 1 ) 一 2 凡一l ，2 儿+ 2 一，3 ，一 n 上l ，n 下2 ，2 儿一1 ：4 ，。) 一 【) 1 一、n 一 1 ) 一 2 m2 十1 ，3 n 1 ) 一 3 n + 1 ，3 n + 2 ，4 ，。 一 0 ，1 ，n 一1 ，b 6 可丘 示号。 o ，1 ，一，n 一1 ) 一 3 n + 1 ，3 几+ 2 ，4 n 一 2 n ，2 咒+ l ，3 礼一1 ) 一 o ，1 ，礼一l 一 3 n ，3 n + 1 ，4 n 一1 卜一 n + 1 ，n + 2 ，2 n 一( o ，1 ，n 一1 ，b 6 可岛标号。 下面考虑b 7 盼标号，由性质2 2 1 可知，b 2 可e 1 标号，且标号形式如下： 0 ，1 ，几一1 一 2 n ，2 n + 1 ，- - ，3 几一1 ) 一 3 n + 1 ，3 n + 2 ，- ，4 n ) b 5 的标号刚刚已经得到，根据引理2 2 3 ，f ( i ，2 ，5 ) cf ( i ，7 ) ，岛的e 1 ，肠标号可由且2 和玩拼接而成，具体形式如下： o ，1 ，n l 卜 扎+ 1 ，佗+ 2 ，2 n 一 3 n + 1 ，3 n 十2 ，4 n 一 o ，i ，- - ，n l 卜 2 n + 1 ，2 n + 2 ，3 咒 一 n ，n + 1 ，一，2 咒一1 ) 一 3 n + 1 ，3 n + 2 ，一，4 n ) o ，l ，- 一，7 一1 ) 奎童奎兰堡圭兰堡丝奎 9 o ，1 ，n 一1 卜 3 n + 1 ，3 n + 2 ，4 , q 一 几，n + 1 ，2 礼一1 一 2 n + 1 ，2 n + 2 ，一，3 n ) 一 o ，1 ，礼一1 ) 一 3 n + 1 ，3 n + 2 ，4 n 一 n + 1 ，n + 2 ，2 n 一 o ，1 ，n 一1 ) 而b 7 的局标号可由玩和b 4 拼接而成，具体形式如下： 0 ，1 ，礼一1 卜 2 + 1 ，2 n + 2 ，3 n 一 礼，n 十1 ，2 礼一1 卜 3 佗+ 1 ，3 n + 2 ，一，4 n 一 o ，1 ，n 一1 ) 一 竹+ 1 ，竹+ 2 ，2 n 一 3 n + 1 ，3 n + 2 ，4 n 一 o ，1 ，- 一，n 一1 接下来考虑b 8 和b 9 的标号按照刚刚类似的想法，b 8 的标号可由岛和b 5 拼接而 成，其中昆的标号已由性质2 2 1 给出。在拼接过程中，只要满足l ( 2 ，1 ) 标号的性质即 可同理，岛的标号可由岛和玩拼接而成至此，对于肠0 = 5 ，6 ，7 ，8 ，9 ) 均证明了可以 蜀，e 2 ，历标号。对于b k ( k 1 0 ) 的情况，只需找两个b f ，岛( 5sl j k ，z + j = 七) 拼接 而成由于马，玩都是可e 1 ，马，场标号，所以这种拼接只须按l ( 2 ，1 ) 标号的性质拼接。 证毕口 下面给出定理2 2 1 的证明： 证明：因为a ( r j 皤】) 24 n ，以下只须证明a ( t 蟛 ) 4 n ，给出一个相应的标号即可 在标号之前，首先选取一个最大度点u ，以该点为根将树悬挂 由引理2 2 1 ：u 的标号只能取 o ，1 ，n 一1 或者 3 n + 1 ，3 n + 2 ，4 n ，不妨令其标 号为f o ，1 ，n 一1 ) 又因为与之关联的3 个树枝的长度均大于等于5 ，根据引理2 2 4 都 可以e 1 ，e 2 ，e 3 标号，不妨令最左边的树枝b 1 以e 1 标号，中间的树枝b 2 以e 2 标号，右 边的树枝b 3 以b 标号。 先考虑左枝的标号情况，设其长度为k l ，因为它可e 1 标号，所以f ( e 1 ，k 1 ) ce o ，而与 该树枝终点v 关联的两个树枝没被标号，且这两个树枝的长度都大于等于5 ，因此它们也可 f l ，e 2 ，e ；标号，则在标号时它们的l 号位的标号从昂i f ( k 1 【；中选取并旦要求满足 l ( 2 。1 ) 标号规则。依次进行下去，树的左边即可全部4 n 一三( 2 ，1 ) 标号。 按照这种际号模式，再处理髓的其他部分，只要所有的讨枝长度都大于等于5 ，这样的 标号方式就可以一直进行下去 最后需要说明一点的是，若在标号过程中遇到最大度点的标号取 3 n + 1 ，3 n + 2 4 n 时，相应的树枝标号都要按4 n 取补 证毕。口 以上证睨未考虑树中存在民的情况，事实上由于在标号模式中，与最大度点相邻的2 度点的标号是易或者。若此时有b 。与最大度点相邻，可以令其一号位点的标号使用该 最大度点相邻的2 度点标号中未被使用的某个易或者e ；( j 1 ，2 ，3 ) ) ，接下去的标号再根 据n ( 2 ，1 ) 的性质，即可以标完这个b 。因此可以不考虑b o 。对树其他部分标号的影响。 东南大学硕士学位论文 1 0 2 3t k i 】的l ( 2 ，1 ) 标号 在本节中，我们将研究t ! j 巧】的l ( 2 ，1 ) 标号由定理2 2 1 可得8 a ( t 【j 】) 9 ，再由 定理2 2 2 ，若t 【j 巧】中任意两个最大度点的距离大于等于5 ，则a ( t 【蟛】) = 8 。但如果树中 存在最大度点的距离小于5 ，t k i l 的标号又该如何确定? 下面就将给出一系列的充分条件， 只要r 【蟛 满足这些条件，即可以确定它的标号数在此之前，先给出一些定义和引理 定义2 3 1 称树枝玩可蜀“= 1 ，2 ，3 j 完美标号是指该树枝的f 号位标届时，按 4 n l ( 2 ，1 ) 标号可标完此树枝且f ( 易，k ) = e o 这节讨论的是t i k ； ，所以n = 2 ，由之前蜀的定义，可令e o = “3 ，4 ，( 5 ，6 ， 7 ，8 ，e 1 = 3 ，4 ，e 2 = 5 ，6 ) ，e 3 = 7 ，8 ) 注解：同第二节，此处的定义是在最大度点的标号取f o ，1 的情况下定义的。若在实际操 作中标号取到了 7 ，8 ) ，则树枝中其他点的标号按8 取补，这时规定e o = “o ，1 ， 2 ，3 ) ， 4 ，5 ) ，e i = 4 ，5 ) ，岛= 2 ，3 ) ，岛= o ，1 ) 引理2 3 1 对于任意的i 8 ，b 。可e 1 ，易，场完美标号 证明；首先给出b 8 的易，易，历完美标号： o ，1 ) 一 3 ，4 ) 一 6 ，7 ) 一 o ，1 ) 一 3 ，4 ) 一 6 ，7 ) 一 o ，1 ) 一 4 ，5 ) 一 7 ，8 o ，1 ) 一 3 ，4 ) 一 6 ，7 ) 一 o ，2 一 4 ，5 ) 一 7 ，8 一 2 ，3 ) 一 5 ，6 一 o ，1 ) o ，1 ) 一 3 4 ) 一 6 ，7 ) 一 1 2 ) 一 4 ，8 ) 一 o ，6 ) 一 2 ，3 ) 一 7 ，8 ) 一 o ，l 0 ，1 ) 一 5 ，6 ) 一 2 ，3 ) 一 o 7 ) 一 4 ，5 ) 一 l ，2 ) 一 6 ，7 ) 一 3 4 一 o 1 0 1 一 5 6 ) 一 3 8 ) 一 0 1 ) 一 4 5 ) 一 7 8 ) 一 2 ，3 ) 一 5 6 一 o 1 ) 0 1 一 5 6 ) 一 2 ，3 ) 一( o 7 ) 一 4 j ) 一 2 8 ) 一 4 6 ，一 o 1 一 7 8 0 1 一 ? 8 ) 一f 3 4 一 i ) 。1 ) 一 j 6 一 3 8 一 l j 1 一 一! j 一 ? 。s 0 1 一 7 ，8 一 2 3 ) 一 5 6 ) 一 0 1 ) 一 7 8 一 2 3 一 5 。6 ) 一 0 1 ) o 1 一 7 8 一 2 3 一 o 5 一( 7 ，8 一 1 ，2 一 4 5 一 7 ，8 一 o 1 岛的e 1 ，韪，局完美标号如下： o ，1 ，一 3 ，4 一 7 ，8 一t o 1 一 3 ，5