（应用数学专业论文）依距离2的图标号.pdf

摘要 本文考虑的频率分配问题源自无线电台的频率干扰问题给定若干电 台，要求给它们分配合适的频率，使得可能产生干扰的电台所用的频率间隔 在允许的范围内，目标是使所使用频率的范围尽可能的小这个问题可归结 为如下图的顶点标号问题； 给定一个直径至少为p 的图g 及实数七1 ，乜，20 ，g 的一个 l ( k 1 ，k 2 ，) 一实数标号是其顶点集到非负实数集的一个映射，使得任 意两个顶点u 和口的标号之差至少是k i ，即。i f ( u ) 一，( ) l k i ，这里， i = d a ( t ，口) 是t | 和t ，之间的距离标号的目标是寻找一个，使其标号跨度 ( 即最大标号与最小标号的差) 最小，记这个最小跨度为a ( g ；k l ，k 2 ，b ) 本文讨论无三角形图和树的l ( k ，1 ) 实数标号问题，其中0 0 ) 标号数的精确值( 其中三角形网格图对k 的部分值只给出 了界) 本文从图g 2 的正常着色入手，讨论无三角形图和树的l ( k ，1 ) 实数标 号问题，其中0 k 百1 主要结果为： ( 1 ) 若图g 无三角形，则x ( a 2 ) 一1 入( g ；k ，1 ) x ( c 2 ) 一1 + x ( g 2 ) 七，这 里x ( h ) 表示个图日的色数 ( 2 ) 若g 为二部图，则x ( g ) 一1 a ( g ；k ，1 ) x ( g ) 一1 + k ( 3 ) 若t 是树，则a ( t ；k ，1 ) = a l - - j a 一1 + k 根据t 的最大度点的分 布情况，进一步确定了一类达到一1 的树特别的，本文给出了a = 3 的树的最小标号数 1 2 基本术语和符号 我们假设所考虑的图都是简单连通的y ( g ) ，e ( g ) 和g 。分别表示图 g 的顶点集，边集和补图图中顶点的最大度记作图g 的顶点让和秒， 若它们之间有边，则称t ， 相邻 g 2 为一个简单图，其顶点集与g 的顶点集v ( g ) 一样，两个顶点可，伽 在g 2 中相邻当且仅当它们在g 中距离为2 如果一条路上的顶点数是奇( 偶) 数。我们就说这是一条奇( 偶) 路 图g 的直径是指图上任意两点之间的最大距离，记为d ( g ) 我们称树t 中的点为主要顶点，若该点的度为最大度通常把某个 主要顶点作为树的根顶点从树的根顶点到t 的任意顶点v 的路径长度称 为v 的层数若顶点a 与顶点b 相邻，则称b 为6 的儿子 由于树t 任意两个主要顶点之间仅有一条路相连，如果这路上没有其 第1 章引言 4 他主要顶点，我们称这两个主要顶点是相邻主要顶点 给定个树t ，记2 为这样个树t 其顶点为树? 的主要顶点，两个 顶点u ，可相邻当且仅当它们在树t 中是相邻的主要顶点 第2 章无三角形图 第2 章无三角形图 引理2 1 若d ( g ) = 2 ，0 k 1 2 ，则 ( n 一1 ) k a ( g ；k ，1 ) 仃一2 证明令u 为图g 的一条边，图g u 口是由图g 去掉边u y 得到 若图g 一缸t ，仍是连通的，且d ( g u u ) = 2 ，假设，是图g u 口的个最 优标号，则d g 一伽( u ， ) = 2 ，根据标号的条件，i y ( u ) 一，( u ) i 1 若我们 给图g 标号，根据标号的条件，i y ( u ) 一，( 口) i2 七，注意到k 1 2 2 ，则g 2 最多有两个连通分支 证明令u ，秽为图g 中满足d g ( u ，u ) = 3 任意两个的顶点，g ，瓯分 别为包含v ，u 的图g 2 的连通分支我们只需证明v ( g ) = y ( g ) uy ( g ) 设w 为图g 中异于，口的点若d a ( w ，“) 是偶数，根据g 2 的定义， w 瓯；若d a ( w ，t i ) 是奇数，因为d g ( u ， ) = 3 ，所以存在一条从到口的 偶路，则w g 即上面两种情况都有叫y ( 瓯) uy ( g ) 另外显然有 v ( g ) y ( 既) uy ( g ) ，所以v ( c ) = y ( 吼) uy ( g ) 即引理成立 口 引理2 3 如果图g 不含三角形，则g 2 最多有两个连通分支，而且g 2 有两个连通分支当且仅当g 是二部图 5 第2 章无三角形图 6 证明任取图g 中的个顶点缸，定义 r ( u ) = 口： g ，顶点u 到顶点v 有一条偶路) 根据g 2 的定义，对任意一个r ( u ) 中的顶点 ，u 和t ，在g 2 中属于同一个 分支，记为q 也就是说f ( u ) u u ) 瓯若瓯= y ( g ) ，则g 2 只有一个 连通分支接下来我们假设瓯y ( g ) 若v ( c ) 瓯只含个顶点则结论明显成立不妨设i v ( c ) g l 2 令 v ，w v ( c ) g ，接着我们只需说明t ，w 在g 2 中同时属于另外个不同于 瓯的分支令r = 让 l u 2 秒和p 2 = u w l w 2 叫t 伽分别为u 到v 和w 的 最短路由于可，加瓯，则8 和t 都是偶数，且 0 2 ， 0 4 ，叫2 ，w 4 ，w t g 同时，只是一条最短的路，口l ，啦，v s - 1 和t j 属于同一个分支，记 为g 类似的，w l ，w 3 ，w t l ，w 属于同个分支，记为瓯另方面， 由于图g 不含三角形，所以d g ( 1 ，w 1 ) = 2 ，也就是说移l 和w l 在同一个分 支里，所以g = 瓯 接着我们给出定理第二部分的证明设图g 为二部图对任一条边乱t ， e ( g ) ，由于图g 不含奇圈，则从他到钉所有的路都是奇路也就是说仳和 u 在g 2 中的不同分支 反之，设g 2 有两个分支g i 和g ；，接着我们证明图g 不含奇圈不妨设 c = i ) 1 7 2 2 仇为图g 中的奇圈由于图g 不含三角形，则点 l ，也，仇 在g 2 中的同一个分支，记为g 令2 1 为v ( v ) v ( c ) 中的任一个点，p = u l u 2 钍 仇为钍到c 的最短路又因为图g 不含三角形，有| i i 地+ l ( m o d k ) 隹 e ( g ) ，即d c ( u h ，仇+ 1 ( 。o a k ) ) = 2 ，所以牡h g 。另一方面，要么u l 和u h 在 同一个分支，要么牡1 和v i 在同一个分支也就是说u l g ，即定理得证 口 令u ，秒为g 中任意两个顶点，若d g ( u ，v ) 为偶数或存在g 中的点，满 足d g ( t ，w ) 和d g ( 叫，u ) 都是偶数，则g 2 是连通的，否则g 2 有两个连通分 第2 章无三角形图 支当g 2 有两个连通分支时，我们设x ( g ；) ，x ( g g ) 为它的两个连通分支， 且x ( g ) 之x ( a i ) 定理2 4 若g 2 有两个连通分支。则 a ( g ；k ，1 ) 阪( g ；) 一1 ，x ( g ；) 一1 + 叫，0 k 1 2 证明图g 中距离为2 的点应满足的标号约束条件相当于在图g 2 中相 邻的点应满足的约束条件，所以有入( 七，1 ) 2x ( g ) 一1 令 ，止分别为x ( g ；) ，x ( g ：) 的最优标号，我们根据下式给图g 标号 f ( v ) = ( u ) ，若t ，g ； f ( v ) = 庀( ) + k ，若钉g ； 则，为图g 的个可行的标号若顶点y l ，v 2 同时在g ；或同时在g ；，则 d g ( u - ，? 3 2 ) 为偶数根据 ，厶的定义，当d g 0 1 ， z ) = 2 时i ( v x ) - - f ( v 2 ) i 1 若顶点u 1 ，砚，个在g ，另个在g ；，则如( t ，l ， 2 ) 为奇数，当d g ( 口l ，i ) 2 ) = l 时i f ( v 1 ) 一f ( v 2 ) l k ，或i f ( v 1 ) 一f ( v 2 ) l 1 一k 因为0 ks1 2 ，所以标 号条件满足因此a ( 七，1 ) x ( g ；) 一1 + k ，定理得证 口 根据定理2 4 的证明，我们有以下推论， 推论2 5 若g 2 有两个连通分支，0 k 1 2 ，则 ( 1 ) 若x ( g ) x ( a i ) ，则a ( g ；k ，1 ) = ) ( ( g ；) 一l ； ( 2 ) 若a ( g ；k ，1 ) = x ( g i ) 一1 + k ，贝1 ix ( g i ) = x ( g ；) 特别的，若图g 为二部图，由引理2 3 ，定理2 4 有。 推论2 6 若图g 为二部图，则 a ( g ；k ，1 ) 阪( g 2 1 ) 一1 ，x ( g i ) 一1 + 叫，0 0 ，k = ( k l b ) 0 ，则 a ( g ；k ) 警l2 k i a ( a 一1 ) 扣1 推论2 1 0 若g 2 有两个连通分支，则入( g ；k ) 2 k a ( a 一1 ) + k ， 1 2 k 1 证明因为在图g 中到任意个顶点距离为2 的点至多有a ( a 一1 ) 个， 即x ( g 2 ) ( 一1 ) + 1 若1 2 k 1 ，由性质2 8 ， a ( k ，1 ) 入( 后，2 k ) = 2 k a ( 1 2 ，1 ) 2 k a ( a 一1 ) + k 口 当g 2 只有个连通分支时，我们记厂为图g 2 的一个最优标号，这些 标号取于 0 ，x ( g 2 ) 一1 l 中的整数定义 f ( t ) = 口g 2 f ( u ) = t ，0 t x ( v 2 ) 一1 ，t r ) 引理2 1 1 若图g 不合三角形，v v l ， 2 ，v 3 f ( t ) ，则在图g 中这三 个点间最多有一条边 证明令口- ，眈，口3 为f ( t ) 中的任意三个点，由于图g 不含三角形，所以 这三个点间最多有两条边我们用反证法，不妨假设边口1 v 2 ，v 2 7 ) 3 g ，则点 可1 和1 ) 3 之间距离为2 ，也就是说v 1 7 3 3 e ( g 2 ) 根据标号的条件点v l 和v a 的标号至少要相差l ，与广( 口1 ) = 广) 矛盾，即引理得证 口 引理2 1 1 说明图g 的导出子图f ( t ) 只含两种结构，k 1 当图g 不 含三角形时，我们用k 和x ( g 2 ) 给出入( g ；k ) 的一个界 定理2 1 2 若图g 不合三角形，则 a ( g ；k ，1 ) x ( e 2 ) 一1 ，x ( c 2 ) 一1 + x ( a 2 ) 明，0 k 1 2 8 第2 章无三角形图 证明若g 2 包含两个连通分支，由定理2 4 ，结论成立以下考虑g 2 只 有一个连通分支的情况 根据标号条件距离为2 的点的标号至少差1 ，定理中的下界容易得到 接着证明定理中的上界 令u t l v 1 ，u t n t v t n 。为g 的导出子图f ( t ) ( o t x ( c 2 ) 一1 ) 中的 m ( m n ) 条边对图g 根据下式标号t f ( v u ) = f ( v u ) + ( t + 1 ) k ，i = l ，傀； f ( v ) = ，( 口) + t k ，u f ( t ) t 7 t l ，v t 竹。】，0 tsx ( c 2 ) 一1 这样得到的，为图g 的一个可行的标号令钉l 可2 为图g 中的任意一 条边若，( 口1 ) = f + ) ，则l 厂( 口- ) 一f ( v 2 ) i = k ，若广( u 1 ) f + ( 观) ，则 l f ( v 1 ) 一f ( v 2 ) i 1 一k k 如果u l ，让2 为g 中的任意两个顶点，满足妃( t l ，u 2 ) = 2 根据，的定 义，即i f ( u - ) 一f ( u 2 ) i = 1 ，所以l f ( u 1 ) 一f ( u 2 ) i 1 也就是说，满足标 号条件注意到，最大值至多为x ( a 2 ) 一1 + x ( c 2 ) 七，所以定理得证 口 我们没找到哪一类图的a ( g ；k ，1 ) 等于定理中的上界，因此不知道定理 中的上界是不是最好的因为x ( a ) + x ( a 。) v ( a ) + 1 和x ( a 2 ) x ( c 。) ， 根据定理2 1 2 ，我们有以下推论， 推论2 1 3 若图g 不合三角形，则 a ( g ；k ，1 ) v ( c ) 一x ( c ) + ( v ( c ) + 1 一x ( g ) ) 后，0 k 1 2 9 第3 章树 第3 章树 1 0 3 1 树的l ( k ，1 ) 标号数的一般结论 在这部分，我们讨论当图g 为树且0 2 性质3 1 1 若树r 的最大度为，则x ( 铲) = 证明设点口为树t 中度为的点，则与t 7 相邻的任意两个顶点之间 的距离都为2 ，根据t 2 的定义，在铲中，所有与移相邻的点构成一个个 顶点的完全图，所以x ( 铲) t 是二部图，则p 有两个连通分支对于每个连通分支，它们中的块 都是由至多个顶点的完全图组成的即x ( 铲) a 所以x ( 严) = a 口 定理3 1 2 若t 是树，则a ( t ；k ，1 ) = a 一1 或一1 + k 证明由定理2 4 ，性质3 1 1 ，a ( t ；k ，1 ) 【一1 ，一1 + 乩设，是树 丁的个最优标号，m a x ( f ) = a 一1 + t ，t ( 0 ，尼) ，我们构造，如下t f ，_ 【儿若【f 】f 一1 也就是说不管点 1 怎么标号，都有 m a x ( f ( v ) ) 一1 ，由定理3 1 2 ，m a x ( f ( v ) ) 一1 + k 结论成立 口 以下我们讨论的图都不含两个相邻的最大度点且并非任意两个主要顶 点之间的距离都是偶数 3 2 最大度为3 的树 定理3 2 1若树t 的最大度= 3 ，则a ( r ；k ，1 ) = 2 + k 当且仅当t 包含图1 所示结构 踞培 蟛够 j ；，蟛杉 图l ：最大度为3 时 证明若我们用 0 ，2 】中的标号给最大度为3 的树标号，有以下结论 命题3 2 2 主要顶点的标号不能用整数 证明令r 为任意个主要顶点，是最大度为3 的树t 的个可行的 标号对树t 与顶点r 相邻的任意两个顶点之间的距离都为2 ，根据标号条 件，它们的标号差至少为1 若，( r ) 是一个整数，则在【0 ，2 】中满足条件的 第3 章树 1 2 标号，除了，( 7 ) 外，最多有2 个，而点，的度为3 ，所以m a x ( f ( v ) ) 2 口 命题3 2 3 与主要顶点相邻的点的标号必须用整数 证明令u 与某个主要顶点相邻，是树t 的个可行的标号对树丁， 任意两个与某个主要顶点相邻的顶点标号至少相差1 若f ( u ) 不是整数，根 据标号条件，在【o ，2 】中，加上，( 让) ，至多有2 个标号，而点r 的度为3 ，因 此m a , x ( f ( v ) ) 2 口 若树t 包含图1 所示结构，不失一般性，我们把点咖( 见图1 ) 看作树 的根顶点假设，为树r 的一个最优标号，且m a x ( f ) = 2 由于3 0 是主要 顶点，顶点 3 1 ， 3 4 不能同时用标号0 ，设f ( v 1 ) = 0 ，若f ( v 4 ) = 1 ，则顶点 不能用 o ，2 】中的非整数标号，与命题3 2 2 矛盾 若f ( v 4 ) = 2 ，则顶点u 5 不能用【o ，2 】中的整数标号，这与命题3 2 3 矛 盾所以我们无法用【o ，2 】中的标号对树t 标号，即m a x ( ) 2 ，由定理 3 1 2 ，a ( t ；后，1 ) = 2 + 七 如果树t 不含图1 所示结构，我们构造一种标号方法给树r 标号，且 使用的标号为【0 ，2 】中的实数我们给出一列向量，向量中的每个分量对应 树的每个顶点所使用的标号例如我们用下面这个向量表示图2 中树t 的 标号 图2 ：用相应的向量给树标号 第3 章树 七 三：三主l 三七。0 1 ：七 1 3 接着我们通过下列步骤给树t 标号 1 ) 把树r 中某个主要顶点作为根顶点，使其标号为k 其儿子标【0 ，2 】 中的整数标号，我们称儿子标号为t 的分支为根顶点的t 分支若某个分支 上没有主要顶点，由定理3 1 2 ，该分支上的点可以用 0 ，1 + k 】上的标号若 该分支上有主要顶点，接着我们给出与根顶点相邻的所有未标号主要顶点标 号不妨设与根顶点相邻的该分支上的未标号的主要顶点在第i 层 如果i 为偶数，则在这分支上的主要顶点和根顶点之间的路上的顶点 可以按如下方式标号标在第2 n ( 2 n i ，n n ) 层的顶点后( 仃为偶数) 或 k + 1 ( n 为奇数) ；标在第2 n + i ( 2 n + 1 5 时，则在这个分支上，与根顶点相邻的主要顶点和根顶点之间的路 第3 章树 1 4 上的前5 个顶点( 从根顶点开始算起) 使用与i = 5 时一样的标号，用下面 的方式标第6 层后的顶点 如果，( 珈) = k ( v o 为该分支上与根顶点相邻的主要顶点和根顶点之间 的路上第5 层的点) ： 当y = 4 n4 - 2 时，( u ) = 2 ；当j = 4 n4 - 3 时，y ( v ) = 1 + 七； 当j = 4 n 时，i ( v ) = 1 ；当j = 4 n4 - 1 时，( v ) = k 如果f ( v o ) = 14 - 七： 当歹= 4 n4 - 2 时，( 口) = 2 ；当j = 4 n4 - 3 时，( 口) = 尼； 当歹= 4 n 时，( v ) = 1 ；当j = 4 n4 - 1 时，( 钉) = 14 - k 如果还有主要顶点未被标号转向2 ) ，否则结束 2 ) 选择个与未被标号的主要顶点相邻的已标号的主要顶点作为新的 根顶点由步骤1 ) 可知该新根顶点的标号为k 或1 - 4 - k ，接着我们给与根顶 点相邻的未标号的主要顶点标号若根顶点的标号为k ，转1 ) 若根顶点的标号为14 - 七i 不妨设与其相邻的未标号的主要顶点在第i 层 如果i 为偶数，则在这分支上的主要顶点和根顶点之间的路上的顶点可 以按如下方式标号标在第2 n ( 2 n i ，n r ) 层的顶点1 + k ( n 为偶数) 或 k ( n 为奇数) ；标在第2 礼4 - 1 ( 2 n - 4 - 1 5 时，则在这个分支上，与根顶点相邻的主要顶点和根顶点之间的路 上的前5 个顶点( 从根顶点开始算起) 使用与i = 5 时一样的标号，用下面 的方式标第6 层后的顶点 若( v o ) = k ( v o 为该分支主要顶点和根顶点之问的路上第5 层的点) ： ( v ) = 0 ，当j = 4 n + 2 ；，( 口) = 1 + k ，当j = 4 n + 3 ； ( v ) = 1 ，当歹= 4 n ；f ( v ) = 七，当j = 4 n + 1 若f ( v o ) = 1 + 七：， ) = 0 ，当j = 4 n + 2 ；f ( v ) = k ，当j = 4 n + 3 ； ( v ) = 1 ，当歹= 4 n ；y ( v ) = 1 + k ，当歹= 4 n + 1 3 ) 重复步骤2 ) 直到所有的主要顶点都被标号 若树r 仍有未标号的点，则这些点组成的导出子图为最大度不超过2 的森林由定理3 1 2 可知，所有未被标号的点可以从 0 ，2 】中选取满足标号 条件的标号定理得证 3 3 最大度为4 的树 接着我们讨论一类特殊的树若7 是树，我们有以下结果 定理3 3 1 如果树t 的最大度= 4 ，且t m 是树，若? 包含图3 所 示结构，则入( t ；k ，1 ) = 3 + 七；若任意两个主要顶点之间的距离都大于3 ，则 入口；k ，1 ) = 3 证明若我们用【0 ，3 】中的标号给树标号，与定理3 2 1 的证明类似，有 以下结论 命题3 3 2 主要顶点的标号不能用整数 命题3 3 3 与主要顶点相邻的点的标号必须用整数 第3 章树 _ t t t 一t i 一一 i i i _ - _ _ t t j 一 一t l 一一 l _ 工l - _ _ 一一广 _ 1ti 一i 一二i 工 _ - tt i t ji 一 iii - _ lt _ 一 i 一t l 二_- i 二_i i 1t t。一一r = _ 一i 一i i l _ - t t t一1 一- lii -_ - _ _ t t 一 l 一t l 一一一l 1i - - - - tt t 一t 一 _ i 二i il _ - t t t? 一1 工一一i i i _ _ lt v一 il _ ，tt t一r i 一二_ii l _ 图3 ：最大度为4 时 1 6 第3 章树 1 7 命题3 3 4 若给图4 中的结构标号，根据标号条件有。 1 ) 如果f ( v 1 ) = t ，k t l k ，f ( v 2 ) = 3 ，则点v 4 的标号不能用【0 ，3 】 中的实数 2 ) 如果( v 1 ) = t ，k t 1 一k ，f ( v 2 ) = 2 ，则点嵋的标号不能用【0 ，3 】 中的实数 3 ) 如果i c v l ) = 2 + t ，k t 1 一k ，f ( v 2 ) = 0 ，则点v 4 的标号不能用 【0 ，3 】中的实数 4 ) 如果f ( v 1 ) = 2 + t ，k t 1 一k ，f ( v 2 ) = 1 ，只- i 点1 3 5 的标号不能用 0 ，3 】中的实数 图4 ：a = 4 树中的一种结构 若树t 包含定理中所述结构，以图5 为例，不失一般性，我们把珈点 当作根顶点假设，为树r 的一个最优标号，m a x ( f ) = 3 不管根顶点如 怎么标号，钉1 ， 2 ，地，地四个点中必有两个点要使用集合( 0 ，1 ) u ( 2 ，3 ) 中的 标号，由命题3 3 2 ，命题3 3 4 ，图5 中的结构不能都使用 0 ，3 】中的标号， 所以m a x ( f ) 3 ，由定理3 1 2 可知，这样结构的最小标号数为3 + k 定理 中的其他结构可以类似证明 若最大度为4 的树且任意两个主要顶点之间的距离大于3 ，我们可以用 【0 ，3 】中的实数给树标号与定理3 2 1 类似，我们先给树t 上的主要顶点和 连接主要顶点的路上的点标号 1 ) 把树t 中任意个主要顶点选作根顶点从根顶点开始标号，使其标 号为1 + k ，其儿子的标号为 0 ，3 】中的整数我们称儿子标号为t ( 0 t 3 ) 第3 章树 _。 , - - o -rt t 一 j j 一 _ 一 l - - o ftt _ - 形蟛。 一 t j 一 一 i m 一 一 _ 1il 一p i 一 _ - - l卜 舨一t _ rt 一l 二i j - 一_ 图5 ：一种a ( t ；k ，1 ) = 3 + k 结构 1 8 的分支为根顶点的分支若在t 分支上，与根顶点相邻的主要顶点在第 i ( i 3 ) 层，若i = 4 n ( n n ) ，则根顶点和该主要顶点之间的路上的顶点可 按如下标号标在第句( n 歹0 ) 层的顶点为1 + 詹；标在第句+ 1 层的顶 点为；标在第幻+ 2 层的顶点为七；标在第句+ 3 层的顶点为t l ( t 0 ) 若i = 4 n + 2 ( 他n ) ，则根顶点和该主要顶点之间的路上的顶点可按如 下标号第2 层的顶点为2 + k ，第3 层的顶点为t l ( t 0 ) 或t + l ( t = 0 ) ； 标在第句o 1 ) 层的顶点为七；标在第幻+ 1 层的顶点为t ；标在第幻+ 2 层的顶点为1 + 七；标在第幻+ 3 层的顶点为t l ( t 0 ) 或t + l ( t = o ) 若i 为奇数，则根顶点和该主要顶点之间的路上的顶点可按如下标号 当i = 5 时我们可以根据t 的值从下列向量中选取相应的标号 1 + 七 ： 32 + 七2 1 + 七 ， + 后 薹 。七2 1 + 七 第3 章树 当i = 7 时我们可以按照t 从下列向量中选取相应的标号 1 9 当i 7 且i = 4 n + l ( n 2 ) 时，在这个分支上，根顶点相邻的主要 顶点和根顶点之间的路上的前5 个顶点( 从根顶点开始算起) 的标号使用与 i = 5 时一样的标号标在第句( 佗j 1 ) 层的顶点为2 ；标在第句+ 1 层 的顶点为1 + 七；标在第句+ 2 层的顶点为1 ；标在第幻+ 3 层的顶点为k 当i 7 且i = 4 n + 3 ( 礼 2 ) 时，在这个分支上，该主要顶点和根顶点 之间的路上的前7 个顶点( 从根顶点开始算起) 的标号使用与i = 7 时一样 的标号标在第句( 亿歹 1 ) 层的顶点为1 ；标在第句+ 1 层的顶点为七； 标在第句+ 2 层的顶点为2 ；标在第句+ 3 层的顶点为1 + k 按照以上标号方式，把与跟顶点相邻的主要顶点都上标号若还有的主 要顶点未被标号，转到步骤2 ) ，否则结束 2 ) 选择一个与未被标号的主要顶点相邻的已标号的主要顶点作为新的 根顶点由步骤1 ) 可知该新根顶点的标号为1 + k ，其未标号的儿子从 0 ，3 】 中的整数选取未被使用的标号按步骤1 ) 同样的方式给所有与根顶点相邻 的未标号的主要顶点标号若还有的主要顶点未被标号，重复步骤2 ) ，否则 结束 所有的主要顶点及连接主要顶点的路上的顶点都按照上述方式标号后， 若仍有未标号的点，则这些点组成的导出子图为最大度不超过3 的森林由 于连接主要顶点的路上的顶点的度至多为3 ，事实上不难发现，即使连接主 要顶点的路上的顶点的度都为3 ，按照上述方式标号后，与这些路上的顶点 相邻的未被标号的顶点仍然可以从【0 ，3 】中选取满足标号条件的标号由定 七 + l2 七 七 七 十 七 2，-1上，1 1 膏 后 七 + + 七 + l 2 1 3 3 0 0 o l 2 3 ，、iii_一 七 + 工 第3 章树 2 0 理3 1 2 可知，所有未被标号的点可以从1 0 ，3 】中选取满足标号条件的标号 定理得证 3 4 最大度大于4 的树 定理3 4 1 如果树t 的最大度= 5 ，且p 是树，若t 包含图6 所 示结构，则a ( t ；k ，1 ) = 4 + 砖若任意两个主要顶点之间的距离都大于3 ，则 入( 丁；k ，1 ) = 4 图6 ：最大度为5 时 证明若我们用 0 ，4 】中的标号给树标号，与定理3 2 1 的证明类似，有 以下结论 第3 章树 1 弓 图7 ：a = 5 树中的一种结构 2 1 命题3 4 2 主要顶点的标号不能用整数 命题3 4 3 与主要顶点相邻的点的标号必须用整数 命题3 4 4 若给图7 中的结构标号，根据标号条件有t 1 ) 如果f ( v t ) = t ，kst 1 一k ，( 口2 ) = 违，当1 1 3 = 4 时，顶点u 5 和秽7 的标号中必有一个不能用 0 ，4 】中的实数；当地= 2 时，顶点讥和的标 号中必有一个不能用 0 ，4 】中的实数 2 ) 如果f ( v 1 ) = t ，kst 1 一七，( 忱) = 4 ，则顶点u 4 和的标号中必 有一个不能用【0 ，4 1 中的实数 3 ) 如果f ( v 1 ) = 3 + t ，k t 1 一k ，f ( v 2 ) = 0 ，则顶点砒和口6 的标号 中必有一个不能用【o ，4 】中的实数 4 ) 如果f ( v x ) = 3 + t ，k t 1 一k ，f ( v 2 ) = 1 ，当珊= 1 时，顶点 和嘶的标号中必有一个不能用 o ，4 】中的实数；当1 1 3 = 2 时，顶点m 和 的标号中必有一个不能用 0 ，4 】中的实数 若最大度为5 的树t 包含定理中描述的结构，以图8 为例不失一般性， 我们以珈点为根顶点，设，为树t 的个最优标号，且m a x ( f ) = 4 不管顶 点u o 怎么标号，在顶点移1 ，可2 ，1 3 3 ，1 3 4 ，v 5 中至少有两个要用集合( 0 ，1 ) u ( 3 ，4 ) 中的标号由命题3 4 2 ，命题3 4 4 ，图8 中的结构不能使用【0 ，4 】中的标号 所以m a x ( f ) 4 ，由定理3 2 1 可知，这样结构的最小标号数为4 + k 对定 理中的其他结构可以类似地证明 第3 章树 图8 ：一种a ( t ；k ，1 ) = 4 + k 的结构 若最大度为5 的树且任意两个主要顶点之间的距离大于3 ，我们可以用 【0 ，4 】中的实数给树标号与定理3 2 1 类似，我们先给树丁上的主要顶点和 连接主要顶点的路上的点标号 1 ) 把树t 中任意个主要顶点选作根顶点从根顶点开始标号，使其标号 为1 + k ，其儿子的标号为 0 ，4 】中的整数若在t 分支上与根顶点相邻的主 要顶点在第i ( i 3 ) 层，若i = 4 n ( n n ) ，则根顶点和该主要顶点之间的路 可按如下标号标在第4 j ( n 歹0 ) 层的顶点为1 + 七；标在第句+ 1 层的 顶点为t ；标在第句+ 2 层的顶点为尼；标在第句+ 3 层的顶点为t 一1 ( t 0 ) 或t + l ( t = o ) 若i = 4 n + 2 ( n n ) ，则根顶点和该主要顶点之问的路可按如下标号 第2 层的顶点为2 + k ，第3 层的顶点为t l ( t 0 ) 或t + l ( t = o ) ；标在第 4 j ( j 1 ) 层的顶点为七；标在第句+ 1 层的顶点为t ；标在第句+ 2 层的顶 第3 章树 点为1 + 七；标在第句+ 3 层的顶点为t l ( t 0 ) 或t + l ( t = o ) 若i 为奇数，则根顶点和该主要顶点之间的路可按如下标号当i = 5 时我们可以根据t 的值从下列向量中选取相应的标号 i = 5 ：1 + 七 0 32 + k 当i = 7 时我们可以按照t 从下列向量中选取相应的标号 1 + k 32 + k 32 + k 0k 0k 0七 2七 2尼 当i 7 且i = 4 n + l ( n 2 ) 时，在这个分支上，根顶点和与之相邻的主要 顶点之间的路上的前5 个顶点( 从根顶点开始算起) 使用与i = 5 时一样的 标号标在第4 j ( n j 1 ) 层的顶点为2 ；标在第句+ 1 层的顶点为1 + 七； 标在第句+ 2 层的顶点为1 ；标在第句+ 3 层的顶点为k 当i 7 且i = 4 n + 3 ( n 2 ) 时，在这个分支上，根顶点和与之相邻的 主要顶点之间的路上的前7 个顶点( 从根顶点开始算起) 使用与i = 7 时一 样的标号标在第4 j ( n j 1 ) 层的顶点为2 ；标在第句+ 1 层的顶点为 七；标在第幻+ 2 层的顶点为1 ；标在第句+ 3 层的顶点为1 + k 按照以上 标号方式，把与根顶点相邻的主要顶点都上标号若还有的主要顶点未被标 号，转到步骤2 ) ，否则结束 七 + 12 七 + 七 七 七 23 o 0 0 七 + 1l 七 七 后 + + + 2 2 2 2 2 2 第3 章树 2 4 2 ) 选择一个与未被标号的主要顶点相邻的已标号的主要顶点作为新的 根顶点由步骤1 ) 可知该新根顶点的标号为1 + k ，其未标号的儿子从【0 ，4 1 中的整数选取未被使用的标号按步骤1 ) 同样的方式给所有与根顶点相邻 的未标号的主要顶点标号若还有的主要顶点未被标号，转到步骤2 ) ，否则 结束 所有的主要顶点及连接主要顶点的路上的顶点都按照上述方式标号后， 若树t 中还有未标号的点，则这些点组成的导出子图为最大度不超过4 的 森林由于连接主要顶点的路上的顶点的度至多为4 ，事实上，即使连接主要 顶点的路上的顶点的度都为4 ，按照上述方式标号后，与这些路上的顶点相 邻的未被标号的顶点仍然可以从【0 ，4 】中选取满足标号条件的标号由定理 3 1 2 可知，所有未被标号的点可以从【0 ，4 】中选取满足标号条件的标号定 理得证 口 定理3 4 5 若树t 的最大度 5 ，且p 是树，j l j 入( 丁；k ，1 ) = 一1 证明以t 中某个主要顶点作为根顶点，使其标号为1 + k ，我们从这个 根顶点开始对树t 的与根顶点相邻的所有主要顶点和连接这些主要顶点之 间的路上的顶点进行标号设与根顶点相邻的主要顶点在第i 层若i 为偶 数，则标在第2 n ( 2 n i ，n n ) 层的顶点为七( 若n 为偶) 或k + 1 ( 若n 为 奇) ；标在第2 n + l ( 2 n + 1 3 时，则在这个分支上，根顶点和与之相邻的主要顶点之间的路 上的前3 个顶点( 从根顶点开始算起) 使用与i = 3 时一样的标号，用下面 的方式标第3 层后的顶点 若，( 咖) = 3 + k ( v o 为这分支根顶点和与之相邻的主要顶点之间的路上 的第3 层的顶点) ， ( v ) = 1 ，当j = 4 n ；f ( v ) = 1 + k ，当j = 4 n + 1 ； ，( 秒) = 2 ，当j = 4 n + 2 ；，( ) = 3 + k ，当歹= 4 n + 3 ，n 1 若f ( v o ) = 1 + k ， f ( v ) = 1 ，当j = 4 n ；，( 口) = 3 + k ，当j = 4 n + 1 ； f ( v ) = 2 ，当歹= 4 n + 2 ；，( u ) = 1 + k ，当j = 4 n + 3 ，7 l 1 按照上述方式把所以与根顶点相邻的主要顶点标号 若还有未被标号的主要顶点，则选取一个与未被标号的主要顶点相邻的 已标号的主要顶点作为新的根顶点，按照同样的方式给与新的根顶点相邻的 未被标号的主要顶点标号重复这样的步骤直到所以的主要顶点都被标号 当所有的主要顶点及连接主要顶点的路上的顶点都按照上述方式标号 后，若树t 中还有未标号的点，则这些点组成的导出子图为最大度不超过 一1 的森林由于连接主要顶点的路上的顶点的度至多为一1 ，事实上， 即使连接主要顶点的路上的顶点的度都为一1 ，按照上述方式标号后，与 这些路上的顶点相邻的未被标号的顶点仍然可以从 0 ，一1 】中选取满足标 号条件的标号由定理3 1 2 可知：所有未被标号的点可以从 0 ，a 一1 】中选 取满足标号条件的标号所以定理得证 参考文献 参考文献 【1 】w k h a l e ，f r e q u e n c ya s s i g n m e n t ：t h e o r ya n da p p l i c a t i o n s j p r o c i e e e ，6 8 ，( 1 9 8 0 ) ，1 4 9 7 - 1 5 1 4 2 】t i z i a n ac a l a m o n e r i a ，a n d r z e jp e l c b ，r o s s e l l ap e t r e s c h i a ，l a b e l i n gt r e e s w i t hac o n d i t i o na td i s t a n c et w o j d i s c m a t h 3 0 6 ，( 2 0 0 6 ) ，1 5 3 4 - 1 5 3 9 3 】g j c h a n ga n dd k u o ，t h el ( 2 ，1 ) 一l a b e l i n gp r o b l e mo ng r a p h s j s i a mj d i s c r e t em a t h 9 ，( 1 9 9 6 ) ，3 0 9 3 1 6 。 【4 】j o h np g e o r g e , d a v i dw m a u r o ，g e n e r a l i z e dv e r t e xl a b e l i n g sw i t ha c o n d i t i o na td i s t a n c et w o j n c o n g r e s s n u m e r 1 0 9 ，( 1 9 9 5 ) ，1 4 1 1 5 9 5 】j o h np g e o r g e s ，d a v i dw m a u r o ，l a b e l i n gt r e e sw i t hac o n d i t i o na t d i s t a n c et w o j d i s c m a t h 2 6 9 ，( 2 0 0 3 ) ，1 2 7 - 1 4 8 6 】g j c h a n g ，d k u o ，t h el ( 2 ，1 ) 一l a b e l i n gp r o b l e mo ng r a p h s j s i a m j d i s c m a t h 9 ( 1 9 9 6 ) ，3 0 9 3 1 6 7 】p k j h a ，s k l a v z a r ，a v e s e l ，l ( 2 ，1 ) 一l a b e l i n go fd i r e c tp r o d u c to f p a t h sa n dc y c l e s j d i s c a p p l m a t h 1 4 5 ( 2 0 0 5 ) ，3 1 7 - 3 2 5 8 】d k o r z e ，a v e s e l ，l ( 2 ，1 ) l a b e l i n go fs t r o n gp r o d u c t so fc y c l e s j i n - f o r m p r o c e s s l e t t 9 4 ( 4 ) ( 2 0 0 5 ) ，1 8 3 - 1 9 0 【9 】j e r r o l dr g r i g g s ，r o g e rk y c h ，l a b e l l i n gg r a p h sw i t hac o n d i t i o na t d i s t a n c e2 j 】s i a mj d i s c m a t h 5 ，( 1 9 9 2 ) ，5 8 6 - 5 9 5 1 0 】j e r r o l dr g r i g g s ，x i a o h u at e r e s aj i n ，r e a ln u m b e rg r a p hl a b e l i n g s w i t hd i s t a n c ec o n d i t i o n s j s i a mj d i s c m a t h ，v 2 0 3 0 2 3 2 7 参考文献 【11 】j e r r o l dr g r i g g s ，x i a o h u at e r e s aj i n ，r e a ln u m b e rc h a n n e la s s i g n m e n t s f o rl a t t i c e s j p r o c i e e ei p d p s 0 5 ，( 2 0 0 5 ) ，2 3 8 1 【1 2 】f r e ds r o b e r t s ，w o r k i n gg r o u pa g e n d a ，d i m a c s d i m a t i a r e n y i w o r k i n gg r o u po ng r a p hc o l o r i n g sa n dt h e i rg e n e r a l i z a t i o n s ( 2 0 0 3 ) z