四色定理

2021-02-08 FHM 2K

四色定理(世界近代三大數學難題之一),又稱四色猜想、四色問題,是世界三大數學猜想之一。四色定理的本質正是二維平面的固有屬性,即平面內不可出現交叉而沒有公共點的兩條直線。很多人證明了二維平面內無法構造五個或五個以上兩兩相連區域,但卻沒有將其上升到邏輯關係和二維固有屬性的層面,以致出現了很多偽反例。不過這些恰恰是對圖論嚴密性的考證和發展推動。計算機證明雖然做了百億次判斷,終究只是在龐大的數量優勢上取得成功,這並不符合數學嚴密的邏輯體系,至今仍有無數數學愛好者投身其中研究。

四色問題又稱四色猜想、四色定理,是世界近代三大數學難題之一。地圖四色定理(Four color theorem)最先是由一位叫古德裡(Francis Guthrie)的英國大學生提出來的。

四色問題的內容是「任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。」也就是說在不引起混淆的情況下一張地圖只需四種顏色來標記就行。

用數學語言表示即「將平面任意地細分為不相重疊的區域,每一個區域總可以用1234這四個數字之一來標記而不會使相鄰的兩個區域得到相同的數字。」這裡所指的相鄰區域是指有一整段邊界是公共的。如果兩個區域只相遇於一點或有限多點就不叫相鄰的。因為用相同的顏色給它們著色不會引起混淆。

理論基礎

地圖上任何一個區域必將存在鄰域,且又通過鄰域與其他非鄰域發生間接聯繫,可以將任何一個地圖以圖論圖形的表示出來。

假設存在一張至少需要m種著色的地圖,那麼決定該地圖必須要用m種著色的條件有且只有一個,即該地圖至少存在這樣一個區域Q,與該區域相鄰的所有區域必須滿足m-1著色。首先滿足這個條件後,Q只能用第m種顏色,其次如果這個推論一是錯誤的,對於m著色地圖不存在這樣的區域,那麼地圖上任何一個區域的鄰域只能滿足少於m-1的著色,那麼整個地圖勢必不需要m種顏色,這與假設相矛盾,所以這是一個充分必要條件。(推論一)

假設隨意取一張任意結構的至少m著色的地圖M,其上滿足上述條件的區域有n個,那麼將圖論圖形中的這n個區域及其與鄰域的關係線我們可以全部去掉,這樣我們就將構建一個至少m著色地圖M的問題轉化成了一個在至少需要m-1著色地圖上添加n個滿足推論一條件的區域問題。

如果五著色地圖存在且能構建成功,那麼必然存在構建這樣五著色的四著色模型圖,而要存在這樣的四著色模型圖必然存在構建該四著色的三著色模型圖,同理要存在這樣的三著色模型圖必然要存在構建它的二著色模型圖,那麼我們來構建一下五色圖是否存在。


二著色地圖

二著色地圖是由一著色而來的一種簡單的著色地圖模型,我們很容易得到滿足二著色的地圖僅有的兩種類型的結構,一種是不閉合的鏈狀結構;另一種是由第一種衍生出來的閉合的環狀結構且環所聯繫的區域為偶數個,稱為偶數環。

二著色結構特點是奇偶位置決定著色,任何兩個區域的任何聯繫鏈條只有相隔偶數個區域才滿足兩區域著色不同,我們定義這兩個區域為偶隔域。


三著色地圖

我們隨意取一張任意結構的二著色的地圖M,來構建一個具有n個滿足推論一條件區域的地圖Q,構建方式有且只有一個,就是在圖論圖形中我們如何去掉的這n個區域及其與鄰域的關係線,我們接怎麼給它添加回去。我們任取這n個區域中一個區域q為例,只要我們在M地圖上將必須滿足二著色的幾個區域W直接聯繫到q上,這樣就滿足推論一中的條件而使Q必須為三著色。而W要滿足二著色則必定含有偶隔域,如果W有x個區域和q發生直接聯繫,則q上出去的關係線有x個,那麼我們一定可以將該複雜的聯繫分解成x-1個不可分解關係環,其中至少有一個不可再分的關係環是M中的偶隔域與q聯繫的,(推論二)假設這個推論是錯誤的,所有不可再分的環全部是奇隔域,那麼這些環拼接回去時滿足每個小環的間隔區域數相加再減去共用的區域,仍舊是奇隔域,這樣W便不滿足二著色,所以這些不可再分環中一定有偶隔域和q發生聯繫而構成奇數環(環連的區域為奇數),並且導致q必須使用第三色的就是這些不可再分的奇數環。由於滿足二著色的只有偶隔域一種條件,那麼構造的三著色地圖中決定三著色的條件也只有一種,存在不可再分的奇數環。

相關焦點

  • 四色定理用於解析晶體磁性能
    這一情況如今正適用於數學領域的四色定理。這條幾百年前被最初一代製圖師們用於繪製地圖的理論,如今竟可用來了解晶體結構及複雜材料的磁性能。  「是否能只用四種顏色,就為所有地圖染色?」這一命題最早在1852年由一位英國製圖員提出。他的疑問是,能否每張不出現飛地(即兩個不連通的區域屬於同一個國家的情況)的地圖,都可以用不超過四種顏色染色,且不會有兩個相鄰地區顏色相同?
  • 數統攻略 | 四色定理—你get到了嗎?
    地圖四色定理(Four color theorem)最早是在1852年,由一位叫古德裡(Francis Guthrie)的英國大學生提出來的。四色問題的內容是「任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。」
  • 百年世界難題「四色定理」被於成仁老師成功證明
    近日,吉林市數學協會於成仁老師宣布:成功運用數學方法證明出世界三大數學難題之一的「四色定理」。這意味著沉寂百年的世界數學難題,由中國人填補了空白。「四色猜想」是著名的數學定理,自1852年提出以來已有164年。
  • 地圖上的數學難題——四色定理
    四色猜想的本質是在平面或者球面無法構造有五個或者五個以上的兩兩相連的區域,如果有五個以上兩兩相連區域,第五個區域至少與一個區域同一種顏色。1852年,一位畢業於倫敦大學的製圖員格斯裡來到一家科研單位做地圖著色工作。
  • 九天攬月一一敢峰證明四色定理之謎
    :倪振良     四色定理,是1850年英國的一位繪圖員弗朗塞斯·古斯裡提岀的。他說證明了四色定理,我們的第一感覺是:他決不是虛誇,會是真的!     然而,敢峰的學歷、工作崗位、桂冠,似乎與四色定理風馬牛不相及,這又究竟是怎麼一回事啊?!
  • 四色定理新用途:可解析晶體結構及複雜材料的磁性能
    原標題:四色定理新用途:可解析晶體結構及複雜材料的磁性能   原標題:四色定理用於解析晶體磁性能   疇結構可用四色定理來理解,它們的圖案及相關著色方案,與材料的磁特性密切相關。如圖所示,a圖中的晶體材料的疇結構,依照四色定理可染色為b圖「模樣」;而c圖中第二種晶體材料,需依照特殊版本四色定理,染色後為d圖,顯示為紅藍綠三種顏色中的深色或淺色。   科技日報訊 (記者張夢然)有時候,一條理論所產生的影響,遠遠超出其誕生的初衷。這一情況如今正適用於數學領域的四色定理。這條幾百年前被最初一代製圖師們用於繪製地圖的理論,如今竟可用來了解晶體結構及複雜材料的磁性能。
  • 四色定理 - 區分地圖上的每個區域我們需要幾種顏色?
    高速數字計算機的發明,促使更多數學家對「四色問題」的研究。計算機問世以後,由於演算速度迅速提高,加之人機對話的出現,大大加快了對四色猜想證明的進程。就在1976年6月,在美國伊利諾伊大學的兩臺不同的電子計算機上,用了1200個小時,作了100億判斷,結果沒有一張地圖是需要五色的,最終證明了四色定理,轟動了世界。
  • 「約當定理「攜手「鴿籠法則」可演繹證明四色猜想成立
    數學界於是就把猜想變成了定理,可惜多年以後殺出個希伍德,又把定理變回了猜想。希伍德的反例不是四色猜想的反例,是肯普證法的反例,他使肯普的四色猜想證明落空了,但四色猜想並沒有證否。希伍德也沒有完全抹殺肯普的成果,根據「不可避免集」,存在五色圖總是可約的,於是用數學歸納法證明得到了五色定理。希伍德的反例,肯普無法解決。根據希伍德的說明,肯普的錯誤在於證明5鄰國是可約構形時,構造兩條肯普鏈以換色,然而第二次換色時,肯普的方法並不總是成功的。
  • 【數學文化】「四色問題」是什麼?
    然而到1890年,一位大學數學講師希伍德指出肯普的「證明」中有一個漏洞,然後,他應用肯普的方法給出一個定理——五色定理,也就是五色足夠。儘管四色定理沒有得到證明,肯普和希伍德對於後來圖論的發展都作出決定性的貢獻。
  • 四色猜想到底被證明出來了嗎?
    四色定理是世界近代三大數學難題之一,其證明難度足以媲美費馬大定理,迄今為止,尚無人能從理論上證明四色定理。1852年,一位大學生古德裡在對地圖進行著色工作中驚訝地發現,每副地圖只需用四種顏色就可以實現不混淆的目的。什麼意思呢?
  • 關於四色問題有一些想法
    所謂四色問題,最初是由地圖塗色而來四色問題現在應該叫做四色定理,藉助計算機,數學家到目前為止給出了前後共計三代的機器證明計算機的解法大致思路是利用窮舉法,驗證經過歸納的、有限種情況的可約構形「四色」都成立;然後再利用另外的程序進行驗證
  • 四色問題 | 數學名題(3)
    戳上方藍字關注【克勞利中文俱樂部】(ID:CrawleyChineseClub)四色定理也因其為首個藉助計算機完成的證明
  • 讀書 四色問題的歷史故事
    《四色足夠》最早在2002年出版,今年再版時改成全彩印刷。《四色足夠》寫的是數學史上的「四色問題」。自從這個問題被提出後,幾乎所有的數學家都曾經對它發生過興趣。這個看似簡單的問題,從提出到解決,一共花了一百多年時間,直到現在依然有人對藉助計算機的證明方案持懷疑態度,甚至引發了對「證明」概念的哲學爭論。
  • 「四色問題」是什麼,這個問題為什麼能困擾數學家近半個世紀!
    不過,哈密頓對這類好像數學遊戲的問題不太感興趣,德·摩爾根於是繼續宣傳,直到另一位英國數學家凱萊於1878年在皇家學會上正式提出並在《皇家地理學會會報》上發表,這才引起人們對四色問題的廣泛重視。各國數學中心和數學雜誌都收到大量的錯誤證明,就如同以後的費馬大定理和哥德巴赫猜想一樣。
  • 這些數學中的有趣定理,你知道幾個?
    這個定理可以推廣到更高維的空間:對於任意一個偶數維的球面,連續的單位向量場都是不存在的。由此可以理解:由於地球表面的風速和風向都是連續的,因此由毛球定理,地球上總會有一個風速為 0 的地方,也就是說氣旋和風眼是不可避免的。
  • 世界難題四色猜想首次數學直接證明(完整版)——劉江
    四色問題:又稱四色猜想、四色定理,是世界近代三大數學難題之一。地圖四色定理(Four color theorem)最先是由一位叫古德裡(Francis Guthrie)的英國大學生提出來的。四色問題的內容是「任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。」也就是說在不引起混淆的情況下一張地圖只需四種顏色來標記就行。
  • 四色的地圖問題
    四色的地圖問題   1976年,著名的四色地圖問題由美國伊利諾斯大學的K·阿佩爾和W·哈肯用計算機給予了證明,但他們的計算機證明依然面臨著挑戰.   四色問題要求證明:每一張畫在平面上的地圖能夠只用四種顏色著色,使得所有鄰接的地域都有不同的顏色.
  • 四色右腦記憶法
    如果你羨慕別人過目不忘的本領
  • 三色學說與四色學說
    缺點:不能滿意的解釋色盲現象;四色學說(對抗學說opponent-color theory)1878年德國物理學家赫林提出對立顏色學說,又稱四色學說,其要點是:觀察到顏色現象總是以紅—綠、黃—藍、黑—白成對關係發生的。
  • uv印表機的四色印刷和專色印刷是什麼?
    理論上來說,uv印表機只要有三個顏色就能印出任何色彩效果與漸變色,但是印刷的基本色彩是四色印刷,CMYK這四個顏色組合的,而有的印刷還會加上專業印刷,那四色印刷和專業印刷有什麼區別呢?四色印刷的屬性和特點:1.所謂四色印刷是指採用黃、品紅、青三原色油墨和黑墨來印刷彩色圖案原稿的種種顏色的印刷工藝。2.四色印刷工藝適合的產品是用攝影機攝影的彩色相片、畫家的彩色美術作品或其他摻雜不同顏色的畫面,由於出於工藝上的要求或是出於經濟效益上的考慮,操作人員一般會採用四色印刷工藝來印刷完成。