九色定理

九色定理

九色定理很重要。

起源

又叫Heawood定理。人類在企圖證明四色定理過程中,發現了在曲面上作圖,反而更加容易。1974年德國的林格和美國的楊斯證明了:Np=[(7+√1+48P)/2].證明這個公式,數學家用了78年。P是指這個曲面的洞的個數,又叫虧格。當虧格為3時: N3=[(7+√1+48×3)/2]=9(公式來源:《圖論導引》214頁,機械工業出版社,《圖論導引》258頁,人民郵電出版社)
《圖論和網路流理論》239頁,高等教育出版社

介紹

。需要9種顏色染色的圖形:(王曉明王蕊珂畫圖構造)下圖是全景圖,上圖:上下對摺,再左右對摺,形成一個汽車輪胎形狀,就是有7個區域兩兩相連,再把含有區域8和區域9的三叉管子安裝在輪胎上的含有區域8和區域9的位置上,就是一個有3個洞的(類似方向盤形狀)的曲面,有9個區域兩兩相連。
9色定理圖片9色定理圖片

表明:在有三個洞的曲面上染色,8種顏色是不夠的。
如果能夠將一個圖G畫在平面上,使得他的邊僅僅在端點相交,則稱這個圖是可以嵌入平面的,或者稱其為平面圖。
證明部分在證明四色定理過程中,
Heawood的文章不僅僅指出了Kempe的錯誤,而且也給出了五色定理的一個證明,然而他沒有停留於此,Heawood繼續考慮其它一些想法,Heawood文章的主要後續成果是征對於可嵌入到球面的圖的最大色數問題。Heawood把注意力轉移到其它曲面上圖的色數確定問題上。
對於非負整數k,設
χ(Sκ)=max{χ(G)}.
其中,max取遍嵌入到Sx的所有圖G,自Kempe的1879年的文章之後,大家都相信χ(Sò)=4,而在Heawood的1890年的文章之後,僅僅知道χ(Sò)=4,或者χ(Sò)=5.
1976年當Appel和Haken宣布其成果之後,確定了χ(Sò)=4(四色定理)。
在Heawood的1890年的文章中,他試圖獲得關於χ(Sκ)的一個公式,在其中k為正整數,事實上,他認為他已經做到了,然而,他所做的僅僅是獲得了χ(Sκ)的一個上界。
定理;對於每一個正整數k,
χ(Sκ)≤[(7+√1+48K))/2]
證明:(直接證法)設G為看嵌入到Sκ的一個圖,並且設
h=[(7+√1+48K)/2],
由h的定義可以證明:
6+12(k-1)/h=h-1
下面證明χ(G)≤h
在G的所有誘導子圖中,設H具有最大的最小度,根據定理:對每個圖G,
X(G)<1+max{S(H)}
其中,max取遍G的所有誘導子圖H。
可以得到X(G)≤1+δ(H),假設H的階為n,邊數為m,若n≤h,則δ(H)≤n-1,X(G)≤n≤h,因此我們可以假設n>h.
由於G可以嵌入到Sk,所以,H也能夠嵌入到Sk,因此由推論可知
K>γ(H)≥m/6-n/2+1,
易見,m≤3n+6(k-1),因此nδ(H)≤Σdegu=2m≤6n+12(k-1)所以,
δ(H)≤6+12(k-1)/n≤6+12(k-1)/h=h-1。從而,X(G)≤1+δ(H)=h=[(7+√1+48k)/2]。
,結論成立。
證明這個公式對於所有整數k成立又花費了78年。數學家GerhardRingel和TedYoung對這個公式的證明發揮了最主要的作用。王曉明王蕊珂構造圖形使得工作最後完成。
上下對摺再左右對摺就是一個輪胎形狀,有7個區域兩兩相連。它有1個洞。1974年德國數學家林格(GerhardRingel)和美國數學家楊斯(TedYoungs)證明:Np=[(7+√1+48k)/2];k表示洞的數目。N3=[(7+√1+48x3)/2]=9,當k=3時,N3=9。

相關詞條

相關搜尋

熱門詞條

聯絡我們