張曉亮　耿顯亞　劉斌　等

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

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

中圖分類號：O157.5文獻標志碼：A文章編號：1672-1098（2014）04-0065-03

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

廣播數(shù)就是在不同的信號發(fā)射站點設計頻道區(qū)分標記中的實際用途。 各個站點都標記各自不同的非負整數(shù)， 使他們相互之間不受干擾。 廣播數(shù)的研究就是尋找一種標記方式， 使得在所有可能標記中最大標號最小化。 例如， 研究這種問題的最初模型是兩水平標號距離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)過近十年的研究后， 文獻[2]中提出了多水平距離標號模型， 即尋找

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）

文獻[3]給出了在此數(shù)學模型下路圖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）有小錯誤，即當n=3時，rn（P3）=3，而非按其公式計算的rn（P3）=4。

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

定理設完全二部圖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

距離標號函數(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， 進而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，則有多水平距離標號函數(shù)：

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

可具體標號如下：

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）。

參考文獻：

[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.

（責任編輯：何學華）