四色猜想

摘要：1852年，畢業(yè)于 倫敦大學(xué)的格斯里（Francis Guthrie）來到一家科研單位搞地圖著色工作時，發(fā)現(xiàn)每幅地圖都可以只用四種顏色著色。這個現(xiàn)象能不能從數(shù)學(xué)上加以嚴格證明呢？他和他正在讀大學(xué)的弟弟決心試一試，但是稿紙已經(jīng)堆了一大疊，研究工作卻是沒有任何進展。1852年10月23日，他的弟弟就這個問題的證明請教了他的老師、著名數(shù)學(xué)家德·摩爾根，摩爾根也沒有能找到解決這個問題的途徑，于是寫信向自己的好友，著名數(shù)學(xué)家 哈密頓爵士請教，但直到1865年哈密頓逝世為止，問題也沒有能夠解決。1872年，英國當(dāng)時最著名的數(shù)學(xué)家凱利正式向倫敦數(shù)學(xué)學(xué)會提出了這個問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題。

關(guān)鍵詞：四色猜想；五色定理；

鋪瓦定理：如果任意簡單的二維圖形被分割為充分小的區(qū)域，則不論這些區(qū)域的形狀如何，必然有這樣一些點使三個或更多個區(qū)域在那里相遇，另外，一定存在圖形的這樣一種剖分，使得每個點至多同時屬于這剖分的三個區(qū)域。

我們關(guān)心的平面地圖著色問題，而不是關(guān)心一個國家疆界是正方形還是圓形，因此我們可以利用平面圖形的拓撲關(guān)系，總可以把一副簡單（幾何關(guān)系簡單不是外形簡單）圖形拓撲的等效于鋪瓦定理圖形。鋪瓦定理圖形，是一個國家最多和另外兩個國家彼此比鄰。比鋪瓦定理圖形稍微復(fù)雜一點幾何圖形關(guān)系，是一個國家被三個國家圍繞，而且其中一個國家和另外三個國家保持彼此都相鄰，這樣，顯然需要著四種顏色，要不然就要撞色。如圖：

這種幾何關(guān)系，也可以把鋪瓦定理中實心點改成空心點來等效。此種幾何結(jié)構(gòu)是平面幾何結(jié)構(gòu)中最復(fù)雜的，如果再多一個國家就不能彼此保持這種其中一個與另外四個都彼此間相鄰的幾何關(guān)系。因此，經(jīng)過上述分析，我們知道一張地圖中，不管多復(fù)雜，界點總可以分成如下三類，如圖：

可見，一副地圖著四色是平面圖形幾何結(jié)構(gòu)關(guān)系決定。一副地圖著四種顏色夠嗎？這個完全取決于地圖中國家與國家疆界之間的幾何關(guān)系，而且是綜合幾何關(guān)系，而不是簡單的國家的數(shù)量。假設(shè)用1、2、3、4和5，5個數(shù)字代替5種顏色。我們知道一副地圖國與國之間存在著界線，這兩個國家和至少其他一個國家相界，那么必存在一個界點。因此，一副地圖，到處充滿著界點，而且界點是至少3個國家的界線的交點，有些是4個國家，有些是5個國家，有些甚至更多。我們規(guī)定，1個國家被超過3個，如果達8個國家圍繞，那么多出來6個國家，是偶數(shù)個，按照1-2-1-2-1-2排列；如果多出來的國家是奇數(shù)個呢？我們按照1-2-1-2-1排列，這樣排列是基于為了滿足最少著色要求。

現(xiàn)在我們討論第③類界點數(shù)字標(biāo)注情況，我們用圖形來分析這些界點的幾何關(guān)系：

考慮最復(fù)雜的那種幾何關(guān)系；假如有兩個區(qū)域已經(jīng)標(biāo)注了3和4；那么，另外還有兩種情況與之共點，1、奇數(shù)個國家與之共點，根據(jù)上文最小著色要求的規(guī)定，那么只需要標(biāo)注4個數(shù)字即可；2、偶數(shù)個國家與之共點，那么也只需要標(biāo)注4個數(shù)字即可。具體如下圖，

根據(jù)上圖形分析，在復(fù)雜的第③類界點幾何關(guān)系下，我們標(biāo)注了4個數(shù)字，如果遇到更復(fù)雜的幾何關(guān)系，我們把黑色界點標(biāo)注5即可；而且，3和4如果不相鄰，那么他們之間我們可以插入標(biāo)注1和2，不影響格局。地圖上出現(xiàn)了5，那么還會出現(xiàn)更復(fù)雜的幾何關(guān)系嗎？不會，我們可以用5代替3，結(jié)果仍然只需要標(biāo)注4個數(shù)字，然而遇到更復(fù)雜的幾何關(guān)系（第③類界點是最復(fù)雜的幾何關(guān)系），我們用被代替3標(biāo)注黑色界點即可。

另一種方法標(biāo)注，我們知道地圖的界點有三類，我們從最復(fù)雜第③類界點開始標(biāo)注，讓中心圓圈標(biāo)注4，最復(fù)雜情況下，用1、2和3標(biāo)注其他區(qū)域；接著同樣讓第②類界點中心圓圈標(biāo)注4，其他顯然標(biāo)注1、2和3；那么剩下地圖上都是第①類界點，而且地圖上除了圓圈內(nèi)的4之外，全是1、2和3；排得好1、2和3正好排上第①類界點的三個區(qū)域；排的的不好，比如其中兩個區(qū)域已經(jīng)排了1和2，剩下一個區(qū)域仍然必須排1或2，此時我們選擇4代替1或2即可；最壞的情況，就是第①類界點的三個區(qū)域必須排同樣的數(shù)字比如三個2，那么我們可以在地圖版面上交換第③類界點中的1和2的位置或者2和3的位置，或者兩者同時交換，看看還會不會出現(xiàn)同樣的數(shù)字同排的現(xiàn)象，如果仍然出現(xiàn)，我們用4和5代替兩個2即可，此時需著五色。

經(jīng)過分析，不管地圖上國與國之間的關(guān)系多么的復(fù)雜，理論上只需著五色，即可區(qū)分國與國之間的疆界而不撞色。在實際地圖著色中，我們可以選擇第③類界點中國家數(shù)量最多那個為中心進行著色，向周圍擴散，用沒有邊界的這個條件換取第5色；更何況，我們遇不到國與國之間的復(fù)雜的幾何綜合關(guān)系，再加上選擇性著色，因此，著四色即可。

（作者：浙江省寧波市人，郵編315600）