與圖的L(d,1)_標(biāo)號相關(guān)的幾種圖標(biāo)號問題.pdf

1、圖的染色問題是圖論中研究的主要問題之一,也是圖論研究中一個活躍的領(lǐng)域,因此各類染色問題被相繼提出并加以發(fā)展應(yīng)用,其中圖的染色問題的一個重要推廣是圖的標(biāo)號問題.作為頻道分配問題的一個變形，Griggs和Yeh在1992年文章[1]中提出了圖的L(2,1)-標(biāo)號問題.假如給定一些基站,我們想給每一個基站在避免干擾的條件下給它分配一個頻道.為了避免干擾,我們要求非常近的基站之間必須是至少差兩個頻道的,稍近的一些基站也讓它們分配不同的頻道.為了

2、方便起見,把基站看作是點(diǎn),如果兩個基站非常近則在兩個基站間連一條邊,如果兩個點(diǎn)距離為2則對應(yīng)的基站可以看作是稍近.這樣我們就可以定義L(2,1)-標(biāo)號了本文只考慮簡單連通圖G. 本文中△(G)表示圖G的最大度,δ(G)表示圖G的最小度,d(u,v)表示u,v兩點(diǎn)在圖G中的距離,即u,v之間最短路的長度. 在本文的第二章中,研究了圖G的(d,1)-全標(biāo)號.本文在第三章中所要研究的L(d,1)-T標(biāo)號是比L(d,1)-標(biāo)號要求更松的一種限制

3、.還是要求相鄰的以及距離為2的基站頻道必須不同,另外要求在圖G的任意一棵支撐樹T上相鄰的基站頻道至少差d.也就是只在圖G的某個重要的干道上我們要求的嚴(yán)格一些.這里我們以支撐樹作為主要樞紐.對于任意連通圖G,都有支撐樹在本文第四章中研究的L'(d,1)-T標(biāo)號是比L(d,1)-T標(biāo)號要求更松的一種限制.還是要求相鄰的基站頻道必須不同,另外要求在圖G的任意一棵支撐樹T上相鄰的基站頻道至少差d且在T上距離為2的基站頻道至少差1.也就是只在G的