【正文】 。對于任意的頂點和任意集合，這里有從到的條路徑，使得對于其中的任意兩條路，僅僅只有一個共同頂點。那么，集合就意味著對于而言定理成立。分別把的第一條邊和最后一條邊射入到和?？偟?，使用了種新顏色。歸納證明了，對于的染色滿足所有的需求。現(xiàn)在，對于證明了到成立。是從附加一條長度至少為的路徑到得到的，用兩個不同的頂點來辨別路徑的末端點。否則，刪除直到第一個使得加入的在的外部。首先，是彩虹染色，使用了中顏色。因此，假設(shè)。因此。通過對大量圖形的研究與總結(jié)這類圖形的的彩虹點連通數(shù)隨著所連接的邊數(shù)的增多而減少。我們已經(jīng)在前面說明了圈的彩虹點連通數(shù)，接下來也將給出輪圖的彩虹連通數(shù)，并證明。綜上所述，這類二層輪圖的彩虹頂點連通數(shù)有一個上界。第三種圖類是在輪圖的基礎(chǔ)上進行的推廣，這類圖也還可以有很多種變換，我所研究的都是這些圖雷中相對簡單的，所以還需要更多時間和努力才能把這些圖類研究透徹。6 結(jié)束語 在本文中我們主要談到了圖論中的一個并不為大家所熟知的一個領(lǐng)域，其主要討論了彩虹連通性相關(guān)的一些相關(guān)的知識，讓大家對這些知識有一些初步的了解，同時也對彩虹連通性的研究在一些實際生活中的應(yīng)用有了一些認識。經(jīng)過圖例的觀察內(nèi)部頂點為一個時的輪圖，發(fā)現(xiàn)當(dāng)時輪圖是一個完全圖，；當(dāng)時，無論怎樣的去增加圈上的頂點它的始終不變。輪圖是一個有個內(nèi)部頂點，個葉子頂點，且被一個圈連接的圖，根據(jù)Halin圖的定義，可知輪圖是一個特殊的圖，最小度。討論的過程主要分為幾個步驟來研究，首先來由兩條邊所圍成的一個圈來討論，為一個圈時它的彩虹點連通數(shù)有上界，設(shè)彩虹頂點連通所使用的顏色數(shù)為S，即，染色情況如下圖所示：圖 6然后在增加一條邊來看，令彩虹頂點連通所使用的顏色數(shù)為S，當(dāng)為偶數(shù)時取中間的兩個頂點染上所用過的顏色，其余點分別進行染色；當(dāng)為奇數(shù)時取中間的一個點染所使用的顏色，其余點分別進行染色，如下圖所示圖 7從而有的彩虹點連通數(shù)，按照這個方法對圖的剩下的邊進行研究，最后得出圖的彩虹頂點連通數(shù)的一個上界：。接下來，對染色。因此，證明了，對于每個，是彩虹連通的。最后，重復(fù)標簽分別是。對于定義一個方向和一個平面，以的外部為導(dǎo)向順時針圈，且包含。這是特殊情況，更為一般的情況是，圖是一個廣義圖。對于情況，因為，所以的總的使用顏色數(shù)至多是：。路徑的最后一條邊和路徑（每一條長度為1）染色?？偟模褂昧朔N新的顏色。通過附加一個細分的到得到圖，其中條路徑匯集于頂點。根據(jù)定理3，發(fā)出路到，這里的每對路徑僅僅匯集與，那些路是的一個細分。對于而言，如果，那么其中的一條路徑取自頂點。等人證明了，如果圖的最小度為，那么，并且證明了對于所有階數(shù)為，最小度為的連通圖都是適用的。5 特殊圖類的彩虹點染色在討論廣義圖之前，我們先來了解幾個定義。圖 3 貪心（greedy）著色法 用色1，2，…逐步（按某一頂點排序）對每個頂點進行正常著色，每次選用盡可能少的顏色進行著色。設(shè)時，結(jié)論成立。五色定理稍弱于比四色定理，但是它證明起來就容易多了。4 彩虹染色方面的著名定理 四色定理如果在平面上劃出一些鄰接的有限區(qū)域，那么可以用四種顏色來給這些區(qū)域染色，使得每兩個鄰接區(qū)域染的顏色都不相同；另一個通俗的說法是：每個地圖都可以用少于四種的顏色來染色，而且沒有兩個鄰接區(qū)域的顏色相同。 A6: G, AC。所要開設(shè)的課程為：幾何學(xué)(G),線性代數(shù)(LA),高等微積分(AC),近世代數(shù)(MA),圖論(GT)和統(tǒng)計學(xué)(S)。我們現(xiàn)在已經(jīng)準備好著色方案。大小。顯然注意到，但很重要的事實是：添加頂點到一個2階點集不降低它的度。 一個有個頂點的連通圖有。對于一個階連通圖，給出的上下界，其中彩虹連通數(shù)，強彩虹連通數(shù)，對于任意非平凡連通圖有。定理1 對于一個頂點數(shù)的圈有 令是圖的一種彩虹染色。另一方面，不難看出。注意到，當(dāng)圖直徑為1和2時，它們相等。邊染色稱為圖的一個邊染色，所使用的最小整數(shù)稱為的邊色數(shù)，也成為色指數(shù)，記做。 為可著色的（k=j）最簡單的連通圖是圈，并且其它的圖都可以由一個圈通過不斷添加路而得到。這樣的一個頂點染色給出了的一個劃分（）使每個都是的一個獨立集。 在無向圖中，若從頂點到有一條路相連，則稱和之間是連通的。本文所研究用到的圖均為有限的簡單無向圖。圖的頂點集合是中的各個元素，頂點的集合記作；而圖的邊的集合為中的元素，邊的集合記作。圖 1 研究該課題的意義在日常生活中，還有許多問題可以用彩虹頂點染色加以解決，比如電視頻道分配問題，變址寄存器等，可以運用彩虹染色方法輕松解決，圖的染色理論是圖論中的重要內(nèi)容，也是圖論的起源之一。問題處理：如果把每一個地區(qū)看作一個頂點，把相鄰兩個地區(qū)用一條邊連接起來，就能夠把一個區(qū)域圖看作一個平面圖。試問這次考試最少要進行幾場? 顯然，不可以在同一個時間進行同一個學(xué)生所選修的兩門課程的考試。假如我們需要在一個蜂窩網(wǎng)絡(luò)中進行信息的傳輸。染色問題是圖論的一類重要的題目，具有重要的實際意義和理論意義。1 前言圖論是數(shù)學(xué)中的一個重要的分支。不同類型的圖的染色問題一直是圖論中的熱點題目，而連通圖的染色問題又是其中一種很重要的分支。在網(wǎng)絡(luò)中的任意兩點在之間都要有一條路相連接，而且在該路徑上的每段都被分配一個獨特的頻道（例如，不同的頻率）。當(dāng)然，不會出現(xiàn)同一個學(xué)生的不同課程在同一個時間所進行的考試。例如，圖1（a）所示的區(qū)域圖可看作為圖1（b）所表示的平面圖。幾百年來，很多的數(shù)學(xué)家們都為此花費了大量的心血去研究。一個圖的階就是圖的頂點個數(shù)，記作。 假設(shè)有兩個圖和，如果兩個圖的頂點集有這樣的關(guān)系，是的一個子集，邊集是的一個子集，那么就稱圖是圖的子圖。如果無向圖中的任一對頂點之間都是連通的，則稱圖是連通圖，反之，如果一個無向圖不是連通的，則稱作非連通圖。如果有一個（頂點）著色，則稱是（頂點）可染色。圖的任意兩個頂點之間的最大距離，稱為是圖的直徑，記作。