【正文】 彩虹連通基本知識Chartrand，Johns等人首次提出了圖的彩虹連通性的概念。對于彩虹邊連通和彩虹點聯(lián)通，一些例子表明它們的彩虹連通路并不相同。只要給條邊染色，比如說，顏色1和三角形的其它邊的顏色2,3,4。對的任何兩個頂點和，中的一條彩虹測地線是一條長度為的彩虹路，則圖稱為強彩虹連通。 令是一個階的非平凡連通圖，則有：（1） 當(dāng)且僅當(dāng)是一個完全圖；（2） 當(dāng)且僅當(dāng)。 若是有最小度的連通圖，然后它有一個連通的生成子圖最小度為并有少于條邊。我們最多只能添加的頂點和得到這么一個連接和也是一個強2階點集。的頂點各自被染上不同的顏色?，F(xiàn)有10名學(xué)生選修了這些課程(如下所示)。A7: GT, MA, LA 。鄰接的兩個區(qū)域指的是它們有一段公共的邊界，而不僅僅是一個公共的交點。1879年，阿爾弗雷德考慮的平面圖。例如，對任意圖，按任一順序進(jìn)行貪心著色，則每當(dāng)嘗試對某一頂點著色時，其鄰集中至多出現(xiàn)種色，因此總可從種顏色中挑選一中著在上。首先是彩虹連通，如果一條路的邊分別染不同的顏色，那么這條邊染色路就是一條彩虹路。因此，如果圖是連通的，那么。類似的，對于，如果和相交，那么一條適合的路徑是一個點，這點在中。令是一些路的集合。假設(shè)路徑是。情況：。的其余的邊染不同的新的顏色。最后，我們在情況到情況中驗證，定理的到成立對于成立。定義廣義圖：令，它是的路徑的集合，路徑的長度，其中，并且路勁上的每對內(nèi)部頂點時不相交的，而且都有兩個相同的端點。而且，假設(shè)路徑是以外部為導(dǎo)向。對于每個重復(fù)，直到。所以證明了定理。路徑的邊染色映射到端點和，分別染色和，其中。接下來我們再來研究一類特殊的圖形，是由一個由n個頂點的圈為基礎(chǔ)，把圈上相對的頂點依次相連，構(gòu)成一類圖，相連的邊的數(shù)量記為t。下面我們先介紹一下Halin圖的定義：在平面上嵌入一棵樹，的每個內(nèi)部頂點的度數(shù)至少為，并且至少有一個內(nèi)部頂點。然后我們也發(fā)現(xiàn)增加輪圖的內(nèi)部頂點，它的也是不變的，如圖所示：圖 11下面我們來研究一下輪圖的推廣圖，在圈的外部在增加一個圈，兩個圈上的頂點都與內(nèi)部頂點相連，稱為二層輪圖。我所研究的這些圖形只是一些簡單的圖形，研究起來相對容易，對于一些復(fù)雜的圖形在研究時需要注意很多的條件，所以在選擇圖形時我只選取了一些簡單圖以便研究。第二種圖類是在圈的基礎(chǔ)上的一種推廣形式，這種圖形也還有一些更復(fù)雜的變換形式，我在文章中只解出了其中的一種形式。如下圖所示：圖 12研究這類圖形，我們分為幾個方面來討論，當(dāng)時：（1） 我們先來研究頂點和圈的連線，它們之間并沒有內(nèi)部頂點虹頂點，所以彩虹連通數(shù)；（2） 在看與的連線，他們的連線上只有一個內(nèi)部頂點，所以也只需要一種顏色足以使它們彩虹頂點連通，則；（3） 要使自己內(nèi)部頂點彩虹連通，則需要借助頂點，這樣就構(gòu)成了一個輪圖，所以它也只需一種顏色即可滿足彩虹頂點連通；（4） 要使自己內(nèi)部頂點彩虹連通，可如圖所示，它所需的最小顏色數(shù)是4，則有；圖 13（5） 使圈與上的點彩虹連通，最多需要3種顏色，所以它的彩虹頂點連通數(shù)有。這樣的得到的圖被稱作圖，樹叫做特征樹，圈叫做伴隨圈。下面我們先來討論一下圈上頂點數(shù)為偶數(shù)時的情況，我們先以頂點數(shù)n為10為例，如下圖：圖 8然后分別給每幅圖染色，不加邊時染5色，加一條染4色，加兩條染4色，加三條染3色，如下圖：圖 9可以看出，隨著連接邊數(shù)的增加彩虹連通數(shù)在逐漸的減小，我們接下來繼續(xù)觀察，加四條邊時染3色，加五條邊時染2色，如下圖：圖 10由上所給出的圖形可以看出，在頂點連線增加的過程中彩虹頂點連通數(shù)不是嚴(yán)格遞減的。那么對于使用了種顏色，并且這種染色是一個彩虹連通的，其中。顯然，時，圖就是一個圈。接下來，的邊染色，種顏色。另外，如果，對于選擇外部和導(dǎo)向使得是的末頂點。圖 4定理證明：首先定義一些子圖，是一個圈。類似的，對于，；對于。重復(fù)歸納，可以得到的一個染色。染使用的所有顏色數(shù)為。令，是路勁的另一個端點，其中。對于每個，歸納證明了，存在一個的邊染色，至多使用種顏色，使得定理中的到的性質(zhì)成立，這里使用代替。定理3令是一個連通圖。首先，了解連通圖：定理1 如果是一個連通圖，頂點，那么。接下來，我們給出彩虹連通數(shù)的定義：若存在圖的一個邊染色，使用種顏色就能夠使得圖彩虹連通，其中是最小的整數(shù)，那么彩虹連通數(shù)為：。從而得到推論。設(shè)，令?？掀战o出了四色定理的一個證明方法，被當(dāng)時的人們所接受，但11年后，珀西這就是著名的4色定理。 A9: AC, S, LA。(學(xué)生用Ai表示）A1: LA, S 。的頂點不被染色。令和考慮分區(qū)，其中為直接支配的頂點集和是不被支配的點集。這個生成子圖的每個連接的部分都有至少有個頂點。我們所說的2階點集k強如果每一個并非由它支配的頂點有至少存在這是由它支配相鄰的。 令，是連通圖的兩個頂點，如果距離，那么不存在包含和作為內(nèi)部定點的測地線。這種情況下，染色稱為的強彩虹染色。由于自然組合的概念，彩虹邊連通和彩虹點連通吸引了許多學(xué)者的興趣。例如，而。彩虹邊連通數(shù)就是一個連通圖使它構(gòu)成彩虹邊連通所需要的最小的顏色數(shù)，稱為記做。 若把圖的一個頂點染色看作是一個映射，并令它的任意兩個相鄰的點和都滿足。例： 為1可著色的 219。其中使得圖是連通時的最大整數(shù)稱作的連通度，記作。不與其它的任何頂點鄰接的頂點，即度為0的頂點稱為孤立頂點。此外，僅有一個頂點的圖稱為平凡圖，即平凡圖的階，相反，階的圖稱為非平凡圖。在生產(chǎn)管理、軍事、交通運輸、計算機網(wǎng)絡(luò)等許多的領(lǐng)域圖論的知識在其中都有著重要的應(yīng)用，彩虹連接數(shù)在網(wǎng)絡(luò)領(lǐng)域也有很多的應(yīng)用。100多年之后，才由美國學(xué)者在計算機證明了這個問題，這就是著名的四色定理。如果有同學(xué)同時選擇了課程和，則把點之間連一條邊，可以得到一個有個頂點的無向圖。而這個最少個數(shù)恰好是這個網(wǎng)絡(luò)所對應(yīng)無向圖的彩虹連通數(shù)。目前，伴隨著圖的染色問題在實際問題中被廣泛的應(yīng)用，研究這類問題的學(xué)者在逐漸的增多。圖論原本是應(yīng)用數(shù)學(xué)的一個重要的分支，為此，歷史上曾有許多位數(shù)學(xué)家獨自地建立過圖論。歐拉證明了這個題目沒有解，并且把這個題目進(jìn)行推廣，給出了對于一個給定的圖可以以某種方法走遍的判定規(guī)則。作為一個自然的組合概念，彩虹連通數(shù)不但有其了理論意義，而且在網(wǎng)絡(luò)問題