四色定理是一個(gè)著名的數(shù)學(xué)定理，如果在平面上劃出一些鄰接的有限區(qū)域，那么可以用四種顏色來給這些區(qū)域染色，使得每?jī)蓚�(gè)鄰接區(qū)域染的顏色都不一樣。本文主要針對(duì)N元環(huán)三角形拼接圖三色定理的證明進(jìn)行了一些論述，文章是一篇江西教師論文發(fā)表范文。
　　【摘要】為了給四色定理問題的研究提供啟示，本文對(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)目】阜陽師范學(xué)院自然科學(xué)項(xiàng)目(2013FSKJ05ZD， 2014FSKJ01ZD)

　　一、引 言

　　四色定理是圖論中未經(jīng)證明的一個(gè)問題，這一看似簡(jiǎn)單的問題被認(rèn)為是近代三大數(shù)學(xué)難題之一.這一定理指出，對(duì)于任何地圖，采用四種顏色對(duì)各個(gè)國家進(jìn)行著色即可保證任何兩個(gè)相鄰國家具有不同的顏色，這一問題于1852年由英國制圖員Guthrie提出，距今已有160余年時(shí)間.1879年Kempe最早提出被稱作Kempe鏈的“換色法”對(duì)于這一假設(shè)進(jìn)行了證明.但1890年，Heawood發(fā)現(xiàn)Kempe的證明過程中存在錯(cuò)誤，指出Kempe實(shí)際證明了任何地圖均可實(shí)現(xiàn)五著色的命題.1976年，美國數(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ù)語進(jìn)行描述，所以無法達(dá)到淺顯易懂的效果.為此，本文作者打算用通俗語言對(duì)五色定理進(jìn)行重新描述，以盡可能地達(dá)到無論專業(yè)數(shù)學(xué)工作者或業(yè)余數(shù)學(xué)愛好者均能看懂的效果.

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

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

　　圖1 四國交界點(diǎn)示例 以上TH體中只有三個(gè)國家交界的情形，如果實(shí)際地圖中存在四個(gè)或四個(gè)以上國家共享一個(gè)交界點(diǎn)的非TH體情形(如美國地圖有四州共用交界點(diǎn)情形)或其他如國中之國以及一個(gè)國家只和兩個(gè)國家交界的非TH體情形等，均可轉(zhuǎn)變?yōu)門H體.例如一個(gè)國家若只與兩個(gè)國家交界，則可以先去除這個(gè)國家，待完成著色問題后，再將這個(gè)國家增添到原來的位置，染上與周邊兩個(gè)國家不同的顏色即可.再如，存在四國交界點(diǎn)的情形也可轉(zhuǎn)變?yōu)門H體.如圖1所示(圖1中非四國交界區(qū)未畫出)，圖1(a)中A，B，C，D四點(diǎn)代表四個(gè)國家，四邊形面ABCD代表四國交界點(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è)國家構(gòu)成的地圖符合五色定理，現(xiàn)假設(shè)N個(gè)國家構(gòu)成的地圖符合五色定理，那么若能在此基礎(chǔ)上證明N+1個(gè)國家構(gòu)成的地圖符合五色定理，則命題成立.現(xiàn)以TH體為地圖基本模型描述五色定理的證明過程.

　　我們先來考察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)間有無連線，分別考察B和D有無連線兩種情況. 　　圖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ì)接起來即得一個(gè)符合五色定理的N+1頂點(diǎn)TH體.

　　若B和D無連線，則去除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)示例.接下來我們來研究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)邊被用來構(gòu)建兩個(gè)三角形而每條環(huán)上邊只被用來構(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拼接起來，則所得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ì)四色定理的證明有一定的啟示意義.在接下來的工作中，我們將在此基礎(chǔ)上逐步展開關(guān)于四色定理的后續(xù)研究工作.

　　【參考文獻(xiàn)】

　　[1]王利民，張利明，呂國：使用四色定理求解圖形著色的數(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.
　　江西教育論文發(fā)表期刊推薦《江西教育》創(chuàng)刊于1950年，是江西省委教育工委、省教育廳的工作指導(dǎo)類刊物，刊物覆蓋全省各級(jí)教育行政主管部門、各級(jí)各類學(xué)校，是全省教育系統(tǒng)最具影響的刊物之一，被評(píng)為全國中文核心期刊、江西省一級(jí)期刊。

---

轉(zhuǎn)載請(qǐng)注明來自：http://www.jinnzone.com/gaodengjiaoyulw/56091.html