若干联图的L（2，1）-边染色算法*

朱利娜，李敬文，孙帅

兰州交通大学电子与信息工程学院，甘肃 兰州 730070

Hale（1980）曾用图论中T-coloring 的概念来描述和研究过频道分配问题，最先把该问题转化为图的着色问题。Roberts（1991）提出为了避免干扰使相隔很近的发射台分配的频率至少相差为2，相隔较近的使用不同的频率，作为频率设置问题的一个变形。此后，Griggs et al.（1992）将此问题转化为不同于T-coloring的另一种着色问题并引入了L(2，1)-标号，其中图G的L(2，1)-边标号等价于其线图L(G)的L(2，1)-标号。

截止到目前，对L(2，1)-边标号的研究主要集中在特殊图上，如路、圈、轮、完全图、完全二部图及树（陈琴，2006）已有相关结论。本文利用人工蜂群（ABC，artificial bee colony）算法（Aslan，2020）的思想设计针对随机图的L(2，1)-边染色算法（下文中用CK-ABC 边染色算法表示）。通过分析实验数据，发现了三类联图的染色特性，分别C3↑Pn↑Sm，Cn↓Sm和Cn↑Sm定义这三类联图，进而给出相应的定理和证明。

1 预备知识

本文使用G(p，q)表示具有p个顶点q条边的无向简单图，当p=q时即为本文研究的单圈图，使用E(G)，F(E)，d(e1e2)和∆(G)分别表示图的边集合、边染色集合、边e1，e2之间的距离和最大度。在不特殊说明的情况下，本文将∆(G)简写为∆.

定义1 对于图G(p，q)（简写为G），设m是非负整数，如果存在映射f：V(G) →{0，1，2，…，m}且满足

其中v1，v2∈V(G)，则称f是图G的一个L(2，1)-标号。

定义2 对于图G(p，q)（简写为G），设m是非负整数，如果存在映射f：E(G) →{0，1，2，…，m}且满足

其中e1，e2∈E(G)，则称f是图G的一个L(2，1)-边标号。

本文将L(2，1)-边标号统称为L(2，1)-边染色。另外定义G的所有的L(2，1)-边染色中的最小的值m为图G的L(2，1)-边色数，记为λ′2，1(G)，简写为λ′(G).如无特殊说明，本文使用f表示一个最优的L(2，1)-边染色的映射。

定义3C3↑Pn↑Sm：设C3的顶点集为{u1，u2，u3}，Pn的顶点集为{w1，w2，…，wn}，Sm的顶点集为{v0，v1，…，vm}，C3↑Pn↑Sm是指将路Pn的其中一个端点w1黏接到C3的一个顶点u1，另一个端点wn黏接到星图Sm的中心节点v0后得到图1。

图1 C3 ↑Pn ↑Sm示例图Fig.1 The example of C3 ↑Pn ↑Sm

定义4Cn↓Sm：设Cn的顶点集为{u1，u2，…，un}，Sm的顶点集为{v1，v2，…，vm}.Cn↓Sm是指将星图Sm的中心节点v1邻接到Cn的任何一个顶点后得到图2（a）。

图2 Cn ↓Sm示例图Fig.2 The example of Cn ↓Sm

定义5Cn↑Sm：设Cn的顶点集为{u1，u2，…，un}，Sm的顶点集为{v0，v1，v2，…，vm}.Cn↑Sm是指将星图Sm的中心节点并接到Cn的任一顶点上得到图2（b）。

2 CK-ABC边染色算法

2.1 算法思想

1）将图G转化为相对应的线图L(G)。

2）对图的邻接矩阵进行预处理，求得距离矩阵、度序列等属性。

3）用CK算法求出次优解f′，初步确定最大色数maxColor。

4）采用人工蜂群算法的思想进行寻优。

5）输出求得的最优解f.

2.2 CK-ABC算法

初始化函数：

Input：图G(p，q)的邻接矩阵M.

Output：对应线图L(G)的邻接矩阵LM.

Step 1.令LM为q×q阶矩阵，所有元素置0。

Step 2.若图G中边ei、ej共点，则置LM[i][j]= 1，LM[j][i]= 1，其中0

Step 3.返回LM.

CK-ABC算法：

Input：图G(p，q)线图的邻接矩阵LM.

Output：图G(p，q)的L(2，1)-边染色矩阵RM.

Step 1.按照初始化函数得到图G线图的邻接矩阵LM.

Step 2.对LM进行预处理，得到其距离矩阵、点边数量和最大度等属性。

Step 3.采用孙帅等（2021）的Algorithm1 求出次优解f′及对应的最大色数maxColor。若maxColor 大于∆+1转Step 4；否则f′即为理论最优解，转Step 9。

Step 4.初始化蜜源总数SN、蜜源访问次数上限limit以及最大迭代次数MCN，随机生成初始蜜源并计算其适应度。

Step 5.如果迭代次数未达到MCN，则转Step 6；否则转Step 9。

Step 6.如果蜜源访问次数没有超过limit，则转Step 7；否则重新生成该处蜜源，并将其访问次数置0。

Step 7.采用轮盘赌的方式选择蜜源x进行变异操作，得到新蜜源x′，计算适应度并与x比较，择优保留适应度较大的蜜源并增加其访问次数。

Step 8.转Step 5。

Step 9.将L(G)的点染色结果转化为图G的边染色结果，算法结束。

3 实验结论及证明

3.1 数据统计

我们将CK-ABC 边染色算法应用于16 个点以内的单圈图，各点数下λ′(G)和图的染色数∆+k之间的关系如表1所示。

表1 16个点以内单圈图的L(2，1)-边染色统计1）Table 1 L(2，1)-edge coloring number of unicyclic graphs within 16 points

3.2 主要结论

通过对表的实验数据分析总结，得出以下结论：

定理1 当n≥3，m≥3时，对于图C3↑Pn↑Sm，有λ′(G) = 2m.

证明设C3的顶点集为{u1，u2，u3}，Pn的顶点集为{w1，w2，…，wn}，Sm的顶点集为{v0，v1，…，vm}.

（i）当n= 3时，如图3（a）所示。C3↑Pn↑Sm边染色为

图3 C3 ↑Pn ↑Sm染色举例Fig.3 The examples of edge coloring of C3 ↑Pn ↑Sm

（ii）当n= 4时，如图3（b）所示。C3↑Pn↑Sm边染色为

（iii）当n= 5时，如图4（a）所示。C3↑Pn↑Sm边染色为

图4 C3 ↑Pn ↑Sm边染色举例Fig.4 The examples of edge coloring of C3 ↑Pn ↑Sm

（iv）当n= 6时，如图4（b）所示。C3↑Pn↑Sm边染色为

（v）当n= 7时，如图4（c）所示。C3↑Pn↑Sm边染色为

（vi）对于所有满足n≥8，m≥3的图，都有C3↑Pn↑Sm边染色为

1）当j≥1，n= 5 + 3j时，如图5（a）所示。C3↑Pn↑Sm边染色为

图5 C3 ↑Pn ↑Sm边染色举例Fig.5 The examples of edge coloring of C3 ↑Pn ↑Sm

2）当j≥1，n= 6 + 3j时，如图5（b）所示。C3↑Pn↑Sm边染色为

3）当j≥1，n= 7 + 3j时，如图5（c）所示。C3↑Pn↑Sm边染色为

故C3↑Pn↑Sm的边染色集合f(E)为

定理得证。

定理2 当m≥3时，对于图Cn↓Sm，有λ′(G) = 2m−2.

证明 设Cn的顶点集为{u1，u2，…，un}，Sm的顶点集为{v0，v1，…，vm}.对于所有的m≥3，都有Cn↓Sm边染色为

（i）当n= 3时，如图6（a）所示。Cn↓Sm边染色为

图6 Cn ↓Sm边染色举例Fig.6 The examples of edge coloring of Cn ↓Sm

（ii）当n= 4时，如图6（b）所示。Cn↓Sm边染色为

（iii）当n= 5时，如图6（c）所示。Cn↓Sm边染色为

（iv）当n= 6时，如图6（d）所示。Cn↓Sm边染色为

（v）当n= 7时，如图6（e）所示。Cn↓Sm边染色为

（vi）当n≥8时，如图6（f）所示。Cn↓Sm边染色为

故图Cn↓Sm的边染色集合f(E)为

定理得证。

定理3 当m≥2时，对于图Cn↑Sm，有λ′(G) = 2m+ 2.

证明 设Cn的顶点集为{u1，u2，…，un}，Sm的顶点集为{v0，v1，v2，…，vm}.如图7 所示，对于所有的m≥2，都有Cn↑Sm边染色为

图7 Cn ↑Sm边染色举例Fig.7 The examples of edge coloring of Cn ↑Sm

故图Cn↑Sm的边染色集合f(E)为

定理得证。

4 结 语

本文采用CK-ABC边染色算法对16个点以内的随机图进行L(2，1)-边染色的求解，通过分析实验结果找到了3 类联图的染色特性，分别用C3↑Pn↑Sm，Cn↓Sm和Cn↑Sm定义这3 类联图并给出相关定理及证明，建议今后可做更大范围的实验，得到更多的关于上界的判断。