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