楊 名 生

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

?

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

楊 名 生*

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

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

圖論；四色問題；區(qū)域；邊界線；結(jié)點(diǎn)；鏈路

0 引 言

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

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

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

1 預(yù)備知識[6]

1.1 約定和定義

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

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

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

四色問題不關(guān)心區(qū)域的形狀和面積大小，不關(guān)心邊界線的形狀和長短，不關(guān)心結(jié)點(diǎn)的具體位置，只關(guān)心區(qū)域之間的相鄰關(guān)系、結(jié)點(diǎn)間的邊界線連接關(guān)系等．

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

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

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

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

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

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

1.2 幾個定理

定理2(基本定理1) 設(shè)原始圖中區(qū)域數(shù)為r，結(jié)點(diǎn)數(shù)為n，邊界線數(shù)為b，當(dāng)r≥3時，如下關(guān)系成立：n(r)=2(r-2)，b(r)=3(r-2)．

證明 用數(shù)學(xué)歸納法證明此定理：

(1)當(dāng)r=3時，由于是原始圖，結(jié)點(diǎn)都是簡單的(見圖1)，應(yīng)有r=3，n=2，b=3，結(jié)論顯然成立．

圖1 r=3時的地圖

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

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

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

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

圖2 化為相應(yīng)子地圖的復(fù)雜地圖求解

證明 推論1給出證明．

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

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

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

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

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

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

單層地圖的所有結(jié)點(diǎn)都是簡單結(jié)點(diǎn)，所有相鄰都是一次相鄰的問題稱為簡單問題．

定理5(相鄰定理)r個區(qū)域簡單問題，其相鄰關(guān)系矩陣中非元總數(shù)：

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

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

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

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

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

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

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

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

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

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

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

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

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

引用符號Bm，表示邊界線數(shù)是m的一個區(qū)域．

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

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

圖3 r=12時的地圖

2 鏈 路

2.1 鏈路的規(guī)定

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

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

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

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

B5點(diǎn)只能做端點(diǎn)和過點(diǎn)，不能做孤立點(diǎn)和分支點(diǎn)；對于Bm點(diǎn)：當(dāng)m≥6時，可做端點(diǎn)、過點(diǎn)和分支點(diǎn)，當(dāng)m為偶數(shù)時，還可以做孤立點(diǎn)．

2.2 鏈路的基本要求

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

2.3 鏈路的幾種類型

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

2.4 鏈路的多樣性及產(chǎn)生多個四色解

若是再改變鏈路定義，著色方案雖然不變，卻可能產(chǎn)生一些新鏈路而形成新獨(dú)聯(lián)體，獨(dú)聯(lián)體的單獨(dú)或聯(lián)合變換，雖然不改變鏈路形狀，但確實(shí)改變了著色方案，……由此可見，想通過已確定的千變?nèi)f化的區(qū)域布局，來邏輯地推出四色解是不現(xiàn)實(shí)的，因?yàn)榇嬖诘慕饪赡芊浅６啵旅嬗?2塊五邊形和20塊六邊形區(qū)域構(gòu)造的老式足球?yàn)槔f明．

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

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

綜上所述，改變鏈路族的結(jié)構(gòu)、交換部分獨(dú)聯(lián)體雙色、兩種操作組合進(jìn)行，都能帶來環(huán)狀結(jié)構(gòu)的大量新四色解．就上述足球而言至少有32種不同的四色解．

2.5 鏈路定理

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

證明 從略．

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

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

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

2.6 基礎(chǔ)地圖的鏈路形式?jīng)Q定區(qū)域和節(jié)的數(shù)量關(guān)系

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

2.7 基礎(chǔ)地圖解的存在性

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

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

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

圖6 四色解存在性證明

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

2.8 基礎(chǔ)地圖的求解方法

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

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

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

圖7 無環(huán)路基礎(chǔ)地圖求四色解方法之例

圖8 有環(huán)路基礎(chǔ)地圖求四色解方法之例

3 地圖求四色解的步驟

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

步驟1 統(tǒng)一編號地圖區(qū)域．對地圖的所有區(qū)域進(jìn)行編號，保證每個區(qū)域的編號不缺失又是唯一的即可．

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

步驟3 簡單化處理地圖．當(dāng)?shù)貓D中有階數(shù)大于3的結(jié)點(diǎn)時，有許多種方法可將此結(jié)點(diǎn)“拉伸”以減少其階數(shù)，使所有結(jié)點(diǎn)的階都是3，從而使地圖簡單化．生成圖轉(zhuǎn)化為原始圖的方法很多，它的隨意性也影響四色解的結(jié)果．

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

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

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

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

4 結(jié) 語

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

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

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

[2] 邦迪 J A, 默締 U S R. 圖論及其應(yīng)用[M]. 吳望名,等譯. 北京:科學(xué)出版社, 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] 林 壽. 文明之路—數(shù)學(xué)史演講錄[M]. 北京:科學(xué)出版社, 2010.

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

[4] 張奠廟. 20世紀(jì)數(shù)學(xué)經(jīng)緯[M]. 上海:華東師范大學(xué)出版社, 2002.

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

[5] 前田渡,伊東正安. 現(xiàn)代圖論基礎(chǔ)[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. 現(xiàn)代幾何學(xué):方法與應(yīng)用[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. 組合學(xué)引論[M]. 北京:高等教育出版社, 1985.

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

[9] 徐壽椿. 圖說四色問題[M]. 北京:北京大學(xué)出版社, 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