版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、圖論最早起源于18世紀三十年代.大數(shù)學(xué)家Eulcr在1736年完成的關(guān)于哥尼斯堡七橋問題的論文,被公認為是研究圖論的開山之作.由此,Eulcr也被認為是圖論研究的鼻祖.伴隨著圖論的興起和發(fā)展,這門新興的學(xué)科逐漸在化學(xué)、生物學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、博弈論及計算機科學(xué)領(lǐng)域產(chǎn)生了廣泛的應(yīng)用.染色理論作為圖論最經(jīng)典的問題之一更是受到了廣泛關(guān)注.由著名的“四色猜想”開始,染色理論逐步成熟和壯大,先后產(chǎn)生了點染色、邊染色、全染色、列表染色、頻
2、道染色、條件染色等一系列新的研究方向.在現(xiàn)實生活中染色理論有著廣泛的應(yīng)用背景,如時間表安排問題、工序問題、教室分配問題、選址問題、生產(chǎn)調(diào)度問題、頻道分配問題等等.
本文所考慮的圖都是連通的簡單有限圖.通常情況下,V(G),E(G)分別表示一個圖G的頂點集合和邊集合.|V(G)|,|E(G)|分別表示圖G的頂點數(shù)和邊數(shù),有時也稱為圖的階和大小.圖G的一個正常k-全染色是指用k種顏色對V∪E中的元素進行著色,使得任何兩個相鄰接
3、或相關(guān)聯(lián)的元素獲得不同的顏色.使得圖G存在一個正常k-全染色的最小正整數(shù)k稱為圖G的全色數(shù),記作x(11)(G).若只對圖G的頂點(邊)進行著色,則稱為是圖的一個點(邊)染色.顯然,全染色是對點染色和邊染色的推廣.
Bchzad和Vizing分別在其論文中獨立地給出了如下著名的全染色猜想.全染色猜想.對任意圖G,都有(11)-(G)≤△+2.盡管圍繞著這個猜想已有大量的文獻,該問題卻至今仍未得到完全解決.
本
4、文主要討論兩類新的染色問題,也可以稱為兩類標號問題,即圖的[r,s,t;f]-染色及p,1)-全標號.二者都可以看做是圖的全染色的進一步推廣.
令r,s,t是三個非負整數(shù),f是一個定義在圖G的頂點集合V上取值為正整數(shù)的函數(shù).圖G的一個[r,s,t;f]-染色即給圖的每個頂點和每條邊都從顏色集C={1,2,…,k}中分配一種顏色使得相鄰的頂點獲得的顏色差不小于r;每個頂點所關(guān)聯(lián)的邊滿足(1)獲得不同顏色的邊的顏色差不小于s并
5、且(2)獲得相同顏色的邊數(shù)不超過f(u);相關(guān)聯(lián)的點和邊所獲得的顏色差不小于t.我們把使得圖存在[r,s,t;f]-染色的最小的顏色數(shù)k稱為圖G的[r,s,t;f]-色數(shù),并記作xr,8,t;f(G).
圖的[r,s,t;f]-染色是我們首次提出的一個新的染色概念,它可以看作是對[r,s,t]-染色的進一步推廣.[r,s,t]-染色的概念最初是由Kcmnitz和Marangio提出的.他們研究了該染色的一些性質(zhì)并用足球比賽
6、的日程安排問題舉例說明了其實際的應(yīng)用價值。Kcmnitz和Marangio給出了參數(shù)xr,8,t(G)的一些上下界并針對參數(shù)r,s,t分別取一些特定值的情況得到了一系列的結(jié)果.[r,s,t]-染色是一個難度比較大的問題,即使對于星K1,n和完全圖Kn等一些簡單的圖類也沒有完全地解決.
頻道分配問題實質(zhì)上是一個如何分配無線電頻道資源以實現(xiàn)最合理應(yīng)用的最優(yōu)化問題.這個課題曾經(jīng)被AT&T貝爾實驗室,美國國家安全局等多個機構(gòu)的研究
7、部門所研究.在頻道分配問題中,我們需要將無線電頻率(圖論模型中用一些正整數(shù)代替)分配給不同的無線電接收裝置.為了避免互相干擾而影響信號的傳送,如果兩個無線電接收裝置緊挨著,則要求分配給它們的頻率段至少差2,如果兩個無線電接收裝置靠的比較近但不是緊挨著(比如相隔一個無線電接收裝置),則要求分配給它們的頻率段至少差1.受這個問題的啟發(fā),RogcrYch提出了L(2,1)-標號問題并很快被推廣到L(p,q)-標號的形式.
圖的關(guān)
8、聯(lián)圖是指將圖G中的每條邊都用一條長為2的路代替所形成的新圖.Havct將一個圖的關(guān)聯(lián)圖的L(p,1)-標號問題定義為圖的(p,1)-全標號問題.該問題也可以被看作是全染色問題的一種推廣形式.一個圖G稱為是可k-(p,1)-全標號的當且僅當存在一個將V(G)∪E(G)映射到顏色集合{0,1,…,k}的函數(shù)c滿足:(1)若uu∈E(G),則|c(u)-c(u)|≥1;(2)若e和e′是G的相鄰邊,則|c(e)-c(e′)|≥1;(3)若頂點
9、u和邊e相關(guān)聯(lián),則|c(u)-c(e)|≥p.使得G可k-(p,1)-全標號的最小的正整數(shù)k稱為是圖G的(p,1)-全標號數(shù),并記作λTp(G).
本文主要討論圖的[r,s,t;f]-染色及(p,1)-全標號.文章的主要內(nèi)容及結(jié)構(gòu)安排如下.
第一章是緒論部分.本章的第一小節(jié)是對文中出現(xiàn)和用到的一些基本概念和符號的簡單說明,第二小節(jié)則分別從全染色,圖的[r,s,t卜染色與f-染色和頻道分配問題三個方面對論文研究
10、內(nèi)容的背景做了相對完整的介紹,接下來的第三小節(jié)則給出我們所研究的圖的[r,s,t;f]-染色及(p,1)-全標號問題的基本定義.最后,本章的第四小節(jié)將列出論文中證明的主要結(jié)論.
第二章主要討論[r,s,t;f]-染色.在這一章的第一小節(jié)中我們先對[r,s,t]-染色的一些背景和已知結(jié)果做一個簡單的概括,并介紹一些在主要定理的證明中用到的符號和術(shù)語.接下來的第二小節(jié)是本章的重點部分,在這一節(jié)里我們將給出主要的結(jié)果及其證明,最
11、后的第三小節(jié)接著給出幾個可以繼續(xù)研究的問題.
第三章主要討論圖的(p,1)-全標號.第一小節(jié)對(p,1)-全標號問題的起源和背景做一個簡單的介紹并給出(p,1)-全標號猜想,第二小節(jié)主要介紹該問題的研究進展和對于一些特殊圖類已經(jīng)取得的結(jié)果,第三小節(jié)首先給出一些在主要定理的證明過程中用到的概念和結(jié)構(gòu)性引理,接下來則主要考慮與平面圖相關(guān)的一些圖類的(p,1)-全標號問題,從而為(p,1)-全標號猜想的成立提供新的依據(jù).第四小節(jié)
12、將給出關(guān)于(p,1)-全標號猜想可以進一步研究的問題.
第四章主要討論圖的列表(p,1)-全標號問題.在這一章的第一小節(jié)我們先對列表(p,1)-全標號問題做一個總體的介紹,第二小節(jié)類比列表全染色猜想給出一個關(guān)于列表(p,1)-全標號數(shù)上界的猜想,這里不妨稱為弱列表(p,1)-全標號猜想,第三小節(jié)主要考慮一些特殊圖類,如星、外可平面圖、可嵌入歐拉示性數(shù)為ε的曲面的圖等,通過證明這些特殊圖類的列表(p,1)-全標號數(shù)的上界,進
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 圖的[r,s,t;f]-染色及(p,1)—全標號問題.pdf
- 圖的泛寬度染色和(p,1)-全標號.pdf
- 幾類圖的泛寬度染色和(p,1)-全標號.pdf
- 圖的(p,1_)全標號及圖的弱鄰點可區(qū)分的染色問題.pdf
- 圖的[r,s,t]-染色.pdf
- 圖的(p,1)-全標號和非正常標號.pdf
- 幾類圖的r-hued染色和距離標號.pdf
- 圖的幾種N(p,q)標號問題與圖的兩類染色問題.pdf
- 有鄰域限制的圖染色問題及圖的L(2,1)-標號.pdf
- S?e?l?f?-?a?d?a?p?t?i?v?e? ?a?n?d? ?s?e?l?f?-?c?o?n?f?i?g?u?r?e?d? ?C?P?U? 省略? ?s?e?r?v?e?r?s? ?u?s?i?n?g? ?K?a?l?m?a?n? ?f?i?l?t?e?r?s.pdf
- S?e?l?f?-?a?d?a?p?t?i?v?e? ?a?n?d? ?s?e?l?f?-?c?o?n?f?i?g?u?r?e?d? ?C?P?U? 省略? ?s?e?r?v?e?r?s? ?u?s?i?n?g? ?K?a?l?m?a?n? ?f?i?l?t?e?r?s.pdf
- E?s?t?i?m?a?t?i?n?g? ?t?h?e? ?S?t?r?e?n?g?t?h? ?o?f? ?C?o?n?c?r?e?t?e? ?U?s?i?n?g? ?S?u?r?f?a?c?e? 省略?P?a?r?a?m?e?t?e?r?s? ?o?f? ?C?o?n?c?r?e?t?e? ?M?a?t?e?r?i?a?l.pdf
- E?s?t?i?m?a?t?i?n?g? ?t?h?e? ?S?t?r?e?n?g?t?h? ?o?f? ?C?o?n?c?r?e?t?e? ?U?s?i?n?g? ?S?u?r?f?a?c?e? 省略?P?a?r?a?m?e?t?e?r?s? ?o?f? ?C?o?n?c?r?e?t?e? ?M?a?t?e?r?i?a?l.pdf
- 圖的(d,1)-全標號及游戲著色.pdf
- 特殊圖類的標號染色.pdf
- 特殊圖的(d,1)—全標號.pdf
- K-,n,n-的[r,s,t]-染色.pdf
- 圖的[r,s,t]-著色.pdf
- 圖的L(p,q)-標號問題研究.pdf
- 若干圖的(d,1)全標號和(2,1)標號的研究.pdf
評論
0/150
提交評論