圖的放松的距離二標(biāo)號著色.pdf

1、標(biāo)號著色是從頻道分配問題中抽象出來的一種圖著色概念。與經(jīng)典的圖著色相比，它不僅要求圖中相鄰元素的著色有著明顯的差別，同時(shí)還要求圖中不相鄰元素的著色有所不同。圖G的距離二標(biāo)號著色也即L(j，k)-標(biāo)號，有整數(shù)距離二標(biāo)號（j，k為非負(fù)整數(shù)）和實(shí)數(shù)距離二標(biāo)號（j，k為非負(fù)實(shí)數(shù)）兩種模式。它們分別是定義在V(G)→{0，1，2，3,…}和V(G)→[0，+∞)上的函數(shù)f，滿足條件:(1)|f(u)-f（v）|≥j，若uv∈E(G);(2)|f(

2、u)-f(v)|≥k，若d(u，v)=2。圖G的L(j，k)-標(biāo)號著色數(shù)λj，k(G)=minf max{f(v):v∈V(G)}。
　　隨著圖著色問題研究的不斷深入，各種各樣的圖著色的變形和推廣出現(xiàn)并被廣泛研究，諸如有缺陷著色、非正常著色、蔭度等等，它們都可看作是對圖的正常著色的放松。著色放松問題實(shí)際上還有很多問題值得深入挖掘和思考。標(biāo)號著色的放松問題在理論上就值得研究，同時(shí)它也有實(shí)際應(yīng)用價(jià)值。為解決頻道分配問題，需要選取合適的

3、數(shù)學(xué)模型，合理地分配稀缺并且有限的頻道資源。放松的距離二標(biāo)號著色是更為合適的頻道分配問題的數(shù)學(xué)模型。
　　假設(shè)G是一個(gè)圖，f:V(G)→{0，1，2，…}是一個(gè)映射，s，t是兩個(gè)非負(fù)整數(shù)。若對于G的任何兩個(gè)相鄰頂點(diǎn)u，v，f(u)≠f（v）;對于G的任何頂點(diǎn)u，至多有s個(gè)u的鄰點(diǎn)標(biāo)號屬于集合{f(u)-1，f(u)+1}，至多有t個(gè)u的2-鄰點(diǎn)的標(biāo)號等于f(u)，則稱f是圖G的(s，t)-放松的L(2，1)-標(biāo)號。記f的跨度為sp

4、an(f)，表示圖中頂點(diǎn)的最大標(biāo)號和最小標(biāo)號的差。圖的(s，t)-放松的L(2，1)-標(biāo)號的最小跨度定義為圖的(s，t)-放松的L(2，1)-標(biāo)號著色數(shù)，記為λs,t2,1(G)。圖的(s，t)-放松的L(2，1)-標(biāo)號是對圖的整數(shù)L(2，1)-標(biāo)號作出相應(yīng)的放松而產(chǎn)生的新的圖標(biāo)號概念。
　　假設(shè)G是一個(gè)圖，f:V(G)→[0，+∞）是一個(gè)映射，s，t是兩個(gè)非負(fù)整數(shù)，j，k是實(shí)數(shù)并且j＞k≥1。若對于任一頂點(diǎn)u，至多s個(gè)u的鄰點(diǎn)標(biāo)

5、號屬于(f(u)-j，f(u)-k]∪[f(u)+k，f(u)+j)，其他鄰點(diǎn)的標(biāo)號屬于[0，f(u)-j]∪[f(u)+j，+∞）;至多t個(gè)u的2-鄰點(diǎn)的標(biāo)號屬于(f(u)-k，f（u）+k），u的其他2-鄰點(diǎn)的標(biāo)號屬于[0,f(u)-k]∪[f（u）+k，+∞），則稱f是圖G的(s，t)-放松的L(j，k)-標(biāo)號。圖的(s，t)-放松的L(j，k)-標(biāo)號著色的最小跨度定義為圖的(s，t)-放松的L(j，k)-標(biāo)號著色數(shù)，記為λs,t

6、j,k(G)。圖的(s，t)-放松的L(j，k)-標(biāo)號這一概念是通過對圖的實(shí)數(shù)L(j，k)-標(biāo)號作出相應(yīng)的放松而產(chǎn)生的。
　　若d=j/k，則λs,t j,k(G)=kλs,td,1(G)。圖的(s，t)-放松的L(j,k)-標(biāo)號和圖的(s，t)-放松的L(d，1)-標(biāo)號可以相互轉(zhuǎn)化。網(wǎng)格圖（六邊形網(wǎng)格圖、四邊形網(wǎng)格圖以及三角形網(wǎng)格圖）是頻道分配問題中干擾圖的理想模型。本文主要考慮各種網(wǎng)格圖的(s，t)-放松的L(2，1)-標(biāo)號著

7、色以及(s，t)-放松的L(d，1)-標(biāo)號著色問題，研究并得出了它們的一些基本性質(zhì)，討論了它們的所有可能的(s，t)-放松的情形。確定了三種網(wǎng)格圖的所有s，t情形下的(s，t)-放松的L(2，1)-標(biāo)號著色數(shù)，確定了六邊形網(wǎng)格圖的所有s，t和任意d＞1情形下的(s，t)-放松的L(d，1)-標(biāo)號著色數(shù)，確定了四邊形網(wǎng)格圖的幾乎所有s，t和任意d＞1情形下的(s，t)-放松的L(d，1)-標(biāo)號著色數(shù)（除了s=0，t=1，1＜d＜2這一情形