（应用数学专业论文）两类毛毛虫的多级距离数.pdf

两类毛毛虫的多级距离数 摘要 图g 的多级距离标号( 电台标号) 源于h 幽的无线电频道分配问题它足指函数 ，：y ( g ) 一 o ，1 ，2 ，) ，使得对于图g 中的任意两点t ，秒，满足i ，( 札) 一，( 口) i 饿o m ( g ) + 1 一d ( u ，口) ，其中比n m ( g ) 表示图g 的直径m n z i ，( u ) 一，( ) i ：t ，t j y ( g ) 称为多级 距离标号，的跨度；图g 的所有多级距离标号的最小跨度称为图g 的多级距离数，记为 m ( g ) 如果删去树t 的所有悬挂点及其相关联的边后得到的是一条路或一个孤立点，则称 t 是一个毛毛虫 本文主要研究了两类毛毛虫一一特殊毛毛虫和关于权中心点对称的毛毛虫的多级距 离标号和多级距离数 依据内容，本文分为三个部分： 第一部分主要介绍了本文选题的背景，意义和图的多级距离标号，多级距离数的概念， 国内外的研究现状以及一些预备知识 第二部分研究的是一类特殊的毛毛虫，即除悬挂点外各点度数均相同的毛毛虫应用 反证法给出了它的多级距离数的下界；通过确定权中心点构造了一种特殊的多级距离标 号并由此得出了这类特殊毛毛虫的多级距离数 结论1 令g = 最t 是一个特殊的毛毛虫，则 m c 最。= i 譬二：； 茎二竺：蓦：二耋：；：萋：凳裹萋： 第三部分研究的是一类具关于权中心点结构对称的毛毛虫应用反证法和通过构造 特殊的多级距离标号得出了这类关于权中心点对称的毛毛虫的多级距离数 州剐：p 蛩。h1 】“- 2 陋考鹕掣+ 驴和州和+ 2 _ 2 m 若鼢偶警 l 即戛m 1 ) + 。拳】一2 。字一2 戛2 讹字讲l 1 ) + 2 ， 若七为奇数 1 七【2 邑m 1 ) + 。拳】- 2 。字一2 丕2 o 字讲l 1 ) + 2 ， 若七为奇数 t h em u l t i l e v e ld i s t a n c en u m b e r sf o rt w oc l a s s e so fc a t e r p i l l a u r s a b s t r a c t m u l t i 1 e v e ld i s t a n c el a b e l i n g ( o rr a d i ol a b e l i n g ) i sm o t i 僦e db yt h ec h a n n e la s s 远n m e n t p r o b l 锄i n t r o d u c e db yh a l e i ti saf u n c t i o n ，：y ( g ) _ o ，1 ，2 ， ，s 0t h a tt h ef o l l o w i n gi s s a t i s f i e df o r 锄y ，钉y ( g ) ：i ，( t ) 一，( 口) l 出口m ( g ) + l d ( u ，口) ，w h e r e 出o m ( g ) i st h e d i a m e t e ro fg t h es p a n0 f ，i sd e f i n e da sm 口z i ，( 仳) 一，( 口) l ：t ， y ( g ) ，a i l dt h em u l t i k v e ld i s t a n c en u m b e rf o rag r a p hg ，d e n o t e db yr n ( g ) ，i st h em i n i i i 】【u ms p a no fa ：um u l t i 1 e v e l d i s t a n c ei a b e l i n 黟o ft h e 黟印hg at r e ei sc a l l k d ac a t e r p m a ri fap a t ho r 锄i s o l a t e dv e r t 麟i 8o b t a i n e db yd e l e t i n gi t sa u p e n d e n 七v e r t i c e s 卸da l lp e n d e n te d g 皓 i nt h i sp a p e r ，t h em u l t i _ l e v e ld i s t a n c e 抽e l i n ga n dt h em u l t i _ l e v e ld j s 七触c en u m b e r sf 砸 t w od a 鹃髑o fc a t e r p m a 船缸es 乞u d i e d o n ei st h ep 舭t i c u l a rc a t e r p i l l a ra n dt h eo t h e ri st h e c a t e r p i l l a rw h i c hi ss y m m e t r i c a la b o u ti t sw e i g h tc e n t e r a c c o r d i n gt ot h ec o n t e n t s ，t h i sp a p e ri sd i v i d e di n t ot h r e ec l l 印t e r s i nt h e 矗r s tc h a p t e r ，i ti si n t r o d u c e dt h a tt h eb a c k g r o u n d ，t h es i g n i 丘c a n c eo ft h ep 印e r 姐dt h ec o n c 印t s ，t h ep 豫；e n ta c t u a h 够o ft h em u l t 0 i e v e ld i s t a n c el a b e l i n ga n dt h em u l t i - l e v e l d i s t a n o en u 瑚【b e ra 意h o m ea n da b r o a d ，觚dt h ep r e p a r a 土i v et h e o r i e 8 i nt h e c o i l dc h a p t e r ，i ti ss t u m e dt h a 乞ac l a 鹅o fp a r t i c t l l a rc a t 唧i l l a r st h a td e 伊o fa u v e r t i c 既雏ee ( 1 u a l ，e x c e p t 七h ep e n i l e 】啦、，e r t i c 够i ti so b t a i l l e dt h a tt h el o w 盱b o u n db y 璐i n gt h e p r o o fb yc o n t r a d i c t i o n ，趾dt h e nt h ei 矾l t i - l e 、，e ld i s t 锄c e 肌n l b e ri 8o b t a i l 峨ib ys t r u c t u r i n ga p a r t i c u l a u r 硼n t i k r e ll a b e l i n g c o n c l u s i o n1 l e tg = 最tb eap 8 玳i c u l a rc a t e r p i l l a r w - el 谢v e 州蹦= | ：二嚣嬲：妻二磊篡= i nt h et h i r dc h a p t e r ，i ti 8s t u d i e dt h a tac i a 鹃o fc a t e r p i l l 盯sw h i c ha 舱8 y m m e t r i c a la b o u t t h e i rw e i g h tc e n t e r s b yl l s i n gt h ep r o o fb yc o n t r a d i c 七i o na n ds t r u c t l l r i n gt h ep a r t i c u l a u rm u l t i 1 e v e l l a b e l i n g ，w e0 b t a i ni t s 咖l t o l e 、，e ld 斌锄c en u h l b e r c o n c l 峭i o n2 l e tg = j kb eac a 七e r p i l l a rw h i c hi ss y m l e t r i c a la b o u tt h ew e i g h tc e n t e r t h e n r n ( 最t ) = 要一l 2 鸭+ 如一1 ) + 量i ( 2 和+ 1 + 。扣+ 2 2 ) 】，i f 姚e v e n ， 2 t 出一2 2 i f 后i 8o d d k e yw o r d si n u l t i l e v e ld i s t a i l c el a b e u n g ；m l t i 1 e v e ld i 8 t a n c en u m b e r ；c a t e r p i l l a r 2 + 1 工一 + 王卜 2 字：i c 一 一 + 学 + d d 一 一 陬他 鲁口置。渤 p p 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得叁洼! 重整盘堂或其它教育机构的学位或证j 抒而使用过的材料。 与我一同- t 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：辛埂一日期：蒯 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文 的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇 编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：皇整丘l 军l 一日期： 第一章前言 5 1 1 选题背景和意义 在图论中，多级距离标号又称为电台标号，它是2 - 距离标号( 二( 2 ，1 ) 一标号) 的拓展无 论足工( 2 ，1 ) 一标号还足多级距离标号它们既都是特殊的点染色问题，也都源于h a l e 1 】的无 线电频道分配给定一些电台的一个集合，一个有效的频道分配足指这样一个函数，它分 配给每个电台一个频道，使这些电台彼此之间的信号避免相互干扰它的目的就是找到一 个可用的跨度最小的有效的频道分配方式电台之间相互干扰的度( 级别) 是与电台所处 的位置有关的，即两电台之间的距离越近，它们相互干扰的度就越大因此为了避免这种 干扰，距离越近的电台，它们之间的频道差就应该越大，从而频道差就由两电台之间的距 离决定。 随着社会的进步，通讯信息，信号传递，计算机网络事业发展越来越快随之而来的 是，对于信号、调频频道分配的要求也越来越高。特另l j 足在当今大力提倡建立节约型社会 的背景下，如何应用尽可能少的信号频道提供优质的通讯效果服务就成为现今研究的热 点与难点在这种大的背景和趋势下研究一些图的多级距离标号和多级距离数问题，有很 大的现实意义和应用价值 1 2 图的距离标号介绍及其研究现状 对于前面提到的电台之间的频道分配问题可以用图论的知识模拟表示出来，即把每一 个电台表示成图的个点，每一对相邻的电台在图中相应的点之间都连以边由此h a l e 【1 1 就将此频道分配问题概括成图的点染色问题 对于图汀和图g ，如果y ( 日) y ( g ) 且e ( 日) e ( g ) ，则称图日是图g 的子图，记 为日冬g 若日是g 的子图且y ( 日) = y ( g ) ，则称日是g 的支撑子图( 或生成子图) 设y y ( g ) ，以y 为顶点集，以两端点均在y 7 中的边的全体为边集所构成的子图，称为 g 的由顶点集y 7 导出的子图，简称为g 的点导出子图，记为g 【卅对于图g 个顶点子 集合s ，如果s 中的任意两点在g 中都不相邻，那么s 称为g 的一个独立集图g 的一 个鬼一着色是从y ( g ) 到 l ，2 ，) 的一个映射对于g 的一个给定的七一着色，表示 g 中染t 色的所有顶点，而g 陬】表示k 在g 中的点导出子图。若m ( 1 i 南) 都足独立 集，则称，足一个正常七一着色使得图g 有一个正常一着色的最小数后称为g 的点 色数，记为x ( g ) 若x ( g ) = 南，则称g 是七一色图 令g 是一个连通图，记d ( ，t ，) 为图g 中任意两点“，口之间的距离对于图g ，个 跨度为南的2 一距离标号足指一个函数，：y ( g ) _ o ，1 ，2 ，砖满足：( 1 ) 如果d ( z ，) = l ，则i ，( z ) 一，( 耖) l 2 ；( 2 ) 如果d ( z ，y ) = 2 ，则l ， ) 一，( 秒) f 1 函数，的跨度足指 m 口z i ，( 让) 一，( u ) i ：t ，口y ( g ) 图g 的a 数足指图g 的2 一距离标号的最小跨度，记为 1 a ( g ) 对于有优。仇( g ) 级干扰的频道分配问题，下面给出它的严格定义 定义1 多级距离标号是指一个函数，：y ( g ) 一 o ，1 ，2 ， ，使得对于图g 中的任意两点 牡， 满足l ，( 钆) 一，( u ) i 疵o m ( g ) + l d ( u ，秒) ，其中嘶o m ( g ) 是指图g 的直径( 所有点对 问的最大距离) m o z i ，( 让) 一，( 口) i ：牡，t ，y ( g ) 称为多级距离标号，的跨度；图g 的多 级距离数是指图g 的所有多级距离标号的最小跨度，记为r n ( g ) 当嘶o m ( g ) = 2 时，2 一距离标号与多级距离标号是一致的，即a ( g ) = r 礼( g ) 对于图的距离标号的研究起始于二十世纪8 0 年代1 9 8 8 年，r 0 b e r t s 在与g r i g g s 的 私人通信中提到了上述的频道分配问题对于图的t _ 染色和频道分配问题的研究主要 见r 肪e r t s ( 【2 ，【3 】) 和弧m a n 【4 】 1 9 9 2 年g r i g 眵和y e h 5 】将此类问题推广成二距离标号问题，并得到了如下的结论和 猜想： ( 1 ) 令r 是一条有他个点路( ，l 2 ) ，则 i2 ，若n = 2 ， a ( r ) = 3 ，若佗= 3 ，4 ， l4 ，若n 5 ( 2 ) 令足一个有n 个点的圈( n 3 ) ，则入( g ) = 4 猜想1 ( g 坳s 和娩 倒) 令g 是最大度为( g ) 2 的图，则a ( g ) 2 ( g ) 1 9 9 4 年，s a k a id e n i s e 【6 】验证了一类重要的图一一通弦图( 不包含多于三点的导出环 的图) 满足上述假设对于2 距离标号的研究至今已经非常广泛了，且得到了许多非常 好的结论( 【5 ，7 ，8 ，9 ，1 0 ，1 l ，1 2 】) 多级距离标号也是一个非常有趣的图形标号问题，迄今 为止已有很多学者对它进行了研究 2 0 0 1 年，gc h 疵r a n d ，de r w i i l ，fh a r a 可【1 3 】介绍了图的多级距离标号 2 0 0 2 年，pz h a n g 【1 4 】得出了圈的多级距离数的上界和下界以及一部分圈的多级距离 数；在2 0 0 5 年，d a p h n ed e r f e nl u i ，x u d i n gz h u 【1 6 】完全解决了路和圈的多级距离标号和 多级距离数问题： ( 1 ) 对于任意n 3 ，则 州耻臀矗“嚣 ( 2 ) 令g 是一个有n 个点的圈，其中n 3 ，则 州耻 冀：喜詈：黑： 2 2 0 0 4 年，d 印h n ed e r - f e nl u i ，m e l a n i ex i e 【1 5 】完全解决了偶平方圈的多级距离数问题， 对于奇平方圈的多级距离数得到了一个下界： ( 1 ) 令碟是一个有n 个点的平方圈，其中n 为偶数，则 f 逖掣，若n ：4 南且七为奇数， 州啦 麓扎篆竺是器数， l 南2 + 4 后+ 1 ，若n = 4 + 2 且忌为偶数。 州啦忪荨霎：凳么， 如果岛兰l ( m d d 4 ) ，则而2 + 七十1 r n ( p 毳+ 1 ) 七2 + 七+ 2 2 0 0 6 年，d 印h n ed e r - r ml u i ，m e l a n i ex i e 【17 】完全解决了平方路的多级距离数问题： 令焉足一个有几个点的平方路，= 【剖，则 州耻僻；：籍h 一) ， 2 0 0 8 年，d a p h n ed e r - f e nl u i f l 8 】得到了树的多级距离数的下界，并且得出了一类特殊 的树一“蜘蛛”( 至多有一个顶点的度数大于2 的树) 的多级距离数： 令g = & 。翰，l 。是一个有t 1 个点的蜘蛛，其中n 3 ，j l f 2 k ，瓦= z 2 + f 3 + + k ，贝8 州g ) ：壹m 帕“) + 学1 【学j + l t = l 一一 当且仅当i 掣 对于一般的树，d 印h n ed e r - f e nl l l i 【1 8 】得到了下面的结论 引理1 p 口p 危n ed e r f e t l 三“班劬设r 是有m 个顶点直径为d 的树，则 r 礼( g ) ( m 一1 ) ( d + 1 ) + 1 2 u ( t ) 1 3 预备知识 如果删去树t 的所有悬挂点及其相关联的边后得到的是一条路或一个孤立点，则称 t 是个毛毛虫本文主要研究了两类毛毛虫：一类足除悬挂点外各点度数均相同的毛毛 虫，另一类是具有某些性质的关于权中心点对称的毛毛虫 令t 是以为根的树，对于任意点t y ( t ) ，记( ) = d ( 伽，t ) 对于t 中 3 任意的两点u ，t ，如果仳在m ，口) 一路匕则“称为口的祖先点，而御称为札的后代点 对于树t 中任意一点伽，以叫为根的树r 的权定义为“留( 州) = l 钾( ) ，树t 的权 u ( t ) = m i n 岬( 叫) ：硼y ( g ) 对于树t 中的点，如果满足岬( 伽) = u ( t ) ，则称为 树t 的权中心点，在不引起混淆的情况下，以下简记l ( u ) = l 叫，( 仙) 如果叫7 是树t 的一条边，死，死，为t 一叫叫7 的两个分支，则叼( 加) = 叼( 叫7 ) + i y ( 死训一i y ( 死) i 引理2 口曰设 7 为树t 的权中心点，则r t t ，7 的任意分支至多包含i y ( t ) i 2 个顶点 引理3 口酬每一个树t 有一个或两个权中心点，树t 有两个权中心点t t 7 ，当且仅当t l ， 是树t 的一条边而且t t 7 加7 由两个平衡分支组成。 多级距离标号就足一一映射，；另一方面，每一个顶点集合y ( g ) 上一一映射整函 数，o ，( y ) ，都可以导出顶点集y ( g ) 一个序列，记为矿( ，) ，其中y ( g ) = u ( ，) = 咖，t i l ，m 一1 ，满足： o = ，( t 正o ) ，( t 正1 ) ，( 让2 ) ，( u i y l 1 ) 如果，是一个多级距离标号，那么，的跨度就是，( “m 一1 ) 4 第二章一类特殊毛毛虫的多级距离数 本章将重点研究一类特殊毛毛虫的多级距离数：首先，对于这类特殊的毛毛虫，改进 了l i u 【1 8 给出的关于树的多级距离数的下界，然后构造了一个特殊的多级距离标号，并由 此得出这类特殊毛毛虫的多级距离数的确切值。 引入符号r 。表示直径为府一l ，除悬挂点外各点度数均为t 的特殊毛毛虫，其中r 表 示乓中的最长路显然，这类特殊的毛毛虫段t 共有( t 一1 ) ( 七一2 ) + 2 个点， 一1 ) ( 忌一2 ) + 1 条边 记”l ，o 为r 上第个点，忱，o 则为r 上第t 个点( 1s 后) ，1 为最上第 个点的 第一个悬挂点( 1 i 忌) ，啦卜2 则为r 上第i 个点的第t 一2 个悬挂点( 1 t 后) ( 见图 1 ) 口9 0 马6图1 移1 2 0 p 1 2 5 对于r t ，当南为奇数时，不难发现可学，o 为其权中心点，。( 1 i 墨笋) 以及与它 相关联的边称为r t 的上分支，仇，o ( 学 l 詹) 以及与它相关联的边称为r t 的下分支， 口半，o 以及与它相关联的边称为“中间”，它们既可属于上分支也可属于下分支，在本章中， 我们不妨假定它们属于上分支，为区别于上分支中的其它点、边，我们不妨称它们为。上 5 盘 j 矗七 d a 盘 d 盘 a d q q l 坦 仫倔似 似侣饰 伪w 倔 懈御以 仉仉 2 l 2 l 2 l 2 l 2 l 2 l 2 l 睨 昭 侣 如 以 似 蛞 侣 倦 懈 胛 啊 侣 啦 中”当七为偶数时，t ，o 与u + 1 ，o 都屉权中心点( 在本章中，我们选定t ，鲁，o 为其权中心 点) ，地，o ( 1 t ) 以及与它相关联的边称为r t 的上分支，饥，o ( + lsl 七) 以及与它相 关联的边称为最t 的下分支，而可冬，o 以及与它相关联的边又称为“上中”，t ，+ l o 以及与它 相关联的边又称为“下中” 定理1 令g = 坟t 是一个特殊的毛毛虫，则 u c r 。= | 嚣二：鬟薯二耄：萋竺凳主耋： 证明；容易知道，当后为奇数日寸，t ，半，o 为其权中心点；当七为偶数时，u 考，o 为其权中 心点从而得出 啦扣= 若后为奇数， t ，若后为偶数 整理即可得到结论 证毕 将上面的结果代入到引理1 中即可得到下面的结论 推论1 令g = 忍t 是一个特殊的毛毛虫，则 ，n c 最。 | 鬈二焱竺二竺：蓦：二冀：萋：舅主萋： 前面已经说过，对于一个多级距离标号，u ( ，) = 咖，t l ，m l ，有 o = ，( t 正o ) ，( t 上1 ) ，( t 2 ) ，( t m 1 ) 对于任意的o i i y l 一2 ，令 z = ，( t k + 1 ) 一，( t l t ) + l ( t 正i + 1 ) + 三( t q ) 一出n m ( g ) 一l 则由定义l ，若，是一个多级距离标号，则对于任意的o i i y 卜2 ，有戤o 为方便叙述，对于整数( os ) i ；( 幻+ 2 2 ) + 2 ( o j 譬) ； 当七为偶数，岛均为奇数时，o 喜一f 之 ( 幻+ 2 1 ) + 2 ( o j 学) ； 当七为奇数，如均为偶数时，t 2 = o 半= t 丘一l 且掣一， 岛+ l + l ( 1s 歹譬) ； 当詹为奇数，t 均为奇数时，如= o 毕= “一l 且毕一， ( 巧+ l + 1 ) ( 1 歹譬) 熹喜 显然，当詹为偶数时，r 共有2 慨一1 ) + 2 个点，2 ( 岛一1 ) + l 条边；当为奇数 t = li = l 知一1七一l o口 时，r t 共有2 他一1 ) + 量掣+ 1 个点，2 慨一1 ) + o 半条边 记t ，l ，o 为最上第个点，o 则为r 上第j 个点( 1 i 七) ，l 为最上第歹个点的 第一个悬挂点( 1 歹 七) ，巧，t r 2 则为最上第j 个点的第易一2 个悬挂点( 1 。沁， 、 ：沁： i 一 ，沁： 咖o ”1 0 一 螂： 爪 叭 爪 ? 叭、 ；爪： 图4 弧o 对于乓t ，当七为奇数时，不难发现t ，量掣，o 为其权中心点，吻，o ( 1 j 警) 以及与它 相关联的边称为最t 的上分支，o ( 半 j 七) 以及与它相关联的边称为最t 的下分支， t ，量# ，o 以及与它相关联的边称为“中间”，它们既可属于上分支也可属于下分支，在本章中， 我们不妨假定它们属于上分支，为区别于上分支中的其它点、边，我们不妨称它们为“上 中”当j c 为偶数时，”害，o 与口粤+ l ，o 都是权中心点( 在本章中，我们选定口軎，o 为其权中心 点) ，o ( 1s 歹喜) 以及与它相关联的边称为r t 的上分支，o ( + ls 歹七) 以及与它相 关联的边称为r t 的下分支，而t ，毒，o 以及与它相关联的边又称为。上中”，t ，要+ 。，o 以及与 它相关联的边又称为“下中一 定理4 令g = 最t 是一个特殊的关于权中心点对称的毛毛虫，则 f一l 删：”砖一h 驴和，1 + 。q l 瓤椭数 lo 字+ 三2 i ( o