一、 圖的著色的基本概念

 

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

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

 

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

 

二、圖的著色的基本算法

 

[算法]： 找一個(gè)圖的所有m—著色方案 [動(dòng)畫(huà)]

     procedure mcoloring(k)

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

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

integer k

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

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

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

     if k=n

      then print(x) ／／至多用了m種顏色分配給n個(gè)結(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)對(duì)圖的鄰接矩陣置初值并對(duì)數(shù)組x置0值。

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

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

 [算法]： 生成下一種顏色   [動(dòng)畫(huà)]

procedure nextvalue(k)

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

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

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

         顏色分配給結(jié)點(diǎn)k；如果沒(méi)剩下可用的顏色，則置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) ／／試驗(yàn)下一個(gè)最高標(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 

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

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

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