摘要：图的L(2,1)标号是频率分配问题的图论模型。在E.Dijkstra 最短路问题的基础上，将Floyd 算法用于求任意两节点间的最短距离，同时结合网络最大流Ford-Fulkerson 算法，提出了一种能够有效求解一般图的L(2,1)标号的算法。其基本思想是从任意一个节点出发，对所有未检查的顶点按L(2,1)标号准则进行标号，完成一次标号后，再从其中选出一个标号值最小的节点加入已检查节点集，重复上述标号过程，直到未标号节点集为空，于是该图的标号完成，所用最小标号便是近似最优解。
　　
　　关键词: L(2,1)标号问题 最小标号 频率分配
　　
　　1 前言
　　1980 年,Hale[1]在研究频率分配问题时引入了图的顶点染色模型。所谓频率分配问题是指对每个发射台分配合适的频率,使得“邻近”的发射台占用不同的频率而“非常邻近”的发射台必须占用有一定间隔的频率,以消除干扰,并且所分配的最小频率和最大频率之间的间隔要最小。在1992 年, Griggs 和Yeh[2]用图的顶点表示发射台,距离为2 的点视为“邻近”,而距离为1的点视为“非常邻近”,频率用非负整数表示,从而提出了图的L(2,1) ?标号问题。图G 的L(2,1) -标号定义为一个映射 f :V(G)→{0,1,2,??} ,满足对任意两个顶点x, y ,如果d(x, y) = 1 ,则| f (x) ? f ( y) |≥ 2 ,如果d (x, y) = 2 ,则| f (x) ? f ( y) |≥ 1。若一个 L (2,1) ? 标号中的所有值都不超过整数k ,则称之为k ? L(2,1) ? 标号。图G的L(2,1) ? 标号数,记作λ2,1(G) ,是使得图G存在k ? L(2,1) ? 标号的最小整数k 。Griggs 和Yeh[2]证明了对最大度Δ的一般图有λ ≤ Δ2 + 2Δ，Chang和Kuo[3]证明了对任意图有λ ≤ Δ2 + Δ，Kral 和Skrekovski[4]又稍作改进，证明了对任何Δ ≥ 2的图有λ ≤ Δ2 + Δ ?1。但关于讨论λ 接近最优的L(2,1)标号的有效算法却不多。由于频率设置问题中常常是大型图的标号问题，所以我们只要求的近似最优解就已满足需要，于是在E.Dijkstra 最短路问题[5]的基础上，我们提出了一种求解图的L(2,1)标号的有效算法。
　　2 算法描述算法思想：该算法通过分步方法求出最小标号数。将所有节点分为已检查节点集和未检查节点集，从未检查节点集中选取最小标号的节点加入到已检查节点集中，同时检查未检查节点集中节点的标号值与该节点是否满足L(2,1)标号条件，若不满足则将其更新，如此下去直到未检查节点集为空集为止，此时所有节点都已标号。
　　该算法实质上也是一个贪心算法，我们每次对节点标号都以最小满足条件的值去标号，故该算法可以找到一个近似最优解。以下为具体的算法过程：
　　Step1: 输入邻接矩阵 D，用Floyd[6]子程序求出任意两节点间的距离的距离矩阵A;
　　Step2: 初始化S = ?，S = [1, 2,…m]，S和S分别存储已检查节点和未检查的节点；1 p = [0,0…0]， 2 p = [0,0…0]， 1 p ， 2 p 分别存储已检查节点的标号值和未检查节点的标号
　　3 实例说明已知某一模型图 G(V,E)如下图所示，我们用该算法对其进行L(2,1)标号过程检查节点的标号如下：（我们从1 开始标号的）首先任取一个顶点标号为1(这里我们取顶点1)，同时按L(2,1)标号准则给其他顶点标号；将1 加入已检查节在所有未检查节点中取标号最小的节点6，将其加入到已检查节点集，再按L(2,1)标号准则更新剩下的未检查节点的标号；在所有未检查节点中取标号最小的节点11，将其加入到已检查节点集，再按L(2,1)标号依次进行下去，直到未检查节点集为空，此时标号结束，如上图。
　　经过这几次的不断更新节点的标号值后我们得到了改图的一个近似最优解为10，该图的最大度数为6，根据Kral 和Skrekovski[4]证明的对任何Δ ≥ 2的图有λ ≤ Δ2 + Δ ?1,则λ ≤ 41，另外，还有一个下界为λ ≥ Δ +1，则有λ ≥ 7，显然11 与下界很接近了，而且由基于遗传算法的图的L(2,1)标号算法的研究[7]中求得的最优解为8，可知该近似最优解以满足我们的实际需要了。
　　4 总结
　　本文提出的最小标号算法能以O(n2 )的复杂度求得L(2,1)标号问题的近似最优解，而且只要将step3 和step5 中的选择条件稍微改进下，就可得到L(3,2,1)等L(h,d,..)的标号问题的解。适合于实际解决频率设置问题。

文章由中国论文指导网为您分享，本论文网是专业的经济论文网，如需转载请保留一个链接：http://www.lunwen39.com/post/jingji.html

5 参考文献
[1]. Hale W K.Frequency assignment,theory and applications[J].Proc IEEE,1980,68:1497-1514.
[2]. Griggs J R,Yeh R K.Labeling graphs with a condition at distance two[J].SIAM J DiscreteMath,1992,5:586-595.
[3]. Chang G J,Kuo D. The L(2,1)-labeling problem on graphs[J].SIAM J DiscreteMath ,1996,9:309-316.
[4]. Kral D ,Skrekovski R .A theory about the channel assignment problem[J]. SIAM J DiscreteMath ,2003,16:426-437.
[5]. 郑宗汉，郑晓明.算法设计与分析.[M]北京，清华大学出版社.2005.120-125.
[6]. 薛秀谦，朱开永.运筹学.[M]徐州，中国矿业大学出版社.2002.205-206.239-240.
[7]. 储育青，齐义飞，肖立顺，陈晖敏，石玉文.基于遗传算法的图的L(2,1)标号算法的研究，已投稿.