對四色地圖問題的一個書面證明

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

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

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

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

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

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

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

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

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

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

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

12、那么，它被稱為一個 B2SB2M 矩形，見下圖 (6).如果它有兩條互相垂直的 S 邊和兩條互相垂直的 M 邊, 那么，它被稱為一個 B1SB1S 矩形，見下圖 (7).如果它僅有一條 S邊, 那么，它被稱為一B1SB2M 矩形，見下圖 (8).如果它有4條M邊, 那么，它被稱為一個B2MB2M矩形，見下圖(9).對于一個 AB 矩形: 如果它有兩條相對的S邊, 那么它被稱為一個B2S矩形，見下圖(10). 如果它僅有一條 S 邊, 那么，它被稱為一個 B1S 矩形，見下圖 (11). 如果它有兩條相對的 M 邊, 那么，它被稱為一個 B2M 矩形，見下圖 (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 . . . . . . . . . . . . . . . 第三圖證 明首先，讓我們解決掉這樣的平面或球面地圖，就是它的全部圖形都是每個相鄰至多三個圖形. 對于這樣的平面地圖，只需將它的每個圖形依次染上與它相鄰圖形顏色不同的一種顏色即可，那么四種顏色是足夠的.除此之外的平面地圖，我們將對其上面的圖形先進(jìn)行變換后，然后才能分別給它們著色，有些成片圖形相鄰不到四個圖形，還需要經(jīng)過變換、著色交替進(jìn)行后，才能最終確定每個圖形應(yīng)該著上的顏色. 其具體步驟順序如下：第一步. 在一個未染色的平面地圖上，

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

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

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

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

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

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

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

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

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

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