（运筹学与控制论专业论文）超欧拉图和带约束条件的频率分配的近似算法.pdf

摘要 本文主要研究图的生成欧拉子图和带约束条件的频率分配的近似算法。在第 二节，本文通过举例证明参考文献【4 】中给出猜想：每个最小度不小于4 的2 一连通 双无爪图g 包含一个最大度不大于4 的生成欧拉子图何是错误的：在第三节，对 于带有特定约束条件的所谓的六边形图的频率分配，本文给出了一个比较好的近 似算法。 关键词：欧拉图；双爪；频率分配：近似算法；多重着色 a b s t r a c t i nt h i sp a p e r ，t h em a i nw o r ki sa b o u ts p a n n i n ge u l e r i a ng r a p h sa n da p p r o x i - m a r i o na l g o r i t h mf o rc h a n n e la s s i g n m e n tw i t hc e r t a i nc o n s t r a i n t s i ns e c t i o n2 ，t h e c o n j e c t u r et h a te v e r y2 - c o n n e c t e db i c l a w - f r e eg r a p hg w i t h6 ( g ) 4h a sas p a n - n i n ge u l e r i a ns u b g r a p hhw i t hm a 话m 1 】md e g r e ea ( h ) 4i n 3 】i sa n s w e r e dt o t h en e g a t i v e i ns e c t i o n3 ，a na p p r o x i m a t i o na l g o r i t h mf o rc h a n n e la s s i g n m e n tw i t h c e r t a i nc o n s t r a i n t sf o rs o - c a l l e dh e x a g o ng r a p h si sg i v e n k e yw o r d s ：e u l e r i a ng r a p h s ；b i c l a w ；c h a n n e la s s i g n m e n t ；a p p r o x i m a t i o n ； m u t i c o l o r i n g 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：杏娘 日期叫年6 月孕日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：。是京匠导师签名爿纠爻 作者签名：砖强出 导师签皇乡纠八 ! ! 二竺羔二芏竺二2 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章程 中的 规定享受相关权益。匠意途塞握交卮澄卮! 旦圭生i 旦= 生；旦三生筮查。 作者签名：巷娘 日期叫年6 月4 日 导师签名毒孙又 帆中厶月严日 1 1 符号说明 第一节引言 i x i 集合x 中元素的个数 k ( g )图g 的连通度 l y e ( )图g 中点t j 邻域 k mm 阶完全图 i y ( g ) i 或i g l图g 的阶数 ( g )图g 的最大度 6 ( a ) 图g 的最小度 馆完全二部图 本文没有说明的术语和符号，请参看文献【1 】。 1 2 研究背景和现状 本文主要介绍了两方面的内容。一是与h a m i l t o n 问题有关的生成欧拉子图的 类反例，另一个是带约束条件的频率分配的近似算法。 一、h a m i l i o n 问题起源于一个关于十二面体的游戏，该问题历经百年，引起了 众多图论研究者的兴趣。1 9 5 2 年，d i r a c 首先给出了h a m i l t o n 图的度条件：g 为 钆阶图，n 3 ，若6 ( g ) n 2 ，则g 为h a m i l t o n 图。此后，很多关于图h a m i l t o n 性质的定理相继被证明，如o r e 等人在1 9 6 0 年给出了证明图是h a m i l t o n 图的经 典结论。l i 提出猜想：g 是连通的无双爪二部图，则存在实常数c ，当6 ( g ) c 时，g 是h a m i l t o n 图。但是h a m i l t o n 二部图必然是平衡的，所以l a i 和y a o 对上 述猜想作了修改，并且为了解决它提出：每个最小度不小于4 的2 一连通无双爪图 含最大度不大于4 的生成欧拉子图。本文第二节就其正确性展开探讨。 二、在通讯领域内最基本的问题就是在避免干扰的情况下把无线电频率分配 给用户。近十几年来，随着通讯及其相关行业的发展，用户需求的增多，无线电频 1 率显得越来越少，如何利用现有频率就变得至关重要。为了解决这个问题，提出所 谓的细胞概念。当重复使用距离是3 的时候文献【1 2 】给出了性能比为7 3 的算法， 本文就这个问题给出了性能比比7 3 更好的近似算法。 2 硕士学位论文 m a s t e r st h e s i s 2 1预备知识 第二节图的生成欧拉子图 日是g 的连通子图，顶点u 在日中的度记为妇( u ) 。图c h 是把图g 的连 通子图日收缩为一点而得到的多重图，并且使得 o h 到口v ( g h ) 在g h 中 的边与”到v ( h ) 在g 中的边数目相等。若图g 是连通的且其每个顶点的度都是 偶数，称图g 是欧拉图。如果一个图包含欧拉图作为其生成子图，则该图称为超欧 拉图。 爪是一个同构于甄3 的图。在两个爪的三度点之间连一条边得到的图称为双 爪( 见图1 ) 。我们称双爪中两个四度点之间的边为其中心边。显然，每个双爪有且 只有一条中心边。如果图g 不包含双爪作为其点导出子图，称g 为无双爪图。二 部图g = ( ，) 是平衡的，如果i l = 1 l 。 图1 双爪和其中心边伽 l i 【5 】猜想存在一个实数c 使得每个6 ( g ) c 的无双爪二部图g 是h a m i l t o n 图。 l a i 和y a o 在文献【5 】中发现若一个二部图g 是h a m i l t o n 图，那么图g 一定是平 衡的。所以l i 【5 】5 的猜想应修改为：存在一个实数c 使得每个6 ( g ) c 的无双爪平 衡二部图g 是h a m i l t o n 图。同时，为了解决上述猜想他们提出了下述猜想。 猜想2 1 1 ( 【4 】) 设g 是2 一连通无双爪图，若6 ( g ) 4 ，则g 舍有生成欧拉 子图日且a ( h ) 4 下面我们将举例证明猜想2 1 1 是不正确的，无论是平衡二部图或是非二部图， 都存在满足条件无限2 一连通无双爪图g 不包含生成欧拉子图h 使得a ( h ) 4 。 3 2 2反例 本节我们给出猜想2 1 1 的一类反例。p e t e r s e n 图的每个项点u 用完全图 替换并且使与 关联的边分别和中不同的顶点关联，所得之图记为g m ( 见图 2 ) 。 命题2 2 1 若m 5 ，则图g m 是猜想2 1 1 的反例 证明：设礁( i = 1 ，2 ，l o ) 为的l o 个拷贝。当7 7 l 5 时，易证g m 是 3 一连通图，且石( g m ) 4 。令e x = e = 牡 ：“， y ( 砩) ) ，e 2 = e = 伽：乱 y ( 礁) ，口y ( 礁) ，i j ，所以e ( g m ) = e xue 2 ，并且毋n 岛= 圣 现在我们来证明g m 中不含双爪。假设g m 中含有中心边为牡口的双爪 日。若边删e x ，则m 6 。设) n v ( h ) = 乱l ，锄，u a ，”，n ( v ) n v ( h ) = 口，v 2 ，地，牡) 。因为礁是完全图，则在( 牡) ny ( ) ，( 钐) nv ( h ) 中都至少存在 一点，不妨设为让1 ，u 1 ，使得让l 1 礁，即可得u l v l e ( 日) ，但是这与u v 是日 的中心边矛盾。若伽易，那么仳的邻点除u 外都在某个中，所以它们彼此 相邻，也和伽是日的中心边矛盾。所以日不是g 。的双爪，这与假设矛盾。 下证g m 不含生成欧拉子图。反证法。若日是g m 生成欧拉子图。我们把礁 收缩为一点，则g m 就收缩为p e t e r s e n 图。显然，g m 中含有最大度不大于4 的生 成欧拉子图当且仅当p e t e r s e n 图含有最大度不大于4 的生成欧拉子图。但是这与 p e t e r s e n 图不含这样的图矛盾。命题得证。 口 若n = 1 0 m ，则g m 是3 一连通图，6 ( g m ) = 仇一1 = 靠一1 。由命题2 2 1 知： 对任意的常数c ，存在3 一连通图g ，满足6 ( g ) c ，但是图g 不含最大度不大于4 的生成欧拉子图，所以对于非二部图猜想2 1 1 是错误的。那么对于二部图，猜想 2 1 1 i e 确的吗? 事实上，当n 3 m ，m 4 时，完全二部图n 就是猜想2 1 1 的 反例( 其证明过程类似于命题2 2 2 ) 。命题2 2 2 将证明对于2 连通无双爪平衡二 部图，猜想2 1 1 仍然不成立。 设g i = ( l ，) g = 1 ，2 ) 是n 的两个拷贝，i k i i 芦m ，i l = n ，i = 1 ，2 ， g m ，n = ( ，) 是平衡二部图，其中= v n u 2 u 仳，也】，= 2 u k l u u l ， 4 忱) 。任取z l ，z 2 y n ，玑，抛l ，d l ，a 2 y 2 1 ，b l ，b 2 。令露( g m 。n ) = e ( g 1 ) u e ( g 2 ) u t | l 仇，t | l 抛，t 上2 u l ，u 2 v 2 ，u 1 y l ，u l 抛，t 正l x l ，t 正1 勋，v 2 b a ，t j 2 6 2 ，u 2 a l ，u 2 a 2 ( 见图3 ) 。 命题2 2 2 若礁3 m ，m 4 ，则图g m 。n 也是猜想2 1 1 的反例。 证明：显然，g m ，n 是2 一连通平衡二部图，6 ( g m ，n ) 4 。现在我们来证明g m ，n 无双爪。 假设g 巩n 含双爪日，其中日的中心边为删。若伽e ( g 1 ) 。设( 牡) = ，“l ，乱2 ，地 ，( u ) = t l ，v l ，v 2 ，抛 。因为g l 笺k m ，n ，让l 1 曰( g m ，n ) ，这与是 双爪矛盾。同理可证，当伽e ( c 2 ) 也可得到矛盾。所以钍uge ( g 1 ) ue c c 2 ) ，故 t l t ， t i l 1 ，t 上1 吨，u 2 v l ，坳忱，r a y l ，i ) 1 抛，u l x , l ，u l t , 2 ，v 2 b l ，忱6 2 ，u 2 a l ，u 2 a 2 。由图的对称 性可知，我们只需对乱” 让1 口l ，让1 吨，u l x l ) 讨论即可。 若删= 缸l u l ，不失一般性，设u = 牡l ，口= u l ，则( 让) = 1 3 1 ，吨，x l ，z 2 ，( u ) = 箩1 ，珈，u l ，乱2 ) 。因为z 1 可1 ，z 2 可1 e ( v r e , n ) ，这与u l u l 是日的中心边相矛盾。因 为u l 乱2 e ( g , n ，n ) ，所以让l 也不可能是日的中心边。故日的中心边u 只能是 牡l z l ，不妨设让= u l ，口= z 1 ，则y ( u 1 ) = z 1 ，$ 2 ，仇，忱 ，n ( x x ) = 1u t 上1 ) 。又因 为l z 2 e ( g m ，仆) ，这与u l z l 是日的中心边矛盾。所以g ( m ，n ) 不含双爪。 下证g ( m ，n ) 不含最大度不大于4 的生成欧拉子图。否则，若日是，n 的最 大度不大于4 的生成欧拉子图。因为 乱l 忱，抛u l 是g ( m ，n ) 的一个二边割，所以 “1 忱，忱t l e ( 日) 。显然，如( 乱1 ) ，d h ( 1 3 1 ) 都是偶数，且若d h ( 1 1 1 ) = 妇( 1 ) = 2 ，则 可知乱1 t j lge ( 日) 。 令r 为删去抛，t j 2 和g 2 中所有顶点，同时收缩边乱1 t j l 所得之图。风为 e ( h ) n s ( r ) 在f 上的边导出子图，那么皿是r 的生成欧拉子图且( 皿) 4 设y ( 既) nv n 中的顶点的度的平均值为z ，则 当妇( u 1 ) = 妇( 1 3 1 ) = 2 或妇( “1 ) = 妇( u 1 ) = 4 时， 一 m z e 2 n e ：净。丝6 ， 5 硕士学位论文 m a s t e r st h e s i s 其中 c - 2 妇d h ( ( t u 1 1 ) ) = ：妇d h ( ( v 1 1 ) ) = ：4 2 ； 当d n ( u x ) = 4 ，d h ( v 1 ) = 2 时， 。 m z 2 佗一2 = 令z 2 n - 2 6 m - - 2 5 ： m竹l 当d h ( u t ) = 2 ，d hv 1 ) = 4 时， m z 一2 2 n ：兮z 2 n + 2 6 z 这都与( 矾) 4 矛盾。故命题得证。 口 c a t l i n 在文献【2 】引入了坍缩图概念。设o ( g ) 表示g 中奇度点的集合。若 v ( c ) 的任意偶子集冗，g 都包含连通的生成子图r 使得o ( r r ) = 冗，则称g 是 可坍缩图。因此，若g 是可坍缩图，则g 必然是超欧拉图，所以g 是2 一连通的。 l a j 和y a o 【4 】4 证明了最小度不小于5 的无双爪连通二部图是可坍缩的。当g 是超欧拉图时，g 可能不包含最大度不大于4 的欧拉子图日。我们注意到g 磊n 是 最小度等于4 的无双爪2 一连通平衡二部图。令嚷n = g m ，n - u l v l + u l a l ，v l b l ， 易验证嚷，n 是无双爪4 一边连通平衡二部图且6 ( g ：；l ，竹) 4 。类似于命题2 2 2 的 证明，我们可以证明戗。不含有最大度不大于4 的生成欧拉子图。由此我们猜想 是不是每个最小度不小于5 的无双爪3 一边连通平衡二部图含有最大度不大于4 的 生成欧拉子图? 6 图2 g 5 仳l呦 嘲兰0：漾 塞 口lt 匕 7 g o 图3 g m ，n 第三节带限制条件的频率分配的近似算法 3 1预备知识 随着无线电通讯及相关服务行业的发展，无线电波谱变得越来越少，所以充分 利用现有的无线电波谱就显得至关重要。为了解决这个问题，我们提出了细胞概 念。通过把服务区域划分成小的区域，这些小的区域被我们称作细胞。经过划分以 后，如果两个细胞之间的距离足够远，那么我们就可以在这两个细胞中就可以分配 相同的频率。由于需求的急剧增长，在保证干扰在可接受的水平下，充分利用这种 重复分配就变得非常迫切。细胞网络就是指一个点赋权图，顶点代表细胞，边代表 频率之间互相干扰。顶点的权代表在这个细胞内所需要的频率的数量。基站不仅要 被分配给所需数量的频率，还要满足一定的约束条件。特别地，分配给同一个或距 离相近的细胞的频率，如果两个频率相差太小就会产生干扰。这些干扰可以用整数 集表示：c o c 1 c 2 ，这里q 代表当两个距离为i 的细胞的任何两个频率之 间最小间隔。我们称c o 为c o - s i t e 约束，其他约束称为i n t e r - s i t e 约束。为了尽可能 的利用无线电波谱，频率分配的目标是使分配的跨度最小，也就是使最大的频率与 最小频率直接的间隔最小。 当c o = c l ，c 4 = o ( i 1 ) 时，频率分配问题就转化为对图的多重着色问题，这 个问题虽然已经被广泛研究，但是对很多图来说仍然是n p 困难的，包括被用来代 表细胞网络图的所谓的六边形图。六边形图是三角形网格图的子图( 见图4 ) 。这里 每个细胞都是正六边形，干扰只在相邻的两个细胞之间产生。在文献【l o 】中给出了 完全图、二部图，奇圈与外平面图频率分配的最优算法。对六边形图，文献【l o ，1 1 】 给出了性能比为；近似算法。当c o = c l = c 2 = 1 ，c 4 = o ( i 2 ) 时文献【1 2 】给出了 性能比为；的近似算法。本文主要研究c o = c 1 e a ，c = o ( i 2 ) 时的情况。 设s 是y 的一个子集，若s 中任意两个顶点在g 中不相邻，则称s 为g 中 的一个独立集。图g 的一个团是指y 中的一个子集s ，使得g 旧是完全图。 8 图4 一个约束图g 是一个有序五元组( v e ，c o ，c l ，c 2 ) ，其中h = ( k e ) 是一个 图，龟代表顶点之间距离为 时任意两个频率之间的最小问隔。一个约束权图是 有序对( g ，凹) ，其中g 是约束图，t i j 是由顶点导出的权向量。伽中对应的每个顶 点的分量表示顶点所需分配的频率的数量。 对约束权图( g ，) ( 这里g = ( ke ，c o ，c l ，c 2 ) ) 频率分配，就是把代表频率的 非负整数集分配给g 的顶点，并且满足下列条件： i ，( 乱) l = 加( 仳)( 仳y ) ， i ，( “) ，j f ( v ) 兮l i j l e l ( d ( u ，u ) = 1 ) ， i ，( u ) ，j f ( v ) 兮i i 一歹l c 2 ( d ( 钍，u ) = 2 ) ， i ，歹厂( 让) ，i 歹专l i 一歹i c o( 札y ) 频率分配的最大频率与最小频率的问隔称为频率分配的跨度，记为s ( ，) 。任意 的算法对( g ，伽) 频率分配的最小跨度记为s ( g ，t l j ) 。若( g ，伽) 的频率分配厂使得 b ( f ) = s ( c ，叫) + e ( 1 ) ，我们称，是最优的。若某算法产生的频率分配，使得 s ( f ) 七s ( g ，i 5 ) + e 0 ) ，则称该算法的性能比为k 。g 的多重着色是指把g 的每 一个顶点都涂一种或多种颜色，使得每一个顶点每种颜色恰好出现一次，并且相邻 顶点的颜色集不相交。 9 3 2主要结论 定义3 2 1 设g 是一个图若如( u ， ) = 2 ，连结伽，则所得之图h 称为g 的平方图 引理3 2 2 g = ( ve ，c 0 ，c l ，c 2 ) ( g o c l c 2 ) 是约束图，i g l = 仡若 g 竺k i ，6 ，加是权向量且似( i ) = k ( k n + ，i = 1 ，2 ，礼) ，则图( g ，1 ) ) 上频率分 配的跨度至少为7 k c 2 一c 2 证明：若我们减弱约束条件，假设c o = c l = c 2 ，则( g ，w ) 的频率分配厂对距 离为2 的顶点仳，u ，i l j f i c 2 = c 1 = c 0 ( i ，( 牡) ，j ，( u ) ) 若d ( 牡， ) = 2 ，连接 t l ， ，所得之图日为g 平方图。( g ，叫) 的频率分配，在日中满足： t ，( 牡) ，歹，( 钉) 兮i i 一歹i c l ( d n ( u ， ) = 1 ) ， i ，j ，( 牡) ，i 歹兮i i 一歹l c o( 仳y ) 故厂是对g 是平方图h 的多重着色。因为h 竺k 7 ，而坼的任意多重着色都需 要至少7 k c 2 种颜色。所以( g ，叫) 的频率分配的跨度至少是7 k c 2 一c 2 。 口 引理3 2 3 g = ( k e ，c o ，c 1 ，c 2 ) ( c 0 = c l = 2 c 2 ) 是约束图，i g i = 他若 g 望风，6 ，铷是权向量且w ( i ) = k ( k n + ，i = 1 ，2 ，7 ) ，则图( g ，叫) 上频率分 配的跨度至少为8 k c 2 一c 2 图5 证明：首先，我们来证明可以把波谱【o ，c 2 ，2 c 2 ，8 k c 2 一c 2 】分配给( g ，伽) 。 定义频率分配，为： 1 0 o ，2 c 2 ，2 ( k 一1 ) c 2 卜_ v l 2 七c 2 ，2 ( k + 1 ) c 2 ，( 4 七一2 ) c 2 ) 一也 【( 2 七+ 1 ) c 2 ，( 2 k + 3 ) c 2 ，( 4 七一1 ) m 一地 4 k c a ，( 4 k + 2 ) c 2 ，( 6 七一2 ) c 2 ) 一魄 ( 4 七+ 1 ) c 2 ，( 4 k + 3 ) c 2 ，( 6 七一1 ) c 2 ) 一1 ) 5 6 k c 2 ，( 6 k + 2 ) c 2 ，( 8 七一2 ) c 2 ) 一 ( 6 七+ 1 ) c a ，( 6 k + 3 ) c 2 ，( 8 毛一1 ) c 2 ) _ 嘶 容易验证分配厂满足约束条件。 现在考虑用【0 ，c a ，2 c 2 ，8 k c a 一2 c 21 对( g ，) 进行频率分配。因为在分配频 率时，与点的顺序无关，所以我们可以从波谱中任选k 个频率分配给口l ，不失一 般性，不妨设这后个频率为 ，y l ，仇，饥 且满足i 乍一竹l c o = c l = 2 c 2 ( 1 l ，歹七，i j ) 。因为研与g 的其它顶点都相邻，所以在【0 ，c 2 ，2 0 z ，8 k c 2 2 c 2 】 中与7 i 相邻的两个频率以及都不能分配给其它顶点，并且 7 1 ， 2 ，饥) 中任 何两个频率在【0 ，c 2 ，2 0 z ，8 k c 2 2 c 2 】中最多只有一个频率与它们都相邻。故在 【0 ，o z ，2 c 2 ，8 k c 2 2 c 2 】中至少有2 七个频率不能分配给其它顶点。由g 垡跹，6 知，g 中任意两点之间的距离最长为2 ，故分配给g 的任何两个频率均不相同， 所以要对g 进行频率分配至少还需要6 七个频率，但在波谱中现在至多只有6 七一1 个频率可用。由鸽巢原理，必有一频率被分配给两个顶点，矛盾。 口 定理3 2 4 g = ( k e ，c o ，c 1 ，c 2 ) 是约束六边形权图，l g i = 佗，t i j ( i ) = k ( k 十，i = 1 ，2 ，仃) 若c o = c l c 2 ，则对( g ，t ) ) 的频率分配存在线性时间的性能 比为等学的近似算法 证明：令8 = m a x c 1 ，2 c 2 ，a o = o ，s ，2 s ，( 七一1 ) s ) ，a 1 = ( 七+ 1 ) s ，( 七十 2 ) s ，2 k s ，a 2 = c 2 ，s + c a ，( k - 1 ) s + c 2 ，a s = k s + c 2 ，( 七十1 ) s + c 2 ，( 2 七一 1 ) s + c 2 ；b o = ( 2 七+ 1 ) s + c a ，( 2 k + 2 ) s + c 2 ，3 k s + c 2 ，b 1 = ( 3 七+ 1 ) s + c 2 ，( 3 凫+ 2 ) s + c 2 ，4 k s + c 2 k 岛= ( 2 七+ 1 ) s ，( 2 k + 2 ) s ，3 k s ，b a = ( 3 七十 2 ) s ，( 3 七+ 3 ) s ，( 4 七+ 1 ) s ) 。任意一个六边形图都是某个三角形网格图的子图， 设日是包含g 的最小的三角形网格图( 见图6 ) 为了方便，我们把日中的顶点标 号为，i 代表行，歹代表列。定义频率分配，为： 1 1 图6 a t 一i = 8 k ，j = 4 k 十tt = 0 ，1 ，2 ，3 b t 叫仇ji = 8 k + 1 ，j = 4 k + tt = 0 ，l ，2 ，3 a 件l 叫i = 8 k + 2 ，j = 4 k + tt = 0 ，1 ，2 ，3 b + 1 叫忱，i = 8 k + 3 ，歹= 4 k + tt = 0 ，1 ，2 ，3 a t + 2 叫v o i = 8 k + 4 ，歹= 4 k - t - tt = 0 ，l ，2 ，3 玩十2 一l = 8 k + 5 ，歹= 4 k + t t = 0 ，l ，2 ，3 a 件3 _ 仇，i = 8 k + 6 ，歹= 4 k + tt = 0 ，l ，2 ，3 b 件3 叫地fi = 8 k + 7 ，歹= 4 k + tt = 0 ，l ，2 ，3 其中t + i ( i = l ，2 ，3 ) 是关于m o d3 的。 正确性：显然，同一个顶点的任意两个频率相差至少为s c o ，故满足c o - s i t e 约束。 考虑相邻的顶点忱，吻。设饿，分别是分配给优，的频率。若眈，吻在不同 行中，显然有i 竹一l 5 c l ；若哦，在同一行中，我们是按a o ，a 1 ，a 2 ，a 3 或 ，b l ，玩，b 3 的顺序循环分配给各行上的每个顶点，所以有h 一l s c l 现在考虑距离为2 的顶点忱，叼，乍，分别为其频率。若忱，吩在相邻或同一 行中，容易验证i 佻一l 芝地_ 【c 2 ，s c 2 】c 2 ：若挑，吻在不同行中，不失一般 性，设仇是m 行的第4 七个顶点，则吩可能是m 一2 行是第4 k 一2 ，4 k 一1 ，4 七 1 2 硕士学位论丈 m a s t e r st h e s i s 个顶点或m + 2 行的第4 七，4 七+ l ，4 七+ 2 个顶点，不论是何种情况都可以验证有 i 竹一l r a i n c 2 ，s c 2 】- c 2 ，故满足i n t e r - s i t e 约束。 所以我们得到了h 的频率分配。如果把，限制在g 上，则扫为g 的频率分 配。 跨度：因为扫为g 的频率分配，所以其跨度为( 4 七+ 1 ) s 。由引理3 2 2 知，该 算法的性能比为幽7 k c 2 。 口 推论3 2 5 ( g ，t u ) 是约束六边形权图，l g l = n ，伽( i ) = k ( k n + ， = 1 ，2 ，他) 若c 2 c o = c 1 2 c 2 ，则有一个线性时间的性能比为1 + 表暑的算 法。 证明：因为s = m a x e l ，2 c 2 = 2 c 2 ，按照定理3 2 4 算法，频率分配的跨度为 ( 4 k + 1 ) s = 2 ( 4 k + 1 ) c 2 。由引理3 2 3 知，算法的性能比为2 ( 4 8 k 硒+ 1 ) c 2 = 1 - 1 - 去暑。口 定理3 2 6 ( g ，w ) 是阶数为n 约束六边形权图，w ( i ) = k ( k n 十，i = 1 ，2 ，他) 若c o 号c 1 = c 2 ，则对( g ，叫) 存在线性时间的性能比为；的算法 证明： 令a o = o ，2 c 2 ，2 ( 七一1 ) c 2 ，a i = 2 k c 2 ，2 ( k + 1 ) c 2 ，一，( 4 七一 2 ) c 2 ) ，a 2 = c 2 ，3 c e ，( 2 尼一1 ) c 2 ) ，a 3 = ( 2 七+ 1 ) c 2 ，( 2 k + 3 ) c a ，( 4 七一1 ) c 2 ) ；b o = 4 k c 2 ，( 4 k + 2 ) ，( 6 k - 2 ) c 2 ，b 1 = 6 k c 2 ，( 6 k + 2 ) c 2 ，( 8 k 一2 ) c 2 ) ，岛= ( 4 七+ 1 ) c 2 ，( 4 k + 3 ) c 2 ，( 6 忌一1 ) c 2 ，b 3 = 【( 6 七十1 ) c 2 ，( 6 k + 3 ) c 2 ，( 8 七一1 ) c 2 ，贝u 按 照定理3 2 4 对图( g ，删) 的频率分配的跨度至多为( 8 七一1 ) 0 2 ，由引理3 2 2 知其性 能比为亍8 。 口 注意，当c o = c 1 = c 2 时，上述算法给出的性能比为；，这要比文献【1 2 】给出 的性能比为；算法要好很多。 9 1 j 3 2 7 g = ( ve ，2 ，2 ，1 ) 是约束六边形图，i v i = n ，叫( i ) = 2 g = 1 ，2 ，佗) ，则用上述算法对( g ，加) 进行频率分配的的跨度为1 8 ( 见图7 ) 1 3 图7 1 4 参考文献 【1 】j a b o n d y , u s rm u r t y , g r a p h st h e r o yw i t ha p p l i c a t i o n s ，m a c m i l l a np r e s s l t d ，n e wy o r k ，1 9 7 6 【2 】p a c a t l i n ，ar e d u c t i o nm e t h o d t of i n ds p a n n i n ge u l e r i a ns u b g r a p h s ，j g r a p h t h e o r y1 6 ( 1 9 8 8 ) 2 9 - 4 4 【3 】h 一j l a i ，x y a o ，e r r a t u mt oc o l l a p s i b l eb i c l a w - f r e eg r a p h s 【d i s c r e t em a t h 3 0 6 ( 2 0 0 6 ) 2 1 1 5 2 1 1 7 1 ，d i s c r e t em a t h 3 0 7 ( 2 0 0 7 ) 1 2 1 7 4 】h - j l a i ，x y a o ，c o l l a p s i b l e b i c l a w - f r e eg r a p h s ，d i s c r e t em a t h 3 0 6 ( 2 0 0 6 ) 2 1 1 5 2 1 1 7 5 】h l i ，p r o b l e ma 1 5 ，m e m o r a n d u m1 0 7 6 ，u n i v e r s i t yo ft w e n t e ，e n s c h e d e ，1 9 9 2 ， p 1 1 9 【6 】a g a m s t ，s o m el o w e rb o u n d sf o rac l a s so ff r e q u e n c ya s s i g n m e n tp r o b l e m s ， i e e et r a n s v e h t e c h n 0 1 3 5 ( 1 ) ( 1 9 8 6 ) 8 - 1 4 7 】s n t g e r k e ，c o l o u r i n gw e i g h t e db i p a r t i t eg r a p h sw i t hac o - s i t ec o n s t r a i n t ， d p h i lt h e s i s ，o x f o r d ，2 0 0 0 【8 1 8j j a n s s e n ，k k i l a k o s ，a d a p t i v em u l t i c o l o u r i n g ，c o m b i n a t o r i c a2 0 ( 1 ) ( 2 0 0 0 ) 8 7 - 1 0 2 【9 lc m c d i a x m i d ，b e d ，c h