（运筹学与控制论专业论文）图的l（d1）标号的边跨度.pdf

摘要 图g 的标号着色l ( 2 ，1 ) l a b e l i n g 是一个从顶点集v ( c ) 到非负整数集的函数， 满足条件：( 1 ) l ，( “) 一f ( v ) l22 ，若“u e ( c ) ；( 2 ) f ，( “) 一，( 口) f 1 ，若d ( u ，”) = 2 将所有正常l ( 2 ，1 ) 一标号的集台记作z ( 2 ，1 ) 图g 的标号着色数定义为： a ( g ) = m i n m a x f ( , ) ：u y ( g ) ) ，即使图g 所有正常的l ( 2 ，1 ) 一标号的最大标号达到最小 值我们可以将这个概念推广到一般的情形l ( d ，1 ) 一标号和工( s ，t ) 一标号，相应的标 号着色数分别记为扎( g ) 和a h “( g ) 图的标号着色问题来自所谓的频道分配模型： 不同的电台要使用无线频道发送信号，为了避免相互干扰，位置十分接近的电台要 使用相差足够远的频道，位置较近的电台要使用有一定相差的频道将频道分配给 电台，目标是在保证电台互不干扰的前提下使用最少的频道资源 本文主要研究该标号的另外一个参数，即边跨度，记做芦( g ) = m ；n m a x l ，( u ) 一 ，( ) li “”( g ) ) ，其中，z ( 2 ，1 ) ，即在所有的正常l ( 2 ，1 ) 一标号中，使得相邻顶点的 标号之差最大值达到最小值同样我们可以求出l ( d ，1 ) 一标号下的边跨度尻( g ) 和 l ( s ，t ) 一标号下的边跨度觑叫) ( g ) 对于部分图类，我们还给出了标号着色数限制下 的边跨度，分别记作卢( g ，a ) 和风( g ：a d ) 在第二，三，四，五章中，我们分别讨论了g 、r 、。，。、正三角形 网格、正四边形网格、正六边形网格、轮聃名、路的强积图和弦图的边跨度对于正 六边形网格、轮、路的强积图和弦图，还给出了它们在标号着色数限制下的边跨度 关键词频道分配问题，l ( 2 ，1 ) - 标号， 图，r 一路，正三角形网格、正四边形网格、 标号着色数，边跨度，弦图，单位区间 正六边形网格、轮w 名 a b s t r a c t a nl ( 2 ，1 ) m a b e l i n go fag r a p hgi sa na s s i g m n e n tf u n c t i o n ，f r o mt h ev e r t e xs e t , v ( g ) t on o n n e g a t i v e i n t e g e r s ，s a t i s f y i n g ：( 1 ) i f ( u ) 一，( ) i 2 ，i f u v e ( g ) ；( 2 ) ( u ) - ( v ) i l ， i f d ( u ，v ) = 2 t h es e to f a l ll ( 2 ，1 ) q a b e l l i n gi sd e n o t e db yz ( 2 ，1 ) t h el ( 2 ，1 ) 一l a b e l i n g n u m b e ri sd e f i n e da sx ( c ) = r a i n m a x f ( v ) ： y ( g ) ) ，i e ，t h em i n i m u mo fs p a n ( f ) o v e r a l ll ( 2 ，1 ) 4 a b e l i n g so fgt h ed e f i n i t i o no f l ( 2 ，i ) j a b e l l i n ga r o s ef i 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 ro fs t a t i o n sa r eg i v e n ，w eo u g h tt oa s s i g nac h a n n e lt o e 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 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 y t 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 sa p a r te n o u g h la n da n yt w o c l o s e s t a t i o n s m u s tr e c e i v ed i f f e r e n tc h a n n e l s i nt h i st h e s i s ，w ec o n s i d e ra n o t h e rp a r a m e t e ra b o u tt h el a b e l i n g ，t h ee d g es p a n ，d e - n o t e db yf l ( g ) = 哑n m a x l f ( u ) 一，( ”) ji u 口 ( g ) ) ，w h e r e z ( 2 ，1 ) a n dt h em i n i m u m r u n n i n go v e ra 1 1l ( 2 ，1 ) - - l a b e l i n g so fg a tt h es a m et i m e ，w eh a v es o m er e s u l t sa b o u t t h ee d g es p a no fl ( d ，1 ) 一l a b e l i n ga n d5 ( 8 ，t ) 一l a b e l l i n go i ls o m eg r a p h s ，d e n o t e db y 尻( g ) a n d 卢( s ，) ( g ) i ft h e r ei s ar e s t r i c t i o na b o u tt h ei n a x l m u l nl a b e l i n g ，w ec a ng e tt h eo t h e r p a x a m e t e r s ，d e n o t e db y 阢( g ，k ) i nc h a p t e r s2 ，3 ，4 ，5 ，w eg e ts o m er e s u l t so n 阮( g ) o fs o m es p e c i a lg r a p h s ，s u c ha q g ，t ，l m t h et r i a n t g u l a rl a t t i c ea ，t h es q u a r el a t t i c ea ，t h eh e x a g o nl a t t i c ev ， t h ew h e e l ，t h es t r o n gp r o d u c to f ra n dc h o r a lg r a p h s f o rt h eh e x a g o nl a t t i c e ，w h e e l w 名，t h es t r o n gp r o d u c to fr a n dc h o r a lg r a p h s ，w eg i v e 卢( g ， ) a n d 风( g ，h ) ， k e y w o r d s ：c h a n n e la s s i g n m 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 l i n gn u m b e r ， t h ee d g es p a n ，c h o r a lg r a p h ，t h eu n i ti n t e r v a lg r a p h ，r - p a t h ，t h et r i a n g u l a rl a t t i c e ，t h e s q u a r el a t t i c e ，t h eh e x a g o nl a t t i c e ，t h ew h e e lw n i i 东南大学学位论文 独创- 陛声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 二、关于学位论文使用授权的说明 签名：日期： 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查 阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授 权东南大学研究生院办理。 签名：导师签名：日期： 第一章引言 近年来，对于图论中各个方向的研究都得到了极大的发展其中图的着色问题 研究作为图论研究中的一个重要的分支，近年来也受到广泛地关注图的着色问题 从最早的点着色、边着色和面着色发展到现在的圆着色、列表着色、t 一着色等等各 种着色但这些新的定义往往来自于现实中为了描述某个问题而建立的抽象模型， 而如今我们提出的标号着色就是对现实生活中频道分配问题的一种抽象描述 1 1 标号羞色的背景及定义 频道分配问题 1 】( c h a n n e l p 。a d i of r e q u e n c ya s s i g n m e n t ) 是讨论如何最优地给不 同的电台分配有限频道的问题假如在某一个地理区域内有多个电台，每个电台都 要利用无线电波发送自己的信号但是，如果不同的电台使用了相同或相近的频道 时，就可能产生相互干扰，所以各个电台要避免可能产生干扰而使用不同的频道另 外，地理位置也会影响频道的分配如果两个电台相距的足够远，那么即使使用了相 同的频道也不会影响其正常工作但是，如果两个电台的地理位置接近的话，就要保 证使用的频道有一定的差距，而对于地理位置十分接近的电台，仅仅不同的频道是 不够的，还必须使用相差足够远的频道才能保证互不干扰将频道分配给电台，目 标是在保证电台互不干扰的前提下使用最少的频道资源简单地说，频道分配问题 是指给若干电台分配频道，使得可能产生干扰的两个电台所用的频道之差落在允许 的范围内，从而避免干扰；不可能产生干扰的电台可以使用相同的频道事实上，描 述频道分配问题的模型很多，h a a e 1 用图论中t - c o l o r i n g 的概念来描述过频道分配 问题1 9 8 8 年，r o b e r t s 用标号着色的概念也来描述过这个问题，即相隔很近的电 台使用的频道至少相差2 ，相隔较近的电台必须使用不同的频道g r i g g s 和y e h 将 此问题化为图着色问题，且考虑了更一般的情况他们引入了l a ( 2 ，1 ) 一l a b e l l i n g 的概 念为： 定义1 _ 1 1 i2 对于简单图g ( v f ) ，对于任意给定的实数d 0 ，圈的标号着色l d ( 2 ，1 ) 一 l a b e l i n g 是一个非负函数，：v ( g ) _ f o ，o o ) ，满足条件， p ，i y ( u ) 一，扣) l 2 d ，若 刀( g ) i 俐i ，( “) 一，( u ) d ，若d ( “，”) = 2 若，是图g 的一个l a ( 2 ，1 ) 一l a b e l i n g ，我们就称f l a ( 2 ，1 ) ( g ) 每个点在，下 的象称为该点的标号定义i i f ( g ) 1 1 = m ，( u ) ：口v ( g ) ) ，则图g 的标号着色数 】 东南尤学顽士学位论文 2 ( l d ( 2 1 ) l a b e l i n gn u m b e ，1 ) 定义为：a ( g ；d ) = m 川l ，( g ) i ，即对所有的，l ( d ，1 ) ( g ) 取最小因为我们一直尽量使得l ( 2 ，1 ) 一标号的跨度最小，从而0 做为最小的标号 这里图g 中的点代表电台，如果两个电台十分接近，则在g 中代表这两个电台 的点“，u 相邻；如果两个电台比较接近，则d ( u ，”) = 2 在所有的点上指定值，代表 电台使用的频道，上述定义中的( 1 ) ，( 2 ) 就保汪了各电台之间互不干扰，我们的目标 就是在所有满足条件的频道分配中，寻求使用频道资源最少的分配 1 2 图的l ( d ，1 ) - l a b e l i n g 上面的数学模型清楚地描述了频道分配问题的约束和目标，但由于这里的着色 使用了实数的概念，和通常意义下的图的着色( 用整数来给图中的点着色) 有一定的 区别，也给我们的研究带来了麻烦如何把新的标号着色和通常意义下的着色联系起 来呢? g r i g g s 和y e h 很好的解决了这个问题他们在 2 】中给出了下面两个引理； 引理1 21 【2 z ，0 0 ，d o ，k z + ，如果i 一9 k d ，那么l 一一l k d ，其中 一= l z d j d ，= l # d i d ， 引理1 22 f 2 】对任意的实数d ，a ( g ，d ) = 烈( g ，1 ) 这两个引理事实上解决了前面所说的问题对于任意的实数d 0 ，如果函数， 满足约束( 1 ) ，( 2 ) ，取，协) = 【f ( v ) d j dvu y ( g ) ，那么，也满足约束( 1 ) ，( 2 ) ；如果 a ( g ，d ) = i ，其中，厶( 2 ，1 ) ( g ) ，那么存在g 的一个整数值的三l ( 2 ，1 ) 一l a b e l i n g 函 数n 猿是| = d xf f l 因此有下面的定理： 定理1 2 3 2 对- i - g = 意的圈g ，存在一个整数值的工1 ( 2 ，1 ) 一l a b e l i n g 函数，：v ( a ) _ 以j ，易) 使得 i f ( a ) l = a ( g ，1 ) 这样一来，关于图l d ( 2 ，1 ) 一l a b e l i n g 问题的研究就只需考虑整数值的l 1 ( 2 ，1 ) 一l a b e l i n g 问题了为了简便，我们将l ( 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 是一个非负整数函数，：v ( e ) _ + o ，1 ，2 ，3 ，) ，满足以下 的条件， ( 1 ) i ，) 一，( ”) i 2 ，若t w e ( g ) ；( 2 ) i ，( t ) 一，( ) i 1 ，若d ( u ，口) = 2 相应的我们将l l ( 2 ，1 ) ( g ) 记作l ( 2 ，1 ) ( g ) 或l ( 2 ，1 ) 、a ( g ，1 ) 记作a ( g ) 或a 对 于这个问题的研究主要有这些文章t 【2 】1f 3 】1 4 ， 5 】 【6 ， 8 1 9 】 东南大学硕士学位论文 1 3 图标号着色的跨度和边跨度 图的标号着色的概念能够很好的描述频道分配问题，而且标号着色数是对于使 用最少的频道资源很好的描述那么我们将结果推广到更一般的情形l ( d ，1 ) 一标号 和l ( s ，t ) - 标号下面分别给出它们的定义： 定义1 3 1 对于一个给定的图g ，它的l ( d ，1 ) 一标号是指一个非负整数函数，：v ( c ) _ o ，1 ，2 ，3 ，) ，满足条件： ( 1 ) l ，( u ) 一f ( v ) i d ，若 t t v e ( g ) ；( 2 ) l ，( “) 一，( ”) 1 ，若d ( u ， ) = 2 相应的三1 ) 一标号着色数记傲如( 回= 删n m “ ， ) ：口v f c ) ，f 三瀚2 ) f 定义1 3 2 对于一个给定的图g ，它的l ( s ，t ) 一标号( s , t 都是正整数) 是指一个非负整 数函数，：v ( g ) _ o ，1 ，2 ，3 ，) ，满足条件： ( 1 ) j f ( u ) 一，( ) j s ，若乱u e ( g ) ；( 2 ) j f ( u ) 一，( ”) j t ，若d ( u ， ) = 2 相应的工( s ，t ) 一标号着色数记做 ( 。，t ) ( g ) = 蜘n m a x ，( 口) ： 矿( g ) ，三( s ，t ) 关于这两个参数的研究可以参见【l0 ， 1 4 等相应的另外两个参数：l ( d ，1 ) 一标 号的边跨度和l ( s ，t ) 一标号的边跨度是按照下面的方式分别定义的 定义1 3 3 若f l ( d ，1 ) ( g ) ，定义i i f ( x ) l i = m , a x i f ( “) 一，( u ) i ：u v e ( g ) ) ，则图g 正 常l ( d ，1 ) 一标号的边跨度是指风( g ) = 叫ni i f ( g ) l l ，即使所有的f l ( d ，1 ) 相邻顶点 标号之差的最大值达到最小 定义1 3 4 若f l ( s ，t ) ( g ) ，定义| | ，( 。) | | = m 弘 ，( “) 一，( u ) | ：u e ( g ) ) ，则图g 正 常工( s ，t ) 一标号的边跨度是指反s , t ) ( g ) = m ；n | | f ( c ) l l ，即使所有的f 工( s ，t ) 相邻顶 点标号之差的最大值达到最小 事实上，对于d = 2 的情形，在 7 j 中，对于几类特殊的图类已经有了一些结 果下面的几章中，就是在【7 的基础上，我们将对l ( 2 ，1 ) 一标号，l ( d ，1 ) 一标号和 三( s ，t ) 一标号给出更多的几类图的边跨度 1 4 盥论的基本符号与概念 本文中，我们用g = e ) 表示一个图，其中y 是图的顶点集合，e 是边的集 合除非特另说明，否则这里的图都将是简单的无向图，也就是说，两个点之问至多 只有一一条边，所有的边都是无向边如果( ”) e ( g ) ，就称点“，。相邻，边e 与 点”关联点”的度是所有与它关联的边的个数，记做d ( v ) 或d g ( ) 点”的邻 域( ”) 是指所有与其相邻的顶点的集合集合x v ( c ) 称为图g 的独立集，如果 东南大学硕士学 任意的两个顶点饥”x 均不相邻图g 的最大度( g 1 是图中所有的点中度的最 大值： a ( o ) = m a x d ( v ) v v y ( g ) ) ；图g 的最小度d ( g ) 是图中所有的点中度的最 小值：d ( g ) = m i n d ( v ) 帕v ( g ) ) 图g 的顶点数记做n ，边数记做m 图玎= ( v ，) 是图g = ( v ，e ) 的一个子图，如果v v ，e e 且u ”e ，_ “， v 如果同时有e = f u v i u ，口v 7 ，u v e ，那么就称图h 是图g 有点集矿7 的 导出子图，通常记做c v 1 _ 图g = ( u e ) 中的一条路r = ”1 ”2 ，( 这里耽，i = 1 ，2 ，n 是图中的点) ，如 果( “v 1 ) e ( g ) “= 2 ，3 ，n 如果同时有( 吼，v 。) e ( g ) ，就称这是图g 的圈，记 做路和圈的长是指它们所包含的边的个数：r 的长度为n 一1 ，的长度是” 如果图g 中的两个点“，口之间存在一条路，那么就称u 和v 是连通的，两点之 间的距离是指它们之间最短路的长度，记为d ( u ，”) 如果u 和”是不连通的，那么 d ( u ，v ) = 。，如果图g 中任意两点之间是连通的，则g 是连通的接下来我们介绍 几种基本的图类： ( 1 ) 图t 称为树，如果它是连通的且不含有圈的图 ( 2 ) 图称为完全图，如果l 矿( j 厶) = 刊且尬。中的任意两点相邻 ( 3 ) 图g ( x ，y ) 称为二部完全图，这里x ，y 是两个独立集，如果y u x ，v y 或讹x ，y u y 辛u u e ( g ) 那么二部完全图可以推广成k 部完全图 此外对于其它的图，我们将在文章中再一一介绍 第二章关于边跨度的基本结论 根据边跨度的定义，我们很容易得到以下简单的结论： ( 1 ) 对于所有的图g ，风( g ) 墨a d ( g ) ( 2 ) 如果图g 是完全图k 。，则岛( 墨；) = ( ) = ( n 一1 ) d 因为是完全图， 即任意两个顶点是相邻的，标号0 ，d ，( n 一1 ) d 是它最优的标号，使得结论成立 ( 3 ) 如果图g 是路r ，其中n 2 ，则风( r ) = d 对于尻( r ) d 显然，给r 一 个正常的l ( d ，1 ) 一标号：0 ，d ，2 dr ，( n 1 ) d ，该标号的边跨度是d ，结论成立 ( 4 ) 如果图日是图g 的任一子图，则励( h ) & ( g ) 事实上，对于该标号的边跨度风( g ) 都是在最大标号没有限制的前提下给出的， 也就是说最大标号可以是个有限数，也可以是一个无穷大的正整数，从而卢d ( g ) 和 h ( g ) 并没有一个量的关系，对于不同的图类，它们之间的差距可以很大，但是有时 相差又很小，我们可以从以下的结论中发现： 2 1 关于圈的边跨度 路和圈是着色问题所研究的基本图类 单的结论下面我们主要讨论圈的边跨度 如下结论： 对于路，在吲中，我们上面已经有了简 对于l ( 2 ，1 ) 一标号的边跨度我们已经有了 定理2 1 1 令g 是阶为n 的圈，其中n 3 ，则卢( 仍) = 4 ，卢( ) = 3 ，其中n 4 下面就将这个结果推广到三( 吐1 ) 一标号上去，其中d 1 ，d z 显然n = 3 时 c n = k a ，从而岛( c 3 ) = 2 d 那么，在下面的结论中我们仅对n 4 来考虑 定理2 1 2 设g 是阶为的圈，其中3 ，则风( g ) = 2 d ；防( 瓯) = 2 i 屈( g ) = 3 i 风( g ) = d + 1 ，其中n24 ，d 3 且n 5 ，7 ，2 d 一1 证明：令矿( g ) = f 如，u 1 ，一l ，其中咙与”件1 相邻，v o 与一1 相邻，这里 = 0 ，1 ，2 ，n 一1 下面我们分别对n 为偶数和奇数这两种情形来讨论 ( i ) 当= 2 自，其中k 2 首先因为所有的标号都是非负的，从而必然存在一个顶点的标号为0 ，不失一 般性，我们把这个点设为v o 根据l ( d ，i ) 一标号的定义可知， ”1 和”。一t 中至少 有一个顶点的标号至少为d + l ，从而尻( g ) d + 1 ，其中n 4 其次我们给它 如下的一个标号，：把o ，反2 d , ，( k 一1 ) d 分别给如，1 ，吨，一1 标号；然后我们把 5 重韭一塞鲎堕主譬焦迨塞 d _ 1 ，2 d + 1 ，k d + 1 分别给坼。“， 。一2 6 巩标号很容易验证该标号是正常的l ( d ，1 ) 一 标号，并且励( g 。，) 曼d + 1 从而风( g ) = d + 1 对于n = 2 k 其中2 ( i i ) 当n = 2 k 十1 其中k 2 从上面的讨论我们很容易知道，忍( g ) d + 1 ，我们再对d 分情况来讨论： 当d = 1 时，给一个标号为：0 ，1 ，3 ，5 ，7 ，2 k 一1 ，2 k ，2 k 一2 ，：4 ，2 显然这个 标号的边跨度是2 = d + 1 从而卢l ( g ) = 2 = d + 1 当d = 2 时，我们给一个不同于定理2 1 1 的标号为：0 ，2 ，4 ，2 k ，2 ( + 1 ) ，2 k 一1 ，2 k 一3 ，5 ，3 ，显然这是正常的l ( 2 ，1 ) 一标号，并且该标号的边跨度是3 ，从 而当d = 2 时，岛( g ) = 3 = d + 1 当d 3 时，我们令t = 竺掣业，其中n 2 d + 1 若t = 0 时，给的一种标号为：0 ，d ，2 d ，( d + 1 ) d ，( d 一1 ) ( d 十1 ) ，2 ( d + 1 ) ，d + 1 可以验证这是正常的l ( d ，1 ) 标号，并且该标号的边跨度是d + 1 ，从而当n = 2 d + 1 时，尻( 瓯) = d + 1 若扛1 时，给g 的一种标号为：0 ，d ，2 d ，3 d ，( d - i - 1 ) d ，( d + 2 ) d ，( d 一1 ) ( d + 1 ) 十 d ，( d 一2 ) ( d + 1 ) + d ，2 ( 4 + 1 ) 十d ，( d + 1 ) 十d ，d + 1 ，可以验证这是正常的l ( d ，1 ) 一标 号，并且该标号的边跨度是d + 1 ，从而当n = 2 d + 3 时阮( ) = d 十1 若t = 2 时，给的一种标号为：o ，d ，2 d ，3 d ，4 d , ，( d + 1 ) d ，( d 十2 ) d ，( d + 3 ) d ，( d 一 1 ) ( d + 1 ) + 2 d ，( d - 2 ) ( d + 2 ) + 2 d ，( d - 3 ) ( d + 1 ) + 2 d ，2 ( d + 1 ) + 2 d ，( d + 1 ) + 2 d ，( d + 1 ) + d ，d + 1 ， 显然这是正常的l ( d ，1 ) 一标号，并且该标号的边跨度是d + 1 ，从而当n = 2 d + 5 时， 尻( g ) = d 十1 按照上面标号的规律，我们很容易对一般情形n ；2 t 十2 d + 1 的g 标号为： 0 ，d ，2 d ，3 d ，4 d ，t d ，( t + 1 ) d ，0 + 2 ) d ，( d + t + 1 ) d ，( d 1 ) ( d + 1 ) + t d ，2 ( d + 1 ) + t d ，( d + 1 ) + t d ，( d + 1 ) + ( 亡一1 ) d ，( d + 1 ) + 3 d ，( d + 1 ) + 2 d ，僻+ 1 ) + d ，d 十1 ，可以验证这是正常的 工( 吐1 ) 一标号，并且该标号的边跨度是d + 1 ，从而当n = 2 t + 2 d + 1 时，风( g ) = d + 1 在上面的定理中，我们还遗留下来一个小问题，即对于g ，岛，q d 叱其中 d23 ，我们还不能给出确切的边跨度，但是下面的定理可以给出它们的上下界 定理2 1 3 对于魄，c 7 ， d 1 ，其中d 3 ，则d + 1s 卢d ( q 抖1 ) sm l n ；d 1 ，d + 2 + 【学j ，其中2 s d 1 证明t 我们给晚k + l 一个如下的标号g ：分别将v o ，仇，鲰，”t + l 标号为0 ，d ，2 d ，k d ，( + i ) d 与此同时，分别将”。l ，”。2 ，毗+ 2 标号为d j ，f l 川，( k 一；) 司显然该标号 9 是正常的l ( d ，1 ) 一标号，并且该标号的边跨度是f ；d 另一方面，我们给出另外一 东南= ：学顽士学位论丈 种标号为： d i + l 学h 学j 十k ，2 孚j _ 2 ，学，2 d d ) o 、川譬j + 2 ，【掣2 川学j - 2 ，州字h ，2 d 沁) 当( d k ) ；o ( m o d2 ) 时，c 2 k + l 用( + ) 来标号；当( d k ) ； ( r o o d2 ) 时，q 女+ l 用( “) 来标号很容易验证该标号是正常的l ( d ，l 卜标号，并且该标号的边跨度是 d + l a - kj 十2 ，从而d 十1 z d ( c 2 k + 1 ) sr a i n ； d ，d + 2 + l 与盘j ) 注：猜想下界可以精确到d + 2 事实上，对于具体的d ，比如d = 3 时，岛( g ) = 5 ； d = 4 时，反( g ) = 尻( c 7 ) = 6 但是对于一般的情形，还不能给出更精确的下界 下面我们对圈g n 给出一种特殊的标号，使得该标号的边跨度恰好是d + 1 ，其中 n = f 2 d + 1 1 k 定理214 设是阶为n = ( 2 d + 1 ) k 的圈，则岛( g ) = d + l 证明：首先我们给y ( g n ) 中的每个顶点一个新的下标，即y ( 瓯) = o 。t n 。，v 2 d , d i = 1 ，2 ，。 对于每一个i ，在瓯上就有2 d + 1 个连续的顶点，于是我们可以用吐0 ，d + 1 ，l ，d + 2 ，2 ，2 d 一1 ，d 一1 ，2 d 来标号，从而我们得到一个标号，显然这种标号是正 常的l ( d ，1 ) 一标号，满足风( g ，) 玉d + l ；另一方面，从上文可以知几( g ) 2d + l ， 从而结论成立 2 2关于树和k 部完全图的边跨度 在介绍树的边跨度之前，我们首先介绍一下宽度优先生成树( b r e a d t hf i r s ts e a r c h ) 的概念，它是按照下面的方式生成的：对于任意一个连通的无向图，把任意给定的 点8 作为根，从s 出发，我们首先访问与8 相邻的顶点，把这些顶点记做x ，然后 再访问甄中所有顶点的邻点( 除去自身) ，我们将这些顶点记做x 2 ，依次类推，按照 上面的方式，我们一直访问下去，直到所有的顶点都被访问完为止，这样按照访问 的顺序就得到了图g 的一种生成树，我们就把这种方法生成的树称为宽度优先生成 树关于树的l ( 2 ，1 ) 一标号的边跨度，在【7 中，我们已经有如下结论： 定理2 2 1 令t 是具有最大度为的树，则f l ( t ) = 舍1 + j 对于这个结论，也只能在有限树的前提下才能成立，假如它是一个无限树，我 们也只能给出它的下界鲁1 + 1 ，至于上界，目前还没有得出我们就在这个基础上 给出有限树的l ( d ，1 ) 一标号的边跨度，以及给出某些特殊无限树的边跨度 东南大学硕士学位沦文8 定理2 2 2 令丁是具有最大度的有限树，则风( t ) = f 导 + d l 证明：令m = f 每1 + d 1 因为是树t 的最大度，从而k 1 是树t 的子图令 v ( k 1 ，) = v o ，v l ，地) 其中v i ，i = 1 ，2 ，是i 的叶子我们可以给它一个标 号，即“o 标号为今1 + d 一1 ，其它的顶点分别标号为：o ，】：鲁 一1 ，f 令1 + 2 d 一 1 ，a + 2 d 一2 ，很容易知道这是k l ，的正常的l ( d ，1 ) 一标号，并且该标号的边跨 度是m ；下面我们证明k 1 ，的边跨度就等于m ，不能比m 更小反证法，假设存在 一种标号它的边跨度小于m ，中间顶点的标号可以设为d 十z ，在假设的前提下肯定 有d + z m ； 当是奇数时，口b = + d 一钔= - t - d 一垒尹= 学+ d 一1 = m ，即o m 这两种情形都与假设矛盾，也就是说忍( 硒，j m ，因此玩( r ) 凡( 并i ) = m 另一方面，我们给树t 如下的标号：我们以”o 作为树的根，它的标号为。忙要充 分大，使得所有的标号都是正整数) ，树t 的其它顶点按照宽度优先生成树的方式来依 次标号当我们访问到标号为y 的顶点”时，根据宽度优先生成树的定义可知，该顶点 的所有的孩子都没有标号，又因为顶点”最多有一1 个未标号的孩子，从而我们可以 用下面集合中的元素给它的孩子标号，即 y - d ，y + d ，y - d i 珂+ d + l ，y - 口+ m ， 显然该集合的元素个数大于我们可以按照上面的方式一直标下去直到所有的顶 点都被访问过，很显然该标号是正常的l ( d ，1 ) 一标号，并且该标号的边跨度是m ，从 而风口) m 因此尻口) = m 证毕 从上面定理的证明过程中，我们不难发现要使虬的边跨度是m ，它的标号只能 是定理中的标号，或者在那个标号的基础上每个顶点的标号都加上同一个正整数 另外我们还注意到这里的树必须是有限树，否则按照上面的方式标号就出现了负整 数，那么是不是所有的无穷树都有岛( t ) f 令 + d 一1 7 下面我们介绍两类无穷树，分别记做研和噩，我们很容易求得这两种树的边跨 度是f 钔+ d 1 孔是无限个k 、，通过重合叶子而有规则的排列起来的树，见下 图，这里a = 6 东南大学硕士学位论文9 图n 将那些重合的叶子依次记为”2 ，啪，在第一个k 1 中，我们给它的标号为 o ，1 ，会1 1 ，f 会 + 2 d 一1 ，十2 d 一2 ，其中v l 的标号为1 ，中心顶点的标号为 f 钔+ d 一1 ；对于第2 个耳l ，i 我们在第1 个标号基础上都加1 ，即给它的标号为 l ，2 ，f 令1 ，湾1 + 2 d ，十2 d 一1 ，其中”2 的标号为2 ，中心顶点的标号为f 拿1 + d 按照这种形式一直标下去，很显然这是正常的l ( d ，1 卜标号，并且该标号的边跨度 为舍 + d 一1 从而卢d m ) = f 垒2 + d 1 乃也是无限个凰，通过某种特殊的方式生成的；第1 个片，的一个叶子是第 2 个k l ，的中心，而第2 个凰的某个叶子又是第3 个确的中心，依次类推 当= 6 时，见下图 图易 我们将这些中心顶点依次记为。2 ，第1 个甄，的标号为0 ，1 ，2 ，f 舍卜 l ，f 会1 + 2 d l ，+ 2 d 一2 ，其中虮的标号为f 每1 + d 一1 ，将其余的标号在第1 个 凰，标号的基础上加d ，为第2 个硒，的标号，即d ，d + 1 ，d + 2 ，令 十d - 1 ，f 令 + 3 d 一1 ，+ 2 d 一2 ，其中 2 的标号为令 + 2 d 一1 ，按照这种方式一直标下去，即 可得到的一个正常的l ( d ，1 ) 一标号，并且该标号的边跨度为令1 + d l ，从而 胁( 噩) = f 兮 + d 一1 我们还可以证明肯定有某类无穷树，比如说正则树，根据上面的讨论可知， 它的边跨度大于鲁 + d 一1 关于无穷树的标号着色，在f 1 6 】中已经给出详尽的结 论，所以关于树的边跨度问题有望给出更进一步的结果下面我们来研究k 一部完 东南大学硕士 l 全图的边跨度 定理22 3 令k = k n l m b ，m 是一个k部完全图，其中n 1 7 1 2 哟n 并 且n 】一n 2 d 一1 贝1 j 声d ( k ) = ? u 2 - k k + ”3 + + ? 妊十( 七一1 ) ( d 一1 ) 一l 证明：令t = f r t l a + n 2 + 7 均+ + 7 1 , + ( k 一1 ) ( d 一1 ) 一1 设v ( k ) = h u u k u u k u k ，其中h u k + 1 ，k 是k 的k 一部集， 并且 u ；= 札1 2 1 ，l k + l = h 2 j ，l k i = r t i 、z = 2 ，3 ，k 于是我们可以给每一个嵋 用连续的整数来标号，使得h 中的最小的标号是0 ，码中的最小标号是一l 的最 大标号加上d 显然这是一个正常的l ( d ，1 ) 一标号，并且该标号的边跨度是t ，从而 风( k ) t 另一方面，令，是正常的l ( d ，1 ) - 标号，我们将要证明& ( k ，) t 假如u u 和k ，使得，( ”) = 0 并且p = ，( u ) = i 1 2 a y , w 址，( u ) 其中i = 1 ，2 ， + 1 ，则 p a a ( k ) = 恤十( 女一1 ) ( d 1 ) 一1 = t + i n l l 2 j t i = 1 如果r s ，则风( k ，) = p t 因此我们假设r = 8 令z 和y 分别是，不在k 上的 最大和最小标号，从而 z y 2 啦 t = 1 并且 ( z 一0 ) + 0 一曾) 2 t + 2 h l 2 j n ，一( d 一1 ) 2 t 1 因此，要么2 0 t 要么p y t ，即岛( 墨，) 2 t 证毕 注：在上面定理证明的过程中对第一个部的顶点等分，这种分法可以使在上述标号 方式下所得标号的边跨度最小事实上，假设 ”z = 舀则k + 。 = n 一。，仍然按照 定理中的方法标号，从而巩中的最大标号为。+ 嘲+ ( 1 ) ( d 一1 ) 一1 ，而v k 十l t = 2 的最大标号为e 啦+ k ( d 一1 ) 一1 这时我们很容易算出该标号的边跨度为y l = i = l kt z 十em + ( k 一1 ) ( d 一1 ) 一1 或抛= e 啦+ ( 一1 ) ( d 1 ) 一。一l ，即该标号的边跨度 为r a i nm a x y t ，搬) ，很显然当。= f 等 时，可以达到最小值 第三章正则网格图的边跨度 3 1正则网格的定义及基本结论 下面我们考虑三种正则网格图，即正三角形网格( t h et r a a g l el a t t i c e ) ，正四边形 网格( t h es q u a r el a t t i c e ) ，正六边网格( t h eh e x a g o nl a t t i c e ) ，它们是在平面胞腔电话网 络( c e l l u l a rp h o n en e t w o r k ) 设计中产生的，对于通讯网络的研究有着重要的作用关 于这种图形的标号着色数已经有了很多的结论，在此我们就不一一介绍了但和本 文研究有关的结论介绍如下：在f 7 1 中，我们已经知道： ( t ) 卢( 。) = 5 ，对于m 兰2 ( 2 ) 卢( 4 ) = f l ( a 。，。) = 3 ，对于n m 1 对于上面提到的符号下面都有介绍另外，对于正六边形网格关于此参数的研 究目前还没有任何结果我们不但求解了l ( 2 ，1 ) 一标号的边跨度，还求出了l ( d ，1 ) 一 标号和l ( s ，t ) 一标号下的边跨度。 3 2正三角形网格的边跨度 我们定义欧氏平面上的两个向量l = ( 1 ，0 ) 和e 2 = ( 1 2 ，v g 2 ) 那么三角形 网格( t h et r i a n g u l a rl a t t i c e ) g 是指y ( ) = 掂1 + j e 2 = z 1 ，z ) ，e ( c ) = ( u ： ， 扩( ) ，d e 口) = 1 事实上正三角形网格在信息传播中起到非常重要的作用这是因 为如果每一个发射台的覆盖面是一个以r 为半径的圆盘，那么我们可以把发射中一5 - 分布在正三角形网格的顶点上，使得相邻发射地的距离是r 5 ，这样就有尽可能小的 发射密度由三角形网格的定义可以知道它是一无限图，那么我们定义它的有限子图 。，它是有顶点( ( i ，j ) ：一m i 0 ，0 j m ；o i + j 曼m ，m 2 导出的，参见图1 ： 图1 定理3 2 1m ( ) = 2 d + 1 证明z 因为v ( a ) = 话l + 拈2 ：i ，j z ) ，则为了方便我们可以用( i ，j ) 来代替顶 1 1 奎是生学生主竽焦堡寒 l ： 点一z 】+ ，e2 p 面我们给它一个标号，即令，矿( j z 其中，( ? ) = ( d 十1 ) i + 由，我们只需验证该标号是正常的l ( d 1 ) 一标号即可，那么对于任意的 两个顶点： ( z 1 j 1 ) 、( i 2 ，j 2 ) 矿( ) ( i ) 如果d ( ( z 12 2 ) ，( 2 2 ，托) ) = 1 时，即在中两个顶点的距离为l ，则或者il = i 2 ， l j l j 2 l = 1 ；或者n = ，2 ，h i 。l = l ；或者( i 1 一址) ( j 1 一如) = 一l _ 对于上面的每一种 情形，都很容易验证j f ( i i ，j 1 ) 一f ( i 2 ，2 ) i d ( i