一、 圖的著色的基本概念

 

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

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

 

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

 

二、圖的著色的基本算法

 

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

     procedure mcoloring(k)

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

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

integer k

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

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

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

     if k=n

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

     else call mcoloring<k+1) ／／所有m—著色方案均在此反復(fù)遞歸調(diào)用中產(chǎn)生／／

    endif

    repeat

    end mcoloring

在最初調(diào)用call mcoloring(1)之前，應(yīng)對圖的鄰接矩陣置初值并對數(shù)組x置0值。

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

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

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

procedure nextvalue(k)

／／進(jìn)入此過程前x(1)，...，x(k一1)已分得了區(qū)域[o，m]中的整數(shù)且相鄰近的結(jié)

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

         些顏色，它們與結(jié)點(diǎn)k鄰接的結(jié)點(diǎn)分配的顏色不同，那末就將其中最高標(biāo)值的

         顏色分配給結(jié)點(diǎn)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) ／／試驗下一個最高標(biāo)值的顏色／／

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

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

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

   x(k)=x(j) ／／并且鄰近的結(jié)點(diǎn)有相同的顏色／／

 then exit endif   

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

end nextvalue 

該算法的計算時間上界可以由狀態(tài)空間樹的內(nèi)部結(jié)點(diǎn)數(shù) 得到。在每個內(nèi)部結(jié)點(diǎn)處，為了確定它的兒子們所對應(yīng)的合法著色，由nextvalue所花費(fèi)的時間是 (mn)。因此，總的時間由 所限界。

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

 樹。到葉于結(jié)點(diǎn)的每一條路徑表示一種至多使用3種顏色的著色法。