（运筹学与控制论专业论文）距离图的标号着色问题.pdf

摘要 图g 的标号着色l ( 2 ，1 ) 一l a b e l i n g 是一个从点集v ( v ) 到非负整数集的函数，满足条 件：( 1 ) l f ( u ) 一，( ”) i 2 ，著u e ( a ) ；( 2 ) l f ( u ) 一，( ”) l 1 ，若d ( u ，”) = 2 图g 的 标号着色数定义为： ( g ) = m i n f m a x f ( v ) ：”y ( g ) ) ，即图g 的所有标号着色的最大 标号的最小值图的标号着色问题来自所谓的频道分配模型：不同的电台要使用无线频道 发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置较近 的电台要使用有一定相差的频道将频道分配给电台，目标是在保证电台互不干扰的前提 下使用最少的频道资源 本文主要研究距离图的标号着色问题距离图a ( z ，d ) 是指这样一类图；以整数集z 为点集，v ， z ，u ，口相邻当且仅当l 一 l d ( d 为自然数集的一个子集) d 称 为距离榘 在第二章中，我们对一般的距离图给出了一个统一的上界，我们证明了对任意i d i = k 0 ，图的标号着色( l a ( 2 ，1 ) 一 l a b e l i n g ) 是一个非负函数，：v ( a ) - + 【0 ，) ，满足条件： r 纠l f ( u ) 一，( u ) l 2 d ，若 e e ( g ) j 俜j l ，( u ) 一，( u ) l d ，若d ( u ，”) = 2 若，是图g 的一个l d ( 2 ，1 ) 一l a b e f i n g ，我们就称s l d ( 2 ，1 ) ( g ) 每个点在，下 的象称为该点的标号定义i i f ( a ) l l = m a x f ( v ) ：”y ( g ) ) ，则图g 的标号着色数 ( l a ( 2 ，1 ) 一l a b e l i n gn u m b e r ) 定义为一 ( g ) = m i n ! i i ( c ) 1 1 这里g 中的点代表电台，如果两个电台十分接近，则在g 中代表这两个电台的点u ，u 相邻；如果两个电台比较接近，则d ( u ，”) = 2 在所有的点上指定值，( 代表电台使用的频 道) ，上述定义中的( 1 ) ，( 2 ) 就保证了各电台之间互不干扰我们的目标就是在所有满足条 件的频道分配中，寻求使用频道资源最少的分配 该数学模型清楚地描述了频道分配问题的约束和目标，但由于这里的着色使用了实数 东南大学硬士学位论文2 的概念，给我们的研究带来了麻烦g r i g g s 和y e h 很好的解决了这个问题他们在 2 】中 给出了下面两个引理： 引理1 1 1 【2 】。，y 0 ，d 0 ，南z + ，如果b y l k d ，那么i x 一y i k d ，其中 z 7 = b d j d ，y = 【y d j d 引理1 - 1 2 【2 】对任意的实数d ， ( g ，d ) = 以( g ，1 ) 这两个引理事实上解决了前面所说的问题对于任意的实数d 0 ，如果函数，满 足约束( 1 ) ，( 2 ) ，取，( ) = 【f ( v ) d j dv v ( a ) ，那么，7 也满足约束( 1 ) ，( 2 ) ；如果 ( g ，d ) = l i 川，其中，“( 2 ，1 ) ( g ) ，那么存在g 的一个整数值的l 1 ( 2 ，1 ) 一l a b e l i n g 函数 ，7 ，满足f = d ， 因此有下面的定理： 定理1 1 3 【2 】对于任意的图g ，存在一个整数值的l 1 ( 2 ，1 ) - l a b e l i n g 函数，：v ( c ) _ o ，j ，2 ，) 使得i i f ( g ) l l = ( g ，1 ) 这样一来，关于图岛( 2 ，1 ) 一l a b e l i n g 问题的研究就只需考虑整数值的l l ( 2 ，1 ) 一l a b e l i n g 问题了为了简便，我们将工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 是一个非负函数f ：v ( g ) - - o ，1 ，2 ，3 ，) ，满足条件： ( 1 ) 1 f ( u ) 一，( ) i 2 ，若u e ( g ) ； ( 2 ) i ( u ) 一，( ) i 1 ，若d ( ，口) = 2 相应的我们将l l ( 2 ，1 ) ( g ) 记作l ( 2 ，1 ) ( g ) 或l ( 2 ，1 ) ，a ( g ，1 ) 记作 ( g ) 或a 不失一般 性，我们假定图g 的l ( 2 ，1 ) 一l a b e l i n g 的最小标号是0 一l ( 2 ，1 ) 一l a b e l i n g 表示最大标 号不大于的l ( 2 ，1 ) - l a b e l i n g 更一般的，g r i g g s 和y e h 提出了标号着色，的研究，其中，满足条件：i f ( x ) 一，( ) l m i 若d ( x ，y ) = i 对1si n ，其中是正整数，m 1 o n 2 0 是给定 的数如果n = m l = 1 ，那么，就是普通的点着色如果n = 2 ，m l = d ，m 2 = k ， 则，就是l ( d ，女) 一l a b e l i n g 也就是说，对于一个给定的图g 和正整数d ，图g 的 一个l ( d ，) 一l a b e l i n g 是定义在v ( a ) 上的非负整数函数，满足： l ，( “) 一，( 口) l d 若 d ( “，”) = 1 ；l ，( ) 一，( ) i 若d ( u ，u ) = 2 类似地可定义“m l ( d ，k ) 一l a b e l i n g ”和 “a d ，k ( g ) ”两个概念 在过去的十几年里，图的l ( 2 ，1 ) 一l a b e l i n g 和l ( 1 ，1 ) - l a b e l i n g 得到了广泛地研究 l ( d ，) 一l a b e l i n g 和l ( d ，1 ) 一l a b e l i n g 也有人进行了研究。研究最多的还是l ( 2 ，1 ) 一l a b e l i n g 1 2 关于标号着色现有的一些结论 自标号着色这一概念被提出以来，很多人对一些特殊图类进行了相关的研究，也狸4 t t l 了一些重要的结果首先对一般图，g r i g g s 和y e h 证明了： 定理1 2 1 【2 1 若圜g 的最大度为，则 ( g ) 2 + 2 a 东南大学硕士学位沦文3 gj c h a n g 和d g u o 对这个结果做了改进，得到下面的定理； 定理1 2 2 【3 】若图g 的最大度为a ，则a ( v ) 兰a 2 + g r i g g s 和y e h 对一般图做了如下猜想： 猜想1 2 3 【2 】对任意最大度x 2 的图g ，x ( v ) a 2 对几类特殊的图，这个猜想被证明是正确的。但对于一般的图，此猜想仍未得到证实 此外，一般图的l ( 2 ，1 ) 一l a b e l i n g 问题已被证明是p 一完备问题除此之外，还有如下结 果： 定理1 24 【4 】对任意图g 和任意正整数c ，c a d ( g ) = 。d ，。( g ) 定理1 2 5 【2 】对任意的图g ，x ( c ) 兰a + 1 定理1 2 6 【2 】令r 为包含”个顶点的路则有 ( p 2 ) = 2 ，a ( p 3 ) = 3 ， ( p 4 ) = 3 ， a ( r ) = 4 ，vn 5 定理1 2 7 2 】令g 二为包含n 个顶点的圈则有 ( 0 二) = 4 ，vn 定理1 2 8 【2 】若t 是最大度1 的树，则a ( t ) = + 1 或+ 2 定理1 2 9 【5 】若g 是最大度为的弦图，则a ( g ) s ( a + 3 ) 2 4 这个上界在【6 】里被改进到了【( + 3 ) 2 4 j 一1 此外还有一些关于其它特殊图类的标号着色数的一些结论：h l b o d l a e n d e r 等人证 明了外平面图( o u t e r p l a n a rg r a p h ) 的标号色数 不超过+ 8 ，排列图( p e r m u t a t i o n g r a p h ) 的 不超过5 一2 对于树宽k 的图，他们证明了 k a + 2 k 对于分裂图 ( s p l i tg r a p h ) ，则有 a 1 5 + 2 + 2 的结论m a w h i t t l e s e y 等人在【1o 】中对超立方 体图0 。进行了研究，他们用编码理论的方法证明了n + 3 a ( q 。) 2 n g r i g g s 和y e h 在【2 】中还证明了直径为2 的图的 2 v ，d h e n v e l 等人在 2 8 】中证明了平面图的 a 2 a + 2 5 关于标号着色的算法复杂性，目前为止对平面图、二部图、弦图及分裂图等 几类特殊图，l ( 2 ，1 ) 一标号着色阉题仍然是p 一完备问题关于这些图和其它一些特殊 图的标号色数的结论，可参见文献【7 - 1 4 ，2 8 】 1 3 本文的研究内容 本文主要研究距离图的l ( 2 ，1 ) 一l a b e l i n g 问题假设d ，其中为自然数集，整 数距离图a ( z ，d ) 是指这样一类图：以整数集z 为点集，vu ，口z ， 相邻当且仅当 l u 一”i d 。这类图也可简称为距离图，可简记作g ( d ) ，d 称为距离集g ( d ) 的标号 着色数a ( g ) ) 简记作a ( d ) 在第二章里，我们首先对一般有限的距离集进行讨论，给出 的上、下界然后对一些特殊的k 个元素的d 进行研究，改进了a 的上界第三章主要 研究一些特殊的三元距离集，第四章对二元距离集进行讨论，将其a 的上界改进到8 。最 后，我们大致介绍一下另外两种标号着色的概念；圆标号着色与列表标号着色，并对距离 图进行有关的初步的讨论 至蛊盔堂堡主芏焦丝塞 在本文中，我们用【0 ，翻表示 0 ，1 ，2 ， 数集，z 是整数集。另外需要说明的是， 不是 o ，一。) 。此外，i n i 皇m i = l 口l ，k 一 明的概念和符号参见 1 5 4 ) ，o “表示n 个连续的标号a n 表示自然 若集合d = 仕。) ，表示d = 。) 或卜o ) ，而 n 1 ) ，其中01a 墨k 一1 ，k n 其余未加说 第二章i d l = 忌的距离图的标号色数 本章主要讨论i d i = 的距离图第一节针对一般有限的距离集进行了研究，我们给 出了标号色数的一个形式上统一的上界和下界，证明了2 1 d i + 2 ( d ) sl d 2 i + 3 1 d i 并 由此结论说明g r i g g s 和y e h 的猜想对距离图是成立的第二节里我们着重讨论一些特殊的 距离集，得到了这些距离图的标号色数的上界此外我们还给出了标号色数刚好达到下界 的一些距离图 2 1i d i = k 的一般情况 这一节我们讨论一般的距离集d ，其中d 为有限集，即i d i + 。设g 为d 中所 有元素的公因子，即g = g c d ( d ) ，则距离图a ( z ，d ) 的每个分支和距离图a ( z ，d ) 同构， 其中d ，= d ，：9 d d ) ，所以当我们研究a ( g ( z ，d ) ) 时，可以假设g c d ( d ) = 1 在以后 的讨论中，我们就只考虑g c d ( d ) = 1 的情形 下面引入一些定义及符号： 设d = f a l ，a 2 ，a k ) ，0 口1 0 2 a b g - - b ，则| m ，n n t j 0 ， 使得：t = n o + m b 成立 注：这是数论中一个著名的定理，叫做n o b e n i l l 8 定理具体证明参见 1 7 】 若r ，t 3 是周期的着色，那么我们定义矸甲2 缈始是周期为。”+ 。”的 nm 着色 在第一节里我们证明了 ( 1 ，2 ，自 ) = 2 k + 2 由该结论和命题2 22 ，我们直接可 证明： 推论2 2 4 若d = ( 2 南+ 3 ) 礼l4 - 1 ，( 2 k + 3 ) n 24 - 2 ，( 2 k + 3 ) n k4 - 七 ，其中h i ( 1s tsk ) 是非负整数，k 2 则x ( d ) = 2 k + 2 证明：略 这一节我们将对几种特殊的d = k 的距离图进行讨论 首先我们考察d = 1 ，3 ，5 ，2 k 一1 ) 的情形我们证明了下面的结论： 定理2 2 5 若d = 1 ，3 ，5 ，2 k 一1 ) ，其中自2 则a ( d ) = 2 k + 2 证明：由前面的结论， ( d ) 2 k + 2 显然成立我们只需证明 ( d ) s2 k + 2 这只要给 出图g ( d ) 的一个( 2 - i - 2 ) l ( 2 ，1 ) 一l a b e l i n g 即可为此，我们取 丘+ 3 = 2 k + 2 ，惫，2 k + 1 ，k l ，2 k ，k 一2 ，4 ，南+ 5 ，3 ，k + 4 ，2 ，七+ 3 ，l ，七+ 2 ，0 ，南+ 1 下面我们验证，2 k + 3 是g ( l ，3 ，5 ，2 k 一1 ) ) 的正常的l ( 2 ，1 ) 一l a b e l i n g ： 1 ) 若点。，所着标号相差1 ，即。的标号为i ，y 的标号为i 士1 则可以看出 东南大学硬士学位论文 9 z y i = ：t ：2 ( m o d2 k + 3 ) ，即$ ，y 不相邻。 2 ) 若z ，y 的标号相同，因为同一周期内没有相同的标号，所以i 。一口i o ( m o d2 k + 3 ) ， 。，y 不相邻且d ( z ，y ) 2 t ) ，2 ) 两点保证，2 + 3 是正常的标号着色。定理证毕。 由定理2 2 5 和命题2 2 2 可得到下面的推论： 推论2 2 6 著d = ( 2 女+ 3 ) n 1 土1 ，( 2 k + 3 ) n 2 3 ，( 2 k + 3 ) n k 土( 2 k - 1 ) ) ，其中n i ( 1s i 女) 是非负整数，k 2 则a ( d ) = 2 k + 2 。 证明：略 前面我们考虑了距离集是从1 开始k 个连续整数以及从1 开始个连续奇数的情形 现在我们来研究距离集是不从l 开始的女个连续整数的情形即d = o ，a + 1 ，o + 2 ， o + k 一1 】，n 2 ，k 2 ，a ， 均为整数首先，对一般的a ，k ，我们有下面的结论： 定理2 2 7 当d = o ，a + 1 ，o + 2 ，a + 南一1 ) ，o 2 ，k22 ，a ，k 均为整数时， a m i n 2 ( a + k 一1 ) ，6 i 一2 证明：首先证明 2 ( a + k 一1 ) 为此，令周期的着色 ，2 口+ 2 k 一1 = 0 ，1 ，2 ，2 ( a + 一1 ) 因为a 22 ，容易验证这是图g ( d ) 的一个正常标号所以，a s2 陋+ k 一1 ) 其次证明 曼6 k 一2 由定理2 1 3 中的标号算法知，asi d 2 i + 3 1 d i 当d = o ，口+ l ， a + 2 ，a + k - 1 时，d 2 = 1 ，2 ，k - 1 ，2 a ，2 a + 2 ，2 a + 2 k - 2 ，2 a + l ，2 a + 3 ，。2 a + 2 k 一3 ) ， 1 d 2 1s3 k 一2 所以，a 3 k 一2 + 3 k = 6 k 一2 综合以上两点，定理证毕 由该定理，我们立即得到下面两个推论； 推论2 2 8 若d = ( 2 a + 2 k 一1 ) n l = k a ，( 2 口+ 2 七一1 ) n 2 士+ 1 ) ，( 2 口+ 2 七一1 ) n 土( n + 七一1 ) ) ， 其中m ( 1s i 曼k ) 是非负整数，k 芝2 ，8 2 ，。，女均为正整数则a ( d ) 12 ( a + k 一1 ) 证明：由命题22 2 直接可证 特另4 的，当 l = n 2 = = n = 1 时，a ( + 七，o + 后+ 1 ，a + 2 k 一1 ) ) 墨2 ( a + k 一1 ) 推论2 , 2 9 若d = n i t 士o ，n 2 t 4 - ( 0 + 1 ) ，n k t 4 - ( a + k 一1 ) ) ，其中啦( 1 茎i 墨k ) 是非负整 数，a ，南2 ，a ，k ，t 均为正整数当t 4 ( a + 克) 2 6 ( o + k ) + 1 时， ( d ) 2 a + 2 k 一1 证明：由定理2 2 7 ，周期的标号着色丘。+ 2 t l 相容的另外，不难验证，2 ( 。+ ) = 0 ，l ，2 ， = 0 ，1 ，2 ，2 ( a + k - 1 ) 是如，a + l ，a + k 一1 卜 2 0 + 2 k 一1 也是 ，a + 1 ，a 十k 一1 ) 一相 容的而且亿+ 2 k l 南( ”与丘( 。+ k ) ，2 。+ ? 一1 也是 。，o + 1 ，o + 一1 - 相容的当 t ( 2 a + 2 k 一1 ) ( 2 a + 2 ) 一( 2 a + 2 k 一1 ) 一( 2 a + 2 k ) = 4 ( a + ) 2 6 ( a + k ) + 1 时， = ( 2 。+ 2 k 一1 冲+ ( 2 a + 2 k ) m 都有一组非负整数解( ，m ) 令矗= 船+ 2 一l 船+ 。t = 垒：二苎：垒! ：! ! = ：垂：翌：垒! ：! ! ，则 也是 。，。+ 1 ，。+ 。一1 卜相容的- 由命题2 2 2 ， 是 n i t 士n ，n 2 t 士0 + 1 ) ，n 耵士( a + k 1 ) 卜相容的五的最大标号是2 a + 2 k 一1 ， 东南大学硕士学位论文 1 0 因此当t 4 ( a + ) 2 6 ( 口+ ) + 1 时，a ) 2 a + 2 k 1 定理证毕 特别地，当r o 时，我们有如下结果： 定理2 2 加当d = ，o + 1 ，n + 2 ，a + 后一1 ) ，o 2 ，k 2 ，口，南均为整数时，若 k n ，则a ( d ) = 2 ( a + 一1 ) 证明：首先，由集合d 2 的定义，当n 时，有 d u d 2 = 1 ，2 ，o 一1 ，n ，o + 1 ，。+ k 一1 ，口+ 而，2 ( a + 南一1 ) 由前面d 与d 2 的含义可知，当两点u ， 的差i u 一叫du d 2 时，代表这两点的距离 兰2 那么这两点对应的标号不能相同因此，连续的2 ( a + 一1 ) + 1 个点中任意两点标 号都不能相同( 1s i i 一引sz ( a + k 1 ) ，即i i 一引d u d 2 ) 因为0 也是一个标号， 这意味着， 2 ( a + k 1 ) 下面我们证明 2 ( a + k 一1 ) 为此，我们令周期的着色 ，2 。+ 2 k 一1 = 0 ，1 ，2 ，2 ( a + 一1 ) 因为a 三2 ，容易验证这是图g ( d ) 的一个正常标号所以， 兰2 ( a + 一1 ) 综上， = 2 ( a + 一1 ) 定理证毕 可以看到，当定理2 2 1 0 中的口取2 时，a ( 2 ，3 ，4 ，+ 1 ) = 2 k + 2 ( 2 ) 结合 命题2 2 2 ，有下面的推论： 推论2 2 1 i 当d = ( 2 惫+ 3 ) n l 士2 ，( 2 k + 3 ) n 24 - 3 ，( 2 南+ 3 ) 礼3 士4 ，( 2 k + 3 ) n k 士 + 1 ) ) ， 凫2 ，忍为整数时，a ( d ) ；2 k + 2 证明：略 前面我们证明了：距离集是从1 开始k 个连续的整数或者从1 开始个连续的奇数的 时候， 都达到下界2 k + 2 那么距离集是个连续的整数或k 个连续的奇数的时候，什 么情况下达到2 女+ 2 这个下界呢? 由前面的推论2 2 4 和2 2 ，1 1 ，有： 推论2 2 1 2 当d = o ，a + 1 ，o + 七1 ) ，南2 ，a ，七为正整数时，若d 兰1 ，2 ，七+ 2 ， 南+ 3 ( m o d2 k + 3 ) ，则a ( d ) = 2 k + 2 。 证明：略 类似地，由推论2 2 6 可知z 推论2 21 3 当d = ，n + 2 ，a + 2 k 一2 ) ，2 ，k 为正整数，a 为奇数时，若 a i l ，4 ( m o d2 k + 3 ) ，则 ( d ) = 2 k + 2 证明t 略 前面我们考虑了个连续整数的距离集，下面我们对形如 n ，d + d ，口+ 一1 ) d ) 的 距离集进行研究。首先对一般的o ，d ，有下面的结论： 定理2 2 ，1 4 当d = o ，n + d ，a + ( 一1 ) d ) ，o ，女，d 1 ，a ，d 为正整数时，a ( d ) m i n 2 a + 2 ( k 一1 ) d ，6 k 一2 ) 证明；首先因为o 1 ，易验证周期的着色，2 。+ “女一1 ) d + l = 0 ，1 ，2 ，2 a + 2 一1 ) d 是距离 东南太学硬士学位论文l l 图g ( d ) 的一个l ( 2 ，1 ) 一l a b e l i n g 。所以，a ( d ) 2 a + 2 ( k 一1 ) d 其次证明a 兰6 k 一2 由定理2 13 中的标号算法知，as 【d 2 i + 3 1 d 1 当d = ( 口，+ d ，a + ( k 一1 ) d ) 时，d 2 = d ，2 d ，( 一1 ) d ，2 a ，2 a + 2 d ，2 a + 2 ( k 一1 ) d ，2 a + d ，2 a + 3 d ，2 a + ( 2 k 一3 ) d ，i d 2 fs3 k 一2 所以，a s3 k 一2 + 3 k = 6 k 一2 综合以上两点，定理证毕 由该定理和命题2 2 2 ，我们立即得到下面两个推论： 推论2 2 1 5 若d = ( 2 0 + 2 忙一1 ) d + 1 ) 乱1 士o ，( 2 a + 2 ( 免一1 ) d + 1 ) 钆24 - ( + d ) ，( 2 a + 2 ( k 一1 ) d 十1 ) n k 士( a + ( 一1 ) d ) ) ，其中n i ( 1 isk ) 是非负整数，n ，女，d 2 ，a ，k ，d 均 为正整数。则a ( d ) 茎2 a + 2 ( k 一1 ) d 证明：略 推论2 2 1 6 若d = n i t 士a ，n 2 t 士( n + d ) ，n k t4 - ( a 十( 舟一1 ) d ) ) ，其中m ( 1 i 角) 是 非负整数，a ，k ，d 三2 ，d ，七，t ，d 均为正整数当t 4 如+ ( k 1 ) d ) 2 + 2 ( a + ( k 一1 ) d ) 一1 时，a ( d ) s2 a + 2 ( k 一1 ) d + 1 证明：由定理2 2 ，1 4 ，周期的标号着色厶。+ 2 ( e 1 ) d + 1 = 0 ，1 ，2 ，2 a + 2 ( k 一1 ) d 是如，口十 d ，。+ ( k 一1 ) d ) 一相容的此外，令 丘d + 2 ( 一1 ) d + 2 = 0 ，1 ，2 ，2 a + 2 ( k 一1 ) d + 1 不难验证它也是 。，o + d ，+ ( k 一1 ) d - 相容的。而且，。+ 2 ( 女一1 ) d + l ，2 计2 ( i 1 ) 抖2 与 ，2 。+ 2 ( k 1 ) d + 2 ，2 。+ 2 ( 女一1 ) d + 1 也是 o ，a + d ，a + ( k 一1 ) , q - 相容的 当 ( 2 a + 2 ( k d d + 1 ) ( 2 a + 2 ( k 一1 ) d + 2 ) 一( 2 a + 2 ( k 一1 ) d + 1 ) 一( 2 a + 2 ( k 1 ) d + 2 ) ， 即t 4 ( n + ( k 一1 ) d ) 2 + 2 ( + ( k 一1 ) d ) 一1 时，t = ( 2 a + 2 ( k 一1 ) d + 1 ) n + ( 2 a + 2 ( k 一1 ) d + 2 ) m 都有一组非负整数解( n ，m ) 令 ，t 2 恐+ 。( k - - 1 ) a + 偿+ 。( k - 1 ) a + 。2 乏：竺：兰：! o 垒：坐：兰兰! ! ：兰生：竺竺垒：! 生：型：， 则 也是 o ，。+ d ，a + ( k 一1 ) d - 相容的，由命题2 2 2 ， 是 n i t4 - n ，n 2 t 土( 0 十 d ) ，n a t 土( o + ( 一1 ) d ) 卜相容的 的最大标号是2 。+ 2 ( k 一1 ) d + 1 ，因此当t 4 ( a + ( 一1 ) d ) 2 + 2 + ( 一1 ) d ) 一1 时，a ( d ) 墨2 a + 2 ( 一1 ) d + 1 定理证毕 特别地，当d 。时，我们有： 定理2 2 1 7 当d = o ，a + d ，n + ( k 一1 ) 曲，k ，d 1 ，o ，d 为正整数时，著d a ， a 1 la ( d ) m i n 2 2 + 4 k 一6 ，6 k 一2 ) 证明：由定理2 2 1 4 ，a ( d ) s6 女一2 显然成立我们只嚣证明a ( d ) s2 a + 4 女一6 为此， 令周期的着色 ，2 。+ f 2 一l 】d = 0 4 ，1 ，2 ，8 ，( 8 + 1 ) da + 2 ，a + 3 ，2 a + 1 ，( 2 8 + 2 ) 4 ，( 2 g + 4 ) 8 ，( 2 a + 2 ( 2 k 一3 ) ) 4 因为d 1 ，不难验证这是g ( d ) 的一个l ( 2 ，1 ) 一l a b e l i n g 所以 ( d ) s2 a + 4 k 一6 证毕 东南大学硬士学位论文 注；当d 1 时， 2 0 + 4 k 一6 2 a + 2 ( k 一1 ) d 恒成立 推论2 2 1 8 当a ，k ，d 1 且d o 时，a ( o + k d ，a + ( k + 1 ) d ，a + ( 2 k 一1 ) d ) ) 曼 m i n 2 a + 4 k 一6 ，6 k 一2 证明：同上， ( d ) 6 k 一2 显然成立下面证明 ( d ) 2 a + 4 k 一6 由定理2 2 1 7 ，厶。+ f 2 女一1 ) d 是 o ，a + d ，o + ( 一1 ) 田一相容的( 其中，2 。+ ( 2 一1 ) d 如前 定义) ，因此由命题2 2 2 ，易知，2 。+ ( 2 k 一1 ) d 是 2 a + ( 2 k - 1 ) d 一，2 a + ( 2 k 一1 ) d 一+ d ) ，2 a + ( 2 k 1 ) d a 一( k - 1 ) d ) 一相容的所以， ( 扣+ k d ，。+ ( k + 1 ) d ，+ ( 2 k 一1 ) d ) ) 蔓2 a + 4 k 一6 证毕 第三章j dj = 3 的距离图的标号着色数 这一章我们讨论形如 d ，b ，c ) 的距离集，其中a ，6 ，c 均为自然数且o 6 9 或= 1 ，3 ，5 ，7 ，1 0 ，1 2 ，1 4 ，1 6 ，1 9 ，2 1 ，2 3 ，2 5 ，2 8 ，3 0 ，3 2 ，3 4 ，3 7 ，3 9 ，4 1 ，4 3 4 6 ，4 8 ，5 0 ，5 2 ，5 5 ，5 7 ，5 9 ，6 1 ，6 4 ，6 6 ，6 8 ( 3 ) r = 2 ，s = 5 ， 6 8 或= 3 ，6 ，1 2 ，1 5 ，2 1 ，2 4 ，3 0 ，3 3 ，3 9 ，4 2 ，4 8 ，5 1 ，5 7 ，6 0 ，6 6 ( 4 ) r = 3 ，s = 4 ，k 7 0 或k = 2 ，8 ，1 1 ，1 7 ，2 0 ，2 6 ，2 9 ，3 5 ，3 8 ，4 4 ，4 7 ，5 3 ，5 6 ，6 2 ，6 5 1 3 东南大学硕士学位论文1 4 ( 5 ) r = 3 ，s = 5 ，k 6 9 或k = 1 ，7 ，1 0 ，1 6 ，1 9 ，2 5 ，2 8 ，3 4 ，3 7 ，4 3 ，4 6 ，5 2 ，5 5 ，6 1 ，6 4 ( 6 ) r = 4 ，s = 5 ，k 6 8 或k = 1 ，3 ，6 ，8 ，1 0 ，1 2 ，1 5 ，1 7 ，1 9 ，2 1 ，2 4 ，2 6 ，2 8 ，3 0 ，3 3 ，3 5 ，3 7 ，3 9 ，4 2 ，4 4 ， 4 6 ，4 8 ，5 1 ，5 3 ，5 5 ，5 7 ，6 0 ，6 2 ，6 4 ，6 6 证明：由定理2 1 3 ，当l d l = 3 时，a ( d ) 22 1 d l + 2 = 8 不等式左边成立下面只须对 每种情形构造距离图g “，k + n + s ) 的9 一l ( 2 ，1 ) - l a b e l i n g 即可 ( 1 ) 我们令尸。= 0 2 4 6 8 1 3 5 7 ，p l o = 0 2 4 6 8 1 3 5 7 9 ，不难验证p 口，p 1 0 ，p 9p 1 0 ，p 1 0 p 9 都是 1 ，2 ，3 卜相容的。因为g c d ( 9 ，1 0 ) = 1 ，由f r o b e n i u s 定理知，当t 9 1 0 9 1 0 ，即 7 1 时，。29 n + 1 0 m 都有一组非负整数解( n ，m ) 令b2 胃p 嚣2 犟墨譬当， nm 因为岛，p 1 0 ，p gp 1 0 ，p l o p 。都是 1 ，2 ，3 卜相容的，所以最也是 l ，2 ，3 卜相容的由命鼯 2 22 ，r 是p 一3 ，t 一2 ，t + 1 卜相容的令= t 一3 ，则最= e k + 3 是 ，k + l ，+ 4 卜 相容的所以，当k 7 1 3 = 6 8 时， ( ， + l ，+ 4 ) ) s9 另外，由定理3 1 1 知， 女= 3 ，6 ，1 2 ，1 5 ，2 1 ，2 4 ，3 0 ，3 3 ，3 9 ，4 2 ，4 8 ，5 1 ，5 7 ，6 0 ，6 6 时， ( k ，k + 1 ，k + 4 ) ) = 8 7 1 2 = 6 9 时， ( 女，k + l ，+ 5 ) ) 墨9 另外，由定理3 1 1 知， = 1 ，3 ，5 ，7 ，1 0 ，1 2 ，1 4 ，1 6 ，1 9 ，2 1 ，2 3 ，2 5 ，2 8 ，3 0 ，3 2 ，3 4 ，3 7 ，3 9 ，4 1 ，4 3 ，4 6 ，4 8 ，5 0 ，5 2 ，5 5 ，5 7 ，5 9 ，6 1 ， 6 4 ，6 6 ，6 8 时， ( ，k + 1 ，k + 5 ) ) = 8 7 1 3 = 6 8 时， ( 七，k + 2 ，七+ 5 ) ) 9 又由定理3 1 l 知，= 3 ，6 ，1 2 ，1 5 ，2 1 ，2 4 ，3 0 ，3 3 ，3 9 ，4 2 ，4 8 ，5 1 ，5 7 ，6 0 ，6 6 时，a ( ，k + 2 ，k + 5 ) ) = 8 ( 4 ) 易知( 1 ) 中的b 是o 一1 ，t + 2 ，t - - 3 卜相容的令= t 一1 ，则最= p k - k l 是 k ，k + 3 ，膏+ 4 ) 一相容的当k 7 1 1 = 7 0 时，a ( 七，七+ 3 ，而+ 4 ) ) s9 又由定理3 1 1 可知，当k = 2 ，8 ，1 1 ，1 7 ，2 0 ，2 6 ，2 9 ，3 5 ，3 8 ，4 4 ，4 7 ，5 3 ，5 6 ，6 2 ，6 5 时，a ( ，k + 3 ，+ 4 ) ) = 8 ( 5 ) 易知( 1 ) 中的最是 亡一2 ，t + 1 ，t + 3 卜相容的令k = t 一2 ，则只= p k + 2 是 ，k + 3 ，+ 5 卜相容的当k 7 1 2 = 6 9 时，a c k ， + 3 ， + 5 ) ) s9 由定理3 1 1 ， 南= 1 ，7 ，1 0 ，1 6 ，1 9 ，2 5 ，2 8 ，3 4 ，3 7 ，4 3 ，4 6 ，5 2 ，5 5 ，6 1 ，6 4 时，a ( 南，k + 3 ，k + 5 ) ) = 8 ( 6 ) 易知( 1 ) 中的b 是 t 一3 ，t + 1 ，t + 2 ) 一相容的。令k = t 一3 。则只= p k + 3 是 愚，k + 4 ，k + 5 - 相容的当k 7 1 3 = 6 8 时，a ( 七，k + 4 ，k + 5 ) ) 9 由定理3 1 1 ，k = 1 ，3 ，6 ，8 ，1 0 ，1 2 ，1 5 ，1 7 ，1 9 ，2 1 ，2 4 ，2 6 ，2 8 ，3 0 ，3 3 ，3 5 ，3 7 ，3 9 ，4 2 ，4 4 ，4 6 ，4 8 ，5 1 ，5 3 ，5 5 ，5 7 ，6 0 ，6 2 ，6 4 ，6 6 时， ( ， + 4 ，k + 5 ) ) = 8 综上，定理证毕 类似地可以得到如下定理： 定理3 2 2 设d = 七，k + r ，k + s ) ，当r ，8 ，忌满足下列条件之一时，则8 ( d ) 9 ( 1 ) r = 1 ，s = 2 ，k 6 7 或= 1 ，2 ，5 ，6 ，1 0 ，1 1 ，1 4 ，1 5 ，1 9 ，2 0 ，2 3 ，2 4 ，2 8 ，2 9 ，3 2 ，3 3 ，3 7 ，3 8 ，4 1 ，4 2 ， 4 6 ，4 7 ，5 0 ，5 1 ，5 5 ，5 6 ，5 9 ，6 0 ，6 4 ，6 5 ( 2 1r = 1 ，8 = 6 ， 6 7 或k = 2 ，5 ，1 1 ，1 4 ，2 0 ，2 3 ，2 9 ，3 2 ，3 8 ，4 1 ，4 7 ，5 0 ，5 6 ，5 9 ，6 5 东南大学硕士学位论文 ( 3 ) r = 1 ，8 = 7 ，k 6 8 或k = 3 ，6 ，1 2 ，1 5 ，2 1 ，2 4 ，3 0 ，3 3 ，3 9 ，4 2 ，4 8 ，5 1 ，5 7 ，6 0 ，6 6 ( 4 ) r = 2 ，8 = 7 ， 6 7 或 = 3 ，4 ，5 ，6 ，1 2 ，1 3 ，1 4 ，1 5 ，2 1 ，2 2 ，2 3 ，2 4 ，3 0 ，3 1 ，3 2 ，3 3 ，3 9 ，4 0 ，4 l ，4 2 ， 4 8 ，4 9 ，5 0 ，5 1 ，5 7 ，5 8 ，5 9 ，6 0 ，6 6 ，6 7 ( 5 ) r = 5 ，s = 6 ， 6 9 或= 1 ，7 ，1 0 ，1 6 ，1 9 ，2 5 ，2 8 ，3 4 ，3 7 ，4 3 ，4 6 ，5 2 ，5 5 ，6 1 ，6 4 ( 6 ) r = 5 ，8 = 7 ，k 6 8 或= 5 ，6 ，7 ，8 ，1 4 ，1 5 ，1 6 ，1 7 ，2 3 ，2 4 ，2 5 ，2 6 ，3 2 ，3 3 ，3 4 ，3 5 ，4 1 ，4 2 ，4 3 ，4 4 ， 5 0 ，5 l ，5 2 ，5 3 ，5 9 ，6 0 ，6 1 ，6 2 ，6 8 ( 7 ) r = 6 ，s = 7 ， 6 7 或k = 5 ，8 ，1 4 ，1 7 ，2 3 ，2 6 ，3 2 ，3 5 ，4 1 ，4 4 ，5 0 ，5 3 ，5 9 ，6 2 证明：证明与定理3 2 1 类似，不同的是这里我们取尸9 = 0 1 2 3 4 5 6 7 8 ，p i o = 0 1 2 3 4 5 6 7 8 9 ，可 验证p 9 ，p l o , p g p i o ，p l o p 9 都是 2 ，3 ，4 卜相容的令最= 碍础2 p g ，p 9 p 1 o p 1 0 ，则当 t 9 1 0 9 1 0 = 7 1 时，r 是 2 ，3 ，4 卜相容的，即也是 t 4 - 2 ，t4 - 3 ，t 士4 卜相容的 ( 1 ) 最是o 一4 ，t 一3 ，t 一2 卜相容的。令k = t 一4 ，则当 7 1 4 = 6 7 时， a ( ，k + l ，+ 2 ) 兰9 又由定理3 1 1 知，k = 1 ，2 ，5 ，6 ，1 0 ，1 1 ，1 4 ，1 5 ，1 9 ，2 0 ，2 3 ，2 4 ，2 8 ，2 9 ，3 2 ，3 3 ， 3 7 ，3 8 ，4 1 ，4 2 ，4 6 ，4 7 ，5 0 ，5 1 ，5 5 ，5 6 ，5 9 ，6 0 ，6 4 ，6 5 时，a ( ，k + 1 ，k + 2 ) = 8 7 1 4 = 6 7 时， a ( ，+ 1 ， + 6 ) 9 又由定理3 1 1 知，k = 2 ，5 ，1 1 ，1 4 ，2 0 ，2 3 ，2 9 ，3 2 ，3 8 ，4 1 ，4 7 ，5 0 ，5 6 ，5 9 ，6 5 时， ( 女，k + 1 ，k + 6 ) = 8 7 1 3 = 5 8 时， a ( 女，女+ 1 ，女+ 7 ) 9 又由定理3 1 1 知，k = 3 ，6 ，1 2 ，1 5 ，2 1 ，2 4 ，3 0 ，3 3