“四色定理”又稱“四色猜想”，一個多世紀以來，激發(fā)了大量的數(shù)學專家和愛好者的研究[1][2]。眾多數(shù)學家花了100多年的時間要證明這個聽起來十分簡單的猜想，結果均以失敗告終。1890年，P。J。Heawood指出了Kempe證明中的錯誤，采用Kempe的“色交換技術”，證明了“五色定理”。

1976年7月，美國伊利諾大學的兩位數(shù)學家Kenneth Appel和Wolfgang Hanken用計算機證明了“四色猜想”成立。借助于機器證明“四色定理”是現(xiàn)代計算機應用所取得的一個重大的成就，但由于問題的簡單和證明的復雜，使得此證明顯得不十分理想。

本文分析了Heawood給出的反例，指出了直接采用Kempe換色方法存在矛盾導致Kempe換色失敗。通過對Heawood反例的第二次換色條件的分析，進一步利用Kempe換色方法，證明了“四色猜想”的成立。

2 Kempe證明及Heawood反例

Kempe通過引入不可免完備集F ={O,P,Q,R}(圖1)，采用色交換，“證明”最小圖G不存在來證明四色定理。

但是在證明G不含構型R時，由Heawood給出了反例(圖2)[2]，從而發(fā)現(xiàn)了Kempe證明中的漏洞。

v

v

P

v

v

Q

O

圖1 Kempe證明中的不可完備集

例如，設NG(v)={v1,v2,v3,v4,v5},π=(Vb,Vr,Vy,Vg)是G-v的一種4染色，圖中字母b,r, y,g表示四種不同的顏色。

v2和v4在Gb,g中是連通的，v2和v5在Gb,y中也是連通的。因此無論交換Gb,g中的顏色還是交換Gb,y中的顏色，都不能空出一種顏色來給v。v1和v4在Gr,g中不連通，因此可以考慮交換Gr,g含v1分支中的顏色(圖中括號中的顏色)。但π(v3)=r，因此不能空出顏色來染點v。

又因v3和v5在Gr,y中不連通，所以考慮交換Gr,y含v3分支中的顏色。于是v3被染上y。顏色r雖被空出來了，但此時相鄰兩頂點6和7都被換成顏色r。由此說明Kempe的證明中包含了一個漏洞。

接下來本文首先分析了Kempe對G不含構型Q的證明，然后分析Heawood反例，最后給出新的證明。

3 Kempe對G不含構型Q

考察圖3，如果頂點v1,v2,v3 ,v4只用了少于四種的染色，顯然把第四種顏色對v染色。假若不然，那么v1,v2,v3 ,v4使用了四種顏色，設為b,r, y,g。如果v1和v3在Gr,y中不是連通的，那么可以考慮交換Gr,y分支中的顏色(含v1分支或含v3分支都可以)，從而空出一種顏色對v染色。

否則，那么Gr,y+v構成一個圈，從而v2,v4在Gb,g中不連通，可以換色，從而空出一種顏色對v染色。

由上述證明，我們可以得到如下引理：

引理1：如果圖G的三個頂點v1,v3 ,v4采用三種顏色染色且在各自的兩色導出子圖中都連通，從而其中必存在一個頂點，與染第四種顏色的第四個頂點在其兩色導出子圖中不連通。

這是證明G不含構型Q的本質(zhì)。

6

圖2 Heawood反例

v4(g)

v1(r)

v2(b)

v3(y)

v

圖3

4 Heawood反例分析

在Heawood反例中，v2和v4在Gb,g中是連通的，v2和v5在Gb,y中也是連通的，所以不能對它們進行換色。

根據(jù)引理一，顯然v1,v3必分別與其中的一個頂點在其兩色導出子圖不連通，即v1,v4和v3, v5在Gr,g和Gr,y中不連通。Kempe的做法是分別對其換色，從而得到“證明”。而Heawood反例指出，分別換色后可能得到矛盾的結果。那么其原因在哪兒呢？

通過考察圖2，我們發(fā)現(xiàn)，在經(jīng)過第一步換色之后，其實是得到了一個新的圖，只不過某些頂點的顏色發(fā)生了變化，但仍然保持為4染色。

這個恰恰是Kempe證明中沒有考慮的問題！Kempe沒有考察新圖，想當然的仍然采用原圖的辦法進行換色。Heawood抓住這一點指出了其中的問題。如圖所示，第一換色完成后，新得到的圖中，v3和v5在Gr,y中的關系發(fā)生了變化，已經(jīng)從不連通變?yōu)檫B通了。

顯然，如果仍舊按照原圖換色，必將得到矛盾。

因此，有必要考察第一次換色完成后新的圖的性質(zhì)，從而得到如下證明。

5 四色證明

假設圖G含有構型R，則染色方式有兩種情況，如圖4(a)和4(b)所示，字母b,r, y,g表示四種不同的顏色。

如果在v2,v4,v5三個頂點中存在兩個頂點在其兩色導出子圖中不連通，則可以通過換色，空出一種顏色給v。否則v2,v4,v5在其兩兩兩色導出子圖都連通。根據(jù)引理1，對于v1和v3，在v2,v4,v5中分別存在一個頂點，在其各自的兩色導出子圖中不連通。

如果它們對應于同一個頂點，那么只能如圖4(a)所示，此頂點為v4。顯然可以同時實施換色(對v1和v3所在分支。如果v1和v3連通，則一次換色就可成功)，空出g顏色給v。

否則，v1和v3分別對應不同的頂點，那么只能如圖4(b) 所示，其中v1和v4在Gr,g中不連通，v3和v5在Gr,y中不連通。

第一步操作，交換Gr,g含v1分支中的顏色，得到新的圖G’。考察圖G’，如果v3和v5在G’r,y中仍舊不連通，那么可以交換G’r,y含v3分支中的顏色。這樣空出顏色r給v。否則，v3和v5在G’r,y中變成連通的了，這個時候就不能再進行換色(這正是Heawood反例的情況)。

但是現(xiàn)在，考察G’r,y+v，現(xiàn)在已經(jīng)是一個圈了，對于頂點v2,v4，已經(jīng)從Gb,y中連通變成了G’b,y中的不連通。顯然對于G’b,y可以進行換色(對含v2或v4的分支都可以)，從而空出一種顏色染v。因此得到圖G可染色，從而不存在構型R。四色定理得證。

現(xiàn)在我們分析在什么樣的情況下會導致v3和v5在G’r,y中的關系發(fā)生了變化。第一步換色操作，把Gr,g含v1分支中的r和g顏色進行了交換，導致v3和v5在G’r,y中連通。顯然子圖G’r,y沒有顏色g的頂點，因此必有一個r色頂點是從換色操作得到的。

又由于與r色頂點相鄰的頂點顏色只能是y，由此推斷在原圖G中，在子圖Gr,g的v1分支中必存在一個g色頂點，在其相鄰頂點中存在兩個y色頂點，其中一個y色頂點在Gr,y的含v3分支中，另一個y色頂點在Gr,y的含v5分支中。對于Heawood反例圖2來說，這個頂點就是7頂點。

v4(g)

v1(r)

V5(y)

v

v2(r)

v3(b)

v4(g)

v1(r)

V5(y)

v

v2(b)

v3(r)

6 結論

通過上面的分析，我們可以毫無疑問的說，“四色定理”是成立的。

而問題的關鍵則是對Kempe換色方法的進一步應用。

。

全部

總結

以上是生活随笔為你收集整理的用计算机证明有限,四色定理-四色定理已利用计算机证明,但能否给出简洁的证明方法吗 爱问知识人...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。