資源描述：
《特殊圖類的彩虹點染色畢業(yè)論文》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、1前言1.1課題背景圖論是數(shù)學中的一個重要的分支。它以圖為研究的對象。圖論原本是應(yīng)用數(shù)學的一個重要的分支，為此，歷史上曾有許多位數(shù)學家獨自地建立過圖論。早在1736年歐拉的著作中就出現(xiàn)了關(guān)于圖論的文字記載，最初他所思考的圖論問題都有很強的現(xiàn)實背景。著名的柯尼斯堡七橋問題就是圖論的起源。歐拉證明了這個題目沒有解，并且把這個題目進行推廣，給出了對于一個給定的圖可以以某種方法走遍的判定規(guī)則。這項研究所取得的成果奠定了歐拉圖論〔及拓撲學〕創(chuàng)始人的地位。染色問題是圖論的一類重要的題目，具有重要的實際意義和理論意義。不同類型的圖的染色問題一直是圖論中的熱點題
2、目，而連通圖的染色問題又是其中一種很重要的分支。染色問題就是給定一個圖，把它所有頂點或所有的邊染上顏色，使得相鄰頂點或邊的顏色都不相同時所需要的最少的不同的顏色數(shù)，邊的染色題目可以轉(zhuǎn)化為點染色題目，它們都能歸于將一個圖劃分為獨立子集的理論。目前，伴隨著圖的染色問題在實際問題中被廣泛的應(yīng)用，研究這類問題的學者在逐漸的增多。對不同圖類的染色問題的研究，已經(jīng)有了比較豐富的成果，并且這些結(jié)論還在不斷的完善之中。連通性是圖論中最重要的性質(zhì)之一，2008年，Chartrand，Johns等人首次提出了圖的彩虹連通性的概念，是經(jīng)典連通性概念的一種加強。作為一個
3、自然的組合概念，彩虹連通數(shù)不但有其了理論意義，而且在網(wǎng)絡(luò)問題中起到了非常重要的作用。事實上，它產(chǎn)生于政府機構(gòu)之間機密信息的安全傳輸，在網(wǎng)絡(luò)安全等實際問題中有很多的應(yīng)用。假如我們需要在一個蜂窩網(wǎng)絡(luò)中進行信息的傳輸。在網(wǎng)絡(luò)中的任意兩點在之間都要有一條路相連接，而且在該路徑上的每段都被分配一個獨特的頻道（例如，不同的頻率）。顯而易見，我們需要求出的是能在網(wǎng)絡(luò)中所使用的最少的（不同）頻道個數(shù)。而這個最少個數(shù)恰好是這個網(wǎng)絡(luò)所對應(yīng)無向圖的彩虹連通數(shù)。彩虹點連通的概念是由Krivelevich，Yuster首次提出的，是彩虹連通性的一種重要推廣。它也有著很多實
4、際的應(yīng)用，也同樣是研究的熱點問題之一。1.2問題來源在教學工作中,我們常常能遇到類似這樣的題目：一所學校有n種課程需要由學生來選修，學期結(jié)束后要對學生進行考試。顯然，每個考生每場只能參加一門課程的考試。試問這次考試最少要進行幾場?顯然，不可以在同一個時間進行同一個學生所選修的兩門課程的考試。當然，不會出現(xiàn)同一個學生的不同課程在同一個時間所進行的考試。我們可以把這樣的問題歸結(jié)為：在一個平面上取個頂點分別來表示這門課程。如果有同學同時選擇了課程和，則把點之間連一條邊，可以得到一個有個頂點的無向圖。這樣的問題可以看做給圖的每一個頂點染色，并要求相鄰的兩
5、個頂點染不同的顏色，求最少要進行幾場考試，就是最少能用多少種顏色使得圖的相鄰頂點都有不同顏色。這樣的問題就是頂點染色問題。有關(guān)頂點染色問題的形式有很多種，它們在實際應(yīng)用中也都有著不同的用處。圖的染色問題也是由地圖的染色問題延申而來的：用種顏色給地圖染色，讓地圖上的每一個區(qū)域都有一種一種顏色，并使得相鄰的地區(qū)顏色不同。問題處理：如果把每一個地區(qū)看作一個頂點，把相鄰兩個地區(qū)用一條邊連接起來，就能夠把一個區(qū)域圖看作一個平面圖。例如，圖1（a）所示的區(qū)域圖可看作為圖1（b）所表示的平面圖。19世紀50年代，英國學者提出了任何地圖都可以用4種顏色來染色的問
6、題并稱之為4色猜想。100多年之后，才由美國學者在計算機證明了這個問題，這就是著名的四色定理。例如，在圖1中，把不同的區(qū)域用城市的名字來表示，所染的顏色用不同的數(shù)字來表示，則在圖中表示了不同的地區(qū)用不同的染色來染色的問題。跟圖的邊著色問題一樣，生活中的很多問題，也可以給它們建立一個模型并看作為圖的頂點染色問題來處理。例如課程安排問題，電視頻道分配問題，變址寄存器問題等等。1852年，格里斯注意到可以用4種顏色來為美國地圖進行染色，使得相鄰地區(qū)（有一段公共邊界，不只一個公共點）有不同的顏色，進一步指出了四色猜想。圖11.3研究該課題的意義在日常生活
7、中，還有許多問題可以用彩虹頂點染色加以解決，比如電視頻道分配問題，變址寄存器等，可以運用彩虹染色方法輕松解決，圖的染色理論是圖論中的重要內(nèi)容，也是圖論的起源之一。幾百年來，很多的數(shù)學家們都為此花費了大量的心血去研究。迄今為止，圖論的許多公開問題一直是專家學者們的鉆研的重點題目。在生產(chǎn)管理、軍事、交通運輸、計算機網(wǎng)絡(luò)等許多的領(lǐng)域圖論的知識在其中都有著重要的應(yīng)用，彩虹連接數(shù)在網(wǎng)絡(luò)領(lǐng)域也有很多的應(yīng)用。假設(shè)G代表一個一個細胞網(wǎng)絡(luò)，我們希望在管道的任意兩個頂點之間能夠傳遞消息，這要求每個鏈接上的頂點之間的路由都分配了一個不同的渠道(如不同的頻率)。顯然，我
8、們希望使用不同渠道的數(shù)量降至最低，用彩虹染色的方法就可以解決這個問題。2基本概念2.1圖論、染色問題的基本概念圖是一個二元組使得，所以的
