【正文】 有條相互獨立的路連接，則把圖稱作連通的。其中使得圖是連通時的最大整數(shù)稱作的連通度，記作。如果圖的任意兩個不同頂點之間都有條邊不相交的路相連，則稱圖是邊連通的。其中使得圖是邊連通的最大整數(shù)稱為的邊連通度，記為。圖的頂點染色稱為正常（頂點）染色，如果的每條邊的兩端點都染不同顏色。圖的種顏色的正常（頂點）染色稱為（頂點）染色色。這樣的一個頂點染色給出了的一個劃分（）使每個都是的一個獨立集。如果有一個（頂點）著色，則稱是（頂點）可染色。我們可以得出以下簡單的結果。例： 為1可著色的 219。 為一完全圖。 為可著色的 219。 為部圖。 為可著色的 222。 為可著色的（k=j）最簡單的連通圖是圈，并且其它的圖都可以由一個圈通過不斷添加路而得到。圖的任意兩個頂點之間的最大距離，稱為是圖的直徑，記作。如果圖是一個邊數(shù)為的非平凡連通圖，則有。 若把圖的一個頂點染色看作是一個映射，并令它的任意兩個相鄰的點和都滿足。我們稱里的顏色為可用顏色，并且主要研究的是的基數(shù)。通常，我們都會去試著去找出一個最小的整數(shù)，使得有一個染色，即一個頂點染色，這個就成為圖的頂點所需的色數(shù)，表示作。若，我們就把圖稱作色的；如果，則稱圖為可染色的。 若把圖的一個邊染色看作是一個映射，并令它的任意兩條相鄰的邊和，滿足。邊染色稱為圖的一個邊染色，所使用的最小整數(shù)稱為的邊色數(shù)，也成為色指數(shù)，記做。 彩虹連通基本知識Chartrand，Johns等人首次提出了圖的彩虹連通性的概念。如果一個邊染色圖的任意兩個不同頂點之間有一條邊染不同染色的路徑相連，那么就稱它是彩虹連通的。彩虹邊連通數(shù)就是一個連通圖使它構成彩虹邊連通所需要的最小的顏色數(shù)，稱為記做。Krivelevich和Yuster提出了彩虹點聯(lián)通的概念。一個點染色圖的任意兩點之間有一條內(nèi)部頂點染不同顏色的路相連，則稱它是彩虹點連通的。彩虹點連通數(shù)就是一個連通圖它構成彩虹點連通圖所需的最少的顏色數(shù)，記做。一個簡單的發(fā)現(xiàn)是如果一個圖有個頂點，則有；當且僅當它是一個完全圖時有。注意到，當圖直徑為1和2時，它們相等。對于彩虹邊連通和彩虹點聯(lián)通，一些例子表明它們的彩虹連通路并不相同。在某些情況下可以比要小得多。例如，而。另一方面，在某些其他情況下，可以比小很多。取個頂點不相交的三角形，并給它們中的每一個指定一個頂點，在指定點上添加一個完全圖。此圖有個切點，因此。事實上，的著色只要求每個切點有不同的顏色。另一方面，不難看出。只要給條邊染色，比如說，顏色1和三角形的其它邊的顏色2,3,4。這些例子表明彩虹邊染色的證明與彩虹點染色的不同。由于自然組合的概念，彩虹邊連通和彩虹點連通吸引了許多學者的興趣。除了一些相關的定理，彩虹連通性也已經(jīng)應用到了一些網(wǎng)絡問題中。事實上，這個新概念形成于政府機構之間的信息傳遞。假設我們要在蜂窩網(wǎng)絡的兩個頂點之間傳遞信息，每個連接在網(wǎng)絡上都會有不同的渠道。我們不得不采用路徑最少的渠道，彩虹連通性就可以解決這個問題。定理1 對于一個頂點數(shù)的圈有 令是圖的一種彩虹染色。對的任何兩個頂點和，中的一條彩虹測地線是一條長度為的彩虹路，則圖稱為強彩虹連通。如果對中的每對不同頂點和都存在一條彩虹測地線。這種情況下，染色稱為的強彩虹染色。類似的我們定義連通圖的強彩虹連通數(shù)是使圖強彩虹連通所需要的最少的顏色數(shù)，記作。顯然有：，這里和分別表示圖的直徑和邊數(shù)。同樣的，連通圖的強彩虹點連通數(shù)是使圖強彩虹點連通所需要的最少的顏色數(shù)，記作。彩虹頂點連通數(shù)，強彩虹頂點連通數(shù)（簡單有限無向圖），對于任意非平凡連通圖有。對于一個階連通圖，給出的上下界，其中彩虹連通數(shù)，強彩虹連通數(shù)，對于任意非平凡連通圖有。 令是一個階的非平凡連通圖，則有：（1） 當且僅當是一個完全圖；（2） 當且僅當。如果H是非平凡連通圖的一個聯(lián)通生成子圖，那么，無單調(diào)性。 令，是連通圖的兩個頂點，如果距離，那么不存在包含和作為內(nèi)部定點的測地線。 令是一個階（）的連通圖，那么，則這個界是精確的。（1）當且僅當是一個完全圖；（2）當且僅當；（3）當且僅當是一條n階的路。（）的連通圖，如果不只有一條路，那么有。，存在一個連通圖使得。 一個有個頂點的連通圖有。然而，我們需要從它的額外的重要要求。我們所說的2階點集k強如果每一個并非由它支配的頂點有至少存在這是由它支配相鄰的。 若是具有個頂點和最小度的圖形，則有二階點集，其大小至多為。證明：初始化，然后只要，取一個頂點在的最小度至少為，將它添加到并通過刪除和它相鄰點集更新。觀察到，當過程已經(jīng)停止，其余的每個頂點已經(jīng)失去了超過的度，因此有超過的與它相鄰在被刪除的頂點集合中。顯然，這個過程持續(xù)了至多為步。顯然注意到，但很重要的事實是：添加頂點到一個2階點集不降低它的度。 若是有最小度的連通圖，然后它有一個連通的生成子圖最小度為并有少于條邊。證明:刪除從中度數(shù)大于的邊連接的兩個頂點，只要不是任何我們以最小度得到一個子圖和小于的邊。這個生成子圖的每個連接的部分都有至少有個頂點。因此，通過加最多條邊，我們可以使他聯(lián)通。：定理的語句在是不準確的，所以我們假定。假設是有個頂點和最小為的連通圖。，我們可以假設有小于條邊。，大小。，我們最多只能添加的頂點和得到這么一個連接和也是一個強2階點集。觀察。令和考慮分區(qū)，其中為直接支配的頂點集和是不被支配的點集。由于是強，每個具有至少個相鄰的點在中。我們進一步把分成2份和，其中是那些在中至少有個相鄰的點。請注意，否則將有至少條邊，與我們的假設矛盾。 我們也把L劃分成兩個部分和，其中是那些具有在中至少一個鄰點的頂點。我們現(xiàn)在已經(jīng)準備好著色方案。的頂點各自被染上不同的顏色。的頂點只要用到五種新的顏色，所以的每個頂點隨機的和獨立的從中所有其它的頂點中來選擇它顏色。的頂點不被染色。以上使用的顏色的總數(shù)不超過。3 生活中的一些實際問題 圖著色問題的應用—選課問題類似于圖的邊染色的問題，生活中的許多問題都可以建立模型為圖的頂點著色問題來處理。例如課程安排問題。課程安排問題：某大學數(shù)學系要為這個夏季安排課程表。所要開設的課程為：幾何學(G),線性代數(shù)(LA),高等微積分(A