四色猜想

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

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

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

我們關(guān)心的平面地圖著色問(wèn)題，而不是關(guān)心一個(gè)國(guó)家疆界是正方形還是圓形，因此我們可以利用平面圖形的拓?fù)潢P(guān)系，總可以把一副簡(jiǎn)單（幾何關(guān)系簡(jiǎn)單不是外形簡(jiǎn)單）圖形拓?fù)涞牡刃в阡佂叨ɡ韴D形。鋪瓦定理圖形，是一個(gè)國(guó)家最多和另外兩個(gè)國(guó)家彼此比鄰。比鋪瓦定理圖形稍微復(fù)雜一點(diǎn)幾何圖形關(guān)系，是一個(gè)國(guó)家被三個(gè)國(guó)家圍繞，而且其中一個(gè)國(guó)家和另外三個(gè)國(guó)家保持彼此都相鄰，這樣，顯然需要著四種顏色，要不然就要撞色。如圖：

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

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

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

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

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

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

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

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