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

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

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

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

1 對(duì)偶圖與極大平面圖

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

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

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

2 標(biāo)準(zhǔn)圖與對(duì)角變換

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

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

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

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

圖2 用一次對(duì)角變換能把圖1所示的標(biāo)準(zhǔn)圖變成一個(gè)新的極大平面圖。Fig.2 A new large planar graph by diagonal transformation changed from fig.1

3 對(duì)角變換的四染色方法

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

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

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

我們使用上述的染色方法成功地對(duì)著名的加德納圖進(jìn)行了四染色處理。加德納圖是一個(gè)具有110個(gè)頂點(diǎn)的極大平面圖，曾經(jīng)被誤認(rèn)為是四色猜想的反例。換言之，染加德納圖需要五種顏色?？梢娛褂盟姆N顏色為其染色是相當(dāng)困難的。但從110個(gè)頂點(diǎn)的標(biāo)準(zhǔn)圖出發(fā)經(jīng)過205次對(duì)角變換則可以獲得加德納圖。因此成功得到了加德納圖的四染色方案。由于篇幅的限制我們?cè)诖寺匀ト旧牟襟E。

4 結(jié)論

雖然借助計(jì)算機(jī)已經(jīng)給出了四色定理的證明。但對(duì)任意的一個(gè)地圖如何進(jìn)行四染色還沒有一個(gè)行之有效的方法，還局限在盲目的試驗(yàn)染色階段。用我們介紹的方法成功地為加德納圖進(jìn)行了四染色處理。因此利用對(duì)角變換給一個(gè)平面圖進(jìn)行四著色也許是一個(gè)有效的辦法。只是所需的變換次數(shù)比較多，需要的中間圖也較多。手工繪圖比較繁瑣。如果通過計(jì)算機(jī)編程處理全部的染色過程，則會(huì)較方便地解決平面圖的四染色問題。這會(huì)給四色定理的應(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］.計(jì)算機(jī)工程,2005,31(7):1～2.

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

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