为何地图着色4类足够

 摘要

本文通过约当(Jordan)闭曲线定理进行地图结构分析，用简单算法得到，除1度网格外的任意平面图都有哈密顿通路（Hamiltonian path），皆可完成1笔画，然后用邻接色数不超过3色的相邻闭链（Adjacent closed chain）即肯普链加其它色单区块做基础闭链，再用互异肯普链加其它色单区块做后继相邻闭链，即每条相邻闭链皆不超过3色。合并区分两条相邻闭链却无须6色，而是可根据鸽笼定理，将两条闭链中的单区块彼此由对方闭链覆盖。基于此，单区块就可彼此借用互异肯普链中的区块色或本链中的互异区块色来区分，从而得到相邻闭链是可4色区分地图的基本构形，于是相邻闭链定理获证，用完全数学归纳法证明4色猜想的关键递推部分也就圆满完成。如此无须借助计算机暴力穷举，纯人工演绎证明4色猜想也就成立。

关键词：约当闭曲线定理，鸽笼定理，哈密顿通路，相邻闭链定理，邻接色，单区块，肯普链，希伍德5色定理，机器验算复杂构形，3-着色问题

4色猜想最先由南非数学家格斯里（Francis Guthrie）于1852年提出；另一说法，4色猜想是由德国数学家莫比乌斯（Mobius）于1840 年提出。4色问题的内容是“任何地图（亏格为0的单连通图）不同色相邻区分网格四色足够”。4是区分平面的最优化数。题面很简单，数学工作者却用了120多年才勉强解决了它，且证法超常规。1976年美国数学家阿佩尔（Appell）和哈肯（ Hakon）须借助计算机完成上百亿次验算才证实了那些特殊情形时的四色猜想也成立。计算机辅助证明可分为两大类，一类是验算可穷举部分，一类是验算可递推部分。人工证明环节就是将无穷部分能逻辑地降为有穷部分和可递推部分。

4色猜想是世界数学3大难题之一，其它两大猜想是哥德巴赫猜想和费马猜想。它之所以不平凡，是因为被一流数学家持续关心过而无果。后来数学家摩登（Morden）把它推荐给著名数学家凯莱（Cayley），就是发明线性代数的大牛，凯莱把它公布了出来，于是瘟疫一般传开了。哈密顿思考了它十几年没有进展。闵可夫斯基(Minkowski)听说后斗志昂扬，发表乐观看法，四色猜想之所以没有解决，是因为没有引起一流数学家的注意，然后就面向学生在黑板上开始演算起来，3天过去了无果，硬着头皮进教室准备继续证明，结果打雷了，闵可夫斯基只好自我解嘲说，上帝就是要借用四色问题来打击象我这样骄傲的人。

直到肯普(Kemp )和希伍德( Heywood)出场才陆续有些进展。希伍德用25国反例图否定了肯普的证法，保留了肯普的部分思路。他通过三个公式2e=2f2+3f3+4f4+…（图论第1公式），3v=2e（3度顶点图变换），v+f=e+2（欧拉示性数公式），得到4f2+3f3+2f4+f5=12+f7+2f8…，推导得出存在区块大于5度图的所有3度顶点图都不可避免有小于或等于5度图的国家，从而非常优美地证明了5色定理。我们大可不必否定希伍德（见百度百科），他宣布5色定理成立并没有否定4色定理，希伍德顶点延申的完全数学归纳法证明，是一种超限数学归纳法，是可对应区块的自然数延申的；希伍德不证明5度以上图，是因为通过3个公式得到了不可避免集；希伍德不证明球面图，是因为单连通条件下的平面图与球面图拓扑等价；希伍德只证明顶点3度图，是因为3度以上的顶点图挖掉用区块替代，可全部转换为3度顶点，而着色复杂性不变，故可等价替换。

后来阿佩尔和哈肯宣布4色问题终结，遗憾的是证明4色猜想其有限图部分是用计算机验算暴力穷举完成的，机器验算复杂构形,确实象一本电话簿，而不象一首诗。数学证明的意义是为了理解时空和万物奥秘，而仅靠对计算机的权威信赖所得到的定理，人类的心智无法感受到数学难题被征服。因为大周期递推也依赖前项有限值部分的成立，可见有限部分被理解有多重要。

1.1. 用约当闭曲线找到哈密顿通路

本文作者解决4色问题采取的方法是，用约旦闭曲线区块链一分为二来结构分析任意给定地图（见图a），如此能连接两点的线性动作可持续进行，在两分出来的未可约图中可不断找到约旦闭链，撇开1度图的条件下可得到树结构的哈密顿通路能1笔画。如此约旦闭链即每条相邻闭链皆可用肯普链或肯普链加第3色单区块来着色，也就是说每次邻接色不会超过3色得证。对闭链邻接色未形成后继闭链的单区块一律设置成“着色待定图”，方可避免传统证法须不停地换色，且毫无目标。瑟斯顿（Thurston）说“四色猜想不简单，原因在于它不能在已有成果上迭代推进”，在已着色图的基础上延伸新区块，原着色图需重新结构，这就导致新的给定图需不停地换色来证明。然新思路可证得每条相邻闭链中的单区块是可根据基础闭链来选定的，基础闭链未确定时可待定，故定有不是2邻单区块的结构选择。若别无选择，则定是2邻对齐图（见图c），然2邻对齐图是可4色区分的，如此4色猜想就能整体得到演绎证明。

图a： 由约当闭链（不超3色，其中第3色为单区块）

构成的葫芦串是可1笔画的，套子图的葫芦串仍可1笔画。

只有能演绎完成证明区分地图4色足够原理，才可快速完成不同类相邻着色，才能深刻理解平面世界里最核心的造形结构。任意图有哈密顿通路能1笔画是可证明的（见图a）。我们先从外到里走完右边，然后从里到外走完左边。“葫芦串”可1笔画，套“葫芦串”子图的大地图也可1笔画，总之，任意给定地图都能1笔画，由此可找到“子树遍历序列前序遍历”，也就是说，所有的树叶都是可以1笔画的，可用一根线串联起来。假如有些图存在不可1笔画连通，那么其真子图一定存在不可一笔画连通（2个以上单区块闭环的1度图除外）。继续寻找这样的真子图，而这样的真子图越来越小时必是原始子图，而所有的原始子图都存在哈密顿通（回）路，矛盾，故非1笔画图不存在，任意平面图都有哈密顿通路，皆可1笔画。有哈密顿通路的地图都能满足完全数学归纳法证明的线性条件，哈密顿通路图能4色区分，在此基础添加更多1度图也能4色区分，故任意平面网格都能4色区分。

  图b： n条公共闭线构造n组内外相邻闭链

仅凭这一点就给现代计算机发展提供了很重要的基础数学理论。证明4色猜想的过程也分筑基和封顶两部分，筑基部分用重合法[1] 的数学工具，证明了“每条闭链不超过3色足够区分”的引理成立，同时用约当定理还证明了所有的闭链构成了子树遍历序列（前序遍历即树叶序列）；封顶部分用相邻论的数学工具，证明了“两两相邻闭链不超过四色”的引理成立，同时用鸽笼原则证明了1邻单区块总能被相邻闭链中某区块全覆盖，故互异相邻闭链能成功紧邻延申。其中筑基部分满足“约当（Jordan）曲线定理”，可构造子树遍历序列（树叶序列），从而可用超限数学归纳法证明4色猜想成立。

解决无穷无漏问题就是要跟无限密集延伸打交道，以区块为单位元进行延伸，以顶点为单位元进行延伸，以各种构形为单位元进行延伸。其中延伸法又分为，1阶线性延伸，N阶线性延伸。这是从数量上出发得到的延伸法，还要从方向上出发获取延伸法，可分为紧邻右旋或左旋封闭延伸，紧邻右旋或左旋螺旋延伸等两类。如何有序区分它们，就是结构分析。约当闭链为何会成为平面图的结构单元？这是因为约当闭链完成了平面图的最简可穷分类，由于相邻区分是一种线性区分，因此以闭链做单位元进行线性延伸就能穷尽任意平面。本文用超限数学完全归纳法证明，没有直接用区块的自然数线性延申，而是通过相邻闭链的自然数线性延申来间接实现区块的线性延申的，因为每一条相邻闭链是严格符合区块的自然数线性延申的，故整体也就符合区块的自然数线性延申。

2.1. 相邻闭链定理的简洁证明。

以下约当闭链结构下所有区块序列其任意组合皆满足以下可穷举分类关系。(见图b)

①L1是一条介于y-1闭链和r-2,b-3,g-4闭链之间的公共闭线，L2是一条介于r-2,b-3,g-4闭链和y-5，b-6,r-7,y-8,r-9闭链之间的公共闭线，L3是一条介于y-5，b-6,r-7,y-8,r-9闭链和g-10，b-11，g-12，b-13，g-14，b-15，r-16，g-17，b-18闭链之间的公共闭线。Ln是一条介于Ln内外闭链之间的公共闭线。所有的公共闭线都存在内外相邻闭链以及相邻闭链子图。

② deg(L1内链)＜deg（L1外链），根据鸽笼法则，必有r-2被y-1全覆盖，故单区块能借用互异色完成相邻闭链。deg(L2内链)＜deg（L2外链），根据鸽笼法则，必有r-5被g-4全覆盖，故单区块能借用互异色完成相邻闭链。deg(L3内链)＜deg（L3外链），根据鸽笼法则，必有r-16被y-8全覆盖，故单区块能借用互异色完成相邻闭链。因基于度数不同，大于2个的外紧邻顶点首尾必落在2个内紧邻顶点上或两顶点之间，这是根据鸽笼定理推导出的[3]。

图c：相邻闭链对齐情形分为两种：完全对齐，错开对齐。

③互异闭链分为：1邻单区块互异闭链；2邻单区块互异闭链；偶邻单区块互异闭链；奇邻单区块互异闭链。其中2邻单区块互异闭链容易撞色，故有撞色现象时我们可以回避2邻单区块情形。为何能成功回避呢？因为相邻闭链无基础闭链可偶邻单区块和奇邻单区块完成4色区分，其它情形皆可1邻单区块来完成4色区分。其中2邻单区块若覆盖3色时，可更换单区块，因无基础闭链故必可任意选择单区块，且定有1邻单区块或偶邻单区块或奇邻单区块，若无时必为对齐相邻闭链。故皆可4色区分。                             

④假如deg(Ln内)＜or=or＞deg（Ln外），根据鸽笼法则，必有r-k被y-h全覆盖，故单区块 能借用互异色，则deg(Ln+1内)＜or=or＞deg（Ln+1外），根据鸽笼法则和假设条件（互异闭链必不超3色的邻接色，且第3色为单区块），必有r-k1被y-h1或不超三色链全覆盖。闭链度数较小时为基本肯普闭链，基本肯普闭链上的单区块在4色范围里总能被互异肯普区块覆盖，或被互异肯普闭链覆盖，或被互异肯普闭链加互异肯普区块覆盖。基本肯普闭链上的其他部分则能被互异肯普闭链覆盖。

因相邻闭链属于非对齐的（见图d），故根据鸽笼定理存在单区块被1邻、2邻、偶连、奇邻全覆盖，除了2邻单区块或遇撞色外，其它皆能4色区分。但2邻情形，可更换互异闭链中的单区块，定可避免2邻，不可避免时，为对齐情形。而对齐情形是定可4色区分的。故彼此单区块都能借用互异色完成4色区分，相邻闭链定理成立。

图d：相邻闭链非对齐情形。17-18-19-20-21属于非独立闭链，

凭借16-13-7构成红黄闭链，4-22-23-24属于分支闭链子图。

                  红黄组闭链与蓝绿组闭链是非对齐的。

2.2. 用数学完全归纳法证明四色猜想。

根据以上论述，4色猜想就可以用完全数学归纳法进行封顶证明了[4]。 

证明：①由闭链M1构造的图 G1可4色区分（有限可列）（参考图a，G1为L1内链，M1为L1内链区块1）。②由内向外添加紧致相邻闭链 M2-4构造的图 G2可四色区分（有限可列）（参考图a，G2为L2内链，M2到M4为L2内链区块2到4，以下亦同）。③再由内向外添加闭链 M5-9构造的图 G3可4色区分（有限可列）。④另由子树遍历序列（树叶序列）可知，从 M1到 Mn 可无漏无穷充满任意给定地图，故该序列的延伸与自然数序列的延伸一一映射。⑤现假设依次由内向外（或由外向内）添加紧致可3色足够区分的相邻闭链 Mn 构造出的图 Gn 可4色足够区分任意图，可3色足够区分相邻闭链。⑥那么根据相邻闭链定理，由内向外（或由外向内）添加紧致相邻闭链M（n+1）构造出的图 G（n+1）亦可4色足够区分任意平面地图，可3色区分每条相邻闭链。加上哈密顿通路1笔画判定的解决，递推关系成立。即当n区块能完成四色区分，n+1区块若在同一闭链中根据闭链不超3色定理必能4色区分，若不在同一闭链中而在相邻闭链上亦能根据相邻闭链定理4色区分。故满足超限数学归纳法条件，4色猜想成立。（证毕）

是一笔画的格点迭代决定了线性迭代形成平面，超限归纳法其本质依然是完全归纳法，有了超限归纳法，还可以有多阶超限归纳法，超限归纳法的迭代递推序列，是自然数序列的函数映射所递推的结果，那二阶超限数学归纳法则是自然数序列的映射函数再映射所递推出的函数结果，那n阶超限数学归纳法则是自然数序列的泛函映射所递推出的函数结果，多维空间格点最优化区分数公式就是这种逻辑下的产物。它将成发展人工智能的重要工具。多维空间最优化区分数公式是L（n）=2^n。三维空间的最有优化区分数是8，蜂窝就是六面墙加天地8个元素构造的。它是最省材的。四色猜想的纯人工逻辑证明，解决了多维空间的最优化区分问题。四色猜想和3-着色问题都是图着色问题，它们被证明是NP完全问题，四色猜想被纯人工证明，意味着图着色问题也是可P问题，为P=NP在某种条件下提供了可证明的坦途。

探索近邻未知，我们持图灵可知信念，探索远邻未知，我们持哥德尔不可知信念，远邻会变成近邻，但远邻背后还有远邻，图灵鼓励我们要敢于探索，成功就在眼前，哥德尔提醒我们，人类一思考上帝就发笑。上帝创造了自然数，其余都是人的事情。通往天堂的路是狭窄的，那就是唯有通过悠长的自然数进行各阶泛函表达才能不断逼近远邻，NP验算是可P计算的。道可道（图灵信念可P计算），非常道（哥德尔信念可NP验算）。各执一端的“皆可计算”，“仅可验算”都是不可取的。

作者罗莫简介：深圳市数学科普学会秘书长，著有数论专集《数学底层引擎相邻论和重合法》（海天出版社出版2019年9月），关注数学基础理论方面的一系列重大课题，研究众多未解数论猜想有实质性进展，如哥德巴赫猜想，abc猜想，黎曼假设等。 

参考文献：

[1] 罗莫 . 用重合法可证明哥德巴赫猜想原题 [J]. 数学学习与研究，2013（3）：93-95.

[2]James R. Munkres. 拓扑学 [M]. 熊金城，吕杰，谭枫，译 . 北京：机械工业出版社，2006.

[3] 庞德斯通 . 推理的迷宫：悖论、谜题，及知识的脆弱性 [M]. 李大强，译 .北京：北京理工大学出版社，2011.

[4] 罗莫 . 数学底层引擎相邻论和重合法 . 罗莫. 深圳：海天出版