Cactus圖的 L（j，k）-標(biāo)號數(shù)研究

吳 瓊，呂曉靜

（天津職業(yè)技術(shù)師范大學(xué)理學(xué)院，天津 300222）

隨著計算機(jī)無線網(wǎng)絡(luò)的發(fā)展，無線網(wǎng)絡(luò)的規(guī)模越來越大，這就導(dǎo)致了代碼日漸匱乏，另外因全球范圍內(nèi)的計算機(jī)遠(yuǎn)程信號交互的需要，利用有限的代碼對不斷增加的基站數(shù)完成最優(yōu)分配的工作顯得愈發(fā)重要，這就是代碼分配問題（code assignment problem，CAP）。CAP要求相距“非常近”的2個基站不能產(chǎn)生直接干擾，相距“較近”的2個基站不能產(chǎn)生間接干擾。而計算機(jī)無線網(wǎng)絡(luò)可以抽象為無向圖G，其中用頂點(diǎn)集代表基站集合，用邊集代表相鄰基站之間的關(guān)系，即如果2個基站可以直接傳輸數(shù)據(jù)，它們對應(yīng)在圖中的頂點(diǎn)之間則存在一條邊。若只需要避免間接干擾，Bertossi等[1]給出了一種代碼分配方案，即2個距離為二的基站發(fā)射不同的代碼。因此，代碼分配問題可以被抽象為以下模型：利用數(shù)字代替代碼，將最小的不同數(shù)字分配給距離為二的2個頂點(diǎn)，等值于2個距離為二的不同頂點(diǎn)必須被分配不同的標(biāo)號數(shù)，此即L（0，1）-標(biāo)號問題。但在實(shí)際應(yīng)用中，更為普遍的是既要考慮直接干擾，也要防止間接干擾，因此Jin等[2]提出了 L（j，k）-標(biāo)號問題，其中 j≤k。為避免直接干擾，2個相鄰的基站必須被分配不同的代碼；為避免直接和間接干擾，任何2個距離為二的基站就必須被分配差異更大的代碼，所以j≤k。

目前，基于計算機(jī)無線網(wǎng)絡(luò)代碼分配問題圖的標(biāo)號問題的相關(guān)研究成果并不豐富，相關(guān)結(jié)論主要有文獻(xiàn)[3-10]。隨著圖的標(biāo)號問題在計算機(jī)科學(xué)與通信工程方面的應(yīng)用越來越多，這就需要足夠的理論成果進(jìn)行支撐。而作為刻畫計算機(jī)無線網(wǎng)絡(luò)的最重要的圖——Cactus圖，關(guān)于它的研究就顯得尤為重要了。本文通過研究Cactus圖的結(jié)構(gòu)特性，不僅確定了一系列Cactus圖的L（1，2）-標(biāo)號數(shù)，還給出了相應(yīng)圖的最優(yōu)標(biāo)號方案，可直接被利用到相應(yīng)的計算機(jī)無線網(wǎng)絡(luò)的代碼分配問題中，從而達(dá)到節(jié)約資源，提高經(jīng)濟(jì)效益的目的。

1 基本定義

設(shè) G=＜V，E＞是一個圖，對任意的頂點(diǎn) u，v，d（u，v）表示圖G中頂點(diǎn)u，v之間的距離。

定義1[2]設(shè) m、j、k 都是非負(fù)整數(shù)，f：V（G）→{1，2，…，m}是一個映射，如果滿足如下條件：當(dāng) d（u，v）=1時，|f（u）-f（v）|≥j；當(dāng)d（u，v）=2時，|f（u）-f（v）|≥k，其中 j≤k，則稱 f是圖G的一個 m-L（j，k）標(biāo)號。圖G的L（j，k）-標(biāo)號數(shù)，即距離二標(biāo)號，記作λj，k（G），定義為：

Cactus圖是一個連通圖，它的塊是一個圈或者是一條邊，其中任何2個塊至多包含1個公共點(diǎn)。令G（m1，m2，…，mp）是一個 p-Cactus圖，它包含 p 個導(dǎo)出圈 Cm1，Cm2，…，Cmp，且v是p-Cactus圖的割點(diǎn)。設(shè)v，是導(dǎo)出圈 Cmi的頂點(diǎn)，其中 i=1，2，…，p，p≥2。為敘述方便，本文把p-Cactus圖稱為p元圈[11]。

本文主要針對二元圈、p元圈的L（1，2）-標(biāo)號數(shù)展開研究。

2 二元圈的 L（1，2）-標(biāo)號數(shù)

討論 2-Cactus圖的 L（1，2）-標(biāo)號問題。

引理1[6]設(shè)j、k是2個正整數(shù)，且j≤k，對于任意圖G，若H是圖G的導(dǎo)出子圖，則有λj，k（G）≥λj，k（H）。

定理1令G1=G（m1，m2）為一個二元圈，且m1=m2=3，則 λ1，2（G1）=4。

證明假設(shè) λ1，2（G1）= λ。給圖G1一個標(biāo)號f為：

式中：i，j=1，2。

不難驗(yàn)證標(biāo)號f是圖G1的一個4-L（1，2）-標(biāo)號，即λ≤4。

另外，圖G1中任意2點(diǎn)之間的距離為1或2。因此，任意2點(diǎn)的標(biāo)號都不同，則λ≥4。

綜上所述，可得 λ1，2（G1）=λ=4。

定理2令 G2=G（m1，m2）為一個二元圈，且m1=3，m2≥4，則 λ1，2（G2）=5。

證明假設(shè)λ1，2（G2）=λ。給圖G2定義一個標(biāo)號f為：

針對導(dǎo)出圈Cm2，

1）當(dāng)m2≡1（mod 4）且m2≥5時，令f（v）=4；若1≤s≤m2-2（如果存在），令f（v2s）=[4-s]4；且f（v2m2-1）=5。

不難驗(yàn)證標(biāo)號f是圖G2的一個5-L（1，2）-標(biāo)號，即 λ≤5。

圖H是圖G2的一個導(dǎo)出子圖，如圖1所示。

圖1 圖H

定理3令 G3=G（m1，m2）為一個二元圈，且 m1，m2≥4，則λ1，2（G3）=6。

另外，給圖G3定義一個標(biāo)號f如下：

針對導(dǎo)出圈Cm1，

1）當(dāng) m1≡1（mod 4）且 m1≥5 時，令；若3≤s≤m1-3（如果存在），令1]4；且

不難驗(yàn)證標(biāo)號f是圖G3的一個6-L（1，2）-標(biāo)號，所以 λ≤6。綜上所述，λ1，2（G3）=λ=6。

3 p 元圈的 L（1，2）-標(biāo)號數(shù)（p≥3）

討論 p 元圈的 L（1，2）-標(biāo)號問題，其中 p≥3。

定理4G為一個p元圈，且包含q個邊數(shù)為3的導(dǎo)出圈，即包含（p-q）個邊數(shù)大于3的導(dǎo)出圈，其中0≤q≤p ，則 λ1，2（G）=4p-q-2。

證明假設(shè)λ1，2（G）=λ有p元圈的對稱性，不妨設(shè)圈 Cm1，Cm2，…，Cmq邊數(shù)為 3（若存在），即 m1=m2=… =mq=3（若存在），圈 Cmq+1，Cmq+2，…，Cmp的邊數(shù)均大于 3，即 mq+1，mq+2，…，mp≥4。給圖G 一個標(biāo)號f為：

其中1≤s≤p，對于剩余點(diǎn)的標(biāo)號定義如下：

情形1當(dāng)q=0時，

針對導(dǎo)出圈Cm1的標(biāo)號定義如下：

其中：2≤i≤ms-2，2≤s≤p。

情形2當(dāng)q≠0時，

針對導(dǎo)出圈mq+1，mq+2，…，mp，令f（v）=4p-q-3，

其中：2≤i≤ms-2，q+1≤s≤p。

不難驗(yàn)證標(biāo)號 f是圖G的一個（4p-q-2）-L（1，2）-標(biāo)號，即 λ1，2（G）= λ≤4p-q-2。

另外，假設(shè)f是圖G的一個L（1，2）-標(biāo)號。在圖G 中，除了公共點(diǎn) v，導(dǎo)出圈 Cm1，Cm2，…，Cmq中任意 2 點(diǎn)相鄰，即它們的標(biāo)號之間差異至少為1；圈Cmj中點(diǎn)的距離為2，則它們的標(biāo)號之間差異至少為2，其中 j=q+1，q+2，…，p；除了公共點(diǎn)外，任一個導(dǎo)出圈內(nèi)的第一及最后一個點(diǎn)和另一個圈的第一及最后一個點(diǎn)距離為2，即這些點(diǎn)的標(biāo)號差異至少為2。因此，點(diǎn)集中任意2點(diǎn)的標(biāo)號都不同，利用圖的對稱性，不妨設(shè)且點(diǎn)集S中的標(biāo)號依次增加，則根據(jù)上述分析，可得，即 λ≥4p-q-2。

綜上所述，可得λ1，2（G）=λ=4p-q-2。

4 結(jié)語

本文基于計算機(jī)無線網(wǎng)絡(luò)的代碼分配問題，針對Cactus圖的 L（1，2）-標(biāo)號問題進(jìn)行研究，得到了二元圈 2-Cactus圖以及一般的 p-Cactus圖的 L（1，2）-標(biāo)號數(shù)如下：

1）λ1，2（G（3，3））=4；

2）λ1，2（G（3，m2））=5，其中m2≥4；

3）λ1，2（G（m1，m2））=6，其中m1，m2≥4；

4）λ1，2（G（m1，m2，…，mq，mq+1，…，mp））=4p-q-2，其中，m1= … =mq=3，mq+1，…，mp≥4，且 0≤q≤p。