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