四色圖論
——四色問題解的存在性及求解方法

楊 名 生

( 大連理工大學 工程力學研究所, 遼寧 大連 116024 )

?

四色圖論
——四色問題解的存在性及求解方法

楊 名 生*

( 大連理工大學 工程力學研究所, 遼寧 大連 116024 )

直接從四色問題出發，建立圖論的另外一個新體系．在提出區域、邊界線、結點等定義，對復雜地圖進行分層簡化后，得到體系的3個基本定理，又用鏈路這一工具，證明任意有限個區域地圖的四色解存在并給出了求解方法．

圖論；四色問題；區域；邊界線；結點；鏈路

0 引 言

圖論起源于K?nisberg七橋問題和Guthrie的四色猜測．Euler圖給出前者一個否定的結果，并推動圖論的發展，建立了圖論的傳統體系．它從確定事物的點(稱為頂點)出發，通過兩點間連線(稱為邊)的集合構成線狀圖(有向圖或無向圖，平面圖或非平面圖)，并用矩陣工具對路徑、回路、信號流圖等規律進行研究．同時也推動了四色問題的研究[1-2]．20世紀70年代，Appel和Haken用當時的電子計算機經過近千小時的運算證明四色問題[3-4]，直到80年代才得到學者的首肯，原因是其幾百頁的邏輯推理公式太繁雜，數學界更期待有簡捷的常規證明[4-5]．

四色問題可簡述如下：任何平面地圖都可用4種顏色著色，使其相鄰區域著色不同[1]．

引導圖論誕生的四色問題，具有不同于七橋問題的特點，它關心的是區域的相鄰性．區域有很大的任意性，本文提出一系列簡化處理方案并引入鏈路等新概念，將求解四色問題簡化為求基礎地圖的四色解，并最終解決四色猜測問題．

1 預備知識[6]

1.1 約定和定義

1.1.1 地圖 地圖是球面的一種劃分，它使球面的某些點只屬于1個區域，某些點屬于2個區域，某些點屬于3個或3個以上區域．不存在不屬于任何區域的點；區域都是R2的二維空間的一片[7]，不關心區域形狀和面積大小，它必須是二維的，不能是一維的線或零維的點，換言之，不存在只有有限個點或R1個點的區域．

為表示地圖而把球面剖開展平畫在一個矩形平面上，此時剖線展為矩形，周邊不具有任何幾何意義．矩形平面全體與球面全體完全對應，這是一個最簡單的、無任何邊界線和結點的單區域地圖；若球面地圖有復雜的邊界線和結點，則剖線一定不能與任何邊界線相交，也不能過任何結點．

1.1.2 區域、邊界線和結點 區域是若干條邊界線所圍成平面中的有限部分，區域的分割取決于邊界線，邊界線是一維的，屬于R1[7]．邊界線兩側分屬于兩個不同區域，只有邊界線為它所分割的兩個區域所共有，邊界線之外的點必屬于且僅屬于一個區域．一般邊界線(Jordan曲線)分割兩個區域并為它們所共有，不關心其形狀和長度；邊界線的兩個特殊點為3個或3個以上區域所共有，這種點稱為邊界線的結點，它沒有形狀與大小，是劃分兩個區域邊界線的端點(起點或終點)，是不同邊界線的交接點(這里不討論只有一個結點和沒有結點的邊界線)；結點的階是交于此的邊界線數，用J表示，它也是共有該點的區域個數，顯然有J≥3，結點的階為3時特別稱為簡單結點；區域的邊界線可細分為內邊界線和外邊界線兩種，也可以沒有內邊界線．區域內邊界線若存在則表示區域內挖了孔洞，且不破壞區域的連通性，內外邊界線的劃分并沒有絕對標準，在球面上它們都是自身不相交、又互相不相交的封閉曲線，當球面展開成為平面時(注意：剖線段不能與任何邊界線相交)，從矩形周邊向區域行進中首次遇到的是外邊界線，之后遇到的是內邊界線，故內外邊界線的確定與剖線的位置有關．在區域拓撲關系分類中，只考慮區域的外邊界線往往是很方便的，因為一個區域的內邊界線必定是另外一個區域或一個區域集團的外邊界線．

四色問題不關心區域的形狀和面積大小，不關心邊界線的形狀和長短，不關心結點的具體位置，只關心區域之間的相鄰關系、結點間的邊界線連接關系等．

區域是連通的，是指區域的任何兩點都可以用區域的點連接起來；區域是單層的，是指區域的任何封閉曲線都可以在區域內收縮為一點，有內邊界線的區域不是單層．

定理1(互換定理) 若地圖的一種著色方案滿足四色問題的要求，對換四色中任意兩種顏色，得到的新著色方案依然滿足四色問題的要求．

證明 在滿足四色問題要求的一種著色方案中，任意取兩個相鄰區域，則它們的著色必定相異．如果對換的兩種顏色與這兩個區域的著色完全相同或者完全不同，則它們顯然保持相異的特性；否則對換的兩種顏色之一必與這兩個區域著色之一相同，且對換的兩種顏色的另外一種與兩個區域中另外一個區域的著色不同．故對換后仍能保持兩個區域著色的相異性．由于那兩個區域是任意的，從而證明了定理．

推論1 地圖滿足四色問題要求的著色方案，分別可以指定某一區域的著色、指定相鄰兩區域的著色、指定彼此相鄰三區域的著色．

據此，地圖有一種滿足四色問題的著色方案，必然有許多種不同的著色方案．為此可將解空間寫成C={1c，2c，3c，4c}，其中的符號，例如1c可以代表B，也可以代表G、R或Y，不同符號代表不同著色．凡是通過對換可以互相轉化的兩種著色方案稱為同一類解；如果地圖只有一類解，則稱其解是唯一的．

1.1.4 原始圖與生成圖 地圖的所有區域都是單層的，且所有結點都是簡單結點，則稱其為原始圖；當至少有一個結點不是簡單的則稱其為生成圖．原始圖的某條邊界線的長度縮減為零時，重合結點的階上升為4，此新圖為原始圖的生成圖．兩圖相比區域數相同，原始圖的結點數和邊界線數都最多，即相鄰關系最多，故原始圖的四色解也一定是其生成圖的四色解．生成圖和原始圖的互化方法并不唯一．假設原始圖的邊界線數為b，簡單結點的個數為n，則有b=3n/2．此式說明n必為偶數，引入圖的特征數m，令n=2m，則b=3m．

1.2 幾個定理

定理2(基本定理1) 設原始圖中區域數為r，結點數為n，邊界線數為b，當r≥3時，如下關系成立：n(r)=2(r-2)，b(r)=3(r-2)．

證明 用數學歸納法證明此定理：

(1)當r=3時，由于是原始圖，結點都是簡單的(見圖1)，應有r=3，n=2，b=3，結論顯然成立．

圖1 r=3時的地圖

(2)假定r=k時結論成立，有n=2(k-2)，b=3(k-2)．保持原始圖的區域數增一的方法很多種，但都新增2個結點和3條邊界線；有時區域的生成不止一個，此情況可以化為逐次增加一區域來組合實現[6]．這就證明結論對r=k+1亦成立．

基本定理1的結論與前文的分析是一致的，且更深入地揭示了原始圖中的區域、結點和邊界線三者之間的數量關系，引入圖的特征數m=r-2．

推論2 單層圖的區域數為r，結點數為n，邊界線數為b，當r≥3時，有n(r)=2(r-2)-D，b(r)=3(r-2)-D，其中D是所有結點的階減3的總和．顯然有n-b+r=2，這正是圖論中的Euler 公式[2]．

定理3(裝配定理) 1個(圖2(a)中A)、2個(圖2(b)中A與B)或3個(圖2(c)中A、B與C)相互相鄰的區域如圖2左邊分割的兩個區域集團G1和G2整體圖四色問題，可以分解為圖2中間和右邊兩個獨立的子四色問題；如果這兩個子四色問題都有解，則它們裝配成的原四色問題(圖2左邊)也一定有解．

圖2 化為相應子地圖的復雜地圖求解

證明 推論1給出證明．

圖2(a)可稱為第一類可移去問題(解決去孔洞)；圖2(b)稱為第二類可移去問題(解決去多次相鄰)，特別當區域集團G1或G2為單區域時依然成立．裝配定理解決了地圖化為若干個無孔洞且相鄰次數不多于1的子問題，從而使問題簡化．

定理4(吸收定理) 對單層地圖的二邊、三邊及四邊區域，可將其吸收使圖中區域的最小邊界線數大于等于5．

這里所謂吸收系指彼此相鄰的幾個區域合并的操作．兩個區域的合并使其相鄰邊界線消失，隨之兩條邊界線也合并，總體減3條邊界線及2個結點．

(1)吸收二邊區域．二邊區域的相鄰兩個區域二次相鄰．實際處理時可被其相鄰一區域吸收，使區域總數減一且那兩個區域恢復一次相鄰，地圖返回解的二邊區域著色不唯一，其兩種選擇都能滿足特定要求．

(2)吸收三邊區域．三邊區域與周圍彼此相鄰的3個區域都相鄰，被任一區域吸收時區域總數減一；地圖返回解中，三邊區域選取與那3個區域著色都不同即可．

(3)吸收四邊區域．四邊區域周圍相鄰的4個區域都彼此順序相鄰，但不存在相對的兩個區域相鄰．將四邊區域與任何一對相對區域合并，地圖區域數減少2；地圖返回解中，若另一對相對區域的著色不同，四邊區域取與它們都不同的第四種顏色；若另一對相對區域的著色相同，四邊區域將有另外兩種顏色可選擇．

單層地圖的所有結點都是簡單結點，所有相鄰都是一次相鄰的問題稱為簡單問題．

定理5(相鄰定理)r個區域簡單問題，其相鄰關系矩陣中非元總數：

j(r)=6(r-2)；r≥3

證明 由基本定理1和簡單問題的規定可證明．

引入相鄰關系矩陣的空元總數函數，記為v(r)，在簡單問題中顯然有

v(r)=r2-7r+12；r≥3

方程v(r)=0有兩個根：r=3與r=4．v′(r)=2r-7；當r≥4時，v′(r)>0，故v(r)除去r=3和r=4兩個零點外，再也沒有零點．

特別是v(r)r21(r∞)，故有

推論3r個區域簡單問題的相鄰關系矩陣中空元總數：v(r)=r2-7r+12，其中r≥3．

推論4 簡單問題中區域數很大時，其相鄰關系矩陣為稀疏陣，即實元和非元總數隨區域數增加而比例減少．

推論5 區域數相同時，簡單問題的相鄰關系矩陣的非元總數最多(或空元總數最少)．

定理6(基本定理2)r個區域的簡單問題，其區域最小邊界線數Bmin(r)取值只有3種可能：當4≤r<6時，只能為3；當6≤r<12及r=13時，可能為3，否則為4；當r=12及r>13時，可能為3，否則為4，若不然必為5，沒有其他可能．

推論6 五色定理[2-3]是成立的．

證明 邊界線數為5的區域與其周圍彼此不相鄰的任意兩個區域合并，再求解生成的問題，這4個區域最多可著四色，如果有第五種顏色，則返回解必然存在．

r個區域地圖的區域最小邊界線數大于等于5表示為Bmin(r)=5，滿足Bmin(r)=5的簡單地圖稱為基礎地圖．

引用符號Bm，表示邊界線數是m的一個區域．

定理7(基本定理3) 基礎地圖的B5個數在12的基礎上，每出現一個Bm(m≥6)，B5個數都要增加m-6．

證明 當地圖所有區域都是B5時，顯然它的區域數必為12(見圖3)．對于一般的基礎地圖而言，根據基本定理1知每增加一個單元，就會增加3條邊和2個結點．如果這個單元是Bm(m≥6)，就其本身增加m個結點和m條邊，超出基本定理1的要求，必須用x個B5來抵消；它們產生5x個結點和5x條邊，總圖增加1+x個單元，就單元而言增加m+5x條邊，相當于總圖增加(m+5x)/2條邊，它應當是3(1+x)，即(m+5x)/2=3(1+x)，解得x=m-6，證明了此定理．

圖3 r=12時的地圖

2 鏈 路

2.1 鏈路的規定

基礎地圖的四色解系指，它的每個區域都從四色空間中著一色，且相鄰區域著色相異．四色空間任意兩種顏色可組成一條鏈路族，余下兩種顏色則構成另外的鏈路族；彼此相鄰且著色屬于同一族的區域串接起來就構成了地圖的鏈路，它的寬度是一個區域，每個區域又可稱為鏈路的一個點(或單元)．滿足四色解的基礎地圖的每個區域，都著一定顏色，也必定屬于一個且僅屬于一個鏈路族．

在C={1c，2c，3c，4c}約定下，考慮互換定理，不失一般性地認定{1c，4c}組成鏈路一族；{2c，3c}則構成鏈路另外一族．鏈路族組成方式有3種：{1c，4c}、{1c，2c}和{1c，3c}，相應地另外一族是{2c，3c}、{3c，4c}和{2c，4c}，顯然鏈路中的兩色應當順序交錯出現．

地圖簡單結點周圍的3個區域，由于兩兩相鄰使其在四色空間中著三色，故必有兩個區域位于同一族，第三區域將屬于另外一族，同族兩區域的相鄰邊界線是鏈路的連接線，稱為族相鄰邊界線(在不混淆情況下簡稱為“節”)；另外的兩條邊界線則為兩族間鏈路的分界線(或簡稱“邊”)．

鏈路的點有以下幾種類型．(1)孤立點：與它相鄰的周圍區域都是另外一族，這些區域構成該族的封閉環，因而這些區域的個數必為偶數，故孤立點的區域邊界線數也是同樣的偶數．(2)端點：與它相鄰的周圍區域有且僅有一個區域和它同族，這個區域成為一條鏈路的起止點，余下區域則構成另外一族的開口環．(3)過點：與它相鄰的周圍區域有且僅有兩個彼此不相鄰的區域和它同族，它成為鏈路的中間點．(4)分支點：與它相鄰的周圍區域有3個或3個以上彼此不相鄰的區域和它同族，它成為一條鏈路的分岔．一條鏈路(或環路)只有通過分支點才能連接多條同族鏈路，按規定顯然分支點的邊界線數應大于等于6．

B5點只能做端點和過點，不能做孤立點和分支點；對于Bm點：當m≥6時，可做端點、過點和分支點，當m為偶數時，還可以做孤立點．

2.2 鏈路的基本要求

鏈路是四色解的產物，它的兩條基本要求也就是四色解的要求：(1)鏈路中順序各點著色必須是族中指定兩色交替出現，特殊情況可能是族中指定兩色之一(例如孤立點)．(2)鏈路僅在分支點處能連接同族鏈路，其他情況同族鏈路不能相鄰，它們之間必為另外一族所隔離．這是分支點的邊界線數應大于等于6的原因．

2.3 鏈路的幾種類型

若干依次相鄰的同族區域構成的鏈路有幾種類型．(1)無分支鏈路：由同族的兩個端點和中間若干過點依次相鄰組成，鏈路端點位于另外一族的開口環內．鏈路的長度系指其區域個數，當長度為1時，它沒有過點且兩個端點重合為一點(孤立點)，其周圍是另外一族的封閉環．(2)無分支封閉環鏈路(簡稱環路)：當無分支鏈路的長度為大于等于6的偶數，且兩個端點相鄰而使端點消失時，則形成一族無分支的封閉環路，其每個點都是過點，并將另外一族分隔為沒有聯系的兩部分，使它們可以各自獨立地交換雙色；每個關聯部分特稱為獨聯體，從而增加了交換色的靈活性．(3)鏈路或環路帶分支的鏈路：它的特點是某些過點同時也是分支點，通過這些分支點可以連接若干個同族的分支鏈路，當然分支還可以再帶分支，多一個分支則多一個端點．分支鏈路將隨同主鏈路一起變換著色．環路帶分支鏈路時，其邊長度為環路長度與分支鏈路長度的2倍之和(它當然是偶數)，它等于所圍另外一族的區域集團的和區域邊界線總數[6]．分支使鏈路千變萬化，能適應各種復雜的區域隨機分布．(4)同族的封閉環鏈路之間直接連成一體，或通過鏈路間接連成一體，都是通過某些既是過點又是分支點而完成的，它們要一體地賦值．封閉環鏈路內部或外部的異族可各自獨立地賦值或交換．

2.4 鏈路的多樣性及產生多個四色解

若是再改變鏈路定義，著色方案雖然不變，卻可能產生一些新鏈路而形成新獨聯體，獨聯體的單獨或聯合變換，雖然不改變鏈路形狀，但確實改變了著色方案，……由此可見，想通過已確定的千變萬化的區域布局，來邏輯地推出四色解是不現實的，因為存在的解可能非常多．下面用12塊五邊形和20塊六邊形區域構造的老式足球為例說明．

圖4是32個區域組成的老式足球圖，這3個圖的著色其實完全相同，但它們的鏈路規定不同，因而獨聯體的個數也不同．圖4(a)I=2(1+1)圖的族構造是R-G、B-Y，獨聯體數為1+1，它只有一個四色解；圖4(b)I=4(2+2)圖的族構造是R-B、G-Y，獨聯體數為2+2，它將有4個不同的四色解；圖4(c)I=6(2+4)圖的族構造是R-Y、B-G，獨聯體數為2+4，它將有16個不同的四色解．

圖5同樣是32個區域組成的足球圖，它們的鏈路規定完全相同，都是R-Y、B-G．圖5(a)的獨聯體數為1+2，它將有2個不同解．對換B與Y后，再將孤立點的G換成B而成圖(b)，它的獨聯體數為2+3，它將有8個不同解．將圖(b)的B與Y對換而成圖(c)，它的獨聯體數為1+6，它將有32個不同的四色解．

綜上所述，改變鏈路族的結構、交換部分獨聯體雙色、兩種操作組合進行，都能帶來環狀結構的大量新四色解．就上述足球而言至少有32種不同的四色解．

2.5 鏈路定理

定理8(鏈路定理) 基礎地圖的四色解中，鏈路圖的任何結點都僅連一條族相鄰邊(簡稱為節)和兩條族間邊界線(簡稱邊)．

證明 從略．

對于滿足四色問題要求的基礎地圖的鏈路圖而言，鏈路定理指明：(1)節絕不相互連接，不管是同族還是異族．(2)邊依次連接形成封閉一筆畫線．(3)一條節的兩端分別支撐兩條邊，節將同族的兩個區域連接，邊將不同族分隔開．鏈路定理對一個結點而言是解的必要條件，對一批結點(或所有結點)就變成四色解的充分條件，封閉一筆畫邊線的延續性使四色解的存在性得到證明，還提供了求四色解的操作方法．基礎地圖劃分區域的邊界線，此時分為節和邊兩大類．

圖4 老式足球(12B5+20B6)的3種鏈路圖

圖5 老式足球(12B5+20B6)的另外3種鏈路圖

2.6 基礎地圖的鏈路形式決定區域和節的數量關系

鏈路定理表明全圖的區域數比節數多2．不同的鏈路形式確定不同的區域數與節數之間關系：(1)無分支鏈路族的區域數比節數多1，對于孤立點也是如此．(2)無分支封閉環鏈路族的區域數和節數相同．(3)鏈路或環路所帶分支鏈路的區域數和節數也相同，包括分支又帶分支的情況．(4)同族鏈路或同族環路(及其分支)相遇會使族的區域數比節數減少1．

2.7 基礎地圖解的存在性

r個區域的基礎地圖，根據基本定理1可知，其結點數n(r)=2(r-2)，邊界線數b(r)=3(r-2)．按鏈路定理原則可知，要有r-2個節和2(r-2)條邊，且這些節沒有任何兩個相連接，這些邊依次順序相連，成為一個或若干個一筆畫的封閉線．上述結點數和邊界線數恰能滿足鏈路定理的要求．

當鏈路無環形結構時，即I=2(1+1)情況，基礎地圖的邊將全空間分成互不聯系的兩部分，各為鏈路的一族；由2.6可知每一族的區域數比節數多1．要特別指出的是，這里的一筆畫線嚴格受控于節，每一筆畫線都由節支撐其寬度，或者說由節來連接同族的兩個區域．首先指出最簡單的基礎地圖是12B5，它有四色解(見圖3(a)和圖6(a))；r>13的首個2B6+12B5也有四色解(見圖6(b)，紅藍都是無分支的鏈路，其邊為一筆畫的封閉線)，在此基礎上逐一增加區域，考察一筆畫圖形應當如何變化．同族鏈路增加一個區域只有3種方式：(1)鏈路的端點增加一區域(見圖6(c)上部黑虛線，生成五邊區域)；(2)鏈路的過點增加一區域(見圖6(c)下部黑虛線，對其上生成七邊區域)；(3)鏈路的過點生出新的分支鏈路(見圖6(d)右部黑虛線，對其右生成六邊區域)．

圖6(c)、(d)中黑實線表示紅與藍兩族的邊，紅、藍虛線分別表示紅、藍族的節，黑虛線表示為增加一區域引進的新節，它連接新引進的兩個結點，另外兩條邊則保持一筆畫的線路；如同基本定理1所指出的那樣，區域增一使全圖增加2個結點和3條邊界線，結果是或者使鏈路長度增一，或者使它生出新分支鏈路．一筆畫的封閉線路，形成紅族和藍族各自的樹狀結構，用梳齒型結構來描述更為恰當；每一條無分支的鏈路都相當一個齒，這些不同顏色的齒交錯分布，每個齒都有一個端點，同族齒在分支點處相連成為一個整體，它的外廓就是紅藍兩族的分界線，就是邊連成的封閉一筆畫線，構成該基礎地圖的I=2(1+1)的四色解，類似于圖4(a)中的I=2(1+1)結構的四色解(紅5齒對藍4齒)．

圖6 四色解存在性證明

樹狀結構需要足夠的分支點，在基礎地圖中只有B5不能做分支點．當大量B5區域集中在一起時，形成兩個交叉樹型結構已不可能，只有產生某一族的環形結構才能形成鏈路．哈密爾頓圖就是這樣產生的[9]；例如b25a圖，區域組成：1B9+3B8+21B5(基本定理3)，大量B5聚積不可能形成兩個交叉樹型結構，必須有環形鏈路結構出現．正如2.3中鏈路類型和圖5(a)指出，環形區域數為偶數，且環形族的區域數和節數相等，其內外的另外一族非環形結構都是區域數比節數多1，故保持區域(r)比節(r-2)的總數多2的基本要求．一族的環形結構將另外一族分割為互不連接的兩部分，故不能在同一個一筆畫封閉線內，勢必分屬于兩個相互不連接的一筆畫封閉線．若環形封閉鏈路的內(或外)部是另外一族的無環形的樹形結構，環路帶分支鏈路的邊長度為環路長度與分支鏈區域長度的2倍之和(它當然是偶數)，它相當所圍另外一族的區域集團和區域邊界線總和(見2.3中(3))．這可確保環形封閉鏈路另一側的外(或內)部的待定結點數為偶數，既保證完整節的生成，也保證邊的增加是偶數(基本定理1)．這樣一來就可以分別在其內(或外)部按I=2(1+1)的情況處理，不同的是在全圖的部分范圍內執行，這些內(或外)部的雙樹型鏈路結構都可看成孤立點環形結構經過一系列區域增加操作而完成，偶數邊的孤立點存在四色解也可得出原雙樹型鏈路結構有四色解．按鏈路定理可知，節是支撐鏈路的區域連接及主控寬度和方向，邊是接受主控的相序一筆畫封閉走線并分隔兩族．基礎地圖的2(r-2)個偶數結點，理論上可以形成r-2個完備的節，以及2(r-2)條邊線．如果一條邊線走遍全圖所有結點而沒有形成環形鏈路，則最后構成I=2(1+1)的結果．如果邊線走過部分區域已構成封閉一筆畫邊線，不但已形成環形鏈路，且環形鏈路本身的區域數也為偶數，這就使封閉一筆畫邊線數必為偶數，且環形鏈路之內(或外)的待定結點數都是偶數，可再次形成完備的節，并構成I>2的結果．顯然環路分布遵循如下原則：只有異族環可以相嵌套，同族環則不能相嵌套，同族環可以并立，但必須直接或間接相連．出現多個鏈路的環形結構將形成I-1個一筆畫的偶數條封閉邊線，每個結點都有且僅有一個節，各一筆畫封閉邊線之間仍由這些節支撐．

2.8 基礎地圖的求解方法

2.7中同時也給出求解的“邊-節”探尋法．

當鏈路無環形結構時，即I=2(1+1)情況，參看圖7；任選一個首結點編號為1(紅)，由它引出的邊有3個方向，在圖7(a)中任選一條邊的終點編號為2，從2號開始后的所有結點都有3種可能：一是選邊有兩種可能的可變結點(用藍色碼表示)，選定其邊后的另外一條邊確定為節，用紅虛線表示，這一筆畫邊線前進時還帶一個節對其后操作進行控制．二是進行若干步后出現選邊只有一種可能的不變結點(用黑色碼表示)，出現不變結點的原因有兩個：一個是相鄰出現一個早已生成的節的另外一端點，它必須前行(如圖7(a)的5號點)，且不必再畫新節；另一個是選邊之一卻和初始點1相連，且一筆畫封閉邊總數不是偶數，它不能前行，必須選另外一條邊；為此都只能選一種．三是前進方向不可以選，它的原因也有兩個：一是相鄰出現兩個節的終點，它無法前行(如圖7(b)的17號點)，否則會出現兩個節相連的現象(違背鏈路定理)；另一是一筆畫封閉邊線已構成，而邊的總數不是偶數，為此要作回溯處理：由此點開始沿著數碼順序逆行，每遇見黑碼(即不變結點)時，則將碼和其伴隨的節一起刪除(注意：不是其伴隨節不可刪除)；按此處理直到遇見第一個藍數碼(即可變結點，見圖7(b)的11號點)為止，改變藍色為黑色(即將可變結點變為不變結點)，并改變其前進方向和相應的節(見圖7(c)的11號點)，繼續前進…直到所有結點都被邊跑過，最終回到起始點1處，形成封閉的一筆畫線圖(有時要補上最后的節)，且邊總數是偶數，任何結點都僅連一個節．這種尋“邊”前進帶“節”控制的方法，是要在偶數2(r-2)個結點和偶數2(r-2)條邊中尋找符合鏈路定理的鏈路構造，對后面的有環情況也是如此．獨聯體數為I=2(1+1)的四色解還可能不止一個(見圖7(a) 和(c)，是不同的四色解)．

當鏈路出現某一族的環形結構時，即I>2情況，見圖8：一族的環形結構將另一族分隔為相互不連接的內外兩部分，每一部分對環形族的一側則構成一個無環形結構的求四色解問題，如果把對全局的考慮改為對圖形的相連接的部分作類似處理，就成為一個無環形結構鏈路(I=2)的求解問題，它的前提是要求該環形結構的區域本身總數(不包括它的內或外的分支)是偶數即可．如果環形結構本身的區域總數不是偶數，則作前進方向不可選而失敗，如前所述逆行順序查找并處理．這種一部分一部分地考慮，可得到多個受控于節的封閉一筆畫邊線．圖8(a)和(b)是文獻[9]的哈密爾頓b25a圖的兩個帶不同環路的解；圖8(c)是1B9+6B6+15B5圖的帶環路的四色解．當區域數量r較大時，如前所言，會有很多對應于不同鏈路環形結構的四色解．從實用角度考慮，求多個可控封閉一筆畫偶數條邊線的四色解，更為方便和簡捷，所有封閉一筆畫偶數條邊線的總和是偶數2(r-2)，連接所有結點的節的總和是r-2．

圖7 無環路基礎地圖求四色解方法之例

圖8 有環路基礎地圖求四色解方法之例

3 地圖求四色解的步驟

地圖求四色解的步驟如下：

步驟1 統一編號地圖區域．對地圖的所有區域進行編號，保證每個區域的編號不缺失又是唯一的即可．

步驟2 無孔洞處理地圖．通過裝配定理的第一類可移去問題和第二類可移去問題的處理，化原問題為若干個無孔洞且相鄰次數不多于1的子地圖求四色解問題．(如果有G2是單區域的第二類可移去問題時，也可留后轉步驟4．)

步驟3 簡單化處理地圖．當地圖中有階數大于3的結點時，有許多種方法可將此結點“拉伸”以減少其階數，使所有結點的階都是3，從而使地圖簡單化．生成圖轉化為原始圖的方法很多，它的隨意性也影響四色解的結果．

步驟4 基礎化處理地圖．采用吸收定理來吸收二邊、三邊、四邊區域，至此轉化為基礎地圖求四色解問題．這個處理也有一定隨意性．

步驟2～4的處理，只是可能丟掉一些原問題的四色解，絕沒有引進原問題之外的新四色解，這在研究解的存在性和求解方法中是完全可以接受的．

步驟5 求解基礎地圖．每個基礎地圖都按2.8中的方法求解．(高效的求解方法尚待進一步探討．)

步驟6 逆向反代求原問題的四色解．此步驟只是步驟1～5的逆過程，由本文所提供的理論和方法可得到原問題的四色解，要特別指出的是按著區域的編號進行著色的交換必須一一對應．

4 結 語

本文針對四色問題，通過定義區域、邊界線、結點，將其簡化為基礎地圖的四色解，引入鏈路得到解的存在性及求解新方法．

致謝：大連理工大學的翁國標老師對本文提出了有價值的建議，在此表示感謝．

[1] Ore O. The Four-Color Problem [M]. New York:Academic Press, 1967.

[2] 邦迪 J A, 默締 U S R. 圖論及其應用[M]. 吳望名,等譯. 北京:科學出版社, 1984．

Bondy J A, Murty U S R. Graph Theory with Applications [M]. WU Wang-ming,etal, trans. Beijing:Science Press, 1984. (in Chinese)

[3] 林 壽. 文明之路—數學史演講錄[M]. 北京:科學出版社, 2010.

LIN Shou. Civilization - Mathematical History Lectures on Road [M]. Beijing:Science Press, 2010. (in Chinese)

[4] 張奠廟. 20世紀數學經緯[M]. 上海:華東師范大學出版社, 2002.

ZHANG Dian-miao. A Panorama of the 20th Century Mathematics [M]. Shanghai:East China Normal University Press, 2002. (in Chinese)

[5] 前田渡,伊東正安. 現代圖論基礎[M]. 陶思雨,王緝惠,譯. 北京:高等教育出版社, 1987.

Mayeda W, Ito M. Modern Graph Basis [M]. TAO Si-yu, WANG Ji-hui, trans. Beijing:Higher Education Press, 1987. (in Chinese)

[6] YANG Ming-sheng . Exploration of solutions to the four color problem [J]. International Journal of Analyzing Methods of Components and Combinatorial Biology in Mathematics, 2008, 1(1):27-38

[7] 杜布洛文 Ь A,諾維可夫C Л,福明柯 A T. 現代幾何學:方法與應用[M]. 徐明,譯. 北京:高等教育出版社, 2006.

Dubrovin B A, Novikov S P, Fomenko A T. Modern Geometry: Methods and Applications [M]. XU Ming, trans. Beijing:Higher Education Press, 2006. (in Chinese)

[8] Tomescn I. 組合學引論[M]. 北京:高等教育出版社, 1985.

Tomescn I. Introduction to Combinatorics [M]. Beijing:Higher Education Press, 1985. (in Chinese)

[9] 徐壽椿. 圖說四色問題[M]. 北京:北京大學出版社, 2008．

XU Shou-chun. Four Color Problem by Graph [M]. Beijing:Peking University Press, 2008.

(第56卷卷終)

Graph theory of four-color— Existence and searching method of solution for four-color problem

YANG Ming-sheng*

( Research Institute of Engineering Mechanics, Dalian University of Technology, Dalian 116024, China )

Another new system of graph theory is established directly from four-color problem. By defining the region, boundary line, node, etc., after breaking down the complicated map into several connected single-layer subgraphs and simplifying them, three fundamental theorems of this system are obtained. And using chain, the solution existence and searching method of four-color problem related to any map with limited regions are given.

graph theory; four-color problem; region; boundary line; node; chain

2016-05-15；

2016-07-26．

楊名生*(1938-)，男，教授.

1000-8608(2016)06-0662-09

O157.6

A

10.7511/dllgxb201606016