奇妙的四色問題

田翔仁

繪制地圖，除了要求保證其準(zhǔn)確性外，如何給地圖著色，從而能明顯地區(qū)分地圖上的各個(gè)區(qū)域，也是十分重要的. 很早以前，繪圖員就發(fā)現(xiàn)，只要配置幾種顏色就可以給任何地圖著色了. 究竟最少要用幾種顏色呢？這成了數(shù)學(xué)家們十分感興趣的問題.

四色問題的提出

相傳，四色問題是由英國(guó)青年數(shù)學(xué)家格思里提出來的. 1852年，他在繪制地圖時(shí)發(fā)現(xiàn)，給相鄰地區(qū)涂上不同顏色，只要四種顏色就足夠了. 他把這個(gè)發(fā)現(xiàn)告訴了在大學(xué)讀書的弟弟. 他的弟弟便向英國(guó)數(shù)學(xué)家摩根請(qǐng)教，摩根又向著名數(shù)學(xué)家哈密頓請(qǐng)教，但是，問題仍然沒有解決……

1878年，英國(guó)數(shù)學(xué)家凱萊正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出這個(gè)問題，這才引起了數(shù)學(xué)界的重視. 世界上許多數(shù)學(xué)家爭(zhēng)相進(jìn)行研究，其中有數(shù)學(xué)家肯普、希伍德、閔可夫斯基等，結(jié)果仍然一無所獲. 人們開始認(rèn)識(shí)到，這貌似簡(jiǎn)單的題目，其實(shí)是一道超級(jí)數(shù)學(xué)難題.

四色問題的證明

進(jìn)入20世紀(jì)后，證明四色問題的研究才逐漸取得進(jìn)展. 1913年，美國(guó)數(shù)學(xué)家伯克霍夫改進(jìn)了肯普的方法，引進(jìn)了一些新技巧，導(dǎo)致1939年美國(guó)數(shù)學(xué)家富蘭克林證明了22國(guó)以下的地圖可以只用四色著色. 1950年溫恩證明了35國(guó)，1968年奧爾又證明了39國(guó)，1975年有報(bào)道，已證明了52國(guó).

為什么進(jìn)展如此緩慢？主要是由于數(shù)學(xué)家提出的檢驗(yàn)方法太復(fù)雜，工作量太繁重. 一直到1976年，美國(guó)數(shù)學(xué)家阿佩爾和哈肯利用計(jì)算機(jī)工作了1200小時(shí)，作了100億個(gè)判斷，終于證明了四色問題是正確的. 這是人類首次依靠計(jì)算機(jī)的幫助解決了著名的數(shù)學(xué)難題.

點(diǎn)、線、面的關(guān)系

隨意畫曲線的涂鴉之作也能體現(xiàn)數(shù)學(xué)的趣味性.

下面有一條隨意畫的連續(xù)曲線，起點(diǎn)和終點(diǎn)分開，我們可以用三種顏色，把它們的各個(gè)區(qū)域涂上不同的顏色.

下面我們先動(dòng)手把這張地圖填上顏色，再研究一下幾個(gè)數(shù)量.

1. 頂點(diǎn)與交叉點(diǎn)的個(gè)數(shù)（V）；

2. 連接兩點(diǎn)的曲線段的數(shù)量（E）；

3. 包括底圖在內(nèi)的所有大小區(qū)域的數(shù)量（F）.

看看這三個(gè)數(shù)量之間有什么關(guān)系.

統(tǒng)計(jì)結(jié)果是：點(diǎn)數(shù)為10，線數(shù)為17，面數(shù)為9，然后得出10+9=17+2.

如果我們?cè)俜治鱿旅鎯蓮執(zhí)厥獾牡貓D：

它們之間都滿足這樣的關(guān)系，即點(diǎn)數(shù)+面數(shù)=線數(shù)+2.

即V+F=E+2，這個(gè)關(guān)系式稱為歐拉公式.

給點(diǎn)涂色

這里有一個(gè)圖形，上面有若干個(gè)頂點(diǎn)（交叉點(diǎn)）. 如果我們給這些點(diǎn)涂色，并要求任何一根線的兩個(gè)頂點(diǎn)的顏色不同，最少需要多少種顏色？

給線涂色

如果我們給這里的圖形和線段涂色，并要求相鄰的線段的顏色不同，最少需要多少種顏色？