圖的L(2,1)-標(biāo)號(hào)的島序列.pdf

1、圖G的L(2,1)-標(biāo)號(hào)問(wèn)題是類似于Hale的頻率分配問(wèn)題的一個(gè)頂點(diǎn)標(biāo)號(hào)問(wèn)題.尋求最小的頻率使用范圍同時(shí)確保充分靠近的傳輸機(jī)分配到的傳輸頻率的差不小于一個(gè)給定的數(shù).圖G的一個(gè)L(2,1)-標(biāo)號(hào)是從G的頂點(diǎn)集到非負(fù)整數(shù)集的一個(gè)函數(shù)f,并且滿足:如果d(x,y)=1,則|f(x)-f(y)|≥2;如果d(x,y)=2,則|f(x)-f(y)|≥1,其中x,y分別表示圖G的頂點(diǎn),d(x,y)表示頂點(diǎn)x和頂點(diǎn)y之間的距離.這些標(biāo)號(hào)問(wèn)題已經(jīng)被用來(lái)

2、模仿無(wú)線電分配問(wèn)題.圖G的使用集合{0,1…,k}(不一定是所有的元素)中的元素進(jìn)行標(biāo)號(hào)的一個(gè)L(2,1)-標(biāo)號(hào)叫做一個(gè)k標(biāo)號(hào).使得G有一個(gè)k標(biāo)號(hào)的最小的k叫做G的λ數(shù),用λ(G)來(lái)表示.一個(gè)λ(G)-標(biāo)號(hào)簡(jiǎn)記為λ-標(biāo)號(hào).依據(jù)內(nèi)容,本文分為四個(gè)章:第一章主要介紹本文的選題背景、意義和圖的L(2,1)-標(biāo)號(hào)的研究現(xiàn)狀以及一些預(yù)備知識(shí).后面的章節(jié)通過(guò)考慮了幾類特殊的含圈2-稀疏圖的路覆蓋,得到了這些類型的2-稀疏圖的補(bǔ)圖容許至少兩個(gè)不同的島