對(duì)角變換四染色平面圖

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

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

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

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

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

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

一種簡(jiǎn)單的平面圖被定義為極大平面圖：如果它是平面圖，若增加任何一條邊都將破壞其平面性。極大平面圖的所有面都是由三個(gè)邊組成，極大平面圖也稱之為三角拋分圖。所以只要解決所有的極大平面圖的四染色問(wèn)題則解決了所有的平面圖染色［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ā)，通過(guò)對(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ì)角變換的四染色方法

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

其次，把上述的對(duì)角變換的次序和過(guò)程倒過(guò)來(lái)把一個(gè)同頂點(diǎn)的標(biāo)準(zhǔn)圖通過(guò)對(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ù)上述過(guò)程進(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)過(guò)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ù)比較多，需要的中間圖也較多。手工繪圖比較繁瑣。如果通過(guò)計(jì)算機(jī)編程處理全部的染色過(guò)程，則會(huì)較方便地解決平面圖的四染色問(wèn)題。這會(huì)給四色定理的應(yīng)用帶來(lái)無(wú)窮的魅力。

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

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

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

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

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