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