若干聯(lián)圖的L（2，1）-邊染色算法*

朱利娜，李敬文，孫帥

蘭州交通大學電子與信息工程學院，甘肅 蘭州 730070

Hale（1980）曾用圖論中T-coloring 的概念來描述和研究過頻道分配問題，最先把該問題轉化為圖的著色問題。Roberts（1991）提出為了避免干擾使相隔很近的發(fā)射臺分配的頻率至少相差為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 邊染色算法表示）。通過分析實驗數(shù)據(jù)，發(fā)現(xiàn)了三類聯(lián)圖的染色特性，分別C3↑Pn↑Sm，Cn↓Sm和Cn↑Sm定義這三類聯(lián)圖，進而給出相應的定理和證明。

1 預備知識

本文使用G(p，q)表示具有p個頂點q條邊的無向簡單圖，當p=q時即為本文研究的單圈圖，使用E(G)，F(xiàn)(E)，d(e1e2)和?(G)分別表示圖的邊集合、邊染色集合、邊e1，e2之間的距離和最大度。在不特殊說明的情況下，本文將?(G)簡寫為?.

定義1 對于圖G(p，q)（簡寫為G），設m是非負整數(shù)，如果存在映射f：V(G) →{0，1，2，…，m}且滿足

其中v1，v2∈V(G)，則稱f是圖G的一個L(2，1)-標號。

定義2 對于圖G(p，q)（簡寫為G），設m是非負整數(shù)，如果存在映射f：E(G) →{0，1，2，…，m}且滿足

其中e1，e2∈E(G)，則稱f是圖G的一個L(2，1)-邊標號。

本文將L(2，1)-邊標號統(tǒng)稱為L(2，1)-邊染色。另外定義G的所有的L(2，1)-邊染色中的最小的值m為圖G的L(2，1)-邊色數(shù)，記為λ′2，1(G)，簡寫為λ′(G).如無特殊說明，本文使用f表示一個最優(yōu)的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的中心節(jié)點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的中心節(jié)點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的中心節(jié)點并接到Cn的任一頂點上得到圖2（b）。

2 CK-ABC邊染色算法

2.1 算法思想

1）將圖G轉化為相對應的線圖L(G)。

2）對圖的鄰接矩陣進行預處理，求得距離矩陣、度序列等屬性。

3）用CK算法求出次優(yōu)解f′，初步確定最大色數(shù)maxColor。

4）采用人工蜂群算法的思想進行尋優(yōu)。

5）輸出求得的最優(yōu)解f.

2.2 CK-ABC算法

初始化函數(shù)：

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.按照初始化函數(shù)得到圖G線圖的鄰接矩陣LM.

Step 2.對LM進行預處理，得到其距離矩陣、點邊數(shù)量和最大度等屬性。

Step 3.采用孫帥等（2021）的Algorithm1 求出次優(yōu)解f′及對應的最大色數(shù)maxColor。若maxColor 大于?+1轉Step 4；否則f′即為理論最優(yōu)解，轉Step 9。

Step 4.初始化蜜源總數(shù)SN、蜜源訪問次數(shù)上限limit以及最大迭代次數(shù)MCN，隨機生成初始蜜源并計算其適應度。

Step 5.如果迭代次數(shù)未達到MCN，則轉Step 6；否則轉Step 9。

Step 6.如果蜜源訪問次數(shù)沒有超過limit，則轉Step 7；否則重新生成該處蜜源，并將其訪問次數(shù)置0。

Step 7.采用輪盤賭的方式選擇蜜源x進行變異操作，得到新蜜源x′，計算適應度并與x比較，擇優(yōu)保留適應度較大的蜜源并增加其訪問次數(shù)。

Step 8.轉Step 5。

Step 9.將L(G)的點染色結果轉化為圖G的邊染色結果，算法結束。

3 實驗結論及證明

3.1 數(shù)據(jù)統(tǒng)計

我們將CK-ABC 邊染色算法應用于16 個點以內(nèi)的單圈圖，各點數(shù)下λ′(G)和圖的染色數(shù)?+k之間的關系如表1所示。

表1 16個點以內(nèi)單圈圖的L(2，1)-邊染色統(tǒng)計1）Table 1 L(2，1)-edge coloring number of unicyclic graphs within 16 points

3.2 主要結論

通過對表的實驗數(shù)據(jù)分析總結，得出以下結論：

定理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個點以內(nèi)的隨機圖進行L(2，1)-邊染色的求解，通過分析實驗結果找到了3 類聯(lián)圖的染色特性，分別用C3↑Pn↑Sm，Cn↓Sm和Cn↑Sm定義這3 類聯(lián)圖并給出相關定理及證明，建議今后可做更大范圍的實驗，得到更多的關于上界的判斷。