【正文】 在某些其他情況下，可以比小很多。此圖有個切點，因此。另一方面，不難看出。這些例子表明彩虹邊染色的證明與彩虹點染色的不同。除了一些相關(guān)的定理，彩虹連通性也已經(jīng)應用到了一些網(wǎng)絡(luò)問題中。假設(shè)我們要在蜂窩網(wǎng)絡(luò)的兩個頂點之間傳遞信息，每個連接在網(wǎng)絡(luò)上都會有不同的渠道。定理1 對于一個頂點數(shù)的圈有 令是圖的一種彩虹染色。如果對中的每對不同頂點和都存在一條彩虹測地線。類似的我們定義連通圖的強彩虹連通數(shù)是使圖強彩虹連通所需要的最少的顏色數(shù)，記作。同樣的，連通圖的強彩虹點連通數(shù)是使圖強彩虹點連通所需要的最少的顏色數(shù)，記作。對于一個階連通圖，給出的上下界，其中彩虹連通數(shù)，強彩虹連通數(shù)，對于任意非平凡連通圖有。如果H是非平凡連通圖的一個聯(lián)通生成子圖，那么，無單調(diào)性。 令是一個階（）的連通圖，那么，則這個界是精確的。（）的連通圖，如果不只有一條路，那么有。 一個有個頂點的連通圖有。然而，我們需要從它的額外的重要要求。 若是具有個頂點和最小度的圖形，則有二階點集，其大小至多為。觀察到，當過程已經(jīng)停止，其余的每個頂點已經(jīng)失去了超過的度，因此有超過的與它相鄰在被刪除的頂點集合中。顯然注意到，但很重要的事實是：添加頂點到一個2階點集不降低它的度。證明:刪除從中度數(shù)大于的邊連接的兩個頂點，只要不是任何我們以最小度得到一個子圖和小于的邊。因此，通過加最多條邊，我們可以使他聯(lián)通。假設(shè)是有個頂點和最小為的連通圖。大小。觀察。由于是強，每個具有至少個相鄰的點在中。請注意，否則將有至少條邊，與我們的假設(shè)矛盾。我們現(xiàn)在已經(jīng)準備好著色方案。的頂點只要用到五種新的顏色，所以的每個頂點隨機的和獨立的從中所有其它的頂點中來選擇它顏色。以上使用的顏色的總數(shù)不超過。例如課程安排問題。所要開設(shè)的課程為：幾何學(G),線性代數(shù)(LA),高等微積分(AC),近世代數(shù)(MA),圖論(GT)和統(tǒng)計學(S)。依據(jù)這些信息，使這些課程的開設(shè)所需要的最少時間段數(shù)得以確定，使得學生不會發(fā)生選課沖突。 A2: MA, LA, G 。A4: G, LA, AC 。 A6: G, AC。 A8: LA,GT, S 。A10：GT，S。圖 2如果我們用相同的顏色給同一時段進行的課程頂點染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求所謂的點色數(shù)問題。4 彩虹染色方面的著名定理 四色定理如果在平面上劃出一些鄰接的有限區(qū)域，那么可以用四種顏色來給這些區(qū)域染色，使得每兩個鄰接區(qū)域染的顏色都不相同；另一個通俗的說法是：每個地圖都可以用少于四種的顏色來染色，而且沒有兩個鄰接區(qū)域的顏色相同。 1852年，剛畢業(yè)于倫敦大學的格斯里(1831—1899)發(fā)現(xiàn)：給一張平面地圖正常著色，至少需要4種顏色。當這個定理被提出后，很多科學家都希望能對此進行證明，但都沒有成功。但這個證明一直受到一些數(shù)學家的質(zhì)疑，因為直到現(xiàn)在都沒有數(shù)學家不借助計算機能夠證明。五色定理稍弱于比四色定理，但是它證明起來就容易多了。布雷約翰 我們對圖的頂點作數(shù)學歸納證明。設(shè)時，結(jié)論成立。因是平面圖，所以。由歸納假設(shè)，是可用5種顏色正常頂點染色的。 (1) 如果, 顯然c可以擴充為的5正常頂點染色； (2) 如果, 分兩種情況討論。圖 3 貪心（greedy）著色法 用色1，2，…逐步（按某一頂點排序）對每個頂點進行正常著色，每次選用盡可能少的顏色進行著色。整個著色過程至多用種顏色，故為可著色的。顯然，貪心著色法所用的顏色數(shù)完全取決于著色的順序，即頂點的一個排序。按 的順序任作一頂點排序（同一色集內(nèi)隨意排序），按此順序進行貪心著色，顯然恰好使用了種顏色。5 特殊圖類的彩虹點染色在討論廣義圖之前，我們先來了解幾個定義。如果圖中任意兩個頂點之間是連通的，并且由條內(nèi)部頂點不相交的彩虹路連通，那么邊染色圖就是彩虹連通的，其中。對于連通圖的彩虹連通數(shù)，記作，即。因此，前面定義的僅僅是針對連通圖而言的。等人證明了，如果圖的最小度為，那么，并且證明了對于所有階數(shù)為，最小度為的連通圖都是適用的。另外，上文有說明圖是連通的，即，可以采用改善后的界，即。在情況中，如果圖是一個連通串并聯(lián)圖是一個簡單圖，從三個頂點開始，反復運用一個操作序列，這個序列是一個分支，由一條邊變換成雙條邊，反復增加分支邊。證明定理，我們是通過先證明一個強有力的定理的結(jié)論，然后間接證明定理。對于而言，如果，那么其中的一條路徑取自頂點。顯然，定理是來自定理，所以先證明定理，證明之前先給出一個定理。對于任意的頂點和任意集合，這里有從到的條路徑，使得對于其中的任意兩條路，僅僅只有一個共同頂點。因為任意的連通圖都含有一個頂點至少是的圈，于是令是圖的一個頂點至少是的圈。根據(jù)定理3，發(fā)出路到，這里的每對路徑僅僅匯集與，那些路是的一個細分。重復這個過程，直到結(jié)束。那么，集合就意味著對于而言定理成立。顯然，是一個圈，它是彩虹染色的。通過附加一個細分的到得到圖，其中條路徑匯集于頂點。對于的情況，可以假設(shè)。分別把的第一條邊和最后一條邊射入到和。彩虹染色使用的顏色為。總的，使用了種新的顏色。彩虹染色使用的顏色為?？偟?，使用了種新顏色。假設(shè)存在最大的整數(shù)，使得。路徑的最后一條邊和路徑（每一條長度為1）染色。總的使用了種新的顏色。歸納證明了，對于的染色滿足所有的需求。現(xiàn)在，假設(shè)對于的染色，至多使用了種顏色，定理的到成立。對于情況，因為，所以的總的使用顏色數(shù)至多是：。對于歸納假設(shè)，如果?，F(xiàn)在，對于證明了到成立。完成了連通圖的介紹，接下來考慮圖是一個連通的串并聯(lián)圖：定理如果圖是一個連通的串并聯(lián)圖，頂點，那么。這是特殊情況，更為一般的情況是，圖是一個廣義圖。如圖4所示的就是一個有四條路徑的廣義圖。是從附加一條長度至少為的路徑到得到的，用兩個不同的頂點來辨別路徑的末端點。每個是一個連通串并聯(lián)圖。對于定義一個方向和一個平面，以的外部為導向順時針圈，且包含。如果增加的路徑是以外部為導向，那么導向使得，任然在新的外部圈中。否則，刪除直到第一個使得加入的在的外部。注意點，是加入到由造出的外部界，當加入的外部。最后，重復標簽分別是。假設(shè)是的外部圈，使得。首先，是彩虹染色，使用了中顏色。加入到的外部。因此，證明了，對于每個，是彩虹連通的。完成了連通串并聯(lián)圖，最后考慮廣義圖：定理5如果是一個廣義