（运筹学与控制论专业论文）网格图的多重l21标号.pdf

摘要 图的l ( 2 ，1 ) 一标号是从频道分配问题中概括出来的一类图的着色问题，近些年来 l ( 2 ，1 ) 一标号问题的研究取得了很多成果，l ( 2 ，1 ) 标号概念也被大大推广了我们考 虑如下复杂一些的频道分配模型，进而引出我们的问题设n 和d 是正整数，如果某个 区域有多个电台，每个电台要发射n 个不同的电波信号，为避免干扰，任意两个位置非 常接近的信号至少要相距d 个频率，而位置比较接近的信号只要频率不同就可以了用 标号的思想来考虑这个问题，就可以把它看成是图的n 重l ( d ，1 ) 标号定义任意两个 整数集合i 和j 之间的距离为d ( i ，j ) = m i n l i j i ：i ，j j ) 对于一个给定的图 g ，它的n 重l ( d ，1 ) 一标号是一个非负整数集函数，：v ( a ) 一非负整数集的所有n 子集 合的集合，厂满足两个条件： ( 1 ) d ( ，( 扎) ，厂( u ) ) d ，若u u e ( g ) ； ( 2 ) d ( 厂( “) ，( 秒) ) 1 ，若u 与v 的距离为2 图g 的佗重l ( d ，1 ) 一标号数定义为垤l ( g ) = m i n m a x f ( v 1 ) uf ( v 2 ) l j u ( v 。) ， 其中，取遍图g 的所有礼重l ( d ，1 ) 一标号用同样的正多边形去覆盖平面，仅仅正三角 形，正六边形，正方形三种网格图是可行的，在第二部分，我们研究三种网格图：正三角 形网格，正六边形网格及多维方形网格的n 重l ( d 1 ) 一标号和礼重l ( d ，1 ) 一圆标号通 过分析论证和对网格图的顶点循环地分配标号集，我们得到了扎重l ( d ，1 ) 一标号数和扎 重l ( d ，1 ) 一圆标号数的取值上下界，特别当d = 2 时，我们完全确定出三种网格的1 2 重 l ( d ，1 ) 一标号数和扎重l ( d ，1 ) 一圆标号数 在本文第三部分，我们进一步研究了图g 的n 重d 分离l ( d ，1 ) 一标号用k 。表示 n 个点的完全图，图g 的扎重d 一分离l ( d ，1 ) 一标号就是复合图g 】的l ( d ，1 ) 一标号， 而图g 的n 重l ( d ，1 ) 标号等价于g 蟛】的l ( d ，1 ) 一标号当d = 2 时，我们得到了正 三角形网格的r e 重2 一分离l ( 2 ，1 ) 一标号数取值范围，并且完全确定了正六边形网格与多 维方形网格的的n 重2 分离l ( 2 ，1 ) 一标号数 关键词：频道分配问题，网格图，复合图，2 重l ( d ，1 ) 一标号，扎重l ( d ，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 hw a sm o t i v a t e db yas p c c i a lk i n do fc h a n n e la s s i g n m e n t p r o b l e m t h e r eh a v eb c c nm a n yr e s e a r c hr e s u l t so nl ( 2 ，1 ) 一l a b e l i n go fg r a p h si nr e c e n t l y y e a r s ，a n dt h ec o n c e p to fl ( 2 ，1 ) 一l a b e l i n gh a sb e e ng r e a t l ye x t e n d e d w cc o n s i d e rt h e c h a n n e la s s i g n m e n tm o d e la sf o l l o w sw h i c hl e a d st oo u rq u e s t i o n s s u p p o s ena n dda r e p o s i t i v ei n t e g e r s ，i ft h e r ea r cm a n yb r o a d c a s t i n gs t a t i o n si na na r e a ，e a c hs t a t i o nn c e d t ou s end i f f e r e n tc h a n n e l s t oa v o i di n t e r f e r e ，t w oc h a n n e l so ft w op r e t t yc l o s es t a t i o n s n e e dt ob ea tl e a s tda p a r t ，a n dt w oc h a n n e l so ft w oc l o s es t a t i o n ss h o u l db ed i f f e r e n t t h i sp r o b l e mc a nb cf o r m u l a t e dg u sn f o l dl ( d ，1 ) 一l a b e l i n go fag r a p h d e f i n et h ed i s t a n c e b e t w e e nt w oa r b i t r a r yi n t e g e rs e t sia n dja s ：d ( i ，j ) = m i n i j i ：i i ，j j 】t h e n - f o l dl ( d ，1 ) 一l a b e l i n go fag r a p hgi saf u n c t i o nff r o mv ( a ) t ot h es e tc o n s i s t i n go fa l l n s u b s e t so ft h es e to fn o n n e g a t i v ei n t e g e r ss a t i s f y i n gt h ef o l l o w i n gt w oc o n d i t i o n s ： ( 1 ) d ( ，( u ) ，( 口) ) d ，i fu v e ( g ) ； ( 2 ) d ( ，( 钍) ，厂( u ) ) 1 ，i ft h ed i s t a n c eb e t w e e nua n dvi s 2 t h en f o l dl ( d ，1 ) 一l a b e l i n gn u m b e ro fg r a p hgi sd e f i n e da s 入z 1 ( g ) = m i n im a x f ( v 1 ) u f ( v 2 ) u u f ( v 。) ，w h e r ef i st a k e no v e ra l ln f o l dl ( d ，1 ) 一l a b e l i n g so fg i fw ew a n tt oc o v e r t h ep l a n ew i t hr e g u l a rp o l y g o n s ，o n l yr e g u l a rt r i a n g l e ，r e g u l a rh e x a g o n ，a n dm u l t i d i m e n s i o n a ls q u a r el a t t i c ea r cp o s s i b l e i nc h a p t e rt w o ，w ei n v e s t i g a t et h en f o l dl ( d ，1 ) 一l a b e l i n g a n dn f o l dl ( d ，1 ) 一c i r c u l a rl a b e l i n go ft h et h r e el a t t i c c 溜w eo b t a i nt h eu p p e ra n dl o w e r b o u n d sf o rt h en f o l dl ( d ，1 ) 一l a b e l i n gn u m b e ra n dn f o l dl ( d ，1 ) 一c i r c u l a rl a b e l i n gn u m b e r b yc i r c u l a r l ya s s i g n i n gl a b e ls e t st ov e r t i c e s w h e nd = 2 ，w ec o m p l e t e l yd e t e r m i n et h e 扎一f o l dl ( d ，1 ) 一l a b e l i n gn u m b e r sa n dn f o l dl ( d ，1 ) 一c i r c u l a rl a b e l i n gn u m b c r so ft h et h r e e l a t t i c e s i nc h a p t e rt h r e e ，w eg of u r t h e rt oi n v e s t i g a t et h e7 一f o l d d - s e p a r a t e dl ( d ，11 一l a b e l i n g o fag r a p h d e n o t et h ec o m p l e t eg r a p ho nnv e r t i c e sb y a nn f o l dd - s e p a r a t e d l ( d ，1 ) l a b e l i n go fg i si n d e e da nl ( d ，1 ) 一l a b e l i n go ft h ec o m p o s i t i o ng r a p hg 【】，a n da n 几一f o l dl ( d ，1 ) 一l a b e l i n go fgi se q u i v a l e n tt oa nl ( d ，1 ) l a b e l i n go ft h ec o m p o s i t i o ng r a p h g k i w h e nd = 2 ，w eo b t a i nt h er a n g eo fn f o l d2 - s e p a r a t e dl ( 2 ，1 ) 一l a b e l i n gn u m b e r o fr e g u l a rt r i a n g l e ，a n dw ec o m p l e t e l yd e t e r m i n et h en - f o l d2 一s e p a r a t e dl ( 2 ，1 ) 一l a b e l i n g n u m b e r so fr e g u l a rh e x a g o na n dm u l t i d i m e n s i o n a ls q u a r el a t t i c e k e y w o r d ：c h a n n e la s s i g n m e n tp r o b l e m ，l a t t i c e ，c o m p o s i t i o ng r a p h ，n f o l dl ( d ，1 ) 一l a b e l i n g ， n f o l dc i r c u l a rl ( d ，1 ) 一l a b e l i n g 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的 材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意 研究生签名域 嗍碑冲7 目 东南大学学位论文使用授权声明 东南大学，中国科学技术信息研究所，国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印，缩印或其他复制手段保存论文本人电子文档的内容和 纸质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅可以公布 ( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办 理 研究生签名：驻 摊各貅坳嗍碑z 月7 7 目 第一章引言 图的着色是图论研究中的一个重要课题，它所涉及的范围十分广泛点着色，边着 色，圆着色等等都属于它的主要内容这些不同的着色概念往往来自于现实世界中为描 述不同问题而建立的抽象模型距离二标号问题最初来自于上世纪九十年代为研究频道 分配问题而建立的数学模型，它实际上是图的顶点着色的一个推广最近十几年来，图的 距离二标号研究已经有了很多结果具体见综述 1 】 1 1 距离二标号的定义和背景 图的l ( 2 ，1 ) 一标号的概念最早来自于频道分配问题 2 】( r a d 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 ) 的研究假设在某一地区有多个电台，每个电台都要利用无线电波发送自己的 信号如果不同的电台使用了频率相同或相近的频道，就可能产生信号干扰，如果两个电 台相距足够远，即使使用了相同频率的频道也不会影响其正常工作而对于地理位置接 近的电台，只要保证使用的频道的频率有一定的相差将频道分配给电台，目标是在保证 电台互不干扰的前提下使用最少的频道资源 1 9 9 2 年，j r g r i g g s 和r k y e h 在论文【3 】中研究了该问题，他f r i l l 入了l ( 2 ，1 ) 一标 号的概念： 定义1 1 1 对于一个给定的图g ，是定义在v ( a ) 上的非负整数函数，如果，满足条 件； ( 1 ) i 厂( u ) 一，( u ) i 2 ，若札u e ( g ) ； ( 2 ) i f ( u ) 一厂( u ) i 1 ，若d ( u ，u ) = 2 则称，是图g 的l ( 2 ，1 ) 一l a b e l i n g 仁( 2 ，1 ) 一标号，定义入2 ，1 ( g ) = m i n ym a x f ( v ) ：v y ( g ) ，称为图g 的l ( 2 ，1 ) 一标号数 1 9 9 8 年，j v a nd e nh e u v e l ，r a l e e s e 和m a s h e p h e r d 在发表的论文 4 】中提出了 圆标号的概念， 定义1 1 2 设m 是一个实数，用s ( m ) 表示周长为m 的圆，圆上的点用【0 ，m ) 中的实 数表示圆上的两点z ，y 【0 ，仇) 的在s ( m ) 上的圆距离定义为：i z 一可i 。= r a i n i x 一 ! ，l ，m i 。一可i 定义1 1 3 考虑简单图g ( k e ) ，对于给定的正整数m 0 ，图g 的m l ( 2 ，1 ) - 圆标号 是一个非负函数f ：v ( a ) 一 o ，1 ，m 一1 ) ，满足条件： 1 东南大学硕士学位论文第一章引言 2 ( 1 ) l f ( u ) 一f ( v ) l m 2 ，若u e ( g ) ； ( 2 ) l ，( u ) 一f ( v ) l m 1 ，若d ( u ，v ) = 2 定义图g 的l ( 2 ，1 ) 一圆标号数0 2 ，1 ( g ) = m i n f m l f 为g 的m l ( 2 ，1 ) 一圆标号) 类似的又有了图g 的l ( 3 ，七) 一标号与m z ( j ，七) 圆标号的概念，其相应标号数记 为：a j ，七( g ) 与，知( g ) 关于圆标号还有 5 】，f 6 】等文章做了进一步研究 图g 的l ( 3 ，七) 一标号数与l ( 3 ，七) 一圆标号数有如下的关系： 定理1 1 1 俐对于任意的图g 及两个正整数j 和k ，歹k ，则：a j ，南( g ) + 1 乃k ( g ) ，七( g ) + j 1 2 图的佗重l ( d ，1 ) 一标号 上一节我们介绍了标号问题的产生及基本概念近些年来对l ( 2 ，1 ) 一标号问题的研 究取得了很多成果，研究图类包扩树，网格图，超方体等等，参见 7 【1 3 】乘积图方面的 研究参见【1 4 - 1 7 】本篇文章主要讨论了网格图的n 重l ( 2 ，1 ) 一标号，它实际上是一种复 合图的l ( 2 ，1 ) - 标号我们就从复合图的概念讲起 定义1 2 1 图g 具有顶点集v = v x ，v 2 ，u 。) ，图凰有? z i 个顶点，1 i 仇，1 j m 图g 和h 1 ，凰，的复合图g h x ，吼，如】定义为：由日1 ，凰， 分别代替g 中的点y l ，u 2 ，u r n ，且满足：若图g 中点v i 和相邻，那么h i 中的每 个点都与马中的每个点相邻 注解：当日l = 1 - 1 2 = = h m = h 时，复合图g i n l ，h 2 ，】可以简记为 g h i 用k ；表示n 个点的完全图，在本文中我们主要讨论g k 三 与g k 。】 下面我们再来考虑n 重l ( d ，1 ) 一标号考虑这样的频道分配问题假设1 1 和d 是正 整数，如果某个区域有多个电台，每个电台要发射n 个不同的电波信号，为避免干扰，任 意两个位置非常接近的信号至少要相距d 个频率，而位置比较接近的信号只要频率不同 就可以了类似的，用标号的思想来考虑这个问题，就可以把它看成是图的t t 重l ( d ，1 ) 一 标号为了研究方便，首先我们要定义整数集合间的距离 定义1 2 2 对于任意两个整数集合，和j ，它们之间的距离定义为d ( i ，j ) = m i n l i - j l ： i ，j j 我们给出图g 的佗重l ( d ，1 ) 一标号概念： 东南大学硕士学位论文第一章引言3 定义1 2 3 对于一个给定的图g ，它的1 7 , 重l ( d ，1 ) 标号是一个非负整数集函数，： y ( c ) _ 非负整数集的所有礼子集合的集合满足条件： ( 1 ) d ( ，( u ) ，( u ) ) d ，若u u e ( g ) ； ( 2 ) d ( 厂( 乱) ，( 秒) ) 1 ，若乱与u 的距离为2 定义垤l ( g ) = m i n im a x f ( v 1 ) uf ( v 2 ) u uf ( v 。) 根据n 重l ( d ，1 ) 一标号的定义，不同顶点间的标号要满足l ( d ，1 ) 标号的性质，并 且同一点的n 个标号互不相同这恰恰与g 蜒 的l ( d ，1 ) 标号等价即有崦。( g ) = a d l l ( g 【蟛】) 由于本文需要，我们还要引入礼重l ( d ，1 ) 一圆标号的概念，首先要定义整数集合间 的圆距离： 定义1 2 4 设m 是正整数，集合j f ，j 是 o ，1 ，m 1 ) 的两个子集合，在圆s ( m ) 上 j ，j 之间的圆距离定义为d m ( ，j ) = m i n i j l m ：i ，j ， 接着我们给出扎重l ( d ，1 ) 圆标号的定义： 定义1 2 5 对于一个给定的图g ，它的n 重m l ( d ，1 ) 圆标号是一个非负整数集函数 ，：v ( c ) _ o ，1 ，m 一1 的所有礼子集合的集合满足条件： ( 1 ) ( ，( u ) ，厂( 可) ) d ，若u e ( g ) ； ( 2 ) d m ( ，( u ) ，厂( ) ) 1 ，若“与u 的距离为2 定义仃呈l ( g ) = m i n i m l f 为g 的n 重m l ( d ，1 ) 一圆标号) 显然有盯z l ( g ) = o d 1 ( g 蜒】) 为研究g 【】的l ( d ，1 ) 一标号，我们引入分离集的概念： 定义1 2 6 设s z + ，d z + ，如果比，y s 都有i z y l d ，则称s 是d 一分离的 定义1 2 7 设，是图g 的一个几重l ( d ，1 ) 一标号，且满足对于v v y ( g ) ，( u ) 是d 分离的，则称f 是图g 的一个n 重d 一分离l ( d ，1 ) - 标号，相应标号数记为a 勰( g ) 定义1 2 8 设，是图g 的一个n 重仇一l ( d ，1 ) 一圆标号，且满足对于v 秒y ( g ) ，f ( v ) 是d 分离的，则称，是图g 的一个扎重d 分离m - l ( d ，1 ) 一圆标号，相应标号数记为 哟( g ) 容易看出a 勰( g ) = a d ，1 ( g 【 ) 东南大学硕士学位论文 1 3 关于标号问题已有的结果 第一章引言 4 经过近些年的研究，标号问题已有了很多结果在佗重l ( d ，1 ) 一标号方面，已有下列 关于路，圈，树的结果： 定理1 3 1 s 当r 为一个具有m 个顶点的路，a ( p 2 【蟛】) = 2 n ；a ( p 3 【k ：】) = a ( 4 蟛】) = 3 n ；a ( p m 【蟛】) = 3 n + 1 ，当m 5 定理1 3 2p s i 当g 为圈时，a ( g k 蜒 ) = 3 n + 1 ，k 1 ；入( c 4 蜂】) = 4 n ；a ( c 5 蛭】) = 5 礼一1 ；a ( g 蟛】) = 4 n l ；入( g 【蟛】) = 8 ；当圈g 长度足够大时入( c 【蟛 ) = 3 n + 1 当d = 2 时，很自然可以得到下面的定理： 定理1 3 3p s 当g 为树时，g 蟛 的l ( 2 ，1 ) 一标号数为( a + 1 ) n 或( a + 1 ) n + 1 定理1 3 4 l s 对于任意一个最大度为a 的树，满足( a + 1 ) n + d 一2 a 1 ( 丁) m i n i ( a + 1 ) n + 2 d 一3 ，2 a n + d 一2 】1 在网格图方面，往往研究正方形，正三角形，正六边形三种网格图这是由于用同样 的正多边形去覆盖平面，仅仅上述三种图形是可行的因为用同样的正n 边形覆盖平面 后，形成的图中顶点的度：a = 丽3 1 6 0 丽= 2 + 刍，只有当n = 3 ，4 ，6 时，才是一个整数 网格图在计算机网络与通信中有很多实际应用我们在本文中用r 3 ，r a ，r 6 分别表示正三 角形，正方形，正六边形三种网格图t c a l a m o n c r i 与r p e t r c 爆c h i 研究了三种网格图的 l ( d ，1 ) 标号【1 9 】，其中0 d 2 ，戴本球在其论文中作了推广有下述结论： 定理1 3 5 2 0 a d ，1 ( f 6 ) = 入d ，1 ( f 4 ) = 入d ，1 ( r 3 ) = 1 ，2 ： 1 ，2 ； 1 ，2 ； 而h e u v c l ，l c e s e 和s h c p h c r d 在【4 】中得出了f 3 的l ( j ，) 一圆标号数 | l 一 f i = 一 若若 若若若 搿m 8 川 0 3 4 | l i i 一 d d d若若若 4 6 十 + d 1 d 2 1 2 ，、li、 东南大学硕士学位论文第一章引言5 定理1 3 6 厚j 对于任意两个正整数j 和k 且j k ，则： 御s ，= 3 j + 3 k , 4 ：o 篡果j 娑 2 k , 2 岛， 1 4 本文的主要工作 本文主要研究的是正三角形，正六边形，多维方形三种网格的 重l ( d ，1 ) 标号，n 重l ( 2 ，1 ) 一标号，以及凡重2 一分离l ( 2 ，1 ) 标号多维方形网格是二维正方形网格在高 维空间的推广，本文中我们用r 口表示 在第二章中，我们先研究正三角形，正六边形，多维方形三种网格的佗重l ( d ，1 ) 标 号结合已知结论和给出相应标号函数，从而得到扎重l ( d ，1 ) 标号数取值范围并讨论 然后再令d = 2 研究三种网格的n 重l ( 2 ，1 ) 一标号，我们完全确定出三种网格的n 重 l ( 2 ，1 ) 一标号数本章中主要结果如下： 口呈1 ( r 3 ) = a 呈1 ( r 3 ) + 1 = 7 n + 4 ，其中礼3 ； 入1 ( r 6 ) = 4 n 十l ，其中n z + ； 遐1 ( r d ) = ( 2 p + 1 ) n - t - l ，其中n ，p z + ，p 是多维方形的维数 在第三章中，我们研究正三角形，正六边形，多维方形三种网格的n 重2 一分离l ( 2 ，1 ) 一 标号得到的主要结果如下： 8 n 入7 2 “() + ，其中n + ； a 霸( 6 ) , 1 = f 3 ，其8 n 中n 2 + ； zf 5 n z a 纽( r 口) = 2 ( p + 1 ) n ，其中n ，p z + ，p 是多维方形的维数 第二章三种网格的仡重l ( d ，1 ) - 标号 首先给出本章及下一章要经常用到的定义： 设m 是正整数，我们将一个圆做m 等分，用0 ，l ，m 一1 标记等分点，如下图 o 定义2 0 1 设a ，b o ，1 ，m 一1 ) nz ，我们用 a 6 。，表示圆上沿j 顿时针方向起始于 a ，终于b 的标号集合 定义2 0 2 【a ，6 】m + k = 【a + km o dm ，b + 七m o dm 。 注意：在本章中出现的所有标号应看作m o dm 后的值 2 1 正三角形网格的佗重l ( d ，1 ) 一标号 首先为三角形网格建立坐标系，定义二维欧氏空间中的向量e 1 = ( 1 ，o ) ，e 2 = ( ；，譬) ， 则三角形网格图r 3 表示为：v ( g ) = i q + j e 2 ：i ，歹z ) ，e ( g ) = u v ：u ，u y ( g ) ，d e ( u ，秽) = 1 ) ，d e 表示殴氏距离顶点i e l + j e 2 坐标记为( i ，) ，则建立坐标系后 的三角形网格如下图： 6 东南大学硕士学位论文第二章三种网格的n 重l ( a ，1 ) 标号7 我们注意到定理1 1 1 中的结论，对于任意图g ，如果d k 则a d ，k ( g ) + l o d ，k ( c ) 入d ，k ( c ) + d 因为1 ( g ) = 入d ，l ( g 【蟛 ) 且口z l ( g ) = ( 7 d 1 ( g k 三】) 我们立刻得 到a 爱l ( g ) + 1 0 - 。n ，l ( g ) a z l ( g ) + d 在图g 的一个n 重m l ( d ，七) 一圆标号f 中，如果g 的每个顶点标圆s ( m ) 上1 1 个 连续的整数标号，那么就称f 是一个n 重连续i n l ( d ，七) 一圆标号使图g 具有礼重连续 m l ( d ，七) 一圆标号的最小的m ，称为图g 的n 重连续m l ( d ，七) 一圆标号数，记作c o r 鼬n ( g ) 显然对任意图g 有：屹七( g ) c o 甜n ( g ) 令f 是图g 的一个佗重连续m l ( d ，后) 一圆标号如果对g 的一个顶点u ，y ( u ) = t ，t + 佗一1 m ，则令厂7 ( 札) = t ，我们就得到图g 的一个m l ( d + 礼一1 ，忌+ n 一1 ) 一圆 标号反之我们能够从图g 的一个m l ( d + n 一1 ，k + 几一1 ) 圆标号得到一个礼重连 续m l ( d ，七) 一圆标号因此，对任意正整数d ，k ，n ，c 略k ( g ) = 盯d + n - 1 ，k + n - l ( g ) 由定理 1 3 6 ，我们得到下面的定理 定理2 1 1 设d 和扎是正整数，则： 盯孑。c r s ，c 仃z 。c r s ，= 莩三，二二三二 3 ，如果竹d 一1 ， 如果d 一1 n 2 d 一2 ， 4 ，如果佗2 d 一2 定理2 1 2 设d 和佗是正整数，则略l ( r 3 ) 7 n + 2 d 一2 证明：令f 是r 3 的一个n 重m - l ( d ，1 ) 一圆标号我们将证明m 7 n + 2 d 一2 令u 是 r 3 的任意一个顶点，我们定义，( u ) 的闭包如下：页面= h 士i ：其中h ，( u ) 且i = 0 ，1 ，d 一1 ) ，这里“+ ”与。一”要模m 那么页可中的所有标号不能在i l 的邻点上出 现很显然页可是圆s ( m ) 上一些互不相交的闭区间 a o ，b o m ，【a 1 ，b l 】m ，【a p 一1 ，b p 一】。 东南大学硕士学位论文第二章三种网格的n 重l ( a ，1 ) 标号8 的并其中l b i ，+ 1 】m i 3 ，i = 0 ，1 ，p 一1 ，下标里的“+ ”要模p 很明显，对于每个 i ，在k ，饥】。，( u ) 中至少有2 d 一2 个标号所以m 7 n + 2 d 一2 定理得证 我们立刻可得下面的推论： 推论2 1 3 设n 是任意的正整数，我们有o r n l 1 ( r 3 ) = h 1 ( r 3 ) + 1 = 7 n 推论2 1 4 设d 2 且n = d 一1 是整数，则盯呈1 ( r 3 ) = 7 n + 2 d 一2 = 9 n 因此，在某些情况下定理2 1 2 中屹1 ( r 3 ) 的下界是最好的实际上，推论2 1 4 是 在d 2 的情况下定理2 1 2 中略l ( r 3 ) 达到下界的唯一情况，我们有下面的定理： 定理2 1 5 设d 和佗是正整数，如果d 2 且n d 一1 ，则盯三】( f 3 ) 7 n + 2 d 一1 证明：设m = 7 n + 2 d - 2 假设定理不成立，那么设f 是r 3 的一个n 重m l ( d ，1 ) 圆标号 对任意顶点u ，因为m = 7 n + 2 d 一2 并且u 有6 个邻点，我们必有f ( u ) = 【t ，t + n 一1 。， 其中t 是整数且0 t m 一1 因此f 是f 3 的一个n 重连续m 一( d ，1 ) 一圆标号根据定 理2 1 1 ，当d 2 且礼d 一1 时，c 略】( r 3 ) 7 n + 2 d 一2 ，所以我们有m 7 n + 2 d 一2 这与我们前面的假设相矛盾 推论2 1 6 设d 和r l , 是正整数，如果d22 且n d 一1 ，则粗1 ( f 3 ) 7 n + d 一1 如果n 适度的大于d ，则定理2 1 2 中的下界是可以改进的，我们有下面的定理： 定理2 1 7 设d 和佗是正整数，如果d 2 且亿3 d 一4 ，则o - d 1 n ( r 3 ) 7 n + 3 d 一3 证明：设f 是r 3 的一个n 重i n l ( d ，1 ) 一圆标号我们证明m 7 n + 3 d - 3 设u 是r 3 的任 意一个顶点，我们和定理2 1 2 中的证明一致，定义，( 札) 的闭包那么y ( u ) 是圆s ( m ) 上 一些互不相交的闭区间 o o ，6 0 】。，【o l ，b l 】m ， o 【p - 1 ，b p 一1 】m 的并，其中b ，( z i + i 。l 3 ，i = 0 ，l ，p l ，下标里的“+ ”要模p 对于每个i ，在【0 4 ，h i 。，( 廿) 中至少有2 d 一2 个标号， 这些标号都不能出现在u 的邻点上如果p 2 则m 7 n + 4 d 一4 ，已得证，因此我们设 p = 1 这说明对每个顶点1 1 ，f ( u ) 由圆s ( m ) 上连续的标号构成设f ( u ) = n 1 6 】。为方 便我们设f ( u ) = 【a + d l ，b d + 1 】m 如果i ，( u ) i 一礼d 一1 则显然m 7 n + 3 d 一3 因此我们设对于r 3 的任意顶点l l ，l ，( 钆) i n d 一2 设u 是r 3 的顶点，注意到f ( u ) 中所有标号都不能出现在1 1 的邻点上设f ( u ) = 【口，6 m ，则对1 1 的每个邻点v ，f ( v ) 【b + d ，o d 】m 设c 是圆s ( m ) 上的标号，c 被 标在u 的某个邻点v 上且满足对于u 的任意顶点w ， 6 + 1 ，c 一1 。ny ( w ) = 0 显然 i 【6 + 1 ，c l 】m l d 一1 如果l ，( 札) 卜n + | 6 + 1 ，c 一1 】”l i 2 d 一2 ，那么考虑u 和它六个 东南大学硕士学位论文第二章三种网格的n 重l ( a 1 ) 标号 9 邻点我们很容易证明m 7 礼+ 3 d 一3 因此我们设i 厂( u ) i 一几+ i 【6 + l ，c 一1 1 m i 2 d 一3 设w 是u 和v 的一个公共邻点如果存在w 的邻点w 7 使【6 + 1 ，c 一1 】。n f ( w 7 ) 0 ，因为 i ，( 札) l + l ，( u ) i 一2 n + i 6 + l ，c 一1 1 m i 3 d - 5 7 n + 1 证明：反设本断言不成立，则a = 7 n + 1 令m = 7 n + 2 ，由于r 3 中每个顶点有六个邻 点，此六个邻点标号集中无相同标号，所以对r 3 的任意顶点v ，f ( v ) 不是3 + 一限制的 而且，如果f ( v ) 是1 一限制的，则f ( v ) 应为【0 ，n 一1 l m 或【6 n + 2 ，7 n + 1 】m ；如果f ( v ) 是 2 一限制的则厂( ) 应有下列三种形式之一； ( a 1 ) o ，叫m t ) ，( 1 t n 一1 ) ； ( a 2 ) 【6 礼+ 1 ，7 n + 1 。 ) ，( 6 n + 2 ts7 佗) ； ( a 3 ) 【t ，t + n l 】m ，( t 0 ，6 n + 2 ) 因为r 3 的每个顶点有六个邻点，此六个邻点标号集中无相同标号，且至多有两个邻 点的标号集是l 一限制的或是( a 1 ) 或( a 2 ) 形式，我们很清楚的得到下面观察： 东南大学硕士学位论文第二章三种网格的n 重l ( d ，1 ) 标号 1 0 观察1r 3 中一定存在顶点u ，满足，( 札) = 【t ，t + n - 1 m ，其中t 是整数且t 【0 ，n o ，6 n + 2 ) 如果对上述观察中的顶点u ，u 有一个邻点v ，f ( v ) = 【0 ，n 】m t ) ，( 1 t 茎1 2 1 ) 或 者y ( v ) = 【6 n + 1 ，7 n + 1 】m _ 【 ，( 6 n + 2 t 7 佗) ，则由于y ( u ) 是2 一限制的，1 1 必有某 个邻点w 的标号集中含t ，y ( w ) 必是3 + 一限制的，矛盾! 因此我们又得到了下面的观察： 观察2 如果f 3 的顶点乱，f ( u ) = 【t ，t + t i , 一1 】。，其中t 是整数且t 【0 ，n 。 o ，6 n + 2 ) ， 则钍的舀个邻点标号集为【t + p n + 1 ，t + p + 1 ) 佗】m ，p = 1 ，2 ，6 现设顶点1 1 ，f ( u ) = 【t ，t + n 一1 m ，t 【0 ，a 】。 o ，6 n + 2 ) ，1 1 的6 个邻点标号 集为【t + p n + 1 ，t + 0 + 1 ) n 】。，p = 1 ，2 ，6 注意到标号集【t + n + 1 ，t + 2 扎】m 与 ( t + 6 n + 1 ，t + 7 n 】m 中至少有一个是2 限制的，不失一般性设【t + n + 1 ，t + 2 叫。是2 一 限制的令v 是u 的一个顶点且标号集是【t + n + 1 ，t + 2 叫。则由观察2 知，v 的6 个 邻点标号集为 t + q n + 2 ，t + ( g + 1 ) n + 1 】。，口= 2 ，3 ，7 ，因为1 1 与v 有两个公共的邻 点，所以存在p ，g 使t + p n + 1 = t + q n + 2m o dm ，在n 3 条件下这不可能断言1 成立 。下面我们证明入 7 n + 2 假设这不成立，则入= 7 n + 2 ，令m = 7 几+ 3 此时r 3 的任意顶点标号集不是4 + 一限制的对于顶点v ，如果，( u ) 是3 一限制的则f ( v ) 应有下 列六种形式之一： ( b 1 ) 【0 ，m 1 】价u 8 1 ，t 1 】m ，( 0 m l 8 1 2 t x 一2 7 他) ； ( b 2 ) 8 2 ，t 2 mu 【m 2 ，7 n + 2 】。，( 0 8 2 t 2 m 2 2 7 扎) ； ( b 3 ) 【0 ，竹+ 1 】。 s 3 ，t 3 ，( 0 8 3 t 3 1 n ) ； ( b 4 ) 【6 n + 1 ，7 n + 2 】m ( s 4 ，t 4 ，( 6 n + 1 8 4 t 4 1 7 n + 1 ) ； ( b 5 ) f t ，t + 仃】m 岛) ，( t 0 ，6 n + 2 ；t + 1 s 5 t + 礼一1 ) ； ( b 6 ) i t ，t + 叫。 s 6 ，( t 0 ，6 n + 2 ；8 6 = t + 1 或+ 佗一1 ) 令u 是r 3 的一个顶点为方便起见，用f ( ( 札) ) 表示 y ( w ) 1 w ( u ) ) 我们 将经常使用两个相邻顶点有两个公共邻点这一事实，所以若u 和v 是两个相邻顶点则 l f ( ( t ) ) nf ( ( 秒) ) j 2 断言2 对于r 3 的任意顶点让，f ( u ) 不会是形式( b 3 ) 或( b 4 ) 证明：由对称性，我们仅需证明y ( u ) 不会是形式( b 3 ) 假设这不对，对于r 3 的顶点 u ，f ( u ) 有( b 3 ) 的形式令y ( u ) = 【0 ，n + 1 m s 3 ，3 】- ，其中( 0 8 3 t 3 1 n ) 因为 东南大学硕士学位论文第二章三种网格的n 重l ( d 1 ) 一标号1 1 i ( u ) 是3 - 限制的，每个不在 0 ，n + 2 】m 中的标号必在u 的邻点上出现设v 是u 的邻 点，满足n + 3 f ( v ) 因为u 和v 有两个公共的邻点，其中必有一个邻点w ，f ( w ) 是 2 + 限制的注意到r 3 的任意顶点标号集不是4 + 一限制的设h 是 s 3 ，t 3 ，n + 2 中的 一个标号，若h 出现在w 的某邻点标号集上，该标号集必为 6 n + 4 ，7 佗+ 2 】。u 所 以s 3 ，t 3 ，n + 2 中至少有两个标号不可出现在w 的邻点标号集上，于是w 的6 个邻点至 多有6 n 一1 个标号可用，矛盾本断言已证 - 因此在下面的证明中我们总认为对于r 3 的任意顶点u ，f ( u ) 不会是形式( b 3 ) 或 ( b 4 ) 断言3 对于r 3 的任意顶点乱，f ( u ) 不会是形式( b 1 ) 或( b 2 ) 证明：由对称性，我们仅需证明f ( u ) 不会是形式( b 1 ) 假设这不对，对于r 3 的顶点 u ，f ( u ) 有( b 1 ) 的形式我们导出矛盾 令y ( u ) = 0 ，m 1 mu 【8 1 ，1 】。，( 0 m l 8 1 2 t l 一2 7 n ) 假设u 有邻点v ，使 f ( v ) = 【8 2 ，t 2 】，n u m 2 ，7 n + 2 。，其中0 8 2 t 2 m 2 2 7 n 此时1 _ 1 的除去v ( 或v 的除 去u ) 的邻点w ，如果f ( w ) 是形式( b 5 ) ( 【，t + n 】。 s 5 ，t 0 ，6 n + 2 ；t + l 8 5 t + n 一1 ) ， 则u ( 或v ) 的含有s 5 的邻点标号集是4 + 一限制的，矛盾厂( 伽) 只能有形式( b 6 ) 或 【t ，t + n 一1 】m ，t 【0 ，7 n + 2 m 我们考虑两种情况 情况1 s 1 s 2 因为m 1 + 1 和s 1 1 不能出现在u 的邻点上，必有i m 1 +