四色問題演算法

❶ 「四色定理」在實際中有什麼應用

四色定理是圖的著色問題的一個結果。圖的著色本質是給圖中的頂點貼標簽（labeling），但是要滿足一定的條件。「色」只是一種標簽。

四色定理的描述雖然提到了地圖，但是地圖繪制並不需要四色定理：他只要著色，不需要用最少的顏色。實際畫地圖時一般不用四種顏色。

著色問題的應用，主要排程和分配問題上。
比如我有幾個任務，每個任務都需要一天。而我知道其中幾樣任務是沖突的，不能安排在同一天完成。現在我希望四天完成。這就是四色問題了：所用的圖以任務為頂點，沖突的任務間連邊，用日期做顏色，對圖著色。

再比如我有一些員工，我希望把他們分成四個小組。但是我知道其中幾個員工互相之間有矛盾，不能安排在同一組。那麼這又是四色問題：所用的圖以員工為頂點為，矛盾的員工間連邊，用組做顏色，對圖著色。

四色定理說：如果上面提到的圖是平面圖（有高效演算法判定），那麼可能四天完成／可能分成四組。

❷ 四色定理是什麼

四色定理的誕生過程
世界近代三大數學難題之一(另外兩個是費馬定理和哥德巴赫猜想)。四色猜想的提出來自英國。1852年，畢業於倫敦大學的弗南西斯·格思里(Francis Guthrie)來到一家科研單位搞地圖著色工作時，發現了一種有趣的現象：「看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家著上不同的顏色。」這個結論能不能從數學上加以嚴格證明呢？他和在大學讀書的弟弟格里斯決心試一試。兄弟二人為證明這一問題而使用的稿紙已經堆了一大疊，可是研究工作沒有進展。

1852年10月23日，他的弟弟就這個問題的證明請教他的老師、著名數學家德·摩爾根，摩爾根也沒有能找到解決這個問題的途徑，於是寫信向自己肆渣的好友、著名數學家哈密爾頓爵士請教。哈密爾頓接到摩爾根的信後，對四色問題進行論證。但直到1865年哈密爾頓逝世為止，問題也沒有能夠解決。

1872年，英國當時最著名的數學家凱利正式向倫敦數學學會提出了這個問題，於是四色猜想成了世界數學界關注的問題。世界上許多一流的數學家都紛紛參加了四色猜想的大會戰。1878～1880年兩年間，著名的律師兼數學家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認為四色猜想從此也就解決了。

11年後，即1890年，數學家赫伍德以自己的精確計算指出肯普的證明是錯誤的。不久，泰勒的證明也被人們否定了。後來，越來越多的數學家雖然對此絞盡腦汁，但一無所獲。於是，人們開始認識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題：先輩數學大師們的努力，為後世的數學家揭示四色猜想之謎鋪平了道路。

進入20世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在進行。1913年，伯克霍夫在肯普的基礎上引進了一些新技巧，美國數學家富蘭克林於1939年證明了22國以下的地圖都可以用四色著色。1950年，有人從22國推進到35國。1960年，有人又證明了39國以下的地圖可以只用四種顏色著色；隨後又推進到了50國。看來這種推進仍然十分緩慢。電子計算機問世以後，由於演算速度迅速提高，加之人機對喚渣話的出現，大大加快了對四色猜想證明的進程。1976年，在J. Koch的演算法的支持下，美國數學家阿佩爾(Kenneth Appel)與哈肯(Wolfgang Haken)在美國伊利諾斯大學的兩台不同的電子計算機上，用了1200個小時，作了100億判斷，終於完成了四色定理的證明。四色猜想的計算機證明，轟動了世界,當時中國科學家也有在研究這原理。它不僅解決了一個歷時100多年的難題，而且有可能成為數學史上一系列新思維的起點。

證明方法
證明方法將地圖上的無限種可能情況減少為1,936種狀態（稍後減少為1,476種），這些狀態由計算機一個挨一個的進行檢查。這一工作由不同的程序和計算機獨立的進行了復檢。在1996年，Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas使用了一種類似的證明方法，檢查了633種特殊的情況。這一新證明裂鏈悄也使用了計算機，如果由人工來檢查的話是不切實際的。
（不過最近，在一個叫「東陸論壇」的數學性論壇里看見一個推理性的圖論證明。）

四色定理的重要
四色定理是第一個主要由計算機證明的理論，這一證明並不被所有的數學家接受，因為它不能由人工直接驗證。最終，人們必須對計算機編譯的正確性以及運行這一程序的硬體設備充分信任。
缺乏數學應有的規范成為了另一個方面；以至於有人這樣評論「一個好的數學證明應當像一首詩——而這純粹是一本電話簿！」

德·摩爾根：地圖四色定理

地圖四色定理最先是由一位叫古德里（Francis Guthrie）的英國大學生提出來的。德•摩爾根（A，DeMorgan，1806～1871）1852年10月23日致哈密頓的一封信提供了有關四色定理來源的最原始的記載。他在信中簡述了自己證明四色定理的設想與感受。一個多世紀以來，數學家們為證明這條定理絞盡腦汁，所引進的概念與方法刺激了拓撲學與圖論的生長、發展。1976年美國數學家阿佩爾（K.Appel）與哈肯（W.Haken）宣告藉助電子計算機獲得了四色定理的證明，又為用計算機證明數學定理開拓了前景。以下摘錄德•摩爾根致哈密頓信的主要部分，譯自J． Fauve1 and J.Gray（eds.），The History of Mathematics ：A Reader，pp． 597～598。

德·摩爾根致哈密頓的信（1852年10月23日）

我的一位學生今天請我解釋一個我過去不知道，現在仍不甚了了的事實。他說如果任意劃分一個圖形並給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那麼需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子。現在的問題是是否會出現需要五種或更多種顏色的情形。就我目前的理解，若四個不訂分割的區域兩兩具有公共邊界線，則其中三個必包圍第四個而使其不與任何第五個區域相毗鄰。這事實若能成立，那麼用四種顏色即可為任何可能的地圖著色，使除了在公共點外同種顏色不會。

現畫出三個兩兩具有公共邊界的區域ABC，那麼似乎不可能再畫第四個區域與其他三個區域的每一個都有公共邊界，除非它包圍了其中一個區域。但要證明這一點卻很棘手，我也不能確定問題復雜的程度一對此您的意見如何呢？並且此事如果當真，難道從未有人注意過嗎？我的學生說這是在給一幅英國地圖著色時提出的猜測。我越想越覺得這是顯然的事情。如果您能舉出一個簡單的反例來，說明我像一頭蠢驢，那我只好重蹈史芬克斯的覆轍了……。
參考資料：http://ke..com/view/43945.html

❸ 什麼是四色定理

四色定理（世界近代三大數學難題之一），又稱四色猜想、四色問題，是世界三大數學猜想之一。四色定理的本質正是二維平面的固有屬性，即平面內不可出現交叉而沒有公共點的兩條直線。

很多人證明了二維平面內無法構造五個或五個以上兩兩相連區域，但卻沒有將其上升到邏輯關系和二維固有屬性的層面，以致出現了很多偽反例。

不過這些恰恰是對圖論嚴密性的考證和發展推動。計算機證明雖然做了百億次判斷，終究只是在龐大的數量優勢上取得成功，這並不符合數學嚴密的邏輯體系，至今仍有無數數學愛好者投身其中研究。

(3)四色問題演算法擴展閱讀

四色定理證明的關鍵可以歸納為二維平面內兩條直線相交的問題。

1、將地圖上不同的區域用不同的點來表示。

2、點與點之間的連線用來表示地圖上兩區域之間的相鄰邏輯關系，所以,線與線之間不可交叉（即不可存在交叉而沒有公共交點的情況），否則就超越了二維平面，而這種平面暫時稱它為邏輯平面，它只反應區域之間的關系，並不反應實際位置。

通過以上的變換處理，可以將對無窮盡的實際位置的討論，變為有條理可歸納的邏輯關系的討論，從而提供了簡單書面證明的可行性。

❹ 四色問題C語言怎麼解決

思路：建立數據結構，錄入數據內容，遍歷著色，輸出第一個可行的著色方案。

下面就四個方面詳細分析一下

首先分析數據結構：

對於地圖，一個區塊包含一個唯一編號數據（這個編號可以是地名，也可以是數字）用來區分該區塊和其他區塊的不同

另外要著色，還要考慮該區塊和其他區塊連接的情況

最後就是區塊本身的顏色

羨讓慎通過上面的分析，即可建立如下數據結構：

structarea{
intnID;//這里以數字替代兄敬名稱，作為地塊的唯一標識
intnColor;//用1,2,3,4表示不同的顏色，用0表示還沒有著色
area*pNei;//鄰接的區塊
intnNei;//鄰接區塊的數量
};

然後需要錄入數據，這個請依據具體的地圖進行處理，撰寫相應的錄入函數，填入上面的數據結構

假設錄好的數據如下：

structareacity[64];//假設已經錄制好了數據，初始所有城市顏色都為0

數據錄好後，我們可以如下方式進行遍歷，嘗試著色

遍歷分為個模塊：一個是遍歷模塊，一個是校驗模塊

校驗模塊依序檢查所有的城市和其鄰接城市是否存在同色的情況，是則返回false，否則返回true

遍歷模塊則逐個城市進行上色嘗試

可以考慮遞歸

下面給一個遞歸的示例：

檢測模塊：

boolisOk(){
for(inti=0;i<64;i++)//假設有64個城市，其初始值和城市關系已經錄制完畢
{
for(intj=0;j<city[i].nNei;j++){
if(nColor==city[i].pNei[j].nColor)
returnfalse;
}
}
returntrue;
}

遍歷遞歸模塊：

booladdcity(intnIndex){
if(nIndex>=64)returntrue;//所有城市都著色了，則返回成功
for(inti=1;i<=4;i++){
city[nIndex].nColor=i;
if(isOk()){//本城市的顏色找到了
if(addcity(nIndex+1)==true){//找下一個城市的顏色
滑瞎returntrue;
}else{//無法為下一個城市著色
continue;//更改本城市顏色
}
}
}
returnfalse;//沒有一個顏色可行，返回上一級，重新尋找
}

調用的時候可以採用下面的方式：

if(addcity(0)==false){
printf("無法找到答案，四色定理錯誤！
");
}else{
printf("找到了答案，城市和著色結果如下：
");
for(inti=0;i<64;i++){
printf("city%03dcolor%d
",city[i].nID,city[i].nColor);
}
}

❺ 什麼是四色定理

四色定理

四色地圖的一個例子四色定理指出每個可以畫出來的地圖都可以至多用簡猜4種顏色來上色，而且沒有兩個相接的區域會是相同的顏色。被稱為相接的兩個區域是指他們共有一段邊界，而不是一個點。

這一定理最初是由Francis Guthrie在1853年提出的猜想。很明顯，3種顏色不會滿足條件，而且也不難證明5種顏色滿足條件且綽綽有餘。但是，直到1977年四色猜想才最終由Kenneth Appel 和Wolfgang Haken證明。他們得到了J. Koch在演算法工作上的支持。

證明方法將地攔敏型圖上的無限種可能情況減少為1,936種狀態（稍後減少為1,476種），這些狀態由計算機一個挨一個的進行檢查。這一工作由不同的程序和計算機獨立的進行了復拿和檢。在1996年，Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas使用了一種類似的證明方法，檢查了633種特殊的情況。這一新證明也使用了計算機，如果由人工來檢查的話是不切實際的。

四色定理是第一個主要由計算機證明的理論，這一證明並不被所有的數學家接受，因為它不能由人工直接驗證。最終，人們必須對計算機編譯的正確性以及運行這一程序的硬體設備充分信任。參見實驗數學。

缺乏數學應有的規范成為了另一個方面；以至於有人這樣評論「一個好的數學證明應當像一首詩——而這純粹是一本電話簿！」

❻ 四色定理 要Pascal

四色定理又稱四色猜想、四色問題，是世界三大數學猜想之一。四色定理是一個著名的數學定型寬喚理，通俗的說法是：每個平面地圖都可以只用四種顏色來染色，而且沒有兩個鄰接的區域顏色相同。1976年藉助電子計算機證明了四色問題，問題也終於成為定理，這是第一個藉助計算機證明的定理。四色定理的本質就是在平面或者球面無法構造五個或者五個以上兩兩相連的區域。
雖然任何平面地圖可以只用四個顏色著色，但是這個定理的應用卻相當有限，因為現實中的地圖常會出現飛地，即兩個不連通的區域屬於同一個國家的情況（例如美國的阿拉斯加州），而製作地圖時我們仍會要求這兩個區域被塗上同樣的顏色，在這種情況下，只用四種顏色將會造成諸多巧運不便。
實際中用四種顏色著色的地圖是不多見的，而且這些地圖往往最少只需要三種顏色來卜凱染色。此外，即便地圖能夠只用四種顏色染色，為了區分起見，也會採用更多的顏色，以提示不同地區的差別。

❼ 四色問題

四色問題 和我們上一篇文章所提到的一筆畫問題都是圖論中的重要問題,這個問題的提出還要追溯到19世紀。
1852年，英國的大學生 兄弟在給英國地圖上色時發現,想要讓任意兩個有公共邊界的曲域顏色不同，似乎只需要四種顏色就夠了。但是他們自己證明不了這個結論，於是向數學家 摩根 求教。摩根很容易證明出了三種顏色是不夠的，需要至少三種顏色，但是並沒有解決這個問題。而且當時這個問題並沒有得到數學家們的重視。
直到1878年，英國數學家凱萊在《倫敦數學會文集山虛》上發表《論地圖著色問題》的文章。由此才引起了數學界更大的注意。

因為很長一段時間內四色問題並沒有得到較好的解決，於是數學家們退而求其次，希望先證明更弱的命題。
很快地，數學家們也得出了局唯鬧兩個更弱的結論：
1 .「五色問題」是成立的。
2 .對於有限個國家的地圖著色問題，四種顏色是足夠的。
這里我們發現，有時候退而求其次，先解決更弱的數學問題也是一種數學素養。

直到1976年，美國伊利諾伊大學的哈肯和阿佩爾根據前人的演算法，在計算機的幫助下，耗時1200小時，最終證明了四色猜想。
四色問題是人類第一次使用計算機解決並證明數學問題，不桐罩得不說這是數學發展史上的一大步.