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

張士慶， 張 號

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

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

張士慶1,2， 張 號3

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

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

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

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

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

1 正規地圖染色等價定理

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

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

為使染色分析簡明，對網絡作如下染色等價變換。

圖1 地圖、相鄰域、正規化地圖

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

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

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

證畢

2 兩兩相鄰域定理

兩兩相鄰域定理（引理2） 平面（或球面）上的地圖網絡，兩兩相鄰的區域（注：以下簡稱相鄰域）的最大數目是4。簡稱：相鄰域定理。

圖2 最大兩兩相鄰域數目為4

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

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

證畢

3 基本單元地圖模型

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

圖3 基本單元地圖模型

4 地圖染色類型

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

5 單純性地圖四色定理

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

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

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

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

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

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

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

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

證畢

6 關聯性地圖

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

圖5 關聯性地圖染色

7 結 束 語

近40年，因計算技術的高速發展，又形成一次研究高潮。研究的深度廣度遠遠超過前人。“四色問題”不是經典數學問題，純數學研究及建模的路線是錯誤的，除非經典數學因四色問題而有了質的突破；用計算機去計算更讓人無法接受，因為在“四色定理”沒有得到嚴格證明的前提下，任何數學建模本身就備受質疑，而巨量的計算機計算更受質疑。

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

“四色問題”絕非游戲。其應用價值也值得關注。圖6是《中國行政區劃正規地圖》[9]，她以極其簡單的圖形表達了各省、市、自治區相鄰域關系及染色規則。地圖與書法相結合，構成一部簡明教科書；學術、文化、地理等多層次信息一目了然。可以作為多種傳媒的載體，用于教材插圖，輔助地圖，圖案題材設計，地圖染色分析；也可做旅游、交通、文化、商業廣告等傳媒的載體，應用到社會各個方面。

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

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

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

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

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

[6] B·г·巴爾佳斯基等. 拓撲學奇趣[M]. 裘光明. 北京:北京大學出版社, 1987: 78-80.

[7] 蘇步青. 拓撲學初步[M]. 上海: 復旦大學出版社, 1986: 41-57.

[8] J·R·曼克勒斯.拓撲學基本教程[M]. 羅嵩齡. 北京:科學出版社, 1987: 408-416.

[9] 張士慶, 張學忠. 中國地圖的線元化正規地圖(中國第二地圖)及其應用[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-），男，遼寧遼中人，教授，主要研究方向為圖學理論及應用、圖學教育、現代教育技術。E-mail:comandnet@qq.com

張 號（1977-），男，遼寧阜新人，研發項目負責人，主要研究方向為家電產品研發設計、計算機及網絡應用。E-mail:adu88@sohu.com