tft每日頭條

 > 圖文

 > 拉鍊定理證明

拉鍊定理證明

圖文 更新时间:2024-11-24 19:42:13

拉鍊定理證明(四色定理證明)1

圖1

如圖1,這是一幅重慶市地圖,我們可以把其中的每個區縣級行政區都看作一個點,隻要兩個行政區是相鄰的,就可以連接表示這兩個行政區的兩點,這樣,行政區的相鄰關系就可以表示成兩個點之間的連接關系。可以看出,此連接圖由許多三角形組成,三角形的各個頂點代表各個行政區,兩點之間的連接線代表行政區的相鄰關系。

拉鍊定理證明(四色定理證明)2

圖2

再看圖2: 圖2此圖由許多小的等邊三角形組成,我們按如圖所示的着色規律為其分别着上顔色。可以看出,此圖有四種不同顔色小三角形,且同色小三角形互不相鄰。 然後,我們為這些不同顔色的小三角形各頂點着上顔色,着色規律為:頂點的着色必須與其為中點并向周圍輻射的六個小三角形顔色不同(如圖3)。

拉鍊定理證明(四色定理證明)3

圖3

仔細觀察此圖,我們可以看出,頂點的着色實際上隻有一種選擇,共有四種不同顔色的頂點,且顔色相同的頂點互不相鄰。 圖3我們可以把圖3看作一個标準圖,根據需要,此圖可無限擴大。圖1與圖3不同,其三角形不是等邊的(三角形是否等邊不重要,關鍵是每個頂點之間的連接關系),且以每個頂點為中點向周圍輻射的三角形數量也往往不是六個,即圖1不是“标準圖”。這樣看來,我們不能把圖1頂點的着色規律應用于圖3,但實際上,我們可以采用一些技巧使圖1的各個頂點能以四種顔色完全區分,也即是可以以4種顔色完全區分各行政區。在實際處理中,我們可以使圖1盡量“标準化”,而那些不能标準化的情形,需進行區别處理,這些處理使非“标準化”情形造成的問題局限化,而不緻“牽一發而動全身”,下面就一些不同情形分别進行講述。假如由頂點向四周輻射的三角形數量小于6個,即5個、4個和3個,那麼情形就會分别如下3圖(圖4、圖5、圖6,此3圖黑色線段代表與标準圖不同的頂點連接關系):

拉鍊定理證明(四色定理證明)4

圖4

圖4:由頂點向四周輻射的三角形數量為5個

拉鍊定理證明(四色定理證明)5

圖5

圖5:由頂點向四周輻射的三角形數量為4個

拉鍊定理證明(四色定理證明)6

圖6

圖6:由頂點向四周輻射的三角形數量為3個

我們可以看到,上述情形頂點在空間上仍可均勻分布(當然需要一定的等效處理),隻是改變了标準圖中頂點的連接關系,而改變了頂點的連接關系後,仍不會出現顔色相同的頂點相互連接的情況,即上述這些情形仍可用四種顔色把各個頂點區分開來。假如由頂點向四周輻射的三角形數量大于6個,那麼必須根據其是奇數個(如7個),或偶數個(如8個)的情形分别進行處理。處理方式如下兩圖:

拉鍊定理證明(四色定理證明)7

圖7

圖7 頂點周圍有7個輻射三角形,如果輻射三角形數為大于等于7的奇數,隻需在此圖增加點的黑色線段上再加上2n個點并作相應連接即可,顯然,為這些多出的點着上不矛盾的顔色是很容易的:為方便理解,圖中虛線線段代表新增點與其它點(非輻射中心點及非輻射中心點周圍連接點)之間的連接關系,顯然,這些虛線線段不能經過兩個及兩個以上三角形。

拉鍊定理證明(四色定理證明)8

圖8

圖8 頂點周圍有8個輻射三角形,如果輻射三角形數為大于8的偶數,隻需在此圖上增加點的黑色線段上加上2n個點并作相應連接即可,顯然,為這些多出的點着上不矛盾的顔色也是很容易的。 通過上述的圖形描述(直接上圖更直觀,更易理解),我們對各種非“标準化”情形進行了相應的處理,使得各種非“标準化”所導緻的困擾局限化,也就是前面所說的不會“牽一發而動全身”。 再回到前面所說的地圖中不能“三角化”的情形,如“國中國”,顯而易見,在這些情形下其實具有更多的着色選擇,這裡不作說明。 這是我在研究四色定理中得出的一些東西,可算作證明,有的東西寫得并不太具體,更多的是用圖作說明,因為看圖就可以做出顯而易見的推斷。根據以上的語言描述及圖示的處理方法,應該可設計一種并不複雜的計算機程序對任何簡單或複雜的地圖進行着色(國家或行政區的着色應與代表其的頂點顔色一緻),隻需四種顔色,而且不會出現着色矛盾。我曾經把這種方法用于加德納四難着色圖,很容易就解決了問題。另外,再把圖1及标準圖和萬維網的連接方式對比一下,是不是很有趣? 四色定理所蘊含的東西并不隻涉及圖論,萬物理相通,比如标準圖實際上有分形性質(最簡單的分形),具備自相似性:等邊三角形,1/2等邊三角形,1/4等邊三角形,如此無限下去,如圖9:

拉鍊定理證明(四色定理證明)9

圖9

圖9在此标準圖中,若最小等邊三角形邊長為1,則以其為中心的邊長為2的n次方的三角形如選擇着色與中心最小三角形顔色相同,就不會與其周邊小三角形出現着色矛盾,這種規律,我們可以理解為一種着色的分形,如圖10:

拉鍊定理證明(四色定理證明)10

拉鍊定理證明(四色定理證明)11

圖10

圖10 還可以發現其它的着色分形規律,這裡不作詳解。另外,上述方法及規律可以拓展到三維,隻是标準圖由多個等邊三角形變成了多個正四面體,頂點由二維變成了三維,有興趣大家可以研究一下。另外,從此分形圖還可以看出,低一層級的三角形數量為高一層級三角形數量的四倍,可以這樣認為:如二進制為數字的一維表達,那麼四進制就是數字的二維表達;再想想正四面體,八進制就是二進制的三維表達。

,

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关圖文资讯推荐

热门圖文资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved