四色問題的直觀幾何論證及單純性地圖四色定理

張士慶， 張 號

（1. 遼寧工程技術(shù)大學(xué)，遼寧 阜新123000；2. 中國礦業(yè)大學(xué)銀川學(xué)院，寧夏 銀川 750011；3. 廣東美的廚衛(wèi)電器制造有限公司，廣東 佛山 528300）

四色問題的直觀幾何論證及單純性地圖四色定理

張士慶1,2， 張 號3

（1. 遼寧工程技術(shù)大學(xué)，遼寧 阜新123000；2. 中國礦業(yè)大學(xué)銀川學(xué)院，寧夏 銀川 750011；3. 廣東美的廚衛(wèi)電器制造有限公司，廣東 佛山 528300）

對地圖染色問題的論證已困擾學(xué)術(shù)界160余年，根本原因在于它不是經(jīng)典數(shù)學(xué)問題，而人們總想用經(jīng)典數(shù)學(xué)方法去證明它。用直觀幾何方法將其轉(zhuǎn)換為染色等價的正規(guī)地圖，并嚴(yán)格證明“相鄰域定理”；建立并分析最小單元地圖的染色，發(fā)現(xiàn)了單純性和關(guān)聯(lián)性兩種地圖染色模式；建立基本單元地圖模型，創(chuàng)造由基本單元地圖模型成長為地圖的過程與染色相結(jié)合的直觀方法；嚴(yán)格證明四色定理：任何單純性地圖可以至多用4種顏色染色，而任何關(guān)聯(lián)性地圖所需顏色數(shù)目不確定；創(chuàng)造“縮滅法則”去簡化復(fù)雜地圖；舉出了《中國行政區(qū)劃正規(guī)地圖》應(yīng)用實例。

正規(guī)地圖；染色等價；單純性地圖；相鄰域；縮滅法則

“四色問題又稱四色猜想、四色定理”，自1850年前后提出以來，以“看起來最簡單”但又無法得到嚴(yán)格證明而“特別惹人注目”，成為“世界近代數(shù)學(xué)三大難題之一”。對“圖論”、“拓?fù)鋵W(xué)”的產(chǎn)生和發(fā)展影響深遠(yuǎn)。[1-4]四色問題困擾學(xué)術(shù)界160余年，其根本原因在于它不是經(jīng)典數(shù)學(xué)問題，而人們總想用經(jīng)典數(shù)學(xué)方法去證明它。

地圖染色問題的本質(zhì)是區(qū)域的形狀及其相互間的位置關(guān)系。其形、位可以“變換無窮”，而染色結(jié)果也可能不是唯一的。因此，染色問題不是單純的數(shù)邏輯問題，也不在經(jīng)典幾何公理體系內(nèi)，它是特殊的數(shù)邏輯與極復(fù)雜的形、位關(guān)系相結(jié)合，并主要是位置關(guān)系問題。基于這一認(rèn)識，并借前人在拓?fù)鋵W(xué)方面已取得的某些成就[5-7]，本文用直觀幾何方法，對四色問題作一個完整的論證。

1 正規(guī)地圖染色等價定理

若干簡單封閉線（即區(qū)域的邊界）將平面（注：球面和平面問題沒有實質(zhì)區(qū)別）分割為許多稱為“區(qū)域”的部分，構(gòu)成地圖網(wǎng)絡(luò)，如圖1(a)所示。

定義 1 地圖網(wǎng)絡(luò)相鄰的區(qū)域采用不同顏色，稱為正確染色，簡稱染色。如圖1(a)之區(qū)域I與區(qū)域II、V，必須采用不同顏色。

為使染色分析簡明，對網(wǎng)絡(luò)作如下染色等價變換。

圖1 地圖、相鄰域、正規(guī)化地圖

定義2 若一頂點A所屬區(qū)域數(shù)目大于3時，在A處增設(shè)一個小區(qū)域，如圖1(b)所示，使每個頂點所屬區(qū)域數(shù)目為3，成為3條線的匯聚點。這一變換沒有改變原地圖各區(qū)域的鄰域關(guān)系，稱變換后的網(wǎng)絡(luò)圖為正規(guī)地圖，如圖1(c)所示。

正規(guī)地圖染色等價定理（引理1）正規(guī)地圖Tn正確染色后，則縮滅（減少）任意一個區(qū)域后的地圖Tn-1也是正確染色。簡稱：染色定理。

證明：設(shè)正規(guī)地圖Tn由區(qū)域A、B、C、D……組成。將正規(guī)地圖Tn任意一個區(qū)域，例如A，縮滅為一個點，得到地圖Tn-1。這一簡單變換，沒有改變地圖Tn-1和地圖Tn上的對應(yīng)區(qū)域B、C、D……之間的相鄰區(qū)域關(guān)系，即地圖Tn與地圖Tn-1上的對應(yīng)區(qū)域B、C、D……染色可以相同。稱此兩圖染色等價。如圖1所示：將圖1(c)圖之區(qū)域A縮滅為一點，即成圖1(a)圖；圖1(c)圖上的區(qū)域Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ、Ⅵ與圖1(a)上的對應(yīng)區(qū)域Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ、Ⅵ可以一一對應(yīng)染相同顏色。圖1(d)是圖1(c)區(qū)域Ⅱ縮滅為一點后的圖形；兩圖上的區(qū)域Ⅰ、A、Ⅲ、Ⅳ、Ⅴ、Ⅵ也一一對應(yīng)。

證畢

2 兩兩相鄰域定理

兩兩相鄰域定理（引理2） 平面（或球面）上的地圖網(wǎng)絡(luò)，兩兩相鄰的區(qū)域（注：以下簡稱相鄰域）的最大數(shù)目是4。簡稱：相鄰域定理。

圖2 最大兩兩相鄰域數(shù)目為4

證明：在平面（或球面）S2上作簡單閉曲線C1，C1分S2為兩個相鄰域Ⅰ、Ⅱ，C1為公共邊界[8]，如圖2(a)所示；在C1上任取兩點a、b，將閉曲線C1分為兩部分1、2。任取區(qū)域Ⅰ、Ⅱ之Ⅱ（Ⅰ、Ⅱ沒有實質(zhì)區(qū)別），在Ⅱ內(nèi)作一條含1（1、2沒有實質(zhì)區(qū)別）的簡單閉曲線C2（如圖2(a)虛線處所示），分區(qū)域Ⅱ為兩個相鄰區(qū)域Ⅱ、Ⅲ(注：分割后之Ⅱ是原區(qū)域Ⅱ的一部分，為討論方便仍用Ⅱ標(biāo)示；以后相似問題均如此處理)；C2的一部分（即虛線，不含邊界1）為Ⅱ、Ⅲ的公共邊界。區(qū)域Ⅱ、Ⅲ均與區(qū)域Ⅰ相鄰，公共邊界分別為2、1；得到3個“兩兩相鄰區(qū)域”，如圖2(b)所示。若有區(qū)域Ⅳ與Ⅰ、Ⅱ、Ⅲ均相鄰，則Ⅳ的外圍邊界線必含有Ⅰ、Ⅱ、Ⅲ的邊界。用上述原理及方法必能作出區(qū)域Ⅳ：分別在Ⅰ、Ⅱ邊界線上任取一點d，在Ⅱ、Ⅲ邊界線上任取一點e，將這兩段邊界線分為關(guān)于區(qū)域Ⅱ位置“對稱”的兩部分（即拓?fù)鋵W(xué)意義上的等價，以下的“對稱”是同樣意義），在Ⅱ內(nèi)作一條簡單閉曲線，如圖2(b)虛線處所示。如圖2(c)所示，區(qū)域Ⅰ、Ⅱ、Ⅲ、Ⅳ即是4個兩兩相鄰區(qū)域。

4個相鄰域Ⅰ、Ⅱ、Ⅲ、Ⅳ的4條邊界閉曲線各自皆由本區(qū)域分別與其它3個區(qū)域的“3段公共邊界線”組成，類似4個“對稱”的三角形：△abe、△ebd、△dba、△ade（△ade是類似反演形式三角形），如圖 2(d)所示意。在這樣的類三角形閉曲線上，不存在兩個界點，將這條閉曲線分為“對稱”的兩部分，使每部分均含有3段公共邊界；因此不可能在Ⅰ、Ⅱ、Ⅲ、Ⅳ之任意一個區(qū)域內(nèi)分劃出兩個鄰域，使它們同時與其它3個區(qū)域均相鄰。因此5個相鄰域不存在。沒有5個相鄰域，就不存在5個以上相鄰域。因為，如果存在6個相鄰域必然包含5個相鄰域，這與上述結(jié)論矛盾。

證畢

3 基本單元地圖模型

地圖是由若干基本單元組合而成。基本單元地圖的模型可歸納如圖3所示。圖3(a)、圖3(b)之圖互為反演。鏈?zhǔn)?、?nèi)含式染色最少顏色數(shù)目不大于兩兩相鄰式；圖中各基本單元地圖模型中“四域兩兩相鄰式”（即4個相鄰域Ⅰ、Ⅱ、Ⅲ、Ⅳ）必須4種顏色才能正確染色，其余僅需2～3色就能正確染色。

圖3 基本單元地圖模型

4 地圖染色類型

若地圖的每個區(qū)域染色均獨立，稱為單純性地圖；若存在兩個以上區(qū)域染色關(guān)聯(lián)，稱為關(guān)聯(lián)性地圖。例如兩個區(qū)域Ⅳ1、Ⅳ2 同屬一個國家Ⅳ，其中一部分Ⅳ2被其它國家Ⅴ隔開，成為一塊飛地（或內(nèi)含于第三區(qū)域）；雖然Ⅳ1、Ⅳ2不相鄰，但必須染成同一種顏色，如圖5右圖所示。單純性地圖僅考慮相鄰區(qū)域不同色。關(guān)聯(lián)性地圖還必須考慮染色關(guān)聯(lián)區(qū)域同色。

5 單純性地圖四色定理

單純性地圖四色定理每一幅單純性地圖可以至多用4種顏色正確地染色。簡稱：四色定理。

證明：如圖3所示，基本單元地圖模型中4個相鄰域所需顏色數(shù)目最多，必須采用4種顏色。由4個相鄰域基本單元地圖為基礎(chǔ)可以成長為任意的地圖，如圖4所示。

在4個相鄰域基本單元地圖基礎(chǔ)上，任意增加一個區(qū)域Ⅴ，如圖4上排圖虛線處所示。按照相鄰域定理（引理2）：5個區(qū)域中，必至少有兩個區(qū)域不相鄰，例如圖4(1, 2, 5, 6)圖中Ⅴ與Ⅳ不相鄰，圖4(3)圖中Ⅱ與Ⅳ不相鄰，圖4(4)圖中Ⅱ與Ⅰ、Ⅲ、Ⅳ不相鄰。不相鄰區(qū)域Ⅳ、Ⅴ（或圖4(3、4)圖中Ⅱ、Ⅳ）染同一種顏色。將同色區(qū)域之一，例如Ⅳ縮滅為一個點，按照染色定理（引理1），這一簡單變換，沒有改變其余4個區(qū)域的鄰域關(guān)系和染色。如圖4上排圖所示：圖4(1, 2, 5, 6)圖中Ⅳ、Ⅴ同色，圖4(3, 4)圖中Ⅱ、Ⅳ同色，區(qū)域Ⅳ被縮滅為一個點。如圖4之下排圖所示，新的4個區(qū)域Ⅰ、Ⅱ、Ⅲ、Ⅴ，又是一個四域基本單元地圖：分別是四域鏈?zhǔn)?，如圖4(1)圖；四域內(nèi)含式，如圖4(4, 6)圖；四域兩兩相鄰式，如圖4(2, 3, 5)圖。它們都可以至多用4種顏色正確地染色?；謴?fù)Ⅳ，就是原來生成的五域地圖，稱此方法和過程為“縮滅法則”。

圖4 由四域兩兩相鄰基本單元地圖成長為任意地圖過程分析

在5域地圖上任意增加一個區(qū)域Ⅵ，按照相鄰域定理（引理 2），Ⅵ必至多與原來 5域中 3個相鄰域相鄰，形成一個含Ⅵ的4個相鄰域；Ⅵ可選用這3個區(qū)域顏色之外的第4色。若Ⅵ與更多區(qū)域相鄰（注：非兩兩相鄰域），必然改變原來相鄰域關(guān)系，但改變后，這6個區(qū)域的最大相鄰域數(shù)目仍不超過4（引理2）。按照最大數(shù)目4分析，這4個相鄰域之外的第5域的染色如上所述；之外的第6域必至多與5域中3個相鄰區(qū)域結(jié)成4個兩兩相鄰域，它必可選用其余兩個與自己不相鄰的區(qū)域之一的顏色染色。

重復(fù)以上過程，是7域地圖；再重復(fù)下去可得到8域、9域……等任意多形式的地圖。

需要指出：新增區(qū)域后，任何與新增區(qū)域染色無關(guān)區(qū)域都可縮滅為點，使之簡化；甚至可以從新整理全圖使之成為圖4那樣的簡單狀態(tài)，使染色分析一目了然。按照“縮滅法則”可以將復(fù)雜的染色問題化解成為簡單的染色問題。

圖4(2)～圖4（3）下排圖形與圖4(5)下排圖形互為反演圖形。

證畢

6 關(guān)聯(lián)性地圖

關(guān)聯(lián)性地圖正確地染色比較復(fù)雜，所需顏色數(shù)目不確定。如圖5左圖所示，Ⅳ1、Ⅳ2是關(guān)聯(lián)性兩個區(qū)域，必須染同一種顏色；但Ⅳ1與Ⅰ、Ⅲ、Ⅴ相鄰，只能與Ⅱ同顏色；而Ⅳ2與Ⅱ相鄰，必須染不同顏色。因此，圖5所示關(guān)聯(lián)性地圖必須采用5種顏色，如圖5右圖所示。

圖5 關(guān)聯(lián)性地圖染色

7 結(jié) 束 語

近40年，因計算技術(shù)的高速發(fā)展，又形成一次研究高潮。研究的深度廣度遠(yuǎn)遠(yuǎn)超過前人?！八纳珕栴}”不是經(jīng)典數(shù)學(xué)問題，純數(shù)學(xué)研究及建模的路線是錯誤的，除非經(jīng)典數(shù)學(xué)因四色問題而有了質(zhì)的突破；用計算機(jī)去計算更讓人無法接受，因為在“四色定理”沒有得到嚴(yán)格證明的前提下，任何數(shù)學(xué)建模本身就備受質(zhì)疑，而巨量的計算機(jī)計算更受質(zhì)疑。

“四色問題”確實不應(yīng)該是一個超高難度數(shù)學(xué)問題，故而采用直觀幾何方法去研究，企圖發(fā)現(xiàn)一種新的路線和方法去解決類似問題。作此論文供學(xué)者討論，供 “四色問題”愛好者、關(guān)注者參考。

“四色問題”絕非游戲。其應(yīng)用價值也值得關(guān)注。圖6是《中國行政區(qū)劃正規(guī)地圖》[9]，她以極其簡單的圖形表達(dá)了各省、市、自治區(qū)相鄰域關(guān)系及染色規(guī)則。地圖與書法相結(jié)合，構(gòu)成一部簡明教科書；學(xué)術(shù)、文化、地理等多層次信息一目了然?？梢宰鳛槎喾N傳媒的載體，用于教材插圖，輔助地圖，圖案題材設(shè)計，地圖染色分析；也可做旅游、交通、文化、商業(yè)廣告等傳媒的載體，應(yīng)用到社會各個方面。

[1] 百度百科. 四色定理[OL].http://baike.baidu.com/ view/43945/htm, 2012-02-10.

[2] 朱 彤. 四色問題[N]. 人民教育, 1979. 09.

[3] 作者不詳. 四色問題[J]. 曲阜師范大學(xué)學(xué)報(自然科學(xué)版), 1978, （3）: 77.

[4] 田翔仁. 奇妙的四色問題[N]. 北京: 數(shù)學(xué)教學(xué)通訊, 2009.16.

[5] D·希爾伯特. 直觀幾何[M]. 王聯(lián)芳. 北京: 高等教育出版社, 1964: 330-336.

[6] B·г·巴爾佳斯基等. 拓?fù)鋵W(xué)奇趣[M]. 裘光明. 北京:北京大學(xué)出版社, 1987: 78-80.

[7] 蘇步青. 拓?fù)鋵W(xué)初步[M]. 上海: 復(fù)旦大學(xué)出版社, 1986: 41-57.

[8] J·R·曼克勒斯.拓?fù)鋵W(xué)基本教程[M]. 羅嵩齡. 北京:科學(xué)出版社, 1987: 408-416.

[9] 張士慶, 張學(xué)忠. 中國地圖的線元化正規(guī)地圖(中國第二地圖)及其應(yīng)用[OL]. http://hi.baidu.com/duoloveren/ item/97bd1b17067737772b3e2249, 2012-06-19.

Visualized Geometrical Demonstration of the Four Colors Problem and the Four Color Theorem of Simple Map

Zhang Shiqing1,2, Zhang Hao3
( 1. Liaoning Engineering and Technological University, Liaoning Fuxin 123000, China; 2. China University of Mining and Technology Yinchuan College, Ningxia Yinchuan 750011, China; 3. GD Midea Kitchen & Bath Appliances Mfg. Co., Ltd., Guangdong Foshan 528300, china )

The arguments of the least colors that should be used to dye the 2D net color block graph, such as maps and patterns, have puzzled the academia for one hundred and sixty years or more. The basic reason is that the scholars have been working on to solve the problem with classical mathematics methods, even though it is not a classical mathematics problem. Visualized engineering geometry is used to turn the 2D net color block graph into dyeing equivalence normal map, and critically adjacent domain axioms proved. The smallest unit of maps and their dyeing mode is also established. Two kinds of map dyeing mode are found in the process. The first is simple dyeing mode, and the second is the relevant dyeing mode. At the same time, a visualized method is developed combining the dyeing and the process of turning the smallest map unit into maps together. It is proven critically that any simple maps are suitable for the least four colors dyeing method, but for the relevant maps, the number of colors that should be used are uncertain.

normal map; dyeing equivalence; simple map; adjacent domain; reducing rule

k 99，O 189，TB 113

A

2095-302X (2013)05-0046-05

2012-09-22；定稿日期：2013-04-01

張士慶（1947-），男，遼寧遼中人，教授，主要研究方向為圖學(xué)理論及應(yīng)用、圖學(xué)教育、現(xiàn)代教育技術(shù)。E-mail:comandnet@qq.com

張 號（1977-），男，遼寧阜新人，研發(fā)項目負(fù)責(zé)人，主要研究方向為家電產(chǎn)品研發(fā)設(shè)計、計算機(jī)及網(wǎng)絡(luò)應(yīng)用。E-mail:adu88@sohu.com