對角變換四染色平面圖

徐秋茹，趙寒濤，李乃川，黃興濱

（1.黑龍江省科學(xué)院自動化研究所，黑龍江哈爾濱150090；2.黑龍江大學(xué)物理科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150080）

四色猜想源于英國的F.Guthrie提出的：使用四種顏色就能夠給所有地圖染色而使兩個有公共線段邊界的區(qū)域染以不同的顏色。所有地圖意味著不僅僅是世界地圖集上的全部地圖，而是可以想象得出的所有地圖，地圖也許會有成千上萬(或更多)的國家、各種可能的形狀、大小和彼鄰關(guān)系。由于其證明的難度使其成為繼Fermat大定理之后又一著名的數(shù)學(xué)未解問題。1976年，兩位美國數(shù)學(xué)家，Appel和Haken宣稱他們證明了四色問題。但有不盡人意之處。因為他們的證明主要由計算機完成，并且證明程序太長，人工無法檢查其正確性［1］。

盡管已經(jīng)證明了四色猜想，但如何給任意一個平面圖進行四染色還沒有解決，還停留在試驗染色的階段［2］。民航空域頻率覆蓋是典型的四染色問題案例。研究四染色問題對民航信息化建設(shè)有重要意義［3］。我們利用極大平面圖的對角變換的方法嘗試解決平面圖的四染色問題。

1 對偶圖與極大平面圖

給地圖染色問題與其區(qū)域的具體形狀無關(guān)，僅與它們彼鄰關(guān)系有關(guān)。所以四色問題是一個拓撲學(xué)問題。它很容易被等價為給平面圖頂點染色的問題。

把給定地圖的每個區(qū)域等價為一個點，通常叫做圖的頂點。然后用邊連接這些頂點形成一個圖，規(guī)則是：只有也只有當兩個頂點各自代表的地圖區(qū)域有公共的邊界線時才可以連接這兩個頂點。按如此方法得到的圖稱為地圖的對偶圖。這樣可以把地圖的區(qū)域染色轉(zhuǎn)換為其對偶圖的頂點染色。而保證：該對偶圖的頂點可以最多使用四種顏色染色而讓有一個邊連接的兩個頂點具有不同的顏色。平面圖就是可以在平面上畫出且任何兩邊不會在端點之外相交的圖。地圖是一個平面圖，所以其對偶圖也是一個平面圖，并且是一個簡單平面圖。

一種簡單的平面圖被定義為極大平面圖：如果它是平面圖，若增加任何一條邊都將破壞其平面性。極大平面圖的所有面都是由三個邊組成，極大平面圖也稱之為三角拋分圖。所以只要解決所有的極大平面圖的四染色問題則解決了所有的平面圖染色［4］。

2 標準圖與對角變換

讓我們選取最大平面圖的一種特殊構(gòu)型，如圖1所示。我們稱之為標準圖。標準圖的最小頂點數(shù)為4，標準圖頂點數(shù)量的改變只能在頂點4到頂點n之間進行。明顯的結(jié)論是：任意頂點數(shù)的標準圖都容易用四色染色。

圖1 具有n個頂點的標準圖。按規(guī)則容易用紅色、綠色、黑色和白色染它所有頂點。Fig.1 Standard drawing with n vertices.Color all the vertices with red,green,black and white regularly.

對角變換：在任意極大平面圖中構(gòu)成四邊形的四個頂點中去掉連接對角頂點的邊后，放一個新的邊連接另一對頂點。圖2給出了一次具體的對角變換，即去掉連接頂點②與④的邊之后，放置一個連接頂點③與⑤的邊。

對角變換給出了任意極大平面圖與相同頂點的標準圖之間的關(guān)系。可以證明逐次使用對角變換可以把任意極大平面圖轉(zhuǎn)化到它的標準圖［5］。由于對角變換是可逆變換，所以也可以證明：從一個任意頂點的標準圖出發(fā)，通過對角變換可以獲得所有的極大平面圖。

圖2 用一次對角變換能把圖1所示的標準圖變成一個新的極大平面圖。Fig.2 A new large planar graph by diagonal transformation changed from fig.1

3 對角變換的四染色方法

首先，將待染的極大平面圖通過對角變換轉(zhuǎn)換為標準圖并記錄好每一次對角變換的過程和次序。目的是容易找到從標準圖到待染圖之間的對角變換的關(guān)系。具體操作時要先把帶染色的圖抻成標準圖的形狀，并使各頂點保持原有的連接關(guān)系。這樣就會很容易找到對角變換的次序。

其次，把上述的對角變換的次序和過程倒過來把一個同頂點的標準圖通過對角變換轉(zhuǎn)化為待染的極大平面圖。目的是檢查從標準圖到待染圖之間的對角變換的關(guān)系的正確性。

最后，先把標準圖用四色染好，如圖1；然后開始第一次對角變換，如圖2所示。當新放置的邊要連接的兩個點顏色不同時則直接連接；若顏色相同則利用肯普網(wǎng)進行局部交換顏色至兩頂點的顏色不同，這樣保證在對角變換后的極大平面圖還是四染色的；交換顏色的方法是把連接這兩個頂點的肯普鏈的種類減少到兩種即可。下一步重復(fù)上述過程進行第二次對角變換，又會得到一個四染色的極大平面圖；重復(fù)直至完成全部的對角變換。則完成該圖的四染色方案。

我們使用上述的染色方法成功地對著名的加德納圖進行了四染色處理。加德納圖是一個具有110個頂點的極大平面圖，曾經(jīng)被誤認為是四色猜想的反例。換言之，染加德納圖需要五種顏色?？梢娛褂盟姆N顏色為其染色是相當困難的。但從110個頂點的標準圖出發(fā)經(jīng)過205次對角變換則可以獲得加德納圖。因此成功得到了加德納圖的四染色方案。由于篇幅的限制我們在此略去染色的步驟。

4 結(jié)論

雖然借助計算機已經(jīng)給出了四色定理的證明。但對任意的一個地圖如何進行四染色還沒有一個行之有效的方法，還局限在盲目的試驗染色階段。用我們介紹的方法成功地為加德納圖進行了四染色處理。因此利用對角變換給一個平面圖進行四著色也許是一個有效的辦法。只是所需的變換次數(shù)比較多，需要的中間圖也較多。手工繪圖比較繁瑣。如果通過計算機編程處理全部的染色過程，則會較方便地解決平面圖的四染色問題。這會給四色定理的應(yīng)用帶來無窮的魅力。

［1］K.Appel,and W.Haken.The solution ofthe four-color-map problem.Scientific American［J］.1977,27(4):108～121.

［2］許壽椿.四色問題漫談［J］.科學(xué)中國人,1998,(4):41～44.

［3］王錦彪,王瑋瑋,鄭蕓,等.四色問題反例研究與民航空域頻率覆蓋［J］.計算機工程,2005,31(7):1～2.

［4］王紹文.極大平面圖結(jié)構(gòu)研究［J］.光子學(xué)報,1998,(2):167～172.

［5］劉彥佩.平面圖的理論與四色問題(Ⅰ)［J］.數(shù)學(xué)研究與評論,1983,3(3):123～136.