一種平面圖色數(shù)的計算方法 (1)

《一種平面圖色數(shù)的計算方法 (1)》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、一種平面圖色數(shù)的計算方法（蔣友皎廣西玉林市537000）0引言任何一個連通平面圖都是五色圖。但是后來在平面圖上經(jīng)過多次試驗，沒有找到一種平面圖一定要用5種顏色的。在一百多年前，有人猜測只要用4種顏色就夠了，這就是世界上著名的4色猜測問題。這個猜測一經(jīng)提出，迷住了許多數(shù)學家，但是誰都無法用數(shù)學的方法證明它。直到1976年，Appel和Haken兩人宣布了四色理論的證明方法。他們用大型電子計算機分析了2000多種圖包括幾百萬種情況，花了大量的機器時間，終于證明了這個問題，[1]從而解決了一百多年來引人關注

2、的難題。Sincetheprovingofthetheorem,efficientalgorithmshavebeenfoundfor4-coloringmaps2requiringonlyO(n)time,wherenisthenumberofvertices.In1996,NeilRobertson,DanielP.Sanders,PaulSeymour,andRobinThomascreatedaquadratictimealgorithm,improvingona[2][3][11]quart

3、icalgorithmbasedonAppelandHaken’sproof.ThisnewproofissimilartoAppelandHaken'sbutmoreefficientbecauseitreducedthecomplexityoftheproblemandrequiredcheckingonly633reducibleconfigurations.Boththeunavoidabilityandreducibilitypartsofthis[4][11]newproofmustbee

4、xecutedbycomputerandareimpracticaltocheckbyhand.In2001the[5][11]sameauthorsannouncedanalternativeproof,byprovingthesnarktheorem.In2005BenjaminWernerandGeorgesGonthierformalizedaproofofthetheoreminsidetheCoqproofassistant.Thisremovedtheneedtotrustthevari

5、ouscomputerprogramsusedtoverify[6][11]particularcases;itisonlynecessarytotrusttheCoqkernel.顯然這不是純理論上的嚴格證明，在計算機的輔助工作下四色定理的證明完成了，但是是否存在不需要借助計算機的純數(shù)學方法的證明呢？本文將運用方程組計算連通平面圖的色數(shù)，對連通平面圖的色數(shù)作出判定。1基本性質定義1一個無向圖是一個有序的二元組,記作G，其中（1）V≠稱為頂點集，其元素稱為頂點或結點。[7]（2）E稱為邊集，

6、它是無序積V&V的多重子集，其元素稱為無向邊，簡稱邊。定義2設G=為無向圖，ek=(vi，vj)∈E，則稱vi，vj為ek的端點，ek與vi或ek與vj是彼此相關聯(lián)的。若vi≠vj，則稱ek與vi或ek與vj的關聯(lián)次數(shù)為1，若vi=vj，則稱ek與vi的關聯(lián)次數(shù)為2，并稱ek為環(huán)。任意的vl∈V，若vl≠vi且vl≠vj，則稱ek與vl的關聯(lián)[7]次數(shù)為0。在圖的定義中，用G表示無向圖，D表示有向圖，但有時用G泛指圖(無向的或有向的)，可是D只能表示有向圖。另外，為方便起見，有時用V(G)，

7、E(G)分別表示G的頂點集和邊[7]集，若

8、V(G)

9、=n,則稱G為n階圖，對有向圖可做類似規(guī)定。在圖G中，若邊集E(G)=,則稱G為零圖，此時，又若G為n階圖，則稱G為n[7]階零圖，記作Nn，特別地，稱N1為平凡圖。在圖的定義中規(guī)定頂點集V為非空集，但在圖的運算中可能產(chǎn)生頂點集為空集的運算結[7]果，為此規(guī)定定點集為空集的圖為空圖，并將空圖記為。[7]無論在無向圖中還是在有向圖中，無邊關聯(lián)的頂點均稱孤立點。定義3在無向圖中，關聯(lián)一對頂點的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)

10、。在有向圖中，關聯(lián)一對頂點的有向邊如果多于1條，并且這些邊的始點和終點相同(也就是它們的方向相同)，則稱這些邊為平行邊。含平行邊的圖稱為多重圖，[7]既不含平行邊也不含環(huán)的圖稱為簡單圖。定義4設G=為一無向圖，v∈V，稱v作為邊的端點次數(shù)之和為v的度數(shù)，[7]簡稱為度，記做dG(v)，在不發(fā)生混淆時，簡記為d(v)。定義5設G=為一平面圖，面W由w條邊組成，稱w作為邊的面次數(shù)之和為W的度數(shù)，簡稱為度，記做dG(w)，在不發(fā)生混淆時，簡