完全二部圖Km，n的廣播數(shù)rn（Km，n）

張曉亮　耿顯亞　劉斌　等

摘要：利用圖的頂點之間的距離與多水平標(biāo)號的最大-最小值原理， 依據(jù)頂點排序累積距離最大作為優(yōu)化多水平距離標(biāo)號的衡量標(biāo)準(zhǔn)， 證明了完全二部圖Km，n的廣播數(shù)的計算公式rn（Km，n）=m+n。 修正和填補了圖的多水平距離標(biāo)號研究領(lǐng)域的相關(guān)問題。另外，圖的標(biāo)號在科學(xué)技術(shù)和工程領(lǐng)域中有廣泛的應(yīng)用， 同時又是圖染色理論的推廣， 所以有一定研究價值與應(yīng)用前景.

關(guān)鍵詞：完全二部圖； 多水平距離標(biāo)號； 廣播數(shù)

中圖分類號：O157.5文獻(xiàn)標(biāo)志碼：A文章編號：1672-1098（2014）04-0065-03

在無線網(wǎng)絡(luò)和信號傳播途徑中， 為了避免不同信號之間的相互干擾而設(shè)計不同的廣播頻率是一項重要的任務(wù)。 在信號傳播中， 頻率相近的信號相互會產(chǎn)生干擾。 這個問題的數(shù)學(xué)模型可以抽象為圖論中點的染色和標(biāo)號問題， 頂點表示信號發(fā)射站， 邊表示鄰近的信號發(fā)射站。 頻道設(shè)計問題最先由文獻(xiàn)[1]提出， 問題的解決先后涉及兩水平距離標(biāo)號， 多水平距離標(biāo)號。 通常情況下， 兩個信號發(fā)射站發(fā)射的信號之間的干擾程度與兩個信號發(fā)射站之間的距離有關(guān)， 距離越近干擾程度越強(qiáng)。 現(xiàn)假設(shè)僅考慮兩水平信號干擾， 強(qiáng)調(diào)信號干擾與弱調(diào)信號干擾。 強(qiáng)干擾發(fā)生在非常接近的兩個信號發(fā)射站， 為了避免干擾， 這兩個信號發(fā)射站要分兩個不同時段發(fā)射信號； 弱干擾發(fā)生在鄰近的信號發(fā)射站， 為了避免干擾， 兩個信號發(fā)射站的信號頻道設(shè)計不同即可。 作為問題所抽象的數(shù)學(xué)模型， 利用圖論知識構(gòu)造圖G， 圖G的頂點代表各自不同的信號發(fā)射站， 當(dāng)兩個信號發(fā)射站的距離非常接近時， 連接代表它們的頂點作為邊。 這樣， 不同頻道的設(shè)計就抽象為圖論中道路連接的頂點的標(biāo)號問題。

廣播數(shù)就是在不同的信號發(fā)射站點設(shè)計頻道區(qū)分標(biāo)記中的實際用途。 各個站點都標(biāo)記各自不同的非負(fù)整數(shù)， 使他們相互之間不受干擾。 廣播數(shù)的研究就是尋找一種標(biāo)記方式， 使得在所有可能標(biāo)記中最大標(biāo)號最小化。 例如， 研究這種問題的最初模型是兩水平標(biāo)號距離L（2，1）， 即尋找

λ（G）=minf max{f（V（G））}， 其中f：V（G）→{0，1，2，…，k}， 滿足u，v∈V（G），

|f（u）-f（v）|≥2dist（u，v）=1

1dist（u，v）=2

在經(jīng)過近十年的研究后， 文獻(xiàn)[2]中提出了多水平距離標(biāo)號模型， 即尋找

rn（G）=minf max{f（V（G））}， 其中f：V（G）→

{0，1，2，…，k}，u，v∈V（G），

|f（u）-f（v）|≥diam（G）+1-dist（u，v）

文獻(xiàn)[3]給出了在此數(shù)學(xué)模型下路圖Pn和圈圖Cn的廣播數(shù)在n≥3時分別為

rn（Pn）=2k2+2n=2k+1

2k（k-1）+1n=2k

rn（Cn）=n-22φ（n）+1n≡0，2（mod4）

n-12φ（n）n≡1，3（mod4）

其中φ（n）=k+1n=4k+1

k+2n=4k+r，r=0，2，3，在此文中，其定理3關(guān)于路圖Pn的廣播數(shù)公式rn（Pn）有小錯誤，即當(dāng)n=3時，rn（P3）=3，而非按其公式計算的rn（P3）=4。

本文主要研究完全二部圖Km，n的廣播數(shù)rn（Km，n）。

定理設(shè)完全二部圖Km，n， 則rn（Km，n）=m+n。

證明根據(jù)完全二部圖Km，n的特征有， 頂點集合分V（Km，n）=V1∪V2，|V1|=m，|V2|=n，u∈V1，v∈V2，（u，v）∈E（Km，n）。 直徑為diam（Km，n）=2， 任意兩點間的距離：u，v∈V（Km，n），

dist（u，v）=2u，v∈V1，or，u，v∈V2

1u∈V1，v∈V2，or，u∈V2，v∈V1

距離標(biāo)號函數(shù)f∶V（G）→{0，1，2，…，k}， 滿足

|f（u）-f（v）|≥diam（G）+1-dist（u，v）=

3-dist（u，v）=1u，v∈V1，or，u，v∈V2

2u∈V1，v∈V2，or，u∈V2，v∈V1

首先證明rn（Km，n）≥m+n。

令{x1，x2，…，xm+n}為頂點集合V（Km，n）={v1，v2，…，vm+n}的一個重排，滿足條件： f（xi）

f（x2）-f（x1）≥3-dist（x2，x1）

f（x3）-f（x2）≥3-dist（x3，x2）

f（xm+n）-f（xm+n-1）≥3-dist（xm+n，xm+n-1）

以上各式相加得f（xm+n）-f（x1）≥3（m+n-1）-∑m+n-1i=1dist（xi+1，xi），取f（x1）=0即

f（xm+n）≥3（m+n-1）-∑m+n-1i=1dist（xi+1，xi）

另外由dist（u，v）的定義有∑m+n-1i=1dist（xi+1，xi）≤

2（m-1）+2（n-1）+1=2m+2n-3， 進(jìn)而f（xm+n）≥

3（m+n-1）-∑m+n-1i=1dist（xi+1，xi）≥3（m+n-1）-（2m+2n-3）=m+n

所以rn（Km，n）≥m+n。

下面證明rn（Km，n）≤m+n。

令x1，x2，…xm∈V1，xm+1，xm+2，…xm+n∈V2，則有多水平距離標(biāo)號函數(shù)：

f（xi+1）=f（xi）+3-dist（xi+1，xi），i=1，2，…，m+n-1

可具體標(biāo)號如下：

f（x1）=0， f（x2）=1， f（x3）=2，…， f（xm）=m-1

f（xm+1）=m+1， f（xm+2）=m+2，…， f（xm+n）=m+n

滿足 u，v∈V（G）

|f（u）-f（v）|≥diam（G）+1-dist（u，v）=3-dist（u，v）

所以rn（Km，n）≤m+n。

綜上所述，rn（Km，n）=m+n。證畢

例如：給出完全二部圖K4，3（見圖1），其廣播數(shù)rn（K4，3）=4+3=7。

圖1完全二部圖K4，3推論1rn（K2，2）=rn（C4）。

推論2rn（Km，n）=λ（Km，n）。

參考文獻(xiàn)：

[1]W K HALE.Frequency assignment： Theory and applications[J]. Proc. IEEE， 1980 （68）：1 497-1 514.

[2]DAPHNE DER-FEN LIU， XUDING ZHU.Multilevel Distance Labelings For Paths And Cycles[J]. SIAM J.DISCRETE MATH，2005，19（3）：610-621.

[3]G CHARTRAND， D ERWIN， P ZHANG.A Graph Labeling Problem Suggested by FM Channel Restrictions[J]. Bull Inst. Combin. Appl， 2005 （43） ：43-57.

（責(zé)任編輯：何學(xué)華）