【正文】 我所研究的第一個圖類是廣義圖，這類圖形的變化形式很多，要考慮的條件也有很多我在文章中所求出的彩虹連通數(shù)是有意義的但是否為最佳的還有待考證。它所有的的頂點集為，它所有的邊的集合為。再做一個圈連接的所有葉子頂點，即圈上的頂點時由的所有葉子頂點組成。我們把這類圖分為兩種情況去研究，第一種為圈上的頂點為偶數(shù)，第二種圈上的頂點為奇數(shù)，奇數(shù)頂點時圈上總會有一個頂點是獨立的，不與其他點相連的。下一步，對別的邊染不同的顏色。完成了連通串并聯(lián)圖，最后考慮廣義圖：定理5如果是一個廣義圖，頂點數(shù)為，那么定理證明：假設(shè)是條路徑，是條路徑的共同的端點。假設(shè)是的外部圈，使得。如果增加的路徑是以外部為導(dǎo)向，那么導(dǎo)向使得，任然在新的外部圈中。如圖4所示的就是一個有四條路徑的廣義圖。對于歸納假設(shè)，如果。總的使用了種新的顏色。彩虹染色使用的顏色為。對于的情況，可以假設(shè)。重復(fù)這個過程，直到結(jié)束。顯然，定理是來自定理，所以先證明定理，證明之前先給出一個定理。另外，上文有說明圖是連通的，即，可以采用改善后的界，即。如果圖中任意兩個頂點之間是連通的，并且由條內(nèi)部頂點不相交的彩虹路連通，那么邊染色圖就是彩虹連通的，其中。整個著色過程至多用種顏色，故為可著色的。因是平面圖，所以。布雷 1852年，剛畢業(yè)于倫敦大學(xué)的格斯里(1831—1899)發(fā)現(xiàn)：給一張平面地圖正常著色，至少需要4種顏色。 A8: LA,GT, S 。依據(jù)這些信息，使這些課程的開設(shè)所需要的最少時間段數(shù)得以確定，使得學(xué)生不會發(fā)生選課沖突。的頂點只要用到五種新的顏色，所以的每個頂點隨機的和獨立的從中所有其它的頂點中來選擇它顏色。觀察。證明:刪除從中度數(shù)大于的邊連接的兩個頂點，只要不是任何我們以最小度得到一個子圖和小于的邊。然而，我們需要從它的額外的重要要求。如果H是非平凡連通圖的一個聯(lián)通生成子圖，那么，無單調(diào)性。如果對中的每對不同頂點和都存在一條彩虹測地線。這些例子表明彩虹邊染色的證明與彩虹點染色的不同。在某些情況下可以比要小得多。如果一個邊染色圖的任意兩個不同頂點之間有一條邊染不同染色的路徑相連，那么就稱它是彩虹連通的。如果圖是一個邊數(shù)為的非平凡連通圖，則有。我們可以得出以下簡單的結(jié)果。 如果一個圖的任意兩個不同的頂點之間都有條相互獨立的路連接，則把圖稱作連通的。 一個頂點的度數(shù)是指與它相關(guān)聯(lián)的邊的數(shù)目。根據(jù)圖的階數(shù)，我們把圖分為有限的、無限的、可數(shù)的等等，在本文中所研究的圖，我們總是假定圖是有限的，階為的有限圖，即。迄今為止，圖論的許多公開問題一直是專家學(xué)者們的鉆研的重點題目。19世紀50年代，英國學(xué)者提出了任何地圖都可以用4種顏色來染色的問題并稱之為4色猜想。我們可以把這樣的問題歸結(jié)為：在一個平面上取個頂點分別來表示這門課程。顯而易見，我們需要求出的是能在網(wǎng)絡(luò)中所使用的最少的（不同）頻道個數(shù)。染色問題就是給定一個圖，把它所有頂點或所有的邊染上顏色，使得相鄰頂點或邊的顏色都不相同時所需要的最少的不同的顏色數(shù)，邊的染色題目可以轉(zhuǎn)化為點染色題目，它們都能歸于將一個圖劃分為獨立子集的理論。它以圖為研究的對象。這項研究所取得的成果奠定了歐拉圖論〔及拓撲學(xué)〕創(chuàng)始人的地位。事實上，它產(chǎn)生于政府機構(gòu)之間機密信息的安全傳輸，在網(wǎng)絡(luò)安全等實際問題中有很多的應(yīng)用。顯然，每個考生每場只能參加一門課程的考試。圖的染色問題也是由地圖的染色問題延申而來的：用種顏色給地圖染色，讓地圖上的每一個區(qū)域都有一種一種顏色，并使得相鄰的地區(qū)顏色不同。1852年，格里斯注意到可以用4種顏色來為美國地圖進行染色，使得相鄰地區(qū)（有一段公共邊界，不只一個公共點）有不同的顏色，進一步指出了四色猜想。并且認為和的交集為空集。若是圖中所有的邊都是無向邊，這類圖稱為無向圖。一條路上的邊數(shù)稱為路的長度，記，稱是一條和之間的一條路。圖的種顏色的正常（頂點）染色稱為（頂點）染色色。 為可著色的 222。 若把圖的一個邊染色看作是一個映射，并令它的任意兩條相鄰的邊和，滿足。一個簡單的發(fā)現(xiàn)是如果一個圖有個頂點，則有；當且僅當它是一個完全圖時有。事實上，的著色只要求每個切點有不同的顏色。我們不得不采用路徑最少的渠道，彩虹連通性就可以解決這個問題。彩虹頂點連通數(shù)，強彩虹頂點連通數(shù)（簡單有限無向圖），對于任意非平凡連通圖有。，存在一個連通圖使得。顯然，這個過程持續(xù)了至多為步。我們可以假設(shè)有小于條邊。 我們也把L劃分成兩個部分和，其中是那些具有在中至少一個鄰點的頂點。課程安排問題：某大學(xué)數(shù)學(xué)系要為這個夏季安排課程表。 A5: AC, LA, S 。 儲藏問題一家公司制造種化學(xué)制品，其中某些制品是互不相容的，如果它們互相接觸，則會引起爆炸，作為一種預(yù)防措施，公司希望把它的倉庫分為間隔，以便把不相容的化學(xué)制品儲藏在不同的間隔里，試問：這個倉庫至少應(yīng)該分成幾個間隔？問題處理：構(gòu)造一個圖，其頂點集是兩個頂點和相連當且僅黨化學(xué)制品和互不相容，則倉庫的最小間隔數(shù)即為的頂點數(shù)。把一個平面分成若干的區(qū)域，給這些區(qū)域進行染色，并使任意相鄰的區(qū)域染上不同的染色，滿足這些條件所需的顏色數(shù)最多為五種。當時，結(jié)論顯然。情形1 在c下，如果在與相鄰接點中，至少有兩個頂點著相同顏色，則容易知道，c可以擴充為的5正常頂點著色；情形2在c下，設(shè)在與的相鄰接點中，5個頂點著了5種不同顏色。因此，設(shè)法構(gòu)想一適當?shù)捻旤c排序進行貪心著色，往往可能得到一個較好的著色結(jié)果（如Brooks定理之證明）。我們繼續(xù)說明，對于，等人證明了，如果圖的階數(shù)為，那么，如果圖是連通的，即，那么。定理2如果是一個連通圖，頂點，那么存在圖的一個邊染色，至多是種顏色滿足以下結(jié)論： 對于任意兩個頂點，這里存在兩條不相交的彩虹路； 對于任意一個頂點，任意集合，且，這里兩條彩虹路，只有頂點相同； 對于任意兩個集合，且，這里的兩條彩虹路不相交?，F(xiàn)在，假設(shè)找到這樣一些圖，如果，那么集合，否則的話，這里存在一個頂點。假設(shè)有一個邊染色，顏色是，其中。就而言，的染色使用顏色為，采用這樣的染色方法，每種顏色至少出現(xiàn)過次。對邊進行染色，路徑的第一條邊和路徑的最后一條邊染色，路徑的最后一條邊和路徑的第一條邊染色。對于情況和情況，因為，所以的總的使用顏色數(shù)至多是。我們可以知道，當時圈，有個頂點時，彩虹連通數(shù)。構(gòu)造串并聯(lián)圖，設(shè)置，先確定一個圈，以順時針旋轉(zhuǎn)作為參考。因此，我們能夠重復(fù)加入和重復(fù)導(dǎo)向，按照這樣做法，對于達