（应用数学专业论文）图的（d1）全标号问题.pdf

摘要 图的( d ，1 ) - 全标号问题 摘要 本学位论文研究的( d ，1 ) 全标号问题源于以无线电频道分配 为背景的距离2 标号问题图g 的一个k 一( d 1 ) 一全标号是一个从集合 v ( a ) u e ( g ) 到 o ，1 ，忌) 的映射使得相邻点有不同值、相邻边 有不同值、相关联的点和边的值差至少是d g 的( d ，1 ) 全标号数 a 子( g ) 是使得g 有k ( d ，1 ) 全标号的最小的k 值 2 0 0 2 年，h a v e t 和y u 【l 】最先引进了( d ，1 ) 一全标号这一概念，并猜 想：a 5 ( g ) ( g ) + 2 d 一1 本学位论文主要围绕这个猜想展开研究在第一章，我们给出了 一些基本概念以及图的( d ，1 ) 一全标号问题的研究背景和现状，并且介 绍了本学位论文的主要结果 在第二章，我们给出了最大度为3 的树的( 2 ，1 ) 全标号数的一个 完全刻画在第三章，对于外平面图的( 2 ，1 ) 全标号，我们证明了以下 结果： ( 1 ) 若( g ) 2 ，贝ua ；( g ) 4 ； ( 2 ) 若( g ) 一3 且g 是2 连通的，则砑( g ) 5 ； ( 3 ) 若( g ) = 4 ，g 是2 一连通的且不含有n 一开齿( n 4 ) ，则 a ；( g ) 6 ； ( 4 ) 若( g ) 5 ，贝u 碍( g ) z x ( a ) + 2 在第四章，我们研究了路与路、圈与圈的积图的( 2 ，1 ) 全标号， 得到了它们的( 2 ，1 ) 一全标号数的精确值在第五章，考虑了几类图的 ( d ，1 ) 一全标号问题，如扇和轮，给出了它们( d ，1 ) 全标号数的精确值 关键词：全标号，( d ，1 ) 一全标号，l ( d ，1 ) 一标号，二，g ) 一标号 t h ep r o b l e mo f ( d ，1 ) - t o t a ll a b e l i n gi ng r a p h s h lt h i st h e s i s ，w es t u d yt h e ( d ，1 ) - t o t a ll a b e l l i n go fg r a p h s ，w h i c hi sa s p e c i a lc a s eo f d i s t a n c et w ol a b e l l i n go f g r a p h s m o t i v a t e db yt h ef r e q u e n c y c h a n n e la s s i g n m e n tp r o b l e m a ( 比1 ) - t o t a ll a b e l l i n go fag r a p hgi sa m a p p i n gff r o mv ( a ) ue ( g ) t ot h el a b e ls e t 【o ，1 ，忌) s u c ht h a ta n y t w oa d j a c e n tv e r t i c e sh a v ed i f f e r e n tl a b e l s ，a n yt w oa d j a c e n te d g e sh a v e d i f f e r e n tl a b e l s ，a n da n yi n c i d e n tv e r t e xa n de d g eh a v et h el a b e ld i f f e r e n c e a tl e a s td t h e ( d ，1 ) - t o t a ll a b e l l i n gn u m b e r 巧( g ) o f ag r a p hgi st h el e a s t 后s u c hn l a tgh a sa 南一( d ，1 ) - t o t a ll a b e l l i n g h l2 0 0 2 ，h a v e ta n dy u 【1 】i n v e s t i g a t e dt h e ( d ，1 ) - t o t a ll a b e l l i n go f g r a p h s a n dc o n j e c t u r e dt h a t , f o ra n yg r a p hg ，入子( g ) a ( a ) + 2 d 一1 t h ep u t - p o s eo f t h i st h e s i si st oc o n f i r mt h i sc o n j e c t u r ef o rs o m es p e c i a lc l a s s e so f g r a p h s h c h a p t e r1 w ec o l l e c ts o m eb a s i c n o t i o n su s e di nt h et h e s i sa n dg i v e ac h i e fs u r v e yo nt h i sd i r e c t i o n m a i nr e s u l t si nt h et h e s i sa r es t a t e d t h e ( 2 ，1 ) 一t o t a ln u m b e r o f t r e e sw i t hm a x i m u md e g r e e3i sc o m p l e t e l y c h a r a c t e r i z e di nc h a p t e r2 h lc h a p t e r3 ，w es t u d yt h e ( 2 ，1 ) - t o t a ll a b e l l i n go f a no u t e r p l a n a rg r a p h g b ys h o w i n gt h ef o l l o w i n g ： ( 1 ) a ；( g ) 4 i f a ( g ) 2 ； ( 2 ) a 多( g ) 5i f a ( c ) = 3a n d gi s2 - c o n n e c t e d ； ( 3 ) 入手( g ) 6i f a ( o ) = 4 g i s2 - c o n n e c t e da n dh a sn oo p e nn g e a r s f o r n 4 ； ( 4 ) a t 2 ( g ) a ( g ) + 2i f a ( c ) 5 t h e ( 2 ，1 ) 一t o t a ll a b e l l i n gn u m b e ro f p r o d u c to f t w op a t h s o rt w oc y c l e s i sd e t e r m i n e di nc h a p t e r4 一一 a b s t ra c t i nc h a p t e r5 ，w ec o n s i d e rt h e ( d ，1 ) 一t o t a ll a b e l l i n go fs o m es p e c i a l g r a p h ss u c h 勰f a n sa n dw h e e l s k e yw o r d s ：t o t a ll a b e l i n g ，( d ，1 ) - t o t a ll a b e l i n g ，l ( d ，1 ) 一l a b e l i n g ， l 0 ，g ) l a b e l i n g 一一 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 己在论文中作了明确的声明并表示了谢意。 研究生签名：僻专 日期： 口0 7 学位论文使用授权声明 本人完令了解浙江帅范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究生签名： 西虽 导师签名：夕夕 日期：2 t o 彪o 7 一、绪论 ( 一) 、 基本概念 一、绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号我 们用l s 表示集合s 中的元素个数，并记s = s s n 一个无向图是一个有序对g = m e ) ，其中y 是一个有限集合，e 是y 中的 不同元素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图g 的 边我们通常用y ( g ) ，e ( g ) 分别表示图g 的顶点集合和边集合，用i g i ，i i g l l 分 别表示g 的顶点数和边数边数为0 的图成为空图没有重边和环的图叫做简单 图除非特别指出，本文研究的图均指有限简单无向图通常称含有几个顶点的 图为竹点图对于图g 中的顶点u 和若边e = 札t ，e ( g ) ，则称t 和u 相邻， u 和口互为邻点；称吐和 是e 的端点，t 和t ，分别与e 关联若g 的边e 和，有 一个公共端点，则称e 和，相邻在图g 中与顶点u 相邻的顶点的全体叫作t 的领域，记作g ( u ) ；并把n g m = n a ( u ) u t 称作点u 的闭领域称i r g ( 仳) i 为 顶点u 的度数，记作d o ( u ) 称度数为k 的顶点为k 一度点g 中顶点的度中最大 者和最小者分别称为g 的最大度和最小度，别记作a ( c ) 和d ( g ) 度数为0 的顶 点称为孤立点，度数为i 的顶点称为悬挂点，与悬挂点相关联的边称为悬挂边每 对不同顶点都相邻的简单图称为完全图，n 个顶点的完全图记为在不产生混 淆的情况下，我们把f y ( 回i ，i e ( g ) j ，肌7 ( “) ， r g m ，如( 牡) ，( g ) ，a ( g ) 分别简记为 i y i ，l e i ，( t ) ，n m ，d ( u ) ，a ，6 对于图g = ( v e ) 和图日一( 矿，) ，若有y ，e ，则称图日是图 g 的一个子图对于y 7 y ( g ) ，我们把图g 中属于y 的顶点以及与矿中的点 关联的边都删除所得到的图记作g 或g 一对于u ， y ( g ) ，伽芒e ( g ) ， 我们把在图g 中连接顶点“， 所得到的图记作g + t ) 对于y ( g ) ，我们 把由y 作为顶点集，e = e i e = 伽e ( g ) ，t ，t ，v ，) 作为边集的图叫做g 中 由顶点子集矿导出的子图，记作g 【y 】设g l = ( k ，历) ，g 2 一( ，e 2 ) 是两个图， 称图g = ( ku ，毋u 易) 为图g 1 和图g 2 的并，记作g u 日对于e e ( g ) ， 若删去边e ，并令它的两个端点重合，则称边e 被收缩，记收缩边e 后得到的简单 图为g e 图g 的一条途径是一个有限非空的点边交替序列t ，= r o e l u l e 2 e 讥，使 一、绪论 得对1 k 1 ) 会比l ( 2 ，1 ) 标号问 题更简单，而且证明它是n p - h a r d 的过程会是相当枯燥乏味的因此，人们转而研 究它的界值 a 2 ，l ( g ) 的下界显然是( g ) + 1 ，当g = k t ，( g ) 时下界是紧的对于任意的 图g 的上界，g r i g g s 和y e h 猜想： 猜想1 1 【4 】a 2 1 ( g ) a 2 ( g ) 用构造标号的方法，j o n a s 1 0 - 证明了，当a ( g ) 2 时，a 2 ，l ( g ) 2 ( g ) + 2 a ( g ) 一4 c h a n g 和k u o t 17 】把这个上界降到了a 2 ( g ) + ( g ) 不久之后，文献 【l s 中证明了a 2 ，l ( g ) a 2 ( g ) + a ( g ) 一1 g o n c a l v e s0 9 迸一步得到了目前最 好的上界2 ( g ) + ( g ) 一2 一3 一 一、绪论 路、圈、扇、轮、团都是我们所考虑的最简单和最一般的网络，所有这些图 类的l ( h ，七) 标号问题在多项式时间内都是可以解决的g e o r g e s 和m a u r o 【2 0 】对 于所有的h ，七( 后) 计算了路和圈的跨度 文献 2 1 】研究了路的笛卡尔乘积图p = h 鍪】只的l ( 2 ，1 ) 一标号问题对于给 定的只，文献中得到了a 2 1 ( p ) 的精确值根据这个结果，他们还得到了超立方体 的跨度的上界，也就是n 条长度为1 的路的笛卡尔积图的a 2 , 1 - 数对于某些特殊 的m ，他，文献【2 2 】给出了圈与圈的笛卡尔积图c k c k 的a 2 ，1 - 数文献【2 3 】对 完全图的积图的l ( h ，七) 标号问题也进行了深入研究 对于任意的一棵树t ，g r i g g sa n dy e h 4 1 证明了a 2 1 ( t ) 不是( g ) + 1 就是 ( g ) + 2 ，并且猜想识别这两类是n p h a r d 的c h a n g 和k u o 在文献 1 7 】中否定 了这一猜想，给出了一个基于动态规划的多项式时间算法但是，还没有人能够完 全刻画树的l ( 2 ，1 ) 标号w a n g 2 4 1 给出了a 2 ，l ( t ) = a ( t ) + 1 的一个充分条件 关于树的l ( h ，七) 标号问题( 后 1 ) 的复杂性依然是开放的，很多学者在这方面做 了非常大的努力，见文献 2 0 ，2 5 - 2 8 关于平面图的l ( 2 ，1 ) 标号问题，v a nd e n h e u v e l 和m c g u i n u e s 2 9 1 已证明猜 想1 1 对( g ) 7 时的平面图g 成立w a n g 和l i b p o 】根据平面图g 的围长 _ 口( g ) 得到了以下结论： 若g ( g ) 7 ，则a h 。k ( g ) ( 2 k 一1 ) a ( g ) + 4 h + 4 k 一4 ； 若9 ( g ) 6 ，则a h ，k ( g ) ( 2 k 一1 ) ( g ) + 6 h + 1 2 k 一9 ； 若g ( g ) 5 ，则a 。k ( g ) ( 2 k 一1 ) ( g ) + 6 + 2 4 k 一1 5 一个图g 的剖分图甄( g ) 就是在图g 的每一条边上插入一个点后得到的 图w h i t t l e s e y , g e o r g e s 和m a y o 【2 1 】首先研究了图的剖分图的l ( 2 ，1 ) 一标号问题 & ( g ) 的l ( d ，1 ) 一标号问题对应了v ( g ) ue ( g ) 的一个整数分配使得： ( 1 ) 图g 中任意两个邻点指定不同的整数； ( 2 ) 图g 中任意两条邻边指定不同的整数； ( 3 ) 相关联的点和边所指定的整数差值至少是d h a y e r 和y u 【l 】最先定义这样的整数分配为( d ，1 ) 全标号，也就是相关联的点 和边之间色数最小差值是d 的全染色 一个( d ，1 ) 全标号的跨度就是两个标号之间的最大差值，一个图g 的( d ，1 ) 全标号数( g ) 就是g 的( d 1 ) 一全标号的最小跨度显然，图g 的一个( 1 ，1 ) - 全 一4 一 一、绪论 标号就是它的一个全染色，并且碍( g ) = x t ( g ) 一1 ，其中矿( g ) 是图g 的全色 数 i - i a v e t 和y u 【l 】深入研究了( g ) 的上界，也就是关于图g 最大度( g ) 的 函数，证明了碍( g ) 2 a ( g ) + d 一1 但是对于最大度较大的图，这个上界不是 紧的于是，他们给出了以下猜想： 猜想1 2 【1 ja 亍( g ) ( g ) + 2 d 一1 如果猜想1 2 成立，我们有碍( g ) m i n 2 ( g ) + d 一1 ，( g ) + 2 d 一1 ) 当d = 1 时，这个猜想也就是全染色猜想：x t ( g ) a ( c ) + 2 他们还证明了完全图、以及 最大度较小的图都是满足这个猜想 之后，姗【3 1 】对图的极大割作数学归纳，证明了碍( g ) 2 & c g ) 一 l o g ( a ( g ) + 2 ) + d 一14 - 2 1 0 9 ( 1 6 d 一1 0 ) 并利用同样的方法，改进了( 2 ，1 ) - 全 标号的某些结果：若a ( g ) 3 ，则碍( g ) 2 ( g ) ；若a ( g ) 5 是奇数，则 碍( g ) 2 5 ( g ) 一1 b a z z a r o 和m o n t a s s i e r 【3 2 】证明了一般图满足以下关于围长9 ( g ) 和最大度 a ( g ) 的条件时，碍( g ) a ( g ) + d 一2 ： ( g ) 22 d + 1 且9 ( g ) 1 1 ； a ( g ) 2 d 4 - 2 且9 ( g ) 6 ； a ( g ) 2 d + 3 且9 ( g ) 5 ； ( g ) 8 d + 2 考虑图的( 2 ，1 ) - 全标号数与最大平均度的关系，m o n t a s s i c r 和r a s p a u d 【3 3 】证 明了：一个图g 的最大平均度m o d ( g ) 满足以下条件，则碍( g ) ( g ) + d 一2 ： a c g ) 2 d + 1 且m a d ( g ) ； a ( g ) 22 d + 2 且m a d ( g ) 3 ； a ( g ) 22 d + 3 且m a d ( g ) 2 ，曲( z ) = 2 ，其中i = 1 ，2 ，k ，则我们称这条路尸为舡链特殊 地，若k = 0 ，则一条0 链恰好就是一条边连接着两个度至少是3 的顶点 设t 是一棵( t ) = 3 的第1 类树，设，是t 的一个在标号集合日= o ，1 ，2 ，3 ，4 ) 下的4 一( 2 ，1 ) 一全标号基于，我们可以定义t 的一个新的4 ( 2 ，1 ) _ 全标 号，7 ：对每个$ y ( t ) ue ( t ) ，令，( 霉) = 4 一，( $ ) 显然，是t 在标号日下的 一个舢( 2 ，1 ) 一全标号，4 替换了0 ，3 替换了1 ，1 替换了3 ，0 替换了4 ，只有2 保持不变因 此，我们称，是，的一个对称置换，或者说是，的对称标号 对于( t ) = 3 的树t ，若t 的一棵子树t + 满足以下四个条件，则称t 是坏 的： ( 1 ) i k ( t + ) i l ； ( 2 ) ( p ) ( t ) 且( p ) k ( t ) ； ( 3 ) 对于任意的霉( t + ) ，m i n 如( z ，u ) i u k ( 2 ) ) = 3 ； ( 4 ) 对于任意的z ( t 。) ，r a i n d r - ( 。，u ) l u k ( 2 ) = 2 一7 一 p 图2 1 一棵坏子树p 如图2 一l ，r 就是一棵由1 7 个顶点导出的坏子树显然，当( p ) = 如) 时， p 包含3 条1 链：= z 仇 t 0 2 ，= z t 1 t 2 和p ”= 舢l 坳，其中抛，砚，w 2 在 p 中是叶，但在t 中却都是3 度点；而1 ，l ，t ，1 在p 和t 中都是2 度点如果 i k ( t ) i 2 ，那么在p 中任意一对距离最近的3 度点之间距离都是3 ，也就是 说，它们是被一条2 链所连接此外，p 中的叶与距离它最近的3 度点之间都是一 条1 链 设t 是一棵口) = 3 的树若t 不含有以下结构，则称? 是好的： ( c 1 ) 一个3 度点有两个3 度的邻点； ( c 2 ) 一棵坏的子树t + 设m 是一棵由4 个叶和2 个相邻的3 度点构成的6 阶的树设k 1 3 是一个4 阶 的星显然，m ，甄3 都是好树见图2 2 图2 - 2 树m 和硒3 尬3 引理2 1 设r 是一棵好树且不是m 和尬3 ，则t 至少含有以下结构之一( 见 图2 3 ) ： 一8 一 三：盟塑丝：1 2 ：全堡量 ( a 1 ) 一个叶“与一个2 度点 相邻； ( a 2 ) 一条2 链1 9 = $ o z l 2 2 。3 使得$ o 是大柄； c a 3 ) 一条1 链p = ：u o x l 霉2 使得z o 是大柄，z 2 与一个1 度点或一个3 度点相 邻： ( a 4 ) 一条k 一链p = z o $ 1 x k z , k 4 - 1 ，知3 ； c a 5 ) 一个3 度点“位于一条2 一链p = u z l $ 2 $ 3 和两条1 - 链0 1 = u y l y 2 ，q 2 = u z l z 2 上，使得抛，忽都是大柄； ( a 6 ) 一个3 度点u 与一个叶暑，和一个大柄名相邻，同时“位于一条k 一链 尸= “0 1 $ 2 z , k x k + l ，1 k 2 证明：设t 是一棵好树且不是m 和硒3 ，则a ( 7 3 = 3 ，i t i 5 并且t 不包含 ( c 1 ) 和( c 2 ) 若t 含有( a d ，则引理成立因此，在接下来的讨论中，我们都假设 t 不含有( a 1 ) 设q = t i t 2 是? 中的一条最长路由俐5 可知，t r b 4 又因为口 是最长的路，所以t l ，t m 都是叶由于t 不含有( a 1 ) ，所以屯，t 一1 都是3 度点设y 是t 2 的异于t 1 ，t 3 的另一个邻点我们断言y 是一个叶，否则t 存在一条路使 得z ( q ，) z ( q ) ，这与q 是最长路相矛盾 由m 4 可知，d ( t 3 ) 2 首先假设d ( t a ) = 3 设叫是t 3 的异于t a ，t 4 的另 一个邻点由于t 不包含( c 1 ) ，d ( 伽) 3 若d ) = 2 ，记为 t o 的异于t a 的另 一个邻点因为t 不含有( a 1 ) ，所以叫7 不是叶记为的异于伽的另一个邻 点，则路9 = t o ”伽7 w t 3 t a 的长度z ( o ) z ( q ) ，这与q 是最长路相矛盾于 是，d ( w ) = 1 由t 不包含( c 1 ) 可知，d ( t 4 ) 3 进而由t 不是m 可知，d ( t 4 ) = 2 因为t 不含有( a 1 ) ，所以d ( t 5 ) 2 若d ( t 5 ) = 3 ，则( a 6 ) 的= 1 的情况成立于 是假设d ( t 5 ) = 2 ，由t 不含有( a 1 ) 可知，d ( t e ) 2 若d ( t s ) = 2 ，则( a 4 ) 成立；若 d ( t e ) = 3 ，( a 6 ) 的k = 2 的情况成立 其次，假设d ( t 3 ) = 2 由于t 不含有( a d ，则d ( t 4 ) 2 着d ( t 4 ) = 2 ，则 d ( t 5 ) 2 当d ( t 5 ) = 2 时，( a 4 ) 成立；当d ( t 5 ) = 3 时，( a 2 ) 成立 现在假设d ) = 3 记8 为扎的异于t 3 ，t 5 的另一个邻点若d ( s ) = 1 或 d ( s ) = 3 ，则( a 3 ) 成立所以假设d ( 5 ) = 2 记一为s 的异于t 4 的另一个邻点因 为t 不含有( a 1 ) ，所以d ( 8 ) 2 再记，为，的异于8 的另一个邻点我们断言 s ，是一个叶事实上，若d ( ) 2 ，则，存在异于5 的另一个邻点而t 上的 路= 8 7 s t 4 t 5 的长度z ( q ) z ( o ) ，这与q 是最长路相矛盾因此， 一9 一 三：煎堕f ! ：1 2 ：全堡呈 是一个柄再由丁不含有( a 1 ) 可知，d ( s 7 ) = 3 若d ( t 5 ) = 1 或d ( t 5 ) 一3 ，则( a 3 ) 成立所以假设d ( t 5 ) = 2 ，则由t 不含 有( a 1 ) 可知，d ( t s ) 2 若d ( t 6 ) 3 ，则点子集 t 2 ，t 3 ，t 6 ，s ，s 】导出的子图是 t 的一棵坏子树，矛盾因此d ( t b ) = 2 再根据t 不含有( a 1 ) ，d ( t 7 ) 2 若t 7 是2 度点，贝i j ( a 4 ) 成立；若t 7 是3 度点，则( a 5 ) 成立引理证毕 t ，t 一一一o - - - - - - - - - o ( a d ( a 3 ) z 是小点 + 蓄! 苦! 盘盘警 ( a 4 ) ( a 6 ) k = 1 盘) ( a 5 ) 图2 - 3子图( a 1 h ，a 6 ) 一1 0 一 ( a 6 ) k = 2 三：塑盟f ! ：1 2 ：全堡量 引理2 2 ( h a v e ta n dy u2 0 0 2 ，【1 】) ( 1 ) 若日是g 的子图，则a ；( 日) 碍( g ) ； ( 2 ) 若碍( g ) = ( g ) + 1 且，是g 的一个在标号集 o ，1 ，( g ) + 1 ) 上的( ( g ) + 1 ) 一( 2 ，1 ) 一全标号，则对于g 中每个大点 都有，( 勘) = 0 或，( t ，) = a ( g ) + 1 引理2 3 若g 中存在一个大点 至少与d ( v ) 一1 个大点相邻，则碍( g ) ( g ) + 2 证明：反证法假设碍( g ) ( g ) + 1 设，是g 的一个( ( g ) + 1 ) 一( 2 ，1 ) 全 标号，标号集合8 = o ，1 ，a ( c ) + 1 ) 设 是一个大点， l ，吨，都是 g 中与t ，相邻的大点，其中m d ( t ，) 一1 根据引理2 2 ( 2 ) ，不失一般性地假设， ，( t ，) = 0 再根据引理2 2 ( 2 ) ，我们得到f ( m ) = ( g ) + 1 ， = 1 ，2 ，m 因此，边 口钞l ，伽b ， 钉。的可用标号为2 ，3 ，a ( g ) 一1 由m d ( ) 一1 = ( g ) 一1 可知，必然存在两条不同的边钉吻，伽。，p q 分别到相同的标号这与，的定义相 矛盾因此碍( g ) a ( c ) + 2 引理证毕 引理2 4 假设t 是第1 类的树满足( t ) = 3 ，设，是? 的在标号集合召= 0 ，1 ，2 ，3 ，4 上的4 - ( 2 ，1 ) - 全标号设p 一善o z l 卫。霉。+ 1 是丁的一条m 链那 么以下的结论成立： ( 1 ) 若m = 0 ，则，( z o $ 1 ) = 2 ； ( 2 ) 若r n = 1 ，贝u ，( z o z l ) 2 且，( z 1 勋) 2 ； ( 3 ) 若m = 2 ，则，( z o z l ) ，( z 2 霉3 ) 中至多有一个等于2 证明：根据定义，显然有d ( x o ) = d ( z 。+ 1 ) = 3 ，d ( z ) = 2 ，i 一1 ，2 ，m 由引 理2 2 ( 2 ) 知，( z o ) ，f ( x r a + 1 ) o ，4 ) ( 1 ) 若m = 0 ，则p = t 0 ! 9 1 不失一般性，我们假设f ( x o ) 一o ，于是，( 。1 ) = 0 自然地，我们可以得到，( $ o z l ) 一2 ( 2 ) 若m = 1 ，则p = x o x l z 2 若，( z o z l ) = 2 ，我们可以假设，( 。o ) = 0 ，则 ，( $ 1 ) = 4 于是又引理2 2 ( 2 ) 知，( 现) = 0 ，而此时边x l z 2 无法被正常标号因此， ，( o o 茹1 ) 2 同理可证，f ( x l x 2 ) 2 ( 3 ) 若m = 2 ，贝up = 茹o z l z 2 3 如果f ( x o x l ) = f ( x 2 = 3 ) = 2 ，由，( z o ) ，( z 3 ) o ，4 ) 可知，( $ ) ，( 霉2 ) t o ，4 ) ，也就是说，$ 1 ，霉2 中一个标号是o ，另一个标号 是4 ，而此时边z l z 2 无法被正常标号引理证毕 引理2 5 设2 是一棵( t ) = 3 的树设u 是t 的一个大点， 1 ， 0 2 是t 上的两个 叶，2 ) 3 是的另一个邻点若子树t t ，l 一抛在标号集合嚣= o ，1 ，2 ，3 ，4 ) 上有 一个禾( 2 ，1 ) 一全标号使得f ( u ) o ，4 ) ，则f - t p a 被扩展成为整棵树t 的( 2 ，1 ) - 全 标号 证明：不失一般性，我们假设，( u ) = 0 因此，f ( u v 3 ) 2 ，3 ，q 若，( 伽3 ) = 2 ，则 令伽1 ，t 也，t ，1 ，忱的标号分别为3 ，4 ，1 ，2 ；若，( 珏) = 3 ，则令u t ) 1 ，t 砚，1 ) l ，化的标 号分别为2 ，4 ，4 ，2 ；若，( t 啦) = 4 ，则令 1 , 1 3 1 ，t 地， p 1 ， 0 2 的标号分别为3 ，2 ，1 ，4 易 验证这是t 的4 ( 2 ，1 ) - 全标号引理证毕 ( - - ) 、最大度为3 的树的( 2 ，1 ) 一全标号的刻画 我们知道，对于a ( t ) = 3 的树t ，4 a t ( t ) 5 在这节中，我们给出最大 度为3 的树的完全刻画 定理2 1 若t 是一棵( 功= 3 的树，则a t ( t ) = 4 当且仅当t 是好的 证明：必要性假设a r ( t ) 一4 设，是丁的在标号集合日= o ，1 ，2 ，3 ，4 ) 上 的4 - ( 2 ，1 ) 全标号对于任意e e ( t ) ，i 8 ，若，( e ) = ，则称e 为i 一边下面我 们将要证明t 不含有( c 1 ) 和( c 2 ) 若t 包含一个3 度点与另外两个3 度点相邻，则根据引理2 3 ，a t ( t ) ( t ) + 2 5 这个矛盾意味着t 不含有( c d 假设t 含有一棵坏的子树p 根据定义，i k ( t + ) l 1 并且p 由一些2 - 链 和1 链构成设t ，k ( t ) 根据引理2 2 ( z ) ，f ( v ) o ，4 ) 因此，t ，必然关联某 条2 边，记为注意到，e t ，位于一条2 链上，并根据引理2 4 ，每条2 一链中至多只 有一条2 边也就是说，如果1 | 和口是k ( p ) 中不同的两个3 度点，则气，以及 相对应的2 链r ，r 都是不同的两条2 链不同是指它们是内点不交的因此p 中2 链的个数至少有i k ( 丁) 1 个另一方面r 是棵树，并且p 中任意两个最近 的3 度点之间都是一条2 链，因此t + 至多有l u 口+ ) l 一1 个2 - 链，矛盾因此r 不 包含( c 2 ) 充分性对t 的顶点数i t i 归纳若f t i = 4 ，则t 就是琏。3 ，我们很容易 得到碍( 甄，3 ) = 4 于是假设树t 是好的且i t i 5 若t 是m ，则容易证明 m t ( m ) = 4 所以假设t 不是m 我们只要证明这样的丁有4 - ( 2 ，1 ) 一全标号根据 引理2 1 ，t 包含6 种结构( a d ( a 6 ) 之一，因此以下证明也将分成6 种情况在任何 一种情况中，标号集合都是由5 个元素组成的集合8 = 0 ，1 ，2 ，3 ，4 ) 一1 2 ( a d 设r = t 一讥显然r 是好的，并且( r ) = ( t ) = 3 根据归纳假设， r 有一个廖上的4 - ( 2 ，1 ) 一全标号，对于牡，删，都至多有4 种不可用的标号，而b 中有5 个不同的标号，因此，被扩展成为t 上的4 - ( 2 ，1 ) 一全标号 ( a 2 ) 设y 1 ，y 2 是。o 的异于霉1 的另外两个邻点设r t 一 z o ，x l ，y l ，抛 显 然r 是好的，并且( r ) = ( t ) = 3 根据归纳假设，r 有一个8 上的4 ( 2 ，1 ) 一全 标号，由于是r 中的一个3 度点，根据引理2 2 ( 2 ) ，( x 3 ) o ，4 ) 不失一般 性，假设f ( x 3 ) = 0 ，则f ( x 2 x 3 ) 2 ，3 ，4 只要证明霉2 ，x 1 3 e 2 ，0 1 ，：r 0 x l ，跏能被正 常标号使得z o 的标号是0 或者4 ，则根据引理2 5 ，可以扩展成t 的4 ( 2 ，1 ) 全标 号为此，我们首先擦除霉2 的标号，然后执行以下步骤： 若，( 。2 2 3 ) = 2 ，则令x 2 ，x 2 x l l ，x o x l ，x o 的标号分别为4 ，o ，2 ，4 ，0 ； 若，( 。2 2 3 ) = 3 ，则令现，z 2 。l ，z l ，x o x l ，2 ：0 的标号分别为1 ，4 ，0 ，2 ，4 ； 若，( z 2 2 3 ) = 4 ，则令z 2 ，z 2 2 1 ，x l ，x o x l ，x 0 的标号分别为1 ，3 ，0 ，2 ，4 ( a 3 ) 设讥，伽是z o 的异于$ 1 的另外两个邻点设r = t 一 $ o ，y l ，抛) 显然 r 是好的，并且( r ) = ( t ) 一3 根据归纳假设，r 有一个8 上的4 - ( 2 ，1 ) 一全 标号，因为d , r , ( x 2 ) = 3 ，根据引理2 2 ( 2 ) ，所以f ( x 2 ) 0 ，4 ) 不失一般性，我 们假设f ( x 2 ) = 0 根据定义，如，( 一) = 1 或如( 一) = 3 若如( 一) = 3 ，则x , 2 ，一 在t 中是对相邻的3 度点根据引理2 4 ( 1 ) ，( z 2 ) = 2 设d t t ( g g ) = 1 ，如果 ，( $ 1 2 2 ) 2 ，则不对r 做任何修改；如果f ( x l $ 2 ) = 2 ，则交换z l * t 2 和$ 2 $ 的标 号，再令，( ) = 4 也就是说，此时，( $ l z 2 ) 3 ，4 ) 除z l 的标号，然后执行以下 步骤： 若，( z l z 2 ) = 3 ，则令z 1 ，霉o $ 1 ，2 ：0 的标号分别为1 ，4 ，0 ； 若f ( x l f i 9 2 ) = 4 ，则令$ 1 ，x 0 3 ：i ，z o 的标号分别为2 ，0 ，4 因此，根据引理2 5 ，可以扩展成t 的4 ( 2 ，1 ) 全标号 ( a 4 ) 设r = t 一 z 2 ，z 3 ，霉 一1 ) 因为k 3 ，所以r 包含两棵子树以，珏， 其中