【正文】 立了。定義廣義圖：令，它是的路徑的集合，路徑的長度，其中，并且路勁上的每對內(nèi)部頂點(diǎn)時(shí)不相交的，而且都有兩個(gè)相同的端點(diǎn)。和一定是一些路徑的末端點(diǎn)，如果一些路徑的末端點(diǎn)是路徑的的內(nèi)部頂點(diǎn)，那么路徑一定包含了路徑的兩個(gè)端點(diǎn)。而且，假設(shè)路徑是以外部為導(dǎo)向。加入的和方向同上面方法一樣。對于每個(gè)重復(fù)，直到。假設(shè)是染色，使用了中顏色。所以證明了定理。首先，因?yàn)?，如果給圖染色，少于種顏色，那么對于某些頂點(diǎn)，在中存在唯一的路徑不是彩虹路。路徑的邊染色映射到端點(diǎn)和，分別染色和，其中。建立一個(gè)廣義θ圖，它由條邊連成，如下圖所示。接下來我們再來研究一類特殊的圖形，是由一個(gè)由n個(gè)頂點(diǎn)的圈為基礎(chǔ)，把圈上相對的頂點(diǎn)依次相連，構(gòu)成一類圖，相連的邊的數(shù)量記為t。我們再來研究一類圖——輪圖，輪圖可簡單定義為，因?yàn)榧尤氲街?，產(chǎn)生了一個(gè)新的頂點(diǎn)與的每個(gè)頂點(diǎn)相連。下面我們先介紹一下Halin圖的定義：在平面上嵌入一棵樹，的每個(gè)內(nèi)部頂點(diǎn)的度數(shù)至少為，并且至少有一個(gè)內(nèi)部頂點(diǎn)。當(dāng)然我們所研究的不僅僅是這樣的輪圖，而是圈中加入了個(gè)頂點(diǎn)的輪圖，并且給出輪圖的彩虹連通數(shù)和證明。然后我們也發(fā)現(xiàn)增加輪圖的內(nèi)部頂點(diǎn)，它的也是不變的，如圖所示：圖 11下面我們來研究一下輪圖的推廣圖，在圈的外部在增加一個(gè)圈，兩個(gè)圈上的頂點(diǎn)都與內(nèi)部頂點(diǎn)相連，稱為二層輪圖。上述研究只是一個(gè)大概的范圍，下面我們來研究一下，當(dāng)圈上的點(diǎn)數(shù)為具體數(shù)值時(shí)的情況。我所研究的這些圖形只是一些簡單的圖形，研究起來相對容易，對于一些復(fù)雜的圖形在研究時(shí)需要注意很多的條件，所以在選擇圖形時(shí)我只選取了一些簡單圖以便研究。最后由于我個(gè)人能力和知識水平的有限，還有題目比較新穎所能參閱的資料不足，所以文章中可以會有一些錯(cuò)誤或者不準(zhǔn)確的地方，還希望看過這篇文章的讀者能夠提出一些問題或改進(jìn)意見，讓這些研究能更接近于正確，而我也能從中更好地學(xué)習(xí)這些知識。第二種圖類是在圈的基礎(chǔ)上的一種推廣形式，這種圖形也還有一些更復(fù)雜的變換形式，我在文章中只解出了其中的一種形式。圖 15綜上所述，有。如下圖所示：圖 12研究這類圖形，我們分為幾個(gè)方面來討論，當(dāng)時(shí)：（1） 我們先來研究頂點(diǎn)和圈的連線，它們之間并沒有內(nèi)部頂點(diǎn)虹頂點(diǎn)，所以彩虹連通數(shù)；（2） 在看與的連線，他們的連線上只有一個(gè)內(nèi)部頂點(diǎn)，所以也只需要一種顏色足以使它們彩虹頂點(diǎn)連通，則；（3） 要使自己內(nèi)部頂點(diǎn)彩虹連通，則需要借助頂點(diǎn)，這樣就構(gòu)成了一個(gè)輪圖，所以它也只需一種顏色即可滿足彩虹頂點(diǎn)連通；（4） 要使自己內(nèi)部頂點(diǎn)彩虹連通，可如圖所示，它所需的最小顏色數(shù)是4，則有；圖 13（5） 使圈與上的點(diǎn)彩虹連通，最多需要3種顏色，所以它的彩虹頂點(diǎn)連通數(shù)有。研究 輪圖以及它的推廣圖彩虹連通性的研究在推導(dǎo)新輪圖的彩虹連通數(shù)之前，讓我們先來看看輪圖的彩虹點(diǎn)連通數(shù)。這樣的得到的圖被稱作圖，樹叫做特征樹，圈叫做伴隨圈。對于的圈，在圈中加入一個(gè)頂點(diǎn)，使得與圈上的每個(gè)頂點(diǎn)連接，那么這樣的圖就稱作輪圖。下面我們先來討論一下圈上頂點(diǎn)數(shù)為偶數(shù)時(shí)的情況，我們先以頂點(diǎn)數(shù)n為10為例，如下圖：圖 8然后分別給每幅圖染色，不加邊時(shí)染5色，加一條染4色，加兩條染4色，加三條染3色，如下圖：圖 9可以看出，隨著連接邊數(shù)的增加彩虹連通數(shù)在逐漸的減小，我們接下來繼續(xù)觀察，加四條邊時(shí)染3色，加五條邊時(shí)染2色，如下圖：圖 10由上所給出的圖形可以看出，在頂點(diǎn)連線增加的過程中彩虹頂點(diǎn)連通數(shù)不是嚴(yán)格遞減的。圖 5現(xiàn)在我們來討論一下廣義圖的彩虹頂點(diǎn)連通性。那么對于使用了種顏色，并且這種染色是一個(gè)彩虹連通的，其中。因此。顯然，時(shí)，圖就是一個(gè)圈。那么是染色的，使用了種顏色。接下來，的邊染色，種顏色。因此，我們能夠重復(fù)加入和重復(fù)導(dǎo)向，按照這樣做法，對于達(dá)到一個(gè)外部和一個(gè)導(dǎo)向。另外，如果，對于選擇外部和導(dǎo)向使得是的末頂點(diǎn)。構(gòu)造串并聯(lián)圖，設(shè)置，先確定一個(gè)圈，以順時(shí)針旋轉(zhuǎn)作為參考。圖 4定理證明：首先定義一些子圖，是一個(gè)圈。我們可以知道，當(dāng)時(shí)圈，有個(gè)頂點(diǎn)時(shí)，彩虹連通數(shù)。類似的，對于，；對于。對于情況和情況，因?yàn)椋缘目偟氖褂妙伾珨?shù)至多是。重復(fù)歸納，可以得到的一個(gè)染色。對邊進(jìn)行染色，路徑的第一條邊和路徑的最后一條邊染色，路徑的最后一條邊和路徑的第一條邊染色。染使用的所有顏色數(shù)為。就而言，的染色使用顏色為，采用這樣的染色方法，每種顏色至少出現(xiàn)過次。令，是路勁的另一個(gè)端點(diǎn)，其中。假設(shè)有一個(gè)邊染色，顏色是，其中。對于每個(gè)，歸納證明了，存在一個(gè)的邊染色，至多使用種顏色，使得定理中的到的性質(zhì)成立，這里使用代替?，F(xiàn)在，假設(shè)找到這樣一些圖，如果，那么集合，否則的話，這里存在一個(gè)頂點(diǎn)。定理3令是一個(gè)連通圖。定理2如果是一個(gè)連通圖，頂點(diǎn)，那么存在圖的一個(gè)邊染色，至多是種顏色滿足以下結(jié)論： 對于任意兩個(gè)頂點(diǎn)，這里存在兩條不相交的彩虹路； 對于任意一個(gè)頂點(diǎn)，任意集合，且，這里兩條彩虹路，只有頂點(diǎn)相同； 對于任意兩個(gè)集合，且，這里的兩條彩虹路不相交。首先，了解連通圖：定理1 如果是一個(gè)連通圖，頂點(diǎn)，那么。我們繼續(xù)說明，對于，等人證明了，如果圖的階數(shù)為，那么，如果圖是連通的，即，那么。接下來，我們給出彩虹連通數(shù)的定義：若存在圖的一個(gè)邊染色，使用種顏色就能夠使得圖彩虹連通，其中是最小的整數(shù)，那么彩虹連通數(shù)為：。因此，設(shè)法構(gòu)想一適當(dāng)?shù)捻旤c(diǎn)排序進(jìn)行貪心著色，往往可能得到一個(gè)較好的著色結(jié)果（如Brooks定理之證明）。從而得到推論。情形1 在c下，如果在與相鄰接點(diǎn)中，至少有兩個(gè)頂點(diǎn)著相同顏色，則容易知道，c可以擴(kuò)充為的5正常頂點(diǎn)著色；情形2在c下，設(shè)在與的相鄰接點(diǎn)中，5個(gè)頂點(diǎn)著了5種不同顏色。設(shè)，令。當(dāng)時(shí)，結(jié)論顯然?？掀战o出了四色定理的一個(gè)證明方法，被當(dāng)時(shí)的人們所接受，但11年后，珀西把一個(gè)平面分成若干的區(qū)域，給這些區(qū)域進(jìn)行染色，并使任意相鄰的區(qū)域染上不同的染色，滿足這些條件所需的顏色數(shù)最多為五種。這就是著名的4色定理。 儲藏問題一家公司制造種化學(xué)制品，其中某些制品是互不相容的，如果它們互相接觸，則會引起爆炸，作為一種預(yù)防措施，公司希望把它的倉庫分為間隔，以便把不相容的化學(xué)制品儲藏在不同的間隔里，試問：這個(gè)倉庫至少應(yīng)該分成幾個(gè)間隔？問題處理：構(gòu)造一個(gè)圖，其頂點(diǎn)集是兩個(gè)頂點(diǎn)和