【正文】 色，使得相鄰地區(qū)（有一段公共邊界，不只一個(gè)公共點(diǎn)）有不同的顏色，進(jìn)一步指出了四色猜想。跟圖的邊著色問題一樣，生活中的很多問題，也可以給它們建立一個(gè)模型并看作為圖的頂點(diǎn)染色問題來處理。100多年之后，才由美國學(xué)者在計(jì)算機(jī)證明了這個(gè)問題，這就是著名的四色定理。例如，圖1（a）所示的區(qū)域圖可看作為圖1（b）所表示的平面圖。圖的染色問題也是由地圖的染色問題延申而來的：用種顏色給地圖染色，讓地圖上的每一個(gè)區(qū)域都有一種一種顏色，并使得相鄰的地區(qū)顏色不同。這樣的問題就是頂點(diǎn)染色問題。如果有同學(xué)同時(shí)選擇了課程和，則把點(diǎn)之間連一條邊，可以得到一個(gè)有個(gè)頂點(diǎn)的無向圖。當(dāng)然，不會出現(xiàn)同一個(gè)學(xué)生的不同課程在同一個(gè)時(shí)間所進(jìn)行的考試。顯然，每個(gè)考生每場只能參加一門課程的考試。它也有著很多實(shí)際的應(yīng)用，也同樣是研究的熱點(diǎn)問題之一。而這個(gè)最少個(gè)數(shù)恰好是這個(gè)網(wǎng)絡(luò)所對應(yīng)無向圖的彩虹連通數(shù)。在網(wǎng)絡(luò)中的任意兩點(diǎn)在之間都要有一條路相連接，而且在該路徑上的每段都被分配一個(gè)獨(dú)特的頻道（例如，不同的頻率）。事實(shí)上，它產(chǎn)生于政府機(jī)構(gòu)之間機(jī)密信息的安全傳輸，在網(wǎng)絡(luò)安全等實(shí)際問題中有很多的應(yīng)用。連通性是圖論中最重要的性質(zhì)之一，2008年，Chartrand，Johns等人首次提出了圖的彩虹連通性的概念，是經(jīng)典連通性概念的一種加強(qiáng)。目前，伴隨著圖的染色問題在實(shí)際問題中被廣泛的應(yīng)用，研究這類問題的學(xué)者在逐漸的增多。不同類型的圖的染色問題一直是圖論中的熱點(diǎn)題目，而連通圖的染色問題又是其中一種很重要的分支。這項(xiàng)研究所取得的成果奠定了歐拉圖論〔及拓?fù)鋵W(xué)〕創(chuàng)始人的地位。著名的柯尼斯堡七橋問題就是圖論的起源。圖論原本是應(yīng)用數(shù)學(xué)的一個(gè)重要的分支，為此，歷史上曾有許多位數(shù)學(xué)家獨(dú)自地建立過圖論。1 前言圖論是數(shù)學(xué)中的一個(gè)重要的分支。它以圖為研究的對象。早在1736年歐拉的著作中就出現(xiàn)了關(guān)于圖論的文字記載，最初他所思考的圖論問題都有很強(qiáng)的現(xiàn)實(shí)背景。歐拉證明了這個(gè)題目沒有解，并且把這個(gè)題目進(jìn)行推廣，給出了對于一個(gè)給定的圖可以以某種方法走遍的判定規(guī)則。染色問題是圖論的一類重要的題目，具有重要的實(shí)際意義和理論意義。染色問題就是給定一個(gè)圖，把它所有頂點(diǎn)或所有的邊染上顏色，使得相鄰頂點(diǎn)或邊的顏色都不相同時(shí)所需要的最少的不同的顏色數(shù)，邊的染色題目可以轉(zhuǎn)化為點(diǎn)染色題目，它們都能歸于將一個(gè)圖劃分為獨(dú)立子集的理論。對不同圖類的染色問題的研究，已經(jīng)有了比較豐富的成果，并且這些結(jié)論還在不斷的完善之中。作為一個(gè)自然的組合概念，彩虹連通數(shù)不但有其了理論意義，而且在網(wǎng)絡(luò)問題中起到了非常重要的作用。假如我們需要在一個(gè)蜂窩網(wǎng)絡(luò)中進(jìn)行信息的傳輸。顯而易見，我們需要求出的是能在網(wǎng)絡(luò)中所使用的最少的（不同）頻道個(gè)數(shù)。彩虹點(diǎn)連通的概念是由Krivelevich，Yuster首次提出的，是彩虹連通性的一種重要推廣。在教學(xué)工作中,我們常常能遇到類似這樣的題目：一所學(xué)校有n種課程需要由學(xué)生來選修，學(xué)期結(jié)束后要對學(xué)生進(jìn)行考試。試問這次考試最少要進(jìn)行幾場? 顯然，不可以在同一個(gè)時(shí)間進(jìn)行同一個(gè)學(xué)生所選修的兩門課程的考試。我們可以把這樣的問題歸結(jié)為：在一個(gè)平面上取個(gè)頂點(diǎn)分別來表示這門課程。這樣的問題可以看做給圖的每一個(gè)頂點(diǎn)染色，并要求相鄰的兩個(gè)頂點(diǎn)染不同的顏色，求最少要進(jìn)行幾場考試，就是最少能用多少種顏色使得圖的相鄰頂點(diǎn)都有不同顏色。有關(guān)頂點(diǎn)染色問題的形式有很多種，它們在實(shí)際應(yīng)用中也都有著不同的用處。問題處理：如果把每一個(gè)地區(qū)看作一個(gè)頂點(diǎn)，把相鄰兩個(gè)地區(qū)用一條邊連接起來，就能夠把一個(gè)區(qū)域圖看作一個(gè)平面圖。19世紀(jì)50年代，英國學(xué)者提出了任何地圖都可以用4種顏色來染色的問題并稱之為4色猜想。例如，在圖1中，把不同的區(qū)域用城市的名字來表示，所染的顏色用不同的數(shù)字來表示，則在圖中表示了不同的地區(qū)用不同的染色來染色的問題。例如課程安排問題，電視頻道分配問題，變址寄存器問題等等。圖 1 研究該課題的意義在日常生活中，還有許多問題可以用彩虹頂點(diǎn)染色加以解決，比如電視頻道分配問題，變址寄存器等，可以運(yùn)用彩虹染色方法輕松解決，圖的染色理論是圖論中的重要內(nèi)容，也是圖論的起源之一。迄今為止，圖論的許多公開問題一直是專家學(xué)者們的鉆研的重點(diǎn)題目。假設(shè)G代表一個(gè)一個(gè)細(xì)胞網(wǎng)絡(luò)，我們希望在管道的任意兩個(gè)頂點(diǎn)之間能夠傳遞消息，這要求每個(gè)鏈接上的頂點(diǎn)之間的路由都分配了一個(gè)不同的渠道(如不同的頻率)。2 基本概念、染色問題的基本概念圖是一個(gè)二元組使得，所以的元素是的元子集。圖的頂點(diǎn)集合是中的各個(gè)元素，頂點(diǎn)的集合記作；而圖的邊的集合為中的元素，邊的集合記作。根據(jù)圖的階數(shù)，我們把圖分為有限的、無限的、可數(shù)的等等，在本文中所研究的圖，我們總是假定圖是有限的，階為的有限圖，即。在無向圖中，如果與頂點(diǎn)和相連接的無向邊多于一條，則把這些邊稱作平行邊，而平行邊的條數(shù)我們稱之為重?cái)?shù)。圖的邊的集合中，每個(gè)元素對為一對頂點(diǎn)構(gòu)成的無序?qū)Γ硎卷旤c(diǎn)和相關(guān)聯(lián)的一條無向邊，因此和是同一條邊。本文所研究用到的圖均為有限的簡單無向圖。 一個(gè)頂點(diǎn)的度數(shù)是指與它相關(guān)聯(lián)的邊的數(shù)目。圖形的最小度指的是所有頂點(diǎn)之間的最小度，記為；而圖最大度：指的是所有頂點(diǎn)之間的最大度數(shù)，記為。頂點(diǎn)和由路連接，并稱它們是路的端點(diǎn)，而稱為的內(nèi)部頂點(diǎn)。 在無向圖中，若從頂點(diǎn)到有一條路相連，則稱和之間是連通的。 如果一個(gè)圖的任意兩個(gè)不同的頂點(diǎn)之間都有條相互獨(dú)立的路連接，則把圖稱作連通的。如果圖的任意兩個(gè)不同頂點(diǎn)之間都有條邊不相交的路相連，則稱圖是邊連通的。圖的頂點(diǎn)染色稱為正常（頂點(diǎn)）染色，如果的每條邊的兩端點(diǎn)都染不同顏色。這樣的一個(gè)頂點(diǎn)染色給出了的一個(gè)劃分（）使每個(gè)都是的一個(gè)獨(dú)立集。我們可以得出以下簡單的結(jié)果。 為一完全圖。 為部圖。 為可著色的（k=j）最簡單的連通圖是圈，并且其它的圖都可以由一個(gè)圈通過不斷添加路而得到。如果圖是一個(gè)邊數(shù)為的非平凡連通圖，則有。我們稱里的顏色為可用顏色，并且主要研究的是的基數(shù)。若，我們就把圖稱作色的；如果，則稱圖為可染色的。邊染色稱為圖的一個(gè)邊染色，所使用的最小整數(shù)稱為的邊色數(shù)，也成為色指數(shù)，記做。如果一個(gè)邊染色圖的任意兩個(gè)不同頂點(diǎn)之間有一條邊染不同染色的路徑相連，那么就稱它是彩虹連通的。Krivelevich和Yuster提出了彩虹點(diǎn)聯(lián)通的概念。彩虹點(diǎn)連通數(shù)就是一個(gè)連通圖它構(gòu)成彩虹點(diǎn)連通圖所需的最少的顏色數(shù)，記做。注意到，當(dāng)圖直徑為1和2時(shí)，它們相等。在某些情況下可以比要小得多。另一方面，