特殊圖類的彩虹點(diǎn)染色

《特殊圖類的彩虹點(diǎn)染色》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、1前言1.1課題背景圖論是數(shù)學(xué)中的一個(gè)重要的分支。它以圖為研究的對(duì)象。圖論原本是應(yīng)用數(shù)學(xué)的一個(gè)重要的分支，為此，歷史上曾有許多位數(shù)學(xué)家獨(dú)自地建立過(guò)圖論。早在1736年歐拉的著作中就出現(xiàn)了關(guān)于圖論的文字記載，最初他所思考的圖論問(wèn)題都有很強(qiáng)的現(xiàn)實(shí)背景。著名的柯尼斯堡七橋問(wèn)題就是圖論的起源。歐拉證明了這個(gè)題目沒(méi)有解，并且把這個(gè)題目進(jìn)行推廣，給出了對(duì)于一個(gè)給定的圖可以以某種方法走遍的判定規(guī)則。這項(xiàng)研究所取得的成果奠定了歐拉圖論〔及拓?fù)鋵W(xué)〕創(chuàng)始人的地位。染色問(wèn)題是圖論的一類重要的題目，具有重要的實(shí)際意義和理論意義。不同類型的圖的染色問(wèn)題一直是圖論中的熱點(diǎn)題目，而連通圖的染色問(wèn)題又是其中一種很重要

2、的分支。染色問(wèn)題就是給定一個(gè)圖，把它所有頂點(diǎn)或所有的邊染上顏色，使得相鄰頂點(diǎn)或邊的顏色都不相同時(shí)所需要的最少的不同的顏色數(shù)，邊的染色題目可以轉(zhuǎn)化為點(diǎn)染色題目，它們都能歸于將一個(gè)圖劃分為獨(dú)立子集的理論。目前，伴隨著圖的染色問(wèn)題在實(shí)際問(wèn)題中被廣泛的應(yīng)用，研究這類問(wèn)題的學(xué)者在逐漸的增多。對(duì)不同圖類的染色問(wèn)題的研究，已經(jīng)有了比較豐富的成果，并且這些結(jié)論還在不斷的完善之中。連通性是圖論中最重要的性質(zhì)之一，2008年，Chartrand，Johns等人首次提出了圖的彩虹連通性的概念，是經(jīng)典連通性概念的一種加強(qiáng)。作為一個(gè)自然的組合概念，彩虹連通數(shù)不但有其了理論意義，而且在網(wǎng)絡(luò)問(wèn)題中起到了非常重要的作

3、用。事實(shí)上，它產(chǎn)生于政府機(jī)構(gòu)之間機(jī)密信息的安全傳輸，在網(wǎng)絡(luò)安全等實(shí)際問(wèn)題中有很多的應(yīng)用。假如我們需要在一個(gè)蜂窩網(wǎng)絡(luò)中進(jìn)行信息的傳輸。在網(wǎng)絡(luò)中的任意兩點(diǎn)在之間都要有一條路相連接，而且在該路徑上的每段都被分配一個(gè)獨(dú)特的頻道（例如，不同的頻率）。顯而易見(jiàn)，我們需要求出的是能在網(wǎng)絡(luò)中所使用的最少的（不同）頻道個(gè)數(shù)。而這個(gè)最少個(gè)數(shù)恰好是這個(gè)網(wǎng)絡(luò)所對(duì)應(yīng)無(wú)向圖的彩虹連通數(shù)。彩虹點(diǎn)連通的概念是由Krivelevich，Yuster首次提出的，是彩虹連通性的一種重要推廣。它也有著很多實(shí)際的應(yīng)用，也同樣是研究的熱點(diǎn)問(wèn)題之一。1.2問(wèn)題來(lái)源在教學(xué)工作中,我們常常能遇到類似這樣的題目：一所學(xué)校有n種課程需要由

4、學(xué)生來(lái)選修，學(xué)期結(jié)束后要對(duì)學(xué)生進(jìn)行考試。顯然，每個(gè)考生每場(chǎng)只能參加一門(mén)課程的考試。試問(wèn)這次考試最少要進(jìn)行幾場(chǎng)?顯然，不可以在同一個(gè)時(shí)間進(jìn)行同一個(gè)學(xué)生所選修的兩門(mén)課程的考試。當(dāng)然，不會(huì)出現(xiàn)同一個(gè)學(xué)生的不同課程在同一個(gè)時(shí)間所進(jìn)行的考試。我們可以把這樣的問(wèn)題歸結(jié)為：在一個(gè)平面上取個(gè)頂點(diǎn)分別來(lái)表示這門(mén)課程。如果有同學(xué)同時(shí)選擇了課程和，則把點(diǎn)之間連一條邊，可以得到一個(gè)有個(gè)頂點(diǎn)的無(wú)向圖。這樣的問(wèn)題可以看做給圖的每一個(gè)頂點(diǎn)染色，并要求相鄰的兩個(gè)頂點(diǎn)染不同的顏色，求最少要進(jìn)行幾場(chǎng)考試，就是最少能用多少種顏色使得圖的相鄰頂點(diǎn)都有不同顏色。這樣的問(wèn)題就是頂點(diǎn)染色問(wèn)題。有關(guān)頂點(diǎn)染色問(wèn)題的形式有很多種，它們?cè)?/p>

5、實(shí)際應(yīng)用中也都有著不同的用處。圖的染色問(wèn)題也是由地圖的染色問(wèn)題延申而來(lái)的：用種顏色給地圖染色，讓地圖上的每一個(gè)區(qū)域都有一種一種顏色，并使得相鄰的地區(qū)顏色不同。問(wèn)題處理：如果把每一個(gè)地區(qū)看作一個(gè)頂點(diǎn)，把相鄰兩個(gè)地區(qū)用一條邊連接起來(lái)，就能夠把一個(gè)區(qū)域圖看作一個(gè)平面圖。例如，圖1（a）所示的區(qū)域圖可看作為圖1（b）所表示的平面圖。19世紀(jì)50年代，英國(guó)學(xué)者提出了任何地圖都可以用4種顏色來(lái)染色的問(wèn)題并稱之為4色猜想。100多年之后，才由美國(guó)學(xué)者在計(jì)算機(jī)證明了這個(gè)問(wèn)題，這就是著名的四色定理。例如，在圖1中，把不同的區(qū)域用城市的名字來(lái)表示，所染的顏色用不同的數(shù)字來(lái)表示，則在圖中表示了不同的地區(qū)用不

6、同的染色來(lái)染色的問(wèn)題。跟圖的邊著色問(wèn)題一樣，生活中的很多問(wèn)題，也可以給它們建立一個(gè)模型并看作為圖的頂點(diǎn)染色問(wèn)題來(lái)處理。例如課程安排問(wèn)題，電視頻道分配問(wèn)題，變址寄存器問(wèn)題等等。1852年，格里斯注意到可以用4種顏色來(lái)為美國(guó)地圖進(jìn)行染色，使得相鄰地區(qū)（有一段公共邊界，不只一個(gè)公共點(diǎn)）有不同的顏色，進(jìn)一步指出了四色猜想。圖11.3研究該課題的意義在日常生活中，還有許多問(wèn)題可以用彩虹頂點(diǎn)染色加以解決，比如電視頻道分配問(wèn)題，變址寄存器等，可以運(yùn)用彩虹染色方法輕松解決，圖的染色理論是圖論中的重要內(nèi)容，也是圖論的起源之一。幾百年來(lái)，很多的數(shù)學(xué)家們都為此花費(fèi)了大量的心血去研究。迄今為止，圖論的許多公開(kāi)

7、問(wèn)題一直是專家學(xué)者們的鉆研的重點(diǎn)題目。在生產(chǎn)管理、軍事、交通運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)等許多的領(lǐng)域圖論的知識(shí)在其中都有著重要的應(yīng)用，彩虹連接數(shù)在網(wǎng)絡(luò)領(lǐng)域也有很多的應(yīng)用。假設(shè)G代表一個(gè)一個(gè)細(xì)胞網(wǎng)絡(luò)，我們希望在管道的任意兩個(gè)頂點(diǎn)之間能夠傳遞消息，這要求每個(gè)鏈接上的頂點(diǎn)之間的路由都分配了一個(gè)不同的渠道(如不同的頻率)。顯然，我們希望使用不同渠道的數(shù)量降至最低，用彩虹染色的方法就可以解決這個(gè)問(wèn)題。2基本概念2.1圖論、染色問(wèn)題的基本概念圖是一個(gè)二元組使得，所以的