地圖的四色定理最早是由壹位名叫古德瑞的英國大學生提出的。德摩根(A，德摩根，1806 ~ 1871)1852 10，23)給漢密爾頓的壹封信，提供了關於四色定理起源的最原始的記錄。他在信中概述了自己證明四色定理的想法和感受。壹個多世紀以來，數學家們絞盡腦汁證明這個定理，引入的概念和方法刺激了拓撲學和圖論的成長和發展。1976年，美國數學家K.Appel和W.Haken宣布在電子計算機的幫助下獲得了四色定理的證明，開辟了用計算機證明數學定理的前景。以下節選自德·摩根給漢密爾頓的信的主要部分，翻譯自j·福夫1和j·格雷(編。)，數學史:壹個讀者，第597~598頁。
德摩根給漢密爾頓的信(1852 65438+10月23日)
我的壹個學生讓我解釋壹個過去不知道，現在仍然不知道的事實。他說，如果壹個圖形被任意分割，每個部分都被著色，使得任何有共同邊界的部分顏色都不同，那麽只需要四種顏色。現在的問題是會不會出現需要五種甚至更多顏色的情況。據我所知，如果四個未分割的區域有壹條共同的邊界線，其中的三個必須包圍第四個，使其不與任何第五個區域相鄰。如果這個事實可以成立，那麽任何可能的地圖都可以用四種顏色來著色，這樣除了在公共點上，就不會有相同的顏色了。
現在畫三個有共同邊界的成對區域ABC，所以除非它包圍其中壹個區域，否則不可能畫壹個有共同邊界的第四個區域(圖2)。但是證明這壹點非常困難，我也不確定問題有多復雜——妳對此有什麽看法？而如果這件事很嚴重，難道沒有人註意到嗎？我的學生說這是給英國地圖著色時的猜測。越想越明顯。如果妳能給我壹個簡單的反例來說明我看起來像頭驢，我就不得不重復斯芬克斯了。
四色問題，又稱四色猜想，是現代世界三大數學問題之壹。
四色問題的內容是:“任何只有四種顏色的地圖，都可以使相同邊界的國家有不同的顏色。”用數學語言表達，就是“把平面隨意分成不重疊的區域，每個區域總能標上1、2、3、4四個數字中的壹個，而不使兩個相鄰的區域得到相同的數字。”
這裏所說的相鄰區域是指有壹整段邊界是公共的。如果兩個區域僅在壹點或有限數量的點處相交，則它們不相鄰。因為給它們塗上相同的顏色不會造成混淆。
四色猜想是由英國提出的。1852年，畢業於倫敦大學的弗朗西斯·格思裏(Francis guthrie)來到壹家科研單位做地圖著色時，發現了壹個有趣的現象:“似乎每張地圖都可以用四種顏色著色，這樣同樣邊界的國家就用不同的顏色著色了。”這種現象可以用數學方法嚴格證明嗎？他和正在讀大學的弟弟格萊斯決心試壹試。兩兄弟用來證明這個問題的稿紙已經堆了壹堆，但研究工作壹直沒有進展。
1852，10年10月23日，他的弟弟向他的老師——著名數學家德·摩爾根請教這個問題的證明。摩根也找不到解決這個問題的方法，於是他寫信給他的好朋友，著名數學家漢密爾頓爵士尋求建議。漢密爾頓收到摩爾根的信後，論證了四色問題。但是直到1865漢密爾頓去世，這個問題還是沒有解決。
1872年，當時英國最著名的數學家凱利正式向倫敦數學會提出了這個問題，於是四色猜想成為世界數學界關註的問題。世界上很多壹流的數學家都參加過四色猜想的大戰役。在1878到1880的兩年間，坎普和泰勒兩位著名的律師和數學家分別提交了證明四色猜想的論文，並宣布證明了四色定理。大家都以為四色猜想從此解決了。
坎普的證明是這樣的:首先指出，如果沒有壹個國家包圍其他國家，或者不超過三個國家在壹點相交，則稱這個地圖是“正則的”。如果是規則圖，否則就是不規則圖(右圖)。壹張地圖往往由正規地圖和非正規地圖聯系在壹起，但非正規地圖所需的顏色數量壹般不會超過正規地圖所需的數量。如果有壹張地圖需要五色，說明它的正規地圖是五色的。要證明四色猜想，只要證明不存在有規律的五色地圖就夠了。
坎普用歸謬法證明了這壹點，大意是:如果有壹個正則五色地圖，就會有壹個國家數最少的“極小正則五色地圖”。如果極小正則五色圖中有壹個鄰國少於六個的國家，那麽就會有壹個國家較少的正則圖仍然是五色的，所以就不會有極小五色圖的國家，也就不會有正則五色圖。於是坎普以為自己證明了“四色問題”，但後來人們發現他錯了。
但是，肯普的證明澄清了兩個重要概念，為以後解決問題提供了壹個思路。第壹個概念是“配置”。他證明了在每個正則圖中，至少壹個國家有兩個、三個、四個或五個鄰國，不存在每個國家都有六個或更多鄰國的正則圖。也就是說，壹組由兩個鄰國、三個鄰國、四個或五個鄰國組成的“配置”是不可避免的，每張地圖至少包含這四種配置中的壹種。
坎普提出的另壹個概念是可還原性。“可協商”壹詞的使用來自坎普的論證。他證明了五色地圖中只要有壹個國家有四個鄰國，就會有壹個國家較少的五色地圖。自從“構形”和“可約性”的概念被提出以來，壹些檢驗構形以確定它們是否可約的標準方法逐漸被發展起來，可以找到可約構形的必然群，這是證明“四色問題”的重要基礎。但是要證明壹個大的配置是可約的，需要查很多細節，相當復雜。
11年後，也就是1890年，年僅29歲、就讀於牛津大學的赫伍德用自己的精確計算指出了坎普證明中的漏洞。他指出，坎普提出的沒有最小五色地圖的國家不可能有五個鄰國的理由是有缺陷的。很快，泰勒的證明也被否定了。人們發現他們其實證明了壹個弱命題——五色定理。也就是說，給地圖塗上五種顏色就夠了。後來，越來越多的數學家為此絞盡腦汁，卻壹無所獲。於是，人們開始意識到，這個看似簡單的題目，其實是壹個堪比費馬猜想的難題。
自20世紀以來，科學家們基本上是按照肯普的想法證明四色猜想的。1913、美國著名數學家、哈佛大學boekhoff利用了Kemp的思想，結合了他的新思想；證明了壹些大的構形是可約的。後來美國數學家富蘭克林在1939中證明了22個國家以下的地圖可以用四種顏色著色。1950有人從22國晉級35國。1960中證明了39個國家以下的地圖只用四種顏色就可以著色；然後推進到50個國家。看來這個進度還是很慢的。
高速數字計算機的發明促使更多的數學家研究“四色問題”。從1936開始研究四色猜想的Heck公開宣稱，可以通過尋找可約圖的必然群來證明四色猜想。他的學生圖雷寫了壹個計算程序。Heck不僅可以用這個程序生成的數據證明構型的可約性，還可以通過將映射轉化為數學上稱為“對偶”的形狀來描述可約構型。
他標出每個國家的首都，然後用壹條穿越邊境的鐵路把鄰國的首都連接起來。除了首都(稱之為頂點)和鐵路(稱之為弧或邊)之外，其他所有的線都被抹掉了，剩下的稱為原圖的對偶圖。在20世紀60年代後期，Heck引入了壹種類似於在電網絡中移動電荷的方法來尋找不可避免的壹組配置。在赫克的研究中第壹次以相當不成熟的形式出現的“放電法”，是以後研究必然群的壹把鑰匙，是證明四色定理的壹個中心要素。
電子計算機出現後，由於計算速度的快速提高和人機對話的出現，四色猜想的證明過程大大加快了。美國伊利諾伊大學的哈肯在1970開始改進“放電過程”，然後和Appel壹起編了壹個很好的程序。1976年6月，他們在美國伊利諾伊大學兩臺不同的電子計算機上，花費了1200個小時，做出了1000億次判斷，最終完成了四色定理的證明，在世界上引起了轟動。
這是100多年來吸引了眾多數學家和數學愛好者的壹件大事。當兩位數學家發表他們的研究成果時，當地郵局給當天寄出的所有郵件蓋上了“四種顏色就夠了”的特別郵戳，以慶祝這壹難題的解決。
“四色問題”被證明只是解決了壹個持續了100多年的難題，它成為數學史上壹系列新思想的起點。在“四色問題”的研究過程中，出現了許多新的數學理論，發展了許多數學計算技巧。比如把地圖的著色問題變成圖論問題，豐富了圖論的內容。不僅如此，“四色問題”還在有效設計航空公司航班時刻表和設計計算機編碼程序中發揮了作用。
然而，許多數學家並不滿足於計算機所取得的成就。他們認為應該有壹個簡單明了的書面證明方法。時至今日，許多數學家和數學愛好者仍在尋找更簡潔的證明方法。
德·摩根:地圖的四色定理
地圖的四色定理最早是由壹位名叫古德瑞的英國大學生提出的。德摩根(A，德摩根，1806 ~ 1871)1852 10，23)給漢密爾頓的壹封信，提供了關於四色定理起源的最原始的記錄。他在信中概述了自己證明四色定理的想法和感受。壹個多世紀以來，數學家們絞盡腦汁證明這個定理，引入的概念和方法刺激了拓撲學和圖論的成長和發展。1976年，美國數學家K.Appel和W.Haken宣布在電子計算機的幫助下獲得了四色定理的證明，開辟了用計算機證明數學定理的前景。以下節選自德·摩根給漢密爾頓的信的主要部分，翻譯自j·福夫1和j·格雷(編。)，數學史:壹個讀者，第597~598頁。
德摩根給漢密爾頓的信(1852 65438+10月23日)
我的壹個學生讓我解釋壹個過去不知道，現在仍然不知道的事實。他說，如果壹個圖形被任意分割，每個部分都被著色，使得任何有共同邊界的部分顏色都不同，那麽只需要四種顏色。下圖是需要四種顏色的例子(圖1)。現在的問題是會不會出現需要五種甚至更多顏色的情況。據我所知，如果四個未分割的區域有壹條共同的邊界線，其中的三個必須包圍第四個，使其不與任何第五個區域相鄰。如果這個事實可以成立，那麽任何可能的地圖都可以用四種顏色來著色，這樣除了在公共點上，就不會有相同的顏色了。
現在畫三個有共同邊界的區域ABC，所以除非第四個區域包圍其中壹個區域，否則不可能畫出與其他三個區域都有共同邊界的第四個區域。但是證明這壹點非常困難，我也不確定問題有多復雜——妳對此有什麽看法？而如果這件事很嚴重，難道沒有人註意到嗎？我的學生說這是給英國地圖著色時的猜測。越想越明顯。如果妳能給我壹個簡單的反例來說明我看起來像頭驢，我就不得不重復斯芬克斯了。
坎普的證明是這樣的:首先指出，如果沒有壹個國家包圍其他國家，或者不超過三個國家在壹點相交，則稱這個地圖是“正則的”。如果是規則圖，否則就是不規則圖。壹張地圖往往由正規地圖和非正規地圖聯系在壹起，但非正規地圖所需的顏色數量壹般不會超過正規地圖所需的數量。如果有壹張地圖需要五色，說明它的正規地圖是五色的。要證明四色猜想，只要證明不存在有規律的五色地圖就夠了。
坎普用歸謬法證明了這壹點，大意是:如果有壹個正則五色地圖，就會有壹個國家數最少的“極小正則五色地圖”。如果極小正則五色圖中有壹個鄰國少於六個的國家，那麽就會有壹個國家較少的正則圖仍然是五色的，所以就不會有極小五色圖的國家，也就不會有正則五色圖。於是坎普以為自己證明了“四色問題”，但後來人們發現他錯了。
但是，肯普的證明澄清了兩個重要概念，為以後解決問題提供了壹個思路。第壹個概念是“配置”。他證明了在每個正則圖中，至少壹個國家有兩個、三個、四個或五個鄰國，不存在每個國家都有六個或更多鄰國的正則圖。也就是說，壹組由兩個鄰國、三個鄰國、四個或五個鄰國組成的“配置”是不可避免的，每張地圖至少包含這四種配置中的壹種。
坎普提出的另壹個概念是可還原性。“可協商”壹詞的使用來自坎普的論證。他證明了五色地圖中只要有壹個國家有四個鄰國，就會有壹個國家較少的五色地圖。自從“構形”和“可約性”的概念被提出以來，壹些檢驗構形以確定它們是否可約的標準方法逐漸被發展起來，可以找到可約構形的必然群，這是證明“四色問題”的重要基礎。但是要證明壹個大的配置是可約的，需要查很多細節，相當復雜。
11年後，也就是1890年，年僅29歲、就讀於牛津大學的赫伍德用自己的精確計算指出了坎普證明中的漏洞。他指出，坎普提出的沒有最小五色地圖的國家不可能有五個鄰國的理由是有缺陷的。很快，泰勒的證明也被否定了。人們發現他們其實證明了壹個弱命題——五色定理。也就是說，給地圖塗上五種顏色就夠了。後來，越來越多的數學家為此絞盡腦汁，卻壹無所獲。於是，人們開始意識到，這個看似簡單的題目，其實是壹個堪比費馬猜想的難題。
自20世紀以來，科學家們基本上是按照肯普的想法證明四色猜想的。1913、美國著名數學家、哈佛大學boekhoff利用了Kemp的思想，結合了他的新思想；證明了壹些大的構形是可約的。後來美國數學家富蘭克林在1939中證明了22個國家以下的地圖可以用四種顏色著色。1950有人從22國晉級35國。1960中證明了39個國家以下的地圖只用四種顏色就可以著色；然後推進到50個國家。看來這個進度還是很慢的。
高速數字計算機的發明促使更多的數學家研究“四色問題”。從1936開始研究四色猜想的Heck公開宣稱，可以通過尋找可約圖的必然群來證明四色猜想。他的學生圖雷寫了壹個計算程序。Heck不僅可以用這個程序生成的數據證明構型的可約性，還可以通過將映射轉化為數學上稱為“對偶”的形狀來描述可約構型。
他標出每個國家的首都，然後用壹條穿越邊境的鐵路把鄰國的首都連接起來。除了首都(稱之為頂點)和鐵路(稱之為弧或邊)之外，其他所有的線都被抹掉了，剩下的稱為原圖的對偶圖。在20世紀60年代後期，Heck引入了壹種類似於在電網絡中移動電荷的方法來尋找不可避免的壹組配置。在赫克的研究中第壹次以相當不成熟的形式出現的“放電法”，是以後研究必然群的壹把鑰匙，是證明四色定理的壹個中心要素。
電子計算機出現後，由於計算速度的快速提高和人機對話的出現，四色猜想的證明過程大大加快了。美國伊利諾伊大學的哈肯在1970開始改進“放電過程”，然後和Appel壹起編了壹個很好的程序。1976年6月，他們在美國伊利諾伊大學兩臺不同的電子計算機上，花費了1200個小時，做出了1000億次判斷，最終完成了四色定理的證明，在世界上引起了轟動。
這是100多年來吸引了眾多數學家和數學愛好者的壹件大事。當兩位數學家發表他們的研究成果時，當地郵局給當天寄出的所有郵件蓋上了“四種顏色就夠了”的特別郵戳，以慶祝這壹難題的解決。
“四色問題”被證明只是解決了壹個持續了100多年的難題，它成為數學史上壹系列新思想的起點。在“四色問題”的研究過程中，出現了許多新的數學理論，發展了許多數學計算技巧。比如把地圖的著色問題變成圖論問題，豐富了圖論的內容。不僅如此，“四色問題”還在有效設計航空公司航班時刻表和設計計算機編碼程序中發揮了作用。
然而，許多數學家並不滿足於計算機所取得的成就。他們認為應該有壹個簡單明了的書面證明方法。時至今日，許多數學家和數學愛好者仍在尋找更簡潔的證明方法。
德·摩根:地圖的四色定理
地圖的四色定理最早是由壹位名叫古德瑞的英國大學生提出的。德摩根(A，德摩根，1806 ~ 1871)1852 10，23)給漢密爾頓的壹封信，提供了關於四色定理起源的最原始的記錄。他在信中概述了自己證明四色定理的想法和感受。壹個多世紀以來，數學家們絞盡腦汁證明這個定理，引入的概念和方法刺激了拓撲學和圖論的成長和發展。
我的壹個學生讓我解釋壹個過去不知道，現在仍然不知道的事實。他說，如果壹個圖形被任意分割，每個部分都被著色，使得任何有共同邊界的部分顏色都不同，那麽只需要四種顏色。下圖是需要四種顏色的例子(圖1)。現在的問題是會不會出現需要五種甚至更多顏色的情況。據我所知，如果四個未分割的區域有壹條共同的邊界線，其中的三個必須包圍第四個，使其不與任何第五個區域相鄰。如果這個事實可以成立，那麽任何可能的地圖都可以用四種顏色來著色，這樣除了在公共點上，就不會有相同的顏色了。
現在畫三個有共同邊界的區域ABC，所以除非第四個區域包圍其中壹個區域，否則不可能畫出與其他三個區域都有共同邊界的第四個區域。但是證明這壹點非常困難，我也不確定問題有多復雜——妳對此有什麽看法？而如果這件事很嚴重，難道沒有人註意到嗎？我的學生說這是給英國地圖著色時的猜測。越想越明顯。如果妳能給我壹個簡單的反例來說明我看起來像頭驢，我就不得不重復斯芬克斯了。
四色問題，又稱四色猜想，是現代世界三大數學問題之壹。
四色問題的內容是:“任何只有四種顏色的地圖，都可以使相同邊界的國家有不同的顏色。”用數學語言表達，就是“把平面隨意分成不重疊的區域，每個區域總能標上1、2、3、4四個數字中的壹個，而不使兩個相鄰的區域得到相同的數字。”
這裏所說的相鄰區域是指有壹整段邊界是公共的。如果兩個區域僅在壹點或有限數量的點處相交，則它們不相鄰。因為給它們塗上相同的顏色不會造成混淆。
四色猜想是由英國提出的。1852年，畢業於倫敦大學的弗朗西斯·格思裏(Francis guthrie)來到壹家科研單位做地圖著色時，發現了壹個有趣的現象:“似乎每張地圖都可以用四種顏色著色，這樣同樣邊界的國家就用不同的顏色著色了。”這種現象可以用數學方法嚴格證明嗎？他和正在讀大學的弟弟格萊斯決心試壹試。兩兄弟用來證明這個問題的稿紙已經堆了壹堆，但研究工作壹直沒有進展。
1852，10年10月23日，他的弟弟向他的老師——著名數學家德·摩爾根請教這個問題的證明。摩根也找不到解決這個問題的方法，於是他寫信給他的好朋友，著名數學家漢密爾頓爵士尋求建議。漢密爾頓收到摩爾根的信後，論證了四色問題。但是直到1865漢密爾頓去世，這個問題還是沒有解決。
1872年，當時英國最著名的數學家凱利正式向倫敦數學會提出了這個問題，於是四色猜想成為世界數學界關註的問題。世界上很多壹流的數學家都參加過四色猜想的大戰役。在1878到1880的兩年間，坎普和泰勒兩位著名的律師和數學家分別提交了證明四色猜想的論文，並宣布證明了四色定理。大家都以為四色猜想從此解決了。
坎普的證明是這樣的:首先指出，如果沒有壹個國家包圍其他國家，或者不超過三個國家在壹點相交，則稱這個地圖是“正則的”。如果是規則圖，否則就是不規則圖。壹張地圖往往由正規地圖和非正規地圖聯系在壹起，但非正規地圖所需的顏色數量壹般不會超過正規地圖所需的數量。如果有壹張地圖需要五色，說明它的正規地圖是五色的。要證明四色猜想，只要證明不存在有規律的五色地圖就夠了。
坎普用歸謬法證明了這壹點，大意是:如果有壹個正則五色地圖，就會有壹個國家數最少的“極小正則五色地圖”。如果極小正則五色圖中有壹個鄰國少於六個的國家，那麽就會有壹個國家較少的正則圖仍然是五色的，所以就不會有極小五色圖的國家，也就不會有正則五色圖。於是坎普以為自己證明了“四色問題”，但後來人們發現他錯了。
但是，肯普的證明澄清了兩個重要概念，為以後解決問題提供了壹個思路。第壹個概念是“配置”。他證明了在每個正則圖中，至少壹個國家有兩個、三個、四個或五個鄰國，不存在每個國家都有六個或更多鄰國的正則圖。也就是說，壹組由兩個鄰國、三個鄰國、四個或五個鄰國組成的“配置”是不可避免的，每張地圖至少包含這四種配置中的壹種。
坎普提出的另壹個概念是可還原性。“可協商”壹詞的使用來自坎普的論證。他證明了五色地圖中只要有壹個國家有四個鄰國，就會有壹個國家較少的五色地圖。自從“構形”和“可約性”的概念被提出以來，壹些檢驗構形以確定它們是否可約的標準方法逐漸被發展起來，可以找到可約構形的必然群，這是證明“四色問題”的重要基礎。但是要證明壹個大的配置是可約的，需要查很多細節，相當復雜。
11年後，也就是1890年，年僅29歲、就讀於牛津大學的赫伍德用自己的精確計算指出了坎普證明中的漏洞。他指出，坎普提出的沒有最小五色地圖的國家不可能有五個鄰國的理由是有缺陷的。很快，泰勒的證明也被否定了。人們發現他們其實證明了壹個弱命題——五色定理。也就是說，給地圖塗上五種顏色就夠了。後來，越來越多的數學家為此絞盡腦汁，卻壹無所獲。於是，人們開始意識到，這個看似簡單的題目，其實是壹個堪比費馬猜想的難題。
自20世紀以來，科學家們基本上是按照肯普的想法證明四色猜想的。1913、美國著名數學家、哈佛大學boekhoff利用了Kemp的思想，結合了他的新思想；證明了壹些大的構形是可約的。後來，美國數學家富蘭克林在1939中證明了22個國家以下的地圖可以用四種顏色著色。1950有人從22國晉級35國。1960中證明了39個國家以下的地圖只用四種顏色就可以著色；然後推進到50個國家。看來這個進度還是很慢的。
高速數字計算機的發明促使更多的數學家研究“四色問題”。從1936開始研究四色猜想的Heck公開宣稱，可以通過尋找可約圖的必然群來證明四色猜想。他的學生圖雷寫了壹個計算程序。Heck不僅可以用這個程序生成的數據證明構型的可約性，還可以通過將映射轉化為數學上稱為“對偶”的形狀來描述可約構型。
他標出每個國家的首都，然後用壹條穿越邊境的鐵路把鄰國的首都連接起來。除了首都(稱之為頂點)和鐵路(稱之為弧或邊)之外，其他所有的線都被抹掉了，剩下的稱為原圖的對偶圖。在20世紀60年代後期，Heck引入了壹種類似於在電網絡中移動電荷的方法來尋找不可避免的壹組配置。在赫克的研究中第壹次以相當不成熟的形式出現的“放電法”，是以後研究必然群的壹把鑰匙，是證明四色定理的壹個中心要素。
電子計算機出現後，由於計算速度的快速提高和人機對話的出現，四色猜想的證明過程大大加快了。美國伊利諾伊大學的哈肯在1970開始改進“放電過程”，然後和Appel壹起編了壹個很好的程序。1976年6月，他們在美國伊利諾伊大學兩臺不同的電子計算機上，花費了1200個小時，做出了1000億次判斷，最終完成了四色定理的證明，在世界上引起了轟動。
這是100多年來吸引了眾多數學家和數學愛好者的壹件大事。當兩位數學家發表他們的研究成果時，當地郵局給當天寄出的所有郵件蓋上了“四種顏色就夠了”的特別郵戳，以慶祝這壹難題的解決。
“四色問題”被證明只是解決了壹個持續了100多年的難題，它成為數學史上壹系列新思想的起點。在“四色問題”的研究過程中，出現了許多新的數學理論，發展了許多數學計算技巧。比如把地圖的著色問題變成圖論問題，豐富了圖論的內容。不僅如此，“四色問題”還在有效設計航空公司航班時刻表和設計計算機編碼程序中發揮了作用。
然而，許多數學家並不滿足於計算機所取得的成就。他們認為應該有壹個簡單明了的書面證明方法。時至今日，許多數學家和數學愛好者仍在尋找更簡潔的證明方法。