圖的[r,s,t;f]-染色及(p,1)—全標(biāo)號(hào)問題.pdf

1、圖論最早起源于18世紀(jì)三十年代.大數(shù)學(xué)家Eulcr在1736年完成的關(guān)于哥尼斯堡七橋問題的論文，被公認(rèn)為是研究圖論的開山之作.由此，Eulcr也被認(rèn)為是圖論研究的鼻祖.伴隨著圖論的興起和發(fā)展，這門新興的學(xué)科逐漸在化學(xué)、生物學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、博弈論及計(jì)算機(jī)科學(xué)領(lǐng)域產(chǎn)生了廣泛的應(yīng)用.染色理論作為圖論最經(jīng)典的問題之一更是受到了廣泛關(guān)注.由著名的“四色猜想”開始，染色理論逐步成熟和壯大，先后產(chǎn)生了點(diǎn)染色、邊染色、全染色、列表染色、頻

2、道染色、條件染色等一系列新的研究方向.在現(xiàn)實(shí)生活中染色理論有著廣泛的應(yīng)用背景，如時(shí)間表安排問題、工序問題、教室分配問題、選址問題、生產(chǎn)調(diào)度問題、頻道分配問題等等.
　　 本文所考慮的圖都是連通的簡(jiǎn)單有限圖.通常情況下，V(G)，E(G)分別表示一個(gè)圖G的頂點(diǎn)集合和邊集合.｜V(G)｜，｜E(G)｜分別表示圖G的頂點(diǎn)數(shù)和邊數(shù)，有時(shí)也稱為圖的階和大小.圖G的一個(gè)正常k-全染色是指用k種顏色對(duì)V∪E中的元素進(jìn)行著色，使得任何兩個(gè)相鄰接

3、或相關(guān)聯(lián)的元素獲得不同的顏色.使得圖G存在一個(gè)正常k-全染色的最小正整數(shù)k稱為圖G的全色數(shù)，記作x(11)(G).若只對(duì)圖G的頂點(diǎn)（邊）進(jìn)行著色，則稱為是圖的一個(gè)點(diǎn)（邊）染色.顯然，全染色是對(duì)點(diǎn)染色和邊染色的推廣.
　　 Bchzad和Vizing分別在其論文中獨(dú)立地給出了如下著名的全染色猜想.全染色猜想.對(duì)任意圖G，都有(11)-(G)≤△+2.盡管圍繞著這個(gè)猜想已有大量的文獻(xiàn)，該問題卻至今仍未得到完全解決.
　　 本

4、文主要討論兩類新的染色問題，也可以稱為兩類標(biāo)號(hào)問題，即圖的[r，s，t;f]-染色及p，1)-全標(biāo)號(hào).二者都可以看做是圖的全染色的進(jìn)一步推廣.
　　 令r，s，t是三個(gè)非負(fù)整數(shù)，f是一個(gè)定義在圖G的頂點(diǎn)集合V上取值為正整數(shù)的函數(shù).圖G的一個(gè)[r，s，t;f]-染色即給圖的每個(gè)頂點(diǎn)和每條邊都從顏色集C={1，2，…，k}中分配一種顏色使得相鄰的頂點(diǎn)獲得的顏色差不小于r;每個(gè)頂點(diǎn)所關(guān)聯(lián)的邊滿足(1)獲得不同顏色的邊的顏色差不小于s并

5、且(2)獲得相同顏色的邊數(shù)不超過f(u);相關(guān)聯(lián)的點(diǎn)和邊所獲得的顏色差不小于t.我們把使得圖存在[r，s，t;f]-染色的最小的顏色數(shù)k稱為圖G的[r，s，t;f]-色數(shù)，并記作xr，8，t;f(G).
　　 圖的[r，s，t;f]-染色是我們首次提出的一個(gè)新的染色概念，它可以看作是對(duì)[r，s，t]-染色的進(jìn)一步推廣.[r，s，t]-染色的概念最初是由Kcmnitz和Marangio提出的.他們研究了該染色的一些性質(zhì)并用足球比賽

6、的日程安排問題舉例說明了其實(shí)際的應(yīng)用價(jià)值。Kcmnitz和Marangio給出了參數(shù)xr，8，t(G)的一些上下界并針對(duì)參數(shù)r，s，t分別取一些特定值的情況得到了一系列的結(jié)果.[r，s，t]-染色是一個(gè)難度比較大的問題，即使對(duì)于星K1,n和完全圖Kn等一些簡(jiǎn)單的圖類也沒有完全地解決.
　　 頻道分配問題實(shí)質(zhì)上是一個(gè)如何分配無(wú)線電頻道資源以實(shí)現(xiàn)最合理應(yīng)用的最優(yōu)化問題.這個(gè)課題曾經(jīng)被AT&T貝爾實(shí)驗(yàn)室，美國(guó)國(guó)家安全局等多個(gè)機(jī)構(gòu)的研究

7、部門所研究.在頻道分配問題中，我們需要將無(wú)線電頻率（圖論模型中用一些正整數(shù)代替）分配給不同的無(wú)線電接收裝置.為了避免互相干擾而影響信號(hào)的傳送，如果兩個(gè)無(wú)線電接收裝置緊挨著，則要求分配給它們的頻率段至少差2，如果兩個(gè)無(wú)線電接收裝置靠的比較近但不是緊挨著（比如相隔一個(gè)無(wú)線電接收裝置），則要求分配給它們的頻率段至少差1.受這個(gè)問題的啟發(fā)，RogcrYch提出了L(2，1)-標(biāo)號(hào)問題并很快被推廣到L(p，q)-標(biāo)號(hào)的形式.
　　 圖的關(guān)

8、聯(lián)圖是指將圖G中的每條邊都用一條長(zhǎng)為2的路代替所形成的新圖.Havct將一個(gè)圖的關(guān)聯(lián)圖的L(p，1)-標(biāo)號(hào)問題定義為圖的(p，1)-全標(biāo)號(hào)問題.該問題也可以被看作是全染色問題的一種推廣形式.一個(gè)圖G稱為是可k-(p，1)-全標(biāo)號(hào)的當(dāng)且僅當(dāng)存在一個(gè)將V(G)∪E(G)映射到顏色集合{0，1，…，k}的函數(shù)c滿足:(1)若uu∈E(G)，則｜c(diǎn)（u）-c(u)｜≥1;(2)若e和e′是G的相鄰邊，則｜c(diǎn)(e)-c(e′)｜≥1;(3)若頂點(diǎn)

9、u和邊e相關(guān)聯(lián)，則｜c(diǎn)(u)-c(e)｜≥p.使得G可k-(p，1）-全標(biāo)號(hào)的最小的正整數(shù)k稱為是圖G的(p，1)-全標(biāo)號(hào)數(shù)，并記作λTp(G).
　　 本文主要討論圖的[r，s，t;f]-染色及(p，1）-全標(biāo)號(hào).文章的主要內(nèi)容及結(jié)構(gòu)安排如下.
　　 第一章是緒論部分.本章的第一小節(jié)是對(duì)文中出現(xiàn)和用到的一些基本概念和符號(hào)的簡(jiǎn)單說明，第二小節(jié)則分別從全染色，圖的[r，s，t卜染色與f-染色和頻道分配問題三個(gè)方面對(duì)論文研究

10、內(nèi)容的背景做了相對(duì)完整的介紹，接下來(lái)的第三小節(jié)則給出我們所研究的圖的[r，s，t;f]-染色及(p，1）-全標(biāo)號(hào)問題的基本定義.最后，本章的第四小節(jié)將列出論文中證明的主要結(jié)論.
　　 第二章主要討論[r，s，t;f]-染色.在這一章的第一小節(jié)中我們先對(duì)[r，s，t]-染色的一些背景和已知結(jié)果做一個(gè)簡(jiǎn)單的概括，并介紹一些在主要定理的證明中用到的符號(hào)和術(shù)語(yǔ).接下來(lái)的第二小節(jié)是本章的重點(diǎn)部分，在這一節(jié)里我們將給出主要的結(jié)果及其證明，最

11、后的第三小節(jié)接著給出幾個(gè)可以繼續(xù)研究的問題.
　　 第三章主要討論圖的(p，1)-全標(biāo)號(hào).第一小節(jié)對(duì)(p，1)-全標(biāo)號(hào)問題的起源和背景做一個(gè)簡(jiǎn)單的介紹并給出(p，1)-全標(biāo)號(hào)猜想，第二小節(jié)主要介紹該問題的研究進(jìn)展和對(duì)于一些特殊圖類已經(jīng)取得的結(jié)果，第三小節(jié)首先給出一些在主要定理的證明過程中用到的概念和結(jié)構(gòu)性引理，接下來(lái)則主要考慮與平面圖相關(guān)的一些圖類的(p，1)-全標(biāo)號(hào)問題，從而為(p，1）-全標(biāo)號(hào)猜想的成立提供新的依據(jù).第四小節(jié)

12、將給出關(guān)于(p，1）-全標(biāo)號(hào)猜想可以進(jìn)一步研究的問題.
　　 第四章主要討論圖的列表(p，1)-全標(biāo)號(hào)問題.在這一章的第一小節(jié)我們先對(duì)列表(p，1）-全標(biāo)號(hào)問題做一個(gè)總體的介紹，第二小節(jié)類比列表全染色猜想給出一個(gè)關(guān)于列表(p，1)-全標(biāo)號(hào)數(shù)上界的猜想，這里不妨稱為弱列表(p，1)-全標(biāo)號(hào)猜想，第三小節(jié)主要考慮一些特殊圖類，如星、外可平面圖、可嵌入歐拉示性數(shù)為ε的曲面的圖等，通過證明這些特殊圖類的列表(p，1)-全標(biāo)號(hào)數(shù)的上界，進(jìn)