【正文】 為偶數(shù)時(shí)取中間的兩個(gè)頂點(diǎn)染上所用過(guò)的顏色，其余點(diǎn)分別進(jìn)行染色；當(dāng)為奇數(shù)時(shí)取中間的一個(gè)點(diǎn)染所使用的顏色，其余點(diǎn)分別進(jìn)行染色，如下圖所示圖 7從而有的彩虹點(diǎn)連通數(shù)，按照這個(gè)方法對(duì)圖的剩下的邊進(jìn)行研究，最后得出圖的彩虹頂點(diǎn)連通數(shù)的一個(gè)上界：。經(jīng)過(guò)圖例的觀察內(nèi)部頂點(diǎn)為一個(gè)時(shí)的輪圖，發(fā)現(xiàn)當(dāng)時(shí)輪圖是一個(gè)完全圖，；當(dāng)時(shí)，無(wú)論怎樣的去增加圈上的頂點(diǎn)它的始終不變。第三種圖類是在輪圖的基礎(chǔ)上進(jìn)行的推廣，這類圖也還可以有很多種變換，我所研究的都是這些圖雷中相對(duì)簡(jiǎn)單的，所以還需要更多時(shí)間和努力才能把這些圖類研究透徹。我們已經(jīng)在前面說(shuō)明了圈的彩虹點(diǎn)連通數(shù)，接下來(lái)也將給出輪圖的彩虹連通數(shù)，并證明。因此。首先，是彩虹染色，使用了中顏色。是從附加一條長(zhǎng)度至少為的路徑到得到的，用兩個(gè)不同的頂點(diǎn)來(lái)辨別路徑的末端點(diǎn)。歸納證明了，對(duì)于的染色滿足所有的需求。分別把的第一條邊和最后一條邊射入到和。對(duì)于任意的頂點(diǎn)和任意集合，這里有從到的條路徑，使得對(duì)于其中的任意兩條路，僅僅只有一個(gè)共同頂點(diǎn)。對(duì)于連通圖的彩虹連通數(shù)，記作，即。由歸納假設(shè)，是可用5種顏色正常頂點(diǎn)染色的。當(dāng)這個(gè)定理被提出后，很多科學(xué)家都希望能對(duì)此進(jìn)行證明，但都沒(méi)有成功。 A2: MA, LA, G 。由于是強(qiáng)，每個(gè)具有至少個(gè)相鄰的點(diǎn)在中。 若是具有個(gè)頂點(diǎn)和最小度的圖形，則有二階點(diǎn)集，其大小至多為。類似的我們定義連通圖的強(qiáng)彩虹連通數(shù)是使圖強(qiáng)彩虹連通所需要的最少的顏色數(shù)，記作。另一方面，在某些其他情況下，可以比小很多。我們稱里的顏色為可用顏色，并且主要研究的是的基數(shù)。如果圖的任意兩個(gè)不同頂點(diǎn)之間都有條邊不相交的路相連，則稱圖是邊連通的。在無(wú)向圖中，如果與頂點(diǎn)和相連接的無(wú)向邊多于一條，則把這些邊稱作平行邊，而平行邊的條數(shù)我們稱之為重?cái)?shù)。例如，在圖1中，把不同的區(qū)域用城市的名字來(lái)表示，所染的顏色用不同的數(shù)字來(lái)表示，則在圖中表示了不同的地區(qū)用不同的染色來(lái)染色的問(wèn)題。彩虹點(diǎn)連通的概念是由Krivelevich，Yuster首次提出的，是彩虹連通性的一種重要推廣。早在1736年歐拉的著作中就出現(xiàn)了關(guān)于圖論的文字記載，最初他所思考的圖論問(wèn)題都有很強(qiáng)的現(xiàn)實(shí)背景。連通性是圖論中最重要的性質(zhì)之一，2008年，Chartrand，Johns等人首次提出了圖的彩虹連通性的概念，是經(jīng)典連通性概念的一種加強(qiáng)。這樣的問(wèn)題就是頂點(diǎn)染色問(wèn)題。顯然，我們希望使用不同渠道的數(shù)量降至最低，用彩虹染色的方法就可以解決這個(gè)問(wèn)題。圖是一條路，如果其頂點(diǎn)集和邊集分別為，這里的均互不相同。 為可著色的 219。一個(gè)點(diǎn)染色圖的任意兩點(diǎn)之間有一條內(nèi)部頂點(diǎn)染不同顏色的路相連，則稱它是彩虹點(diǎn)連通的。事實(shí)上，這個(gè)新概念形成于政府機(jī)構(gòu)之間的信息傳遞。（1）當(dāng)且僅當(dāng)是一個(gè)完全圖；（2）當(dāng)且僅當(dāng)；（3）當(dāng)且僅當(dāng)是一條n階的路。：定理的語(yǔ)句在是不準(zhǔn)確的，所以我們假定。3 生活中的一些實(shí)際問(wèn)題 圖著色問(wèn)題的應(yīng)用—選課問(wèn)題類似于圖的邊染色的問(wèn)題，生活中的許多問(wèn)題都可以建立模型為圖的頂點(diǎn)著色問(wèn)題來(lái)處理。建立如下圖所示的模型，把課程看作為圖的頂點(diǎn)，兩頂點(diǎn)之間的連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門(mén)課程。希伍德卻發(fā)現(xiàn)了這個(gè)證明中存在了一些錯(cuò)誤，他對(duì)肯普的證明加以修改，就得到了現(xiàn)在的五色定理。假如我們事先知道圖的一個(gè)著色為。那么這樣的連通圖就是一個(gè)著名的亞族。接下來(lái)，先對(duì)每個(gè)定義一個(gè)邊染色。情況：。這就完成了定理的證明，因此定理也就成立了。加入的和方向同上面方法一樣。首先，因?yàn)?，如果給圖染色，少于種顏色，那么對(duì)于某些頂點(diǎn)，在中存在唯一的路徑不是彩虹路。我們?cè)賮?lái)研究一類圖——輪圖，輪圖可簡(jiǎn)單定義為，因?yàn)榧尤氲街校a(chǎn)生了一個(gè)新的頂點(diǎn)與的每個(gè)頂點(diǎn)相連。上述研究只是一個(gè)大概的范圍，下面我們來(lái)研究一下，當(dāng)圈上的點(diǎn)數(shù)為具體數(shù)值時(shí)的情況。圖 15綜上所述，有。對(duì)于的圈，在圈中加入一個(gè)頂點(diǎn)，使得與圈上的每個(gè)頂點(diǎn)連接，那么這樣的圖就稱作輪圖。因此。因此，我們能夠重復(fù)加入和重復(fù)導(dǎo)向，按照這樣做法，對(duì)于達(dá)到一個(gè)外部和一個(gè)導(dǎo)向。我們可以知道，當(dāng)時(shí)圈，有個(gè)頂點(diǎn)時(shí)，彩虹連通數(shù)。對(duì)邊進(jìn)行染色，路徑的第一條邊和路徑的最后一條邊染色，路徑的最后一條邊和路徑的第一條邊染色。假設(shè)有一個(gè)邊染色，顏色是，其中。定理2如果是一個(gè)連通圖，頂點(diǎn)，那么存在圖的一個(gè)邊染色，至多是種顏色滿足以下結(jié)論： 對(duì)于任意兩個(gè)頂點(diǎn)，這里存在兩條不相交的彩虹路； 對(duì)于任意一個(gè)頂點(diǎn)，任意集合，且，這里兩條彩虹路，只有頂點(diǎn)相同； 對(duì)于任意兩個(gè)集合，且，這里的兩條彩虹路不相交。因此，設(shè)法構(gòu)想一適當(dāng)?shù)捻旤c(diǎn)排序進(jìn)行貪心著色，往往可能得到一個(gè)較好的著色結(jié)果（如Brooks定理之證明）。當(dāng)時(shí)，結(jié)論顯然。 儲(chǔ)藏問(wèn)題一家公司制造種化學(xué)制品，其中某些制品是互不相容的，如果它們互相接觸，則會(huì)引起爆炸，作為一種預(yù)防措施，公司希望把它的倉(cāng)庫(kù)分為間隔，以便把不相容的化學(xué)制品儲(chǔ)藏在不同的間隔里，試問(wèn)：這個(gè)倉(cāng)庫(kù)至少應(yīng)該分成幾個(gè)間隔？問(wèn)題處理：構(gòu)造一個(gè)圖，其頂點(diǎn)集是兩個(gè)頂點(diǎn)和相連當(dāng)且僅黨化學(xué)制品和互不相容，則倉(cāng)庫(kù)的最小間隔數(shù)即為的頂點(diǎn)數(shù)。課程安排問(wèn)題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。我們可以假設(shè)有小于條邊。，存在一個(gè)連通圖使得。我們不得不采用路徑最少的渠道，彩虹連通性就可以解決這個(gè)問(wèn)題。一個(gè)簡(jiǎn)單的發(fā)現(xiàn)是如果一個(gè)圖有個(gè)頂點(diǎn)，則有；當(dāng)且僅當(dāng)它是一個(gè)完全圖時(shí)有。 為可著色的 222。一條路上的邊數(shù)稱為路的長(zhǎng)度，記，稱是一條和之間的一條路。并且認(rèn)為和的交集為空集。圖的染色問(wèn)題也是由地圖的染色問(wèn)題延申而來(lái)的：用種顏色給地圖染色，讓地圖上的每一個(gè)區(qū)域都有一種一種顏色，并使得相鄰的地區(qū)顏色不同。事實(shí)上，它產(chǎn)生于政府機(jī)構(gòu)之間機(jī)密信息的安全傳輸，在網(wǎng)絡(luò)安全等實(shí)際問(wèn)題中有很多的應(yīng)用。它以圖為研究的對(duì)象。顯而易見(jiàn)，我們需要求出的是能在網(wǎng)絡(luò)中所使用的最少的（不同）頻道個(gè)數(shù)。19世紀(jì)50年代，英國(guó)學(xué)者提出了任何地圖都可以用4種顏色來(lái)染色的問(wèn)題并稱之為4色猜想。根據(jù)圖的階數(shù)，我們把圖分為有限的、無(wú)限的、可數(shù)的等等，在本文中所研究的圖，我們總是假定圖是有限的，階為的有限圖，即。 如果一個(gè)圖的任意兩個(gè)不同的頂點(diǎn)之間都有條相互獨(dú)立的路連接，則把圖稱作連通的。如果圖是一個(gè)邊數(shù)為