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

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

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

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