一、 圖的著色的基本概念

 

    已知一個圖g和m>0種顏色，在只準使用這m種顏色對g的結點著色的情況下，是否能使圖中任何相鄰的兩個結點都具有不同的顏色呢?這個問題稱為m-著色判定問題。在m-著色最優化問題則是求可對圖g著色的最小整數m。這個整數稱為圖g的色數。

對于圖著色的研究是從m—可著色性問題的著名特例——四色問題開始的。這個問題要求證明平面或球面上的任何地圖的所有區域都至多可用四種、顏色來著色，并使任何兩個有一段公共邊界的相鄰區域沒有相同的顏色。這個問題可轉換成對一平面圖的４－著色判定問題(平面圖是一個能畫于平面上而邊無任何交叉的圖)。將地圖的每個區域變成一個結點，若兩個區域相鄰，則相應的結點用一條邊連接起來。圖46．1顯示了一幅有5個區域的地圖以及與該地圖對應的平面圖。多年來，雖然已證明用5種顏色足以對任一幅地圖著色，但是一直找不到一定要求多于4種顏色的地圖。直到1976年這個問題才由愛普爾(k．i．apple)，黑肯(w．haken)和考西(j．koch)利用電子計算機的幫助得以解決。他們證明了4種顏色足以對任何地圖著色。在這一節，不是只考慮那些由地圖產生出來的圖，而是所有的圖。討論在至多使用m種顏色的情況下，可對一給定的圖著色的所有不同方法。  

 

假定用圖的鄰接矩陣graPh(1：n，1：n)來表示一個圖g，其中若(i，j)是g的一條邊，則graPh(i，j)=true，否刷graPh(i，j)=false。因為要擬制的算法只關心一條邊是否存在，所以使用布爾值。顏色用整數1，2，…，m表示，解則用n—元組((1)，…，x(n))來給出，其中x(i)是結點i的顏色。此算法使用的基本狀態空間樹是一棵度數為m，高為n+1的樹。在i級上的每一個結點有m個兒子，它們與x(i)的m種可能的賦值相對應，1≤i≤n。在n+1級上的結點都是葉結點。圖46．2給出了n＝3且m＝3時的狀態空間樹。  

 

二、圖的著色的基本算法

 

[算法]： 找一個圖的所有m—著色方案 [動畫]

     procedure mcoloring(k)

／／這是圖著色的一個遞歸回溯算法。圖g用它的布爾鄰接矩陣graPh(1：n，1：n)表示。它計算并打印出符合以下要求的全部解，把整數1，2，…，m分配給圖中各個結點且使相鄰近的結點的有不同的整數。k是下一個要著色結點的下標。／／

global integer m，n，x(1：n)boolean graPh(1；n，1：n)

integer k

loop ／／產生對x(k)所有的合法賦值。／／

    call nextvalue(k)。//將一種合法的顏色分配給x(k)／／

    if x(k)＝0 then exit endif ／／沒有可用的顏色了／／   

     if k=n

      then print(x) ／／至多用了m種顏色分配給n個結點／／  

     else call mcoloring<k+1) ／／所有m—著色方案均在此反復遞歸調用中產生／／

    endif

    repeat

    end mcoloring

在最初調用call mcoloring(1)之前，應對圖的鄰接矩陣置初值并對數組x置0值。

    在確定了x(1)到x(k-1)的顏色之后，過程nextvalue從這m種顏色中挑選一種

符合要求的顏色，并把它分配給x(k)，若無可用的顏色，則返回x(k)＝0。

 [算法]： 生成下一種顏色   [動畫]

procedure nextvalue(k)

／／進入此過程前x(1)，...，x(k一1)已分得了區域[o，m]中的整數且相鄰近的結

         點有不同的整數。本過程在區域[0，m]中給x(k)確定一個值：如果還剩下一

         些顏色，它們與結點k鄰接的結點分配的顏色不同，那末就將其中最高標值的

         顏色分配給結點k；如果沒剩下可用的顏色，則置x(k)為0 ／／ 

global integer m，n，x(1：n)boolean graPh(1：n，1：n)  

integer j，k   

loop   

x(k)+(x(k)+1)mod(m+1) ／／試驗下一個最高標值的顏色／／

if x(k)＝0 then   return endif //全部顏色用完／／

for jß1to n do ／／檢查此顏色是否與鄰近結點的那些顏色不同／／

if graPh(k，j) and ／／如果(k，j)是一條邊／

   x(k)=x(j) ／／并且鄰近的結點有相同的顏色／／

 then exit endif   

 repeat ／／否則試著找另一種顏色／／

end nextvalue 

該算法的計算時間上界可以由狀態空間樹的內部結點數 得到。在每個內部結點處，為了確定它的兒子們所對應的合法著色，由nextvalue所花費的時間是 (mn)。因此，總的時間由 所限界。

    圖46．3顯示了一個包含四個結點的簡單圖。下面是一棵由過程mcoloring生成的

 樹。到葉于結點的每一條路徑表示一種至多使用3種顏色的著色法。