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

朱利娜，李敬文，孫帥

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

Hale（1980）曾用圖論中T-coloring 的概念來描述和研究過頻道分配問題，最先把該問題轉(zhuǎn)化為圖的著色問題。Roberts（1991）提出為了避免干擾使相隔很近的發(fā)射臺分配的頻率至少相差為2，相隔較近的使用不同的頻率，作為頻率設(shè)置問題的一個變形。此后，Griggs et al.（1992）將此問題轉(zhuǎn)化為不同于T-coloring的另一種著色問題并引入了L(2，1)-標(biāo)號，其中圖G的L(2，1)-邊標(biāo)號等價于其線圖L(G)的L(2，1)-標(biāo)號。

截止到目前，對L(2，1)-邊標(biāo)號的研究主要集中在特殊圖上，如路、圈、輪、完全圖、完全二部圖及樹（陳琴，2006）已有相關(guān)結(jié)論。本文利用人工蜂群（ABC，artificial bee colony）算法（Aslan，2020）的思想設(shè)計針對隨機圖的L(2，1)-邊染色算法（下文中用CK-ABC 邊染色算法表示）。通過分析實驗數(shù)據(jù)，發(fā)現(xiàn)了三類聯(lián)圖的染色特性，分別C3↑Pn↑Sm，Cn↓Sm和Cn↑Sm定義這三類聯(lián)圖，進(jìn)而給出相應(yīng)的定理和證明。

1 預(yù)備知識

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

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

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

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

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

本文將L(2，1)-邊標(biāo)號統(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：設(shè)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：設(shè)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：設(shè)Cn的頂點集為{u1，u2，…，un}，Sm的頂點集為{v0，v1，v2，…，vm}.Cn↑Sm是指將星圖Sm的中心節(jié)點并接到Cn的任一頂點上得到圖2（b）。

2 CK-ABC邊染色算法

2.1 算法思想

1）將圖G轉(zhuǎn)化為相對應(yīng)的線圖L(G)。

2）對圖的鄰接矩陣進(jìn)行預(yù)處理，求得距離矩陣、度序列等屬性。

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

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

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

2.2 CK-ABC算法

初始化函數(shù)：

Input：圖G(p，q)的鄰接矩陣M.

Output：對應(yīng)線圖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進(jìn)行預(yù)處理，得到其距離矩陣、點邊數(shù)量和最大度等屬性。

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

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

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

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

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

Step 8.轉(zhuǎn)Step 5。

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

3 實驗結(jié)論及證明

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

我們將CK-ABC 邊染色算法應(yīng)用于16 個點以內(nèi)的單圈圖，各點數(shù)下λ′(G)和圖的染色數(shù)?+k之間的關(guān)系如表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 主要結(jié)論

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

定理1 當(dāng)n≥3，m≥3時，對于圖C3↑Pn↑Sm，有λ′(G) = 2m.

證明設(shè)C3的頂點集為{u1，u2，u3}，Pn的頂點集為{w1，w2，…，wn}，Sm的頂點集為{v0，v1，…，vm}.

（i）當(dāng)n= 3時，如圖3（a）所示。C3↑Pn↑Sm邊染色為

圖3 C3 ↑Pn ↑Sm染色舉例Fig.3 The examples of edge coloring of C3 ↑Pn ↑Sm

（ii）當(dāng)n= 4時，如圖3（b）所示。C3↑Pn↑Sm邊染色為

（iii）當(dāng)n= 5時，如圖4（a）所示。C3↑Pn↑Sm邊染色為

圖4 C3 ↑Pn ↑Sm邊染色舉例Fig.4 The examples of edge coloring of C3 ↑Pn ↑Sm

（iv）當(dāng)n= 6時，如圖4（b）所示。C3↑Pn↑Sm邊染色為

（v）當(dāng)n= 7時，如圖4（c）所示。C3↑Pn↑Sm邊染色為

（vi）對于所有滿足n≥8，m≥3的圖，都有C3↑Pn↑Sm邊染色為

1）當(dāng)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）當(dāng)j≥1，n= 6 + 3j時，如圖5（b）所示。C3↑Pn↑Sm邊染色為

3）當(dāng)j≥1，n= 7 + 3j時，如圖5（c）所示。C3↑Pn↑Sm邊染色為

故C3↑Pn↑Sm的邊染色集合f(E)為

定理得證。

定理2 當(dāng)m≥3時，對于圖Cn↓Sm，有λ′(G) = 2m?2.

證明 設(shè)Cn的頂點集為{u1，u2，…，un}，Sm的頂點集為{v0，v1，…，vm}.對于所有的m≥3，都有Cn↓Sm邊染色為

（i）當(dāng)n= 3時，如圖6（a）所示。Cn↓Sm邊染色為

圖6 Cn ↓Sm邊染色舉例Fig.6 The examples of edge coloring of Cn ↓Sm

（ii）當(dāng)n= 4時，如圖6（b）所示。Cn↓Sm邊染色為

（iii）當(dāng)n= 5時，如圖6（c）所示。Cn↓Sm邊染色為

（iv）當(dāng)n= 6時，如圖6（d）所示。Cn↓Sm邊染色為

（v）當(dāng)n= 7時，如圖6（e）所示。Cn↓Sm邊染色為

（vi）當(dāng)n≥8時，如圖6（f）所示。Cn↓Sm邊染色為

故圖Cn↓Sm的邊染色集合f(E)為

定理得證。

定理3 當(dāng)m≥2時，對于圖Cn↑Sm，有λ′(G) = 2m+ 2.

證明 設(shè)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 結(jié) 語

本文采用CK-ABC邊染色算法對16個點以內(nèi)的隨機圖進(jìn)行L(2，1)-邊染色的求解，通過分析實驗結(jié)果找到了3 類聯(lián)圖的染色特性，分別用C3↑Pn↑Sm，Cn↓Sm和Cn↑Sm定義這3 類聯(lián)圖并給出相關(guān)定理及證明，建議今后可做更大范圍的實驗，得到更多的關(guān)于上界的判斷。