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