對(duì)四色地圖問(wèn)題的一個(gè)書面證明

1、對(duì)四色地圖問(wèn)題的一個(gè)書面證明 張 天 樹(shù) tianshu_摘 要兩個(gè)相鄰圖形的一處相鄰邊界只能是兩條相鄰的邊界線. 并讓我們把任意未著色的平面地圖的平面看成是由兩種平行且一一交互的直線段組成，且每一種的每一條線段也是由一一交互的兩種顏色點(diǎn)組成，于是，整個(gè)平面共有四種顏色點(diǎn). 在對(duì)平面地圖上的圖形著色以前，先要對(duì)它的圖形進(jìn)行分類和變換，首先依次把每個(gè)相鄰不到4個(gè)圖形的圖形、或相鄰不到4個(gè)圖形的一片圖形與至少有4個(gè)相鄰圖形的一個(gè)相鄰圖形合并，然后，從整體到部分地變換每片圖形的每一個(gè)的邊界封閉曲線成只有橫、豎線段組成的矩形框. 最后，根據(jù)矩形邊界線上某些特殊點(diǎn)的顏

2、色或與相鄰圖形不同的顏色對(duì)每個(gè)圖形著色. 關(guān)鍵詞平面地圖, 圖形，分類，四色，邊界封閉曲線，顏色點(diǎn)，拓?fù)渥儞Q，圖形包圍圈，矩形. 基本概念四色地圖問(wèn)題是說(shuō)，給任意一個(gè)平面或球面地圖上的每一個(gè)圖形染上一種顏色，并使相鄰兩個(gè)圖形被染上的顏色不同，那么，只要4種顏色就夠了.我們把球面地圖上的圖形看成是印在橡皮曲面上的圖形，只要在任意一個(gè)圖形中破開(kāi)一個(gè)孔，然后用力伸展球面成平面，那么，這個(gè)球面地圖就變成了一個(gè)平面地圖. 這個(gè)孔的邊緣就成了這個(gè)平面地圖的邊緣，但是，它不是圖形的一條邊界封閉線.顯然，被開(kāi)孔圖形的一條邊界封閉曲線在平面上向內(nèi)包圍了該地圖上除開(kāi)孔圖形本身和開(kāi)孔圖形其它邊界封閉曲線包圍的圖形外

3、的全部圖形，而這條邊界封閉曲線向外包圍它所在的開(kāi)孔圖形和這開(kāi)孔圖形其它邊界封閉曲線向內(nèi)包圍的圖形.因此，我們只需要證明來(lái)自任意球面地圖上的平面地圖上的全部圖形就行了. 因?yàn)閺那蛎娴貓D轉(zhuǎn)換來(lái)的平面地圖包含了每一種局部的平面地圖，于是我們只需要證明在存在各種可能情況下的整體平面地圖, 以下提到的平面地圖指的就是這樣的整體平面地圖，凡是提到的圖形指的都是在這種平面地圖上的圖形.就平面地圖而論，存在各式各樣形狀、各種不同相鄰關(guān)系的圖形.但是，不管怎樣，每個(gè)圖形至少有一條邊界封閉曲線.并且,每個(gè)圖形必須是連成一片，而不能分成至少兩個(gè)不相連接的部分.另外，任意一個(gè)平面地圖都必須由圖形填滿，而不能存在沒(méi)有圖

4、形的任何空隙.大家都知道：我們所說(shuō)的平面地圖的平面都是指的歐幾里德幾何平面.按照歐幾里德幾何對(duì)點(diǎn)和線的定義，即每個(gè)點(diǎn)是不可分的，線是由點(diǎn)組成，和每條線只有長(zhǎng)度而沒(méi)有寬度. 我們可把一條邊界封閉曲線的一部分稱為一段邊界線. 既然如此，任何兩個(gè)相鄰圖形不能共有平面上的若干點(diǎn)、一條或一段邊界封閉線. 那么，任意兩個(gè)相鄰圖形的一處連續(xù)的邊界，就只能是兩條相鄰的邊界線. 如果還未對(duì)一個(gè)平面地圖上的全部圖形著色，我們就稱這個(gè)平面地圖為一個(gè)未染色的平面地圖. 如果一個(gè)平面地圖上的全部圖形都被著上了色，但不是最后著色，盡管某些圖形的每一個(gè)由至少兩個(gè)原有圖形組成，理所當(dāng)然，我們稱這樣的平面地圖為一個(gè)臨時(shí)著色的平

5、面地圖. 讓我們把任意一個(gè)未著色的平面地圖的平面看作由一一交互的兩種縱向直線段組成，并且一種的每一條由一個(gè)黑色點(diǎn)交互一個(gè)白色點(diǎn)組成，另一種的每一條由一個(gè)紅色點(diǎn)交互一個(gè)天藍(lán)色點(diǎn)組成. 另一方面，這個(gè)平面也可看作是由一一交互的兩種橫向直線段組成，并且每一種的每一條橫向直線段也是由彼此交互的兩種顏色點(diǎn)組成.因此，無(wú)論從豎向看，還是從橫向去看，相鄰的兩條直線段的各兩種顏色點(diǎn)都完全不同. 請(qǐng)看第一圖: 第一圖在此，我們需要強(qiáng)調(diào)一點(diǎn)：這里所指的點(diǎn)是允許看得見(jiàn)和劃得出的，不管它是否有面積，但是它是不可分割的；當(dāng)然，由這樣的點(diǎn)組成的線也是能看得見(jiàn)和劃得出的，不管它是否有寬度. 如此地放大點(diǎn)和線，并不影響我們對(duì)

6、平面由點(diǎn)、線組成的理解，也不影響我們對(duì)本命題證明的嚴(yán)密性. 如果有人對(duì)這樣放大點(diǎn)和線提出質(zhì)疑，是否可以看作是為了證明該命題，而在平面上設(shè)計(jì)的一種模式呢？在這樣的平面上的任意一個(gè)圖形的一條邊界封閉曲線不是由三種顏色點(diǎn)、就是由四種顏色點(diǎn)組成. 對(duì)于由三種顏色點(diǎn)組成的任意一條邊界封閉曲線，不僅它是一個(gè)矩形的四條邊，而且它的四個(gè)直角的頂點(diǎn)共有一種顏色. 因?yàn)槿魏我粋€(gè)國(guó)家或地區(qū)的版圖都是在星球上，于是任何一個(gè)平面地圖都只能來(lái)源于球面地圖，因此，任何平面地圖都總有這樣一個(gè)圖形，它的一條邊界封閉曲線向內(nèi)包圍了除它本身和它本身其它的邊界封閉曲線包圍的圖形外的全部圖形. 在一個(gè)未染色的平面地圖上，無(wú)論對(duì)其圖形變

7、換與否，如果每一個(gè)圖形都相鄰至少四個(gè)圖形，并有由至多三個(gè)圖形向內(nèi)包圍的一片圖形，我們就把直接包圍這片圖形的、由至多三段邊界線組成的一條邊界封閉曲線稱為一條圖形包圍圈，簡(jiǎn)稱為一條包圍圈，并用符號(hào)“”表示, 另外符號(hào)“”表示至少有兩條包圍圈. 很多圖形沒(méi)有包圍圈，但有的圖形確有若干整個(gè)或和部分的包圍圈. 在任意一個(gè)平面地圖上，根據(jù)從外向內(nèi)包圍圈所在不同層次的順序，給全部包圍圈初步劃分等級(jí)，而根據(jù)拓?fù)渥儞Q的需要，它們的編號(hào)也是會(huì)改變的. 首先，把含有開(kāi)孔圖形的邊界封閉曲線編為第一或，把由每一條第一向內(nèi)直接包圍的或編為第二或把由第k或向內(nèi)直接包圍的或編為第(k+1)或，這里 k1.也就是說(shuō)，在一條第k

8、與這條第k內(nèi)的每一條第(k+1)之間沒(méi)有任何. 顯然，同一級(jí)的是并列的，不存在包圍與被包圍的關(guān)系.并且，同一級(jí)的，它們可以在同一條包圍圈中，也可以在不同的包圍圈中，另一方面，對(duì)于一條，它可為一個(gè)圖形的邊界封閉曲線，也可為不同圖形的邊界封閉曲線段的連接. 在一條被變換成一條由橫向和豎向線段組成的矩形封閉曲線后，或者它本來(lái)就是這樣的一條矩形封閉曲線，那么，用符號(hào)“1”表示它, 并且用符號(hào)“ 2 ”表示至少兩條矩形封閉曲線. 在一個(gè)未染色的平面地圖上，我們把任意一個(gè)圖形的一條矩形封閉邊界線看作是一個(gè)矩形的四條邊，并且，除第一2外，把這矩形封閉邊界線和它向內(nèi)包圍的平面作為一個(gè)矩形. 如果一個(gè)矩形的兩條

9、相對(duì)的邊共由兩種顏色點(diǎn)組成，那么，我們把這樣的一條橫邊稱為 “一條橫向的A 邊”或簡(jiǎn)稱為 “一條 TA 邊”; 又把這樣的一條豎邊稱為 “一條豎向的A 邊”或簡(jiǎn)稱為 “一條 LA 邊”. 如果一個(gè)矩形有兩條 TA 邊和兩條 LA 邊, 那么這個(gè)矩形被稱為一個(gè) A 矩形，參看第三圖 (1). 一個(gè) A 矩形的4個(gè)直角的頂點(diǎn)共有一種顏色.如果一個(gè)矩形的兩條相對(duì)的邊共由4種顏色點(diǎn)組成，那么，我們把這樣的一條橫邊稱為 “一條橫向的B 邊”或簡(jiǎn)稱為 “一條TB邊”; 又把這樣的一條豎邊稱為 “一條豎向的B邊”或簡(jiǎn)稱為 “一條 LB 邊”. 如果一個(gè)矩形有兩條 TB 邊和兩條 LB 邊, 那么這個(gè)矩形被稱

10、為一個(gè) BB 矩形，參看第三圖 (3). 一個(gè) BB 矩形的4個(gè)直角的頂點(diǎn)有4種顏色. 我們用符號(hào) “X ” 代替符號(hào) “T” 和符號(hào) “L”, 如果一個(gè)矩形有兩條 XA 邊和兩條XB 邊, 那么這個(gè)矩形被稱為一個(gè) B 矩形，參看第三圖 (2). 一個(gè)B 矩形的4個(gè)直角的頂點(diǎn)共有兩種顏色. 如果一整條 XB 邊只相鄰矩形的一條邊的整個(gè)或部分，那么，這整條XB 邊被稱為“一條單一的XB邊” ，或簡(jiǎn)稱為 “一條S 邊”.如果一整條 XB 邊相鄰至少兩條矩形邊的整個(gè)或部分，那么這整條XB邊被稱為 “一條多鄰的XB邊” 或簡(jiǎn)稱為“一條 M 邊” . 如果一條含有XB 邊的直線段與另一條直線段完全地相鄰

11、，且這兩條直線段分別都是由整個(gè)的矩形邊組成， 那么，滿足這樣條件的最短兩條相鄰直線段，我們稱含有 XB 邊的一條為 “ 線段”, 和另一條則被稱為“線段”，自然，線段也可含有 XB 邊. 一條 線段和一條 線段總是孿生的, 并且彼此相等. 例如, 下圖中 CD 是一條含有M邊的 線段，和GH 是與CD相鄰的一條 線段. G T 邊 T 邊 H CT 邊 M 邊 T邊 D 第二圖對(duì)于一個(gè) BB 矩形: 如果它有4條S邊, 那么，它被稱為一個(gè)B2SB2S 矩形，見(jiàn)下圖 (4).如果它僅有一條M邊, 那么，它被稱為一個(gè)B2SB1S 矩形，見(jiàn)下圖(5).如果它有兩條相對(duì)的 S 邊和兩條相對(duì)的 M 邊，

12、那么，它被稱為一個(gè) B2SB2M 矩形，見(jiàn)下圖 (6).如果它有兩條互相垂直的 S 邊和兩條互相垂直的 M 邊, 那么，它被稱為一個(gè) B1SB1S 矩形，見(jiàn)下圖 (7).如果它僅有一條 S邊, 那么，它被稱為一B1SB2M 矩形，見(jiàn)下圖 (8).如果它有4條M邊, 那么，它被稱為一個(gè)B2MB2M矩形，見(jiàn)下圖(9).對(duì)于一個(gè) AB 矩形: 如果它有兩條相對(duì)的S邊, 那么它被稱為一個(gè)B2S矩形，見(jiàn)下圖(10). 如果它僅有一條 S 邊, 那么，它被稱為一個(gè) B1S 矩形，見(jiàn)下圖 (11). 如果它有兩條相對(duì)的 M 邊, 那么，它被稱為一個(gè) B2M 矩形，見(jiàn)下圖 (12). . . . . . .

13、(1) an AA rectangle (2) an AB rectangle (3) a BB rectangle . . . . . . . . . . . (4) a B2SB2S rectangle (5) a B2SB1S rectangle (6) a B2SB2M rectangle . . . . . . . . . . . . . . (7) a B1SB1S rectangle (8) a B1SB2M rectangle (9) a B2MB2M rectangle . . . . . . . . . . . . . . . . . . . . (10)an AB2S r

14、ectangle (11)an AB1S rectangle (12)an AB2M rectangle . . . . . . . . . . . . . . . 第三圖證 明首先，讓我們解決掉這樣的平面或球面地圖，就是它的全部圖形都是每個(gè)相鄰至多三個(gè)圖形. 對(duì)于這樣的平面地圖，只需將它的每個(gè)圖形依次染上與它相鄰圖形顏色不同的一種顏色即可，那么四種顏色是足夠的.除此之外的平面地圖，我們將對(duì)其上面的圖形先進(jìn)行變換后，然后才能分別給它們著色，有些成片圖形相鄰不到四個(gè)圖形，還需要經(jīng)過(guò)變換、著色交替進(jìn)行后，才能最終確定每個(gè)圖形應(yīng)該著上的顏色. 其具體步驟順序如下：第一步. 在一個(gè)未染色的平面地圖上，

15、如果既有每個(gè)圖形相鄰至少四個(gè)圖形的圖形，又有每個(gè)圖形相鄰至多三個(gè)圖形的圖形，那么，就依次將每個(gè)相鄰至多三個(gè)圖形的圖形與它相鄰、且相鄰至少四個(gè)圖形的一個(gè)圖形合并成為一個(gè)圖形，使合并后的這個(gè)圖形也相鄰至少四個(gè)圖形. 第二步. 分別對(duì)每一條第一及它向內(nèi)包圍的圖形進(jìn)行變換.如果一條第一僅僅與一個(gè)圖形的一條邊界封閉曲線相鄰，即一條第一僅僅直接包圍一個(gè)圖形，那么就將開(kāi)孔圖形與該圖形合并成一個(gè)圖形，并把原兩個(gè)圖形所屬的都稱為第一，然后，從外向內(nèi)的的編號(hào)照樣減去1. 然后，在一條第一直接包圍的圖形中，如果仍然存在著與上述相同的相鄰情況，那么，繼續(xù)照此處理；在一條第一包圍的圖形中，如果存在著第二或，那么，就把每

16、一條第二向內(nèi)包圍的全部圖形與一個(gè)含有這條第二整個(gè)或部分的圖形合并為一個(gè)圖形,這樣，原第二已不存在，就把與合并后圖形的邊界封閉曲線相鄰的一條邊界封閉曲線作為一條第二.第三步. 通過(guò)拓?fù)渥儞Q，把每一條第一及各條第一向內(nèi)包圍的圖形的每一條邊界封閉曲線，包括第二，變換成只有橫向邊和豎向邊的矩形框. 另外，我們規(guī)定：相鄰兩個(gè)相鄰圖形的相鄰邊界必須為兩條相鄰的直線段，第一1也不例外，因?yàn)榈谝?所在的圖形也向內(nèi)相鄰至少四個(gè)圖形. 那么，每一條第一就變成了一條第一1. 總的說(shuō)來(lái)，拓?fù)渥儞Q每個(gè)第一1向內(nèi)包圍的全部圖形成為矩形，其類型至多有10種：即A 矩形、B2SB2S 矩形、B2SB1S矩形、B2SB2M矩形

17、、B1SB1S矩形、B1SB2M矩形、B2MB2M 矩形、B2S 矩形、B1S 矩形和B2M 矩形. 第四步. 變換每一條第一1成為一個(gè)A 矩形框，那么，全部這樣的A 矩形框共由三種顏色點(diǎn)組成. 并且，同步地變換向外相鄰每一條第一1的一條圖形的矩形邊界封閉曲線成為另一個(gè)A 矩形框，則每一條這樣的A 矩形框與變換第一1所得的A 矩形框有不同的三種顏色點(diǎn)，但這兩個(gè)A 矩形框仍然是完全相鄰的. 第五步. 將每一條第一1包圍的每列矩形、從左到右依次地、盡量將每個(gè)矩形的兩條豎向邊變換成兩條LA邊，那么，或者矩形的豎向邊保持不動(dòng)，或者向右依次移動(dòng)整條的矩形豎邊或由整條豎邊組成且相鄰相等的和線段到各自相鄰的

18、豎向直線段. 最后，對(duì)于最右一列矩形：當(dāng)每一行的矩形數(shù)目是奇數(shù)時(shí)，則全是僅有兩條LA邊的矩形，當(dāng)每一行的矩形數(shù)目是偶數(shù)時(shí)，則全是僅有兩條LB 邊的矩形，當(dāng)有的行的矩形數(shù)目是奇數(shù)、而另外行的矩形數(shù)目是偶數(shù)時(shí)，則既有兩條LA邊的矩形，又有兩條LB 邊的矩形.再將每一條第一1包圍的每行矩形、從上到下依次地、盡量將每個(gè)矩形的兩條橫向邊變換成兩條TA 邊，那么，或者矩形的橫向邊保持不動(dòng)，或者向下依次移動(dòng)整條的矩形橫邊或由整條橫邊組成且相鄰相等的和線段到各自相鄰的橫向直線段. 最后，對(duì)于最下一行矩形：當(dāng)每一列的矩形數(shù)目是奇數(shù)時(shí)，則全是僅有兩條TA邊的矩形，當(dāng)每一列的矩形數(shù)目是偶數(shù)時(shí)，則全是僅有兩條TB 邊

19、的矩形，當(dāng)有的列的矩形數(shù)目是奇數(shù)、而另外列的矩形數(shù)目是偶數(shù)時(shí)，則既有兩條TA邊的矩形，又有兩條TB 邊的矩形.于是，在每一條第一1包圍的矩形中，除最右邊的一列矩形和最下邊的一行矩形外，全部都是A 矩形. 在一條第一1包圍的矩形中，就最右邊的一列矩形而言：如果每個(gè)都有兩條LA 邊，那么，除了最下面的一個(gè)外，全部都是A 矩形；如果每個(gè)都有兩條LB 邊，那么，除了最下面一個(gè)外，全部都是B 矩形；如果既有兩條LA 邊的矩形，又有兩條LB 邊的矩形，那么，除最下面一個(gè)外，這列矩形既有A 矩形又有B 矩形.在一條第一1包圍的矩形中，就最下邊的一列矩形而言：如果每個(gè)都有兩條TA 邊，那么，除了最右面一個(gè)外，

20、全部都是A 矩形. 如果最右面一個(gè)有兩條LA 邊，那么，這最右面一個(gè)是A矩形；如果最右面一個(gè)有兩條LB 邊，那么，這最右面一個(gè)是AB矩形.如果每個(gè)都是有兩條TB 邊，那么，除了最右面一個(gè)外，全部是B 矩形. 如果最右面一個(gè)有兩條LA 邊，那么，這最右面一個(gè)是B矩形；如果最右面一個(gè)有兩條LB 邊，那么，這最右面一個(gè)是BB矩形. 如果既有兩條TA 邊的矩形，又有兩條TB 邊的矩形, 那么，這一行矩形既有A 矩形，又有B 矩形, 并且， 最右面一個(gè)或者是A 矩形，或者是B 矩形，或者是BB矩形.第六步. 我們首先需要判斷這個(gè)未染色的平面地圖上的各種圖形應(yīng)該染上什么樣的顏色，然后才能正確地給每個(gè)圖形染

21、上一種顏色. 除全部第一2外，可給每一個(gè)A矩形染上與它的四個(gè)直角頂點(diǎn)相同的一種顏色，那么，兩個(gè)相鄰的A矩形被染上了不同的顏色. 如果在一條第一1包圍的圖形中有B矩形，那么，B矩形一定是在最右一列或和最下一行矩形上. 而且，如果最右一列和最下一行僅除相鄰第一1右下角兩邊的一個(gè)矩形外全部是B矩形，那么根據(jù)前面的作法，相鄰這條第一1右下角兩邊的這個(gè)矩形一定是BB矩形.于是，給在最右一列上的每個(gè)B矩形染上與各自左邊兩個(gè)直角頂點(diǎn)相同的一種顏色；給最下一行上的每個(gè)B矩形染上與各自上邊兩個(gè)直角頂點(diǎn)相同的一種顏色；給相鄰第一1右下角兩邊的這個(gè)BB矩形染上與它左上角頂點(diǎn)相同的一種顏色. 現(xiàn)在，恢復(fù)含有整個(gè)和部分

22、最后確定的第一的圖形的邊界封閉曲線，而不論他們的形狀如何. 根據(jù)上面的作法，我們知道，每一個(gè)這樣的圖形相鄰至少四個(gè)原來(lái)的圖形.如果一個(gè)圖形的每一條第一1內(nèi)的矩形都是A矩形，沒(méi)有B矩形和BB矩形，并且，這些第一2總共都是由三種顏色點(diǎn)組成，那么，就給這個(gè)圖形染上與任意這樣一個(gè)第一1直角頂點(diǎn)相同的一種顏色.如果在一條第一1內(nèi)既有A矩形，又有B矩形，那么，按照一圖一色、兩色交替的原則，依次染含有這第一1上邊的整個(gè)或部分的每個(gè)圖形為這第一1上邊點(diǎn)的兩種顏色之一，和依次染含有這第一1左邊的整個(gè)或部分的每個(gè)圖形為這第一1左邊點(diǎn)的兩種顏色之一，但在第一1的左、上角相鄰的兩個(gè)圖形所染顏色不同. 假使第一1內(nèi)最右

23、一列有B矩形，就依次染含有這第一1右邊的整個(gè)或部分的每個(gè)圖形為相鄰第一1右邊的直線段的點(diǎn)的兩種顏色之一，但在第一1的右、上角相鄰的兩個(gè)圖形所染顏色不同. 假使第一1內(nèi)最下一行有B矩形，就依次染含有這第一1下邊的整個(gè)或部分的每個(gè)圖形為相鄰第一1下邊的直線段的點(diǎn)的兩種顏色之一，但 在第一1的左、下角相鄰的兩個(gè)圖形所染顏色不同，在第一1的右、下角相鄰的兩個(gè)圖形所染顏色也不同.如果一個(gè)圖形含有至少兩個(gè)第一2的整個(gè)和或部分，那么，分別從各條第一1去確定這個(gè)圖形應(yīng)該染上的顏色，無(wú)論如何，從每一條第一1去確定的顏色必須是一樣的. 假如不一樣，就需要把有同一顏色的一種圖形的每一個(gè)與它相鄰圖形去交換顏色，使含第

24、一2的圖形能染上一種顏色; 假如不能交換顏色，就要重新變換部分的第一2和它們每一條向內(nèi)包圍的圖形的邊界封閉曲線. 即，首先變換每條這樣的第一1為與原先不同三種顏色點(diǎn)的A矩形框，并同步地變換向外與它全部相鄰的一條邊界封閉曲線. 再變換每條這樣的第一1向內(nèi)包圍的圖形.根據(jù)上述的作法，這樣是完全能夠讓含有至少兩個(gè)第一1的整個(gè)和或部分的圖形被染上同一種顏色的.總而言之，經(jīng)過(guò)前面的作法，我們已達(dá)到：給每個(gè)圖形著上了一種顏色，且相鄰兩個(gè)圖形著上的顏色是不同的. 第七步. 在各條第一1內(nèi)，首先恢復(fù)每條第二1和相鄰至少四個(gè)圖形的每個(gè)圖形的邊界封閉曲線，并消除這些圖形被染上的一種顏色，再恢復(fù)這些圖形的平面上原先的四種顏色點(diǎn). 然后，根據(jù)前面的作法，變換這些圖形成矩形，并給每一個(gè)圖形著上一種顏色.在一個(gè)未著色的平面地圖上，假設(shè)有n 個(gè)等級(jí)的，這兒n1，那么，根據(jù)前面的作法，在依次變換n 個(gè)等級(jí)的和各個(gè)向內(nèi)包圍的圖形、以及給每一個(gè)圖形著上一種顏色后，在這個(gè)臨時(shí)