【摘要】：標(biāo)號(hào)著色是從頻道分配問題中抽象出來的一種圖著色概念。與經(jīng)典的圖著色相比,它不僅要求圖中相鄰元素的著色有著明顯的差別,同時(shí)還要求圖中不相鄰元素的著色有所不同。圖G的距離二標(biāo)號(hào)著色也即L(j,k)-標(biāo)號(hào),有整數(shù)距離二標(biāo)號(hào)(j,k為非負(fù)整數(shù))和實(shí)數(shù)距離二標(biāo)號(hà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(u)-f(v)|≥k,若d(u,v)=2。圖G的L(j,k)-標(biāo)號(hào)著色數(shù)λj,k(G)=minf max{f(v): v∈V(G)}。隨著圖著色問題研究的不斷深入,各種各樣的圖著色的變形和推廣出現(xiàn)并被廣泛研究,諸如有缺陷著色、非正常著色、蔭度等等,它們都可看作是對圖的正常著色的放松。著色放松問題實(shí)際上還有很多問題值得深入挖掘和思考。標(biāo)號(hào)著色的放松問題在理論上就值得研究,同時(shí)它也有實(shí)際應(yīng)用價(jià)值。為解決頻道分配問題,需要選取合適的數(shù)學(xué)模型,合理地分配稀缺并且有限的頻道資源。放松的距離二標(biāo)號(hà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)號(hào)屬于集合{f(u)-1,(u)+1},至多有t個(gè)u的2-鄰點(diǎn)的標(biāo)號(hào)等于f(u),則稱f是圖G的(s,t)-放松的L(2,1)-標(biāo)號(hào)。記f的跨度為span(f),表示圖中頂點(diǎn)的最大標(biāo)號(hào)和最小標(biāo)號(hào)的差。圖的(s,t)-放松的L(2,1)-標(biāo)號(hào)的最小跨度定義為圖的(s,t)-放松的L(2,1)-標(biāo)號(hào)著色數(shù),記為λ2,1s,t(G)。圖的(s,t)-放松的L(2,1)-標(biāo)號(hào)是對圖的整數(shù)L(2,1)-標(biāo)號(hào)作出相應(yīng)的放松而產(chǎn)生的新的圖標(biāo)號(hào)概念。假設(shè)G是一個(gè)圖,f：V(G)→[0,+∞)是一個(gè)映射,s,t是兩個(gè)非負(fù)整數(shù),j,k是實(shí)數(shù)并且jk≥1。若對于任一頂點(diǎn)u,至多s個(gè)u的鄰點(diǎn)標(biāo)號(hào)屬于(f(u)-j,f(u)-k]∪ [f(u)+k,f(u)+j),其他鄰點(diǎn)的標(biāo)號(hào)屬于[0,f(u)-j]∪[f(u)+j,+∞)；至多t個(gè)u的2-鄰點(diǎn)的標(biāo)號(hào)屬于(f(u)-k,f(u)+k),u的其他2-鄰點(diǎn)的標(biāo)號(hào)屬于[0,f(u)-k]∪[f(u)+k,+∞),則稱f是圖G的(s,t)-放松的L(j,k)-標(biāo)號(hào)。圖的(s,t)-放松的L(j,k)-標(biāo)號(hào)著色的最小跨度定義為圖的(s,t)-放松的L(j,k)-標(biāo)號(hào)著色數(shù),記為λj,ks,t(G)。圖的(s,t)-放松的L(j,k)-標(biāo)號(hào)這一概念是通過對圖的實(shí)數(shù)L(j,k)-標(biāo)號(hào)作出相應(yīng)的放松而產(chǎn)生的。若d＝j(luò)/k,則λj,ks,t(G)=kλd,1s,t(G)。圖的(s,t)-放松的L(j,k)-標(biāo)號(hào)和圖的(s,t)-放松的L(d，，1)-標(biāo)號(hào)可以相互轉(zhuǎn)化。網(wǎng)格圖(六邊形網(wǎng)格圖、四邊形網(wǎng)格圖以及三角形網(wǎng)格圖)是頻道分配問題中干擾圖的理想模型。本文主要考慮各種網(wǎng)格圖的(s,t)-放松的L(2,1)-標(biāo)號(hào)著色以及(s,t)-放松的L(d,1)-標(biāo)號(hào)著色問題,研究并得出了它們的一些基本性質(zhì),討論了它們的所有可能的(s,t)-放松的情形。確定了三種網(wǎng)格圖的所有s,t情形下的(s,t)-放松的L(2,1)-標(biāo)號(hào)著色數(shù),確定了六邊形網(wǎng)格圖的所有s,t和任意d1情形下的(s,t)-放松的L(d,1)-標(biāo)號(hào)著色數(shù),確定了四邊形網(wǎng)格圖的幾乎所有s,t和任意d1情形下的(s,t)-放松的L(d,1)-標(biāo)號(hào)著色數(shù)(除了s＝0,t＝1,1d2這一情形以外),確定了三角形網(wǎng)格圖的大多數(shù)情形下的(s,t)-放松的L(d,1)-標(biāo)號(hào)著色數(shù)以及其余情形下的(s,t)-放松的L(d,1)-標(biāo)號(hào)著色數(shù)的界。這些結(jié)果給相應(yīng)的頻道分配問題提供了一系列的頻道分配方案。
【學(xué)位授予單位】：東南大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 盧建立;任鳳霞;馬美琳;;中間圖的鄰點(diǎn)強(qiáng)可區(qū)別全染色[J];河南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年05期

2 馬生全,張忠輔,姚兵,李敬文;C_(3n)~2,C_(4n)~2鄰點(diǎn)可區(qū)別的全染色[J];蘭州鐵道學(xué)院學(xué)報(bào);2003年04期

3 李敬文;強(qiáng)會(huì)英;張忠輔;王文杰;王治文;;高度圖的鄰點(diǎn)可區(qū)別的全染色界的一點(diǎn)注[J];蘭州交通大學(xué)學(xué)報(bào);2006年01期

4 王顏妮;王麗偉;劉萍;;幾類圖的鄰點(diǎn)可區(qū)別的全染色[J];科學(xué)技術(shù)與工程;2007年13期

5 王雅琴;劉西奎;王英;;一些圖的鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色[J];大學(xué)數(shù)學(xué);2008年04期

6 劉海濤;;C_(5m)×C_(5n)圖的鄰點(diǎn)可區(qū)別的邊染色[J];河西學(xué)院學(xué)報(bào);2008年02期

7 卞西燕;苗連英;尚華輝;段春燕;馬國翼;;圖的鄰點(diǎn)可區(qū)別邊劃分(英文)[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

8 鄭純;劉煥平;;扇和輪的鄰點(diǎn)強(qiáng)可區(qū)別全染色[J];哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào);2009年05期

9 嚴(yán)謙泰;;k-方圖的一般鄰點(diǎn)可區(qū)別邊染色[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年03期

10 嚴(yán)謙泰;嚴(yán)楷;;關(guān)于圖的一般鄰點(diǎn)可區(qū)別邊染色[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2010年24期

相關(guān)會(huì)議論文 前3條

1 李莉;耿顯民;;一類隨機(jī)圖的鄰點(diǎn)度數(shù)和[A];第十一屆中國不確定系統(tǒng)年會(huì)、第十五屆中國青年信息與管理學(xué)者大會(huì)論文集[C];2013年

2 曹淵;郭永輝;王鐵良;田宙;;自然鄰點(diǎn)插值方法在材料狀態(tài)方程數(shù)據(jù)庫開發(fā)中的應(yīng)用[A];中國計(jì)算力學(xué)大會(huì)'2010（CCCM2010）暨第八屆南方計(jì)算力學(xué)學(xué)術(shù)會(huì)議（SCCM8）論文集[C];2010年

3 劉君;趙傳成;任志國;包世堂;李敬文;張忠輔;;C_m·F_n的鄰點(diǎn)可區(qū)別的邊染色[A];中國運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

相關(guān)博士學(xué)位論文 前3條

1 戴本球;圖的放松的距離二標(biāo)號(hào)著色[D];東南大學(xué);2015年

2 孔海榮;區(qū)組長為4的二維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)[D];河北師范大學(xué);2008年

3 黃丹君;平面圖的鄰點(diǎn)可區(qū)別染色與點(diǎn)蔭度[D];蘇州大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 馬瑞瓊;復(fù)雜網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)算法的研究[D];電子科技大學(xué);2015年

2 焉秋瑤;圖的廣義字典積與半強(qiáng)積的鄰點(diǎn)可區(qū)別和點(diǎn)可區(qū)別染色[D];西北民族大學(xué);2015年

3 張彩霞;幾類圖的鄰點(diǎn)可區(qū)別均勻E-全染色[D];蘭州交通大學(xué);2015年

4 王立麗;關(guān)于幾類圖的Smarandachely鄰點(diǎn)全染色[D];蘭州交通大學(xué);2015年

5 黃晨悅;一類區(qū)組長為5的一維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)的存在性[D];河北師范大學(xué);2016年

6 李曉麗;區(qū)組長為5的二維不含鄰點(diǎn)的平衡樣本設(shè)計(jì)[D];河北師范大學(xué);2016年

7 張曉望;平面圖的邊染色問題[D];山東大學(xué);2016年

8 聶靜方;平面圖的非正常染色[D];浙江師范大學(xué);2016年

9 李曉艷;平面圖的列表染色[D];浙江師范大學(xué);2016年

10 魏邦魁;若干圖的鄰點(diǎn)強(qiáng)可區(qū)別的E-全染色[D];蘭州交通大學(xué);2016年

本文編號(hào)：2547248