N元環(huán)三角形拼接圖三色定理的證明

廖榮寶 朱云 柴蘭蘭

【摘要】為了給四色定理問題的研究提供啟示，本文對(duì)N元環(huán)經(jīng)過三角形劃分后所得平面三角形拼接圖的著色問題進(jìn)行了研究，本文結(jié)論可歸納如下.（1）任意N元環(huán)劃分所得三角形拼接圖均含有N-2個(gè)三角形和N-3條非環(huán)上邊.（2）任意N元環(huán)劃分所得三角形拼接圖中，至少存在兩個(gè)三角形由連續(xù)三個(gè)環(huán)上點(diǎn)構(gòu)成.（3）任意N元環(huán)劃分所得三角形拼接圖都符合三色定理.

【關(guān)鍵詞】四色定理;圖論;平面圖;數(shù)學(xué)歸納法

【中圖分類號(hào)】O157 AMS（2000）主題分類：05C15

【基金項(xiàng)目】阜陽(yáng)師范學(xué)院自然科學(xué)項(xiàng)目（2013FSKJ05ZD， 2014FSKJ01ZD）

一、引 言

四色定理是圖論中未經(jīng)證明的一個(gè)問題，這一看似簡(jiǎn)單的問題被認(rèn)為是近代三大數(shù)學(xué)難題之一.這一定理指出，對(duì)于任何地圖，采用四種顏色對(duì)各個(gè)國(guó)家進(jìn)行著色即可保證任何兩個(gè)相鄰國(guó)家具有不同的顏色，這一問題于1852年由英國(guó)制圖員Guthrie提出，距今已有160余年時(shí)間.1879年Kempe最早提出被稱作Kempe鏈的“換色法”對(duì)于這一假設(shè)進(jìn)行了證明.但1890年，Heawood發(fā)現(xiàn)Kempe的證明過程中存在錯(cuò)誤，指出Kempe實(shí)際證明了任何地圖均可實(shí)現(xiàn)五著色的命題.1976年，美國(guó)數(shù)學(xué)家Appel、Haken和Kock曾采用計(jì)算機(jī)經(jīng)過一百多億次邏輯判斷方法證明了四色定理;但直到21世紀(jì)，純粹的數(shù)學(xué)證明方法依然沒能獲得.

為了給四著色問題的研究提供啟示，本文將進(jìn)行一類由N個(gè)頂點(diǎn)形成的多邊形劃分為三角形拼接圖后所得圖形著色問題的研究.本文將按如下順序進(jìn)行論述.首先介紹地圖著色問題的簡(jiǎn)化處理以及文獻(xiàn)中五色定理的染色方法，然后討論N元環(huán)三角形拼接圖的性質(zhì)，最后證明N元環(huán)三角形拼接圖符合三色定理.

二、五色定理簡(jiǎn)介

文獻(xiàn)中五色定理的介紹很多，但由于多數(shù)文獻(xiàn)采用圖論專業(yè)術(shù)語(yǔ)進(jìn)行描述，所以無(wú)法達(dá)到淺顯易懂的效果.為此，本文作者打算用通俗語(yǔ)言對(duì)五色定理進(jìn)行重新描述，以盡可能地達(dá)到無(wú)論專業(yè)數(shù)學(xué)工作者或業(yè)余數(shù)學(xué)愛好者均能看懂的效果.

1.地圖著色問題的簡(jiǎn)化處理

一般在研究地圖著色問題中可先對(duì)地圖進(jìn)行“點(diǎn)面翻轉(zhuǎn)”操作，這一操作可具體描述如下.考慮一類簡(jiǎn)單地圖，地圖中只存在三個(gè)國(guó)家交界點(diǎn)的情況且每個(gè)國(guó)家周圍至少有三個(gè)鄰國(guó).此時(shí)，每個(gè)國(guó)家都可看作多邊形“面”，每個(gè)三國(guó)交界點(diǎn)即為一個(gè)“點(diǎn)”;整個(gè)地圖有數(shù)個(gè)多邊形“面”和數(shù)個(gè)三國(guó)交界“點(diǎn)”構(gòu)成.現(xiàn)把原地圖中每個(gè)多邊形“面”變成一個(gè)“點(diǎn)”同時(shí)把每個(gè)三國(guó)交界“點(diǎn)”看成一個(gè)“面”.如果兩國(guó)交界，則用一條線把代表兩個(gè)國(guó)家的點(diǎn)連接起來(lái).此時(shí)原地圖中所有三國(guó)交界點(diǎn)均會(huì)變成三角形面，原地圖變成由三角形面拼接而成的多面體圖形.為了簡(jiǎn)便起見，本文把這種經(jīng)“點(diǎn)面翻轉(zhuǎn)”后獲得的由三角形拼接而成的多面體叫做“TH體”（其中T取自triangle，H取自hedron）.原地圖的四著色問題變?yōu)檠芯縏H體的四著色問題（下文中字母代表國(guó)家，面代表多國(guó)交界點(diǎn)）.

圖1 四國(guó)交界點(diǎn)示例 以上TH體中只有三個(gè)國(guó)家交界的情形，如果實(shí)際地圖中存在四個(gè)或四個(gè)以上國(guó)家共享一個(gè)交界點(diǎn)的非TH體情形（如美國(guó)地圖有四州共用交界點(diǎn)情形）或其他如國(guó)中之國(guó)以及一個(gè)國(guó)家只和兩個(gè)國(guó)家交界的非TH體情形等，均可轉(zhuǎn)變?yōu)門H體.例如一個(gè)國(guó)家若只與兩個(gè)國(guó)家交界，則可以先去除這個(gè)國(guó)家，待完成著色問題后，再將這個(gè)國(guó)家增添到原來(lái)的位置，染上與周邊兩個(gè)國(guó)家不同的顏色即可.再如，存在四國(guó)交界點(diǎn)的情形也可轉(zhuǎn)變?yōu)門H體.如圖1所示（圖1中非四國(guó)交界區(qū)未畫出），圖1（a）中A，B，C，D四點(diǎn)代表四個(gè)國(guó)家，四邊形面ABCD代表四國(guó)交界點(diǎn).此時(shí)圖1（a）不屬于TH體.但若連接圖1（a）中AC兩點(diǎn)，即可將圖1（a）變?yōu)槿鐖D1（b）所示的TH體.若圖1（b）符合四色定理，則斷開AC連線后，所得圖形必然符合四色定理.也就是說，非TH體的著色問題均可通過TH體的著色問題完成.

2.五色定理的相關(guān)介紹

五色定理可用數(shù)學(xué)歸納法證明;即已知四個(gè)國(guó)家構(gòu)成的地圖符合五色定理，現(xiàn)假設(shè)N個(gè)國(guó)家構(gòu)成的地圖符合五色定理，那么若能在此基礎(chǔ)上證明N+1個(gè)國(guó)家構(gòu)成的地圖符合五色定理，則命題成立.現(xiàn)以TH體為地圖基本模型描述五色定理的證明過程.

我們先來(lái)考察TH體的相關(guān)性質(zhì).TH體是一種多面體，依據(jù)多面體歐拉公式，頂點(diǎn)數(shù)（N）、面數(shù)（F）、邊數(shù)（E）符合式（1）.TH體中每條邊被兩個(gè)面共享，每個(gè)面均由三條邊構(gòu)成，所以有式（2）成立，且由式（1）和式（2）可得式（3）.假設(shè)TH體中每個(gè)點(diǎn)均與其他6個(gè)或6個(gè)以上點(diǎn)相連，考慮到每條邊被兩個(gè)頂點(diǎn)共用，可知TH體的邊數(shù)E與頂點(diǎn)數(shù)N關(guān)系符合式（4）.由于式（4）與式（3）矛盾，可知以上假設(shè)不成立.即任意TH體中至少有一個(gè)頂點(diǎn)只與5個(gè)或5個(gè)以下其他頂點(diǎn)相連.

N+F=E+2.

（1）

2E=3F.

（2）

E=3N-6.

（3）

E≥3N.

（4）

因此，對(duì)于一個(gè)N+1頂點(diǎn)的TH體，必有一個(gè)頂點(diǎn)只與5個(gè)或5個(gè)以下其他頂點(diǎn)連線.若此點(diǎn)與其他3個(gè)頂點(diǎn)相連，則可去除此點(diǎn)以及由此點(diǎn)引出的三條連線，獲得一個(gè)N頂點(diǎn)的TH體.依據(jù)假設(shè)，此N頂點(diǎn)TH體可進(jìn)行五著色.待著色完成后，再把剛?cè)コ倪@個(gè)頂點(diǎn)添加到N頂點(diǎn)TH體原位置上并染上與周圍三點(diǎn)不同的顏色，即可完成N+1頂點(diǎn)TH體的五著色過程.若N+1頂點(diǎn)TH體中有一點(diǎn)與其他四點(diǎn)相連，則去除此點(diǎn)后將產(chǎn)生一個(gè)四邊形，把此四邊形劃分為兩個(gè)三角形后可獲得一個(gè)N頂點(diǎn)TH體.依據(jù)假設(shè) N頂點(diǎn)TH體可五著色.待著色完成后將去除的點(diǎn)添加到N頂點(diǎn)TH體原位置上并染上與周圍四點(diǎn)不同的顏色，即可完成N+1頂點(diǎn)TH體的五著色過程.若N+1頂點(diǎn)TH體中有一點(diǎn)與其他五點(diǎn)相連，如圖2（a）中A點(diǎn)，則需檢查B點(diǎn)和D點(diǎn)間有無(wú)連線，分別考察B和D有無(wú)連線兩種情況.

圖2 A點(diǎn)與周圍五點(diǎn)相連情況 若B和D有連線，則存在三角形面ABD（此三角形面不屬于原N+1頂點(diǎn)TH體的外表面），沿著ABD所在的面將TH體切割為左邊和右邊共兩個(gè)共享面ABD的TH體;這兩個(gè)TH體的頂點(diǎn)數(shù)均小于或等于N，所以這兩個(gè)TH體均可五著色.假設(shè)用Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ五種顏色對(duì)左邊TH體著色，并把A，B，D分別染上Ⅰ、Ⅱ、Ⅲ三種顏色.再假設(shè)對(duì)右邊TH體采用（1）、（2）、（3）、（4）、（5）五種顏色進(jìn)行著色，把A，B，D分別染上（1）、（2）、（3）三種顏色.然后用一組新的顏色1、2、3、4、5對(duì)以上兩個(gè)TH體進(jìn)行換色操作.用1取代兩TH體中的Ⅰ和（1），用2取代兩TH體中的Ⅱ和（2），用3取代兩TH體中的Ⅲ和（3），用4取代以上兩TH體中的Ⅳ和（4），用5取代兩TH體中的Ⅴ和（5）.則換色后兩個(gè)TH體中A，B，D三點(diǎn)對(duì)應(yīng)顏色均為1，2，3.再沿著原切割面ABD把兩個(gè)TH體對(duì)接起來(lái)即得一個(gè)符合五色定理的N+1頂點(diǎn)TH體.

若B和D無(wú)連線，則去除A點(diǎn)，并把B和D融為一點(diǎn)，如圖2（b）所示.此時(shí)N+1頂點(diǎn)TH體變?yōu)镹頂點(diǎn)TH體，依據(jù)假設(shè)，任何N頂點(diǎn)TH體均可五著色.待圖2（b）對(duì)應(yīng)的N頂點(diǎn)TH體完成五著色后，將去除的A點(diǎn)恢復(fù)并染上與周圍四點(diǎn)不同的顏色即可完成 N+1頂點(diǎn)TH體的五著色過程.至此，我們完成了任意N頂點(diǎn)TH體的五著色證明.

三、N元平面TP圖的著色問題

設(shè)有N個(gè)點(diǎn)兩兩相連構(gòu)成一個(gè)平面N元環(huán).現(xiàn)對(duì)平面N元環(huán)中的任意兩點(diǎn)進(jìn)行兩兩相連（要求連線過程中保持任意兩條連線不相交）對(duì)N元環(huán)進(jìn)行切割劃分，直至原N元環(huán)內(nèi)沒有四邊形或四條邊以上的多邊形為止，此時(shí)稱獲得的平面圖叫“N元平面TP圖”（其中T取自triangle，P取自polygon）.例如，圖3即為N=11和N=12兩個(gè)N元平面TP圖的結(jié)構(gòu)示例.接下來(lái)我們來(lái)研究N元平面TP圖的性質(zhì).

圖3 N=11和N=12的兩個(gè)TP圖 1.N元平面TP圖的結(jié)構(gòu)

定理1：N元平面TP圖中有N-2個(gè)三角形和N-3條環(huán)內(nèi)邊.

證明：N元平面TP圖有N條環(huán)上邊;設(shè)圖中有K條環(huán)內(nèi)邊和F個(gè)三角形.因?yàn)槊織l環(huán)內(nèi)邊被用來(lái)構(gòu)建兩個(gè)三角形而每條環(huán)上邊只被用來(lái)構(gòu)建一個(gè)三角形，所以可得邊數(shù)與三角形數(shù)的關(guān)系式（5）.

2K+N3=F.

（5）

對(duì)于一個(gè)N元環(huán)，在劃分為TP圖過程中內(nèi)角和不變.所以F個(gè)三角形的內(nèi)角和等于原N元環(huán)的內(nèi)角和，由此得出式（6）.顯然F=N-2，進(jìn)而可得K=N-3.即N元平面TP圖中有N-2個(gè)三角形和N-3條環(huán)內(nèi)邊，證畢.

180F=180（N-2）.

（6）

定理2：N（N>3）元平面TP圖中，至少有兩個(gè)三角形為原N（N>3）元環(huán)上緊鄰三點(diǎn)構(gòu)成的三角形.

證明：N元平面TP圖可視為由N-2個(gè)三角形拼接而成，且此時(shí)圖中有N-3條環(huán)內(nèi)邊和N條環(huán)上邊.顯然，當(dāng)N大于3時(shí)N元環(huán)上任何連續(xù)三條邊不能形成三角形.所以N元平面TP圖中的任何三角形，不可能擁有三條環(huán)上邊，即N元TP圖中任意三角形最多擁有兩條環(huán)上邊.另外，在N元TP圖中，任意一條環(huán)上邊不可能參與構(gòu)建兩個(gè)或兩個(gè)以上的三角形.現(xiàn)N頂點(diǎn)TP圖中有N-2個(gè)三角形，有N條環(huán)上邊.為了盡量少地出現(xiàn)一個(gè)三角形擁有兩條環(huán)上邊的情況，可讓每個(gè)三角形均擁有一條環(huán)上邊;此時(shí)N-2個(gè)三角形共用去N-2條環(huán)上邊，但還剩下兩條環(huán)上邊.由于任何三角形不能擁有三條環(huán)上邊，所以這兩條環(huán)上邊只能分別分配到兩個(gè)三角形中去.這就造成N（N>3）元TP圖中至少有兩個(gè)三角形擁有兩條環(huán)上邊.只有環(huán)上緊鄰三點(diǎn)才可構(gòu)成屬于同一個(gè)三角形的兩條環(huán)上邊，所以至少有兩個(gè)三角形為N（N>3）元環(huán)上緊鄰三點(diǎn)構(gòu)成，證畢.

若把某個(gè)擁有兩條環(huán)上邊的三角形從N頂點(diǎn)TP圖中切除，則可得一個(gè)N-1元TP圖，即為這個(gè)被切除的擁有兩個(gè)環(huán)上邊的三角形可看作外接在N-1元TP圖上;我們把這種擁有兩個(gè)環(huán)上邊的三角形稱為“外接三角形”.

2.N元平面TP圖的三著色證明

圖4 當(dāng)N=3，4，5時(shí)TP圖的三色方案 當(dāng)N=3，4，5時(shí)，若不考慮TP圖中各個(gè)點(diǎn)的差別以及各條邊長(zhǎng)的差別，則所得TP圖均只有如圖4所示的一種結(jié)構(gòu)花樣（其他結(jié)構(gòu)花樣可由圖4經(jīng)旋轉(zhuǎn)獲得，不能獨(dú)立存在）.如圖4所示（圖中1，2，3表示三種顏色），N=3，4，5時(shí)對(duì)應(yīng)TP圖均可三著色.

定理3：任何N元平面TP圖都可三著色.

證明：現(xiàn)采用數(shù)學(xué)歸納法證明定理3，假設(shè)N元TP圖可以實(shí)現(xiàn)三著色，再證明N+1元TP圖也可三著色.定理2指出，N+1（N>3）元平面TP圖中至少有兩個(gè)外接三角形，現(xiàn)把其中的一個(gè)外接三角形標(biāo)記為ABC;其中AB和BC均為環(huán)上邊，AC為非環(huán)上邊.則沿著AC邊切去外接三角形ABC，可獲得一個(gè)N元平面TP圖.即此N+1元平面TP圖可以看作由一個(gè)N元平面TP圖和一個(gè)三角形拼接而成.顯然，切去的三角形是可三著色的，設(shè)其三種顏色為Ⅰ、Ⅱ、Ⅲ.依據(jù)數(shù)學(xué)歸納法假設(shè)，N元平面TP圖可三著色.現(xiàn)對(duì)切割后產(chǎn)生的N元TP圖進(jìn)行三著色，設(shè)對(duì)應(yīng)三種顏色為x、y、z.假設(shè)對(duì)切割后產(chǎn)生的N元TP圖和三角形ABC分別進(jìn)行三著色.設(shè)N元TP圖中點(diǎn)A和點(diǎn)C分別著色為x和y（其他點(diǎn)著色暫不考慮）;三角形中A，B，C三點(diǎn)分別著色為Ⅰ、Ⅱ、Ⅲ.現(xiàn)用另外三種顏色1，2，3取代N元TP圖和三角形ABC的顏色.取代操作規(guī)定為：用1取代x和Ⅰ;用2取代y和Ⅲ;用3取代z和Ⅱ.經(jīng)過顏色取代后，N元TP圖和三角形ABC中點(diǎn)A均為顏色1，點(diǎn)C均為顏色2;現(xiàn)把兩圖沿切割邊AC拼接起來(lái)，則所得N+1元TP圖只具有三種顏色1，2，3，即為N+1元TP圖可三著色.結(jié)合圖4中N=3，4，5時(shí)可三著色的事實(shí)，可知任意N元TP圖均可三著色，證畢.

四、結(jié) 論

本文研究了由N元環(huán)經(jīng)連線劃分所得N元平面TP圖的性質(zhì).得出N元平面TP圖中有N-2個(gè)三角形和N-3條環(huán)內(nèi)邊;且所得三角形中至少有兩個(gè)三角形為N元環(huán)上緊鄰三點(diǎn)構(gòu)成.并在此基礎(chǔ)上證明了N元平面TP圖是可三著色的.本文結(jié)論對(duì)四色定理的證明有一定的啟示意義.在接下來(lái)的工作中，我們將在此基礎(chǔ)上逐步展開關(guān)于四色定理的后續(xù)研究工作.

【參考文獻(xiàn)】

[1]王利民，張利明，呂國(guó)：使用四色定理求解圖形著色的數(shù)學(xué)模型[J].河北建筑工程學(xué)院學(xué)報(bào)，2006（24）：102～103.

[2]王禮萍，王慧蓉：平面圖四色問題的一個(gè)必要定理[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào) 2003（19）：29～30.

[3]Kempe，A.B.：On the geographical problem of the four colours[J].American journal of mathematics 1879（2）：193～200.

[4]Kempe，A.：How to color a map with four colours without coloring adjacent districts the same color[J].Nature 1879（20）：275.

[5]Heawood，J.：On the fourcolor map problem[J].Quart.J.Pure Math 1898（29）：270～285.

[6]陳明，李剛：四色定理證明的探討[J].山東理工大學(xué)學(xué)報(bào)：自然科學(xué)版 2013（27）：10～12.

[7]Appel，K.，Haken，W.，Koch，J.：Every planar map is four colorable.Part II：Reducibility[J].Illinois Journal of Mathematics 1977（21）：491～567.

[8]謝力同，劉桂真.與四色定理等價(jià)的幾個(gè)命題[J].應(yīng)用數(shù)學(xué) 2000（13）：59～62.