Operations Research and Fuzziology
Vol. 09  No. 01 ( 2019 ), Article ID: 28706 , 13 pages
10.12677/ORF.2019.91007

Innovative Proof of Four-Color Conjecture

Yudian Zhang, Lichong Zhang

Yuxian Party School of Shanxi Province, Yangquan Shanxi

Received: Jan. 9th, 2019; accepted: Jan. 22nd, 2019; published: Jan. 29th, 2019

ABSTRACT

By using the law of “Non-tenfold symmetry transformation of geometric structures in H-M family configurations”, a minimum reducible set of infinite “dyeing dilemma configurations” in the four-color conjecture is established; an innovative proof of the four-color conjecture is given.

Keywords:Four Color Conjecture, Dyeing Dilemma Configuration, A Geometric Structure of Tenfold Symmetry, Transform of Non-Tenfold Symmetry

四色猜想的创新证明

张彧典,张利翀

山西省盂县党校,山西 阳泉

收稿日期:2019年1月9日;录用日期:2019年1月22日;发布日期:2019年1月29日

摘 要

利用“H-M族构形中的几何结构的非十折对称变换”法则确立了四色猜想中无限多个“染色困局构形”的一个最小可约构形集,给出四色猜想的一个创新证明。

关键词 :四色猜想,染色困局构形,十折对称几何结构,非十折对称变换

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

1935年,《美国数学学会会刊》发表了《对已部分染色地图的一组操作》 [1] ,其中,定义了“染色困局构形”,给出一个基本模型,如图1左所示,我们用对偶图简化表示为8点式的最小模型,如图1右所示;作者还给出“Errera图”。

Figure 1. Dyeing dilemma model

图1. 染色困局

1992年,英国牛津《数学季刊》发表了《应该知道的赫伍德范例》 [2] ,其中,把“Errera图”用它的对偶图表示出来,并且详细论述了这个最小十折对称构形(我们按照两位作者姓的第一字母简称为“H-M”构形,如图21中H-M-1所示),在4次赫伍德颠倒染色(我们简称H染色程序,为一个循环节)时发生周期循环,无法正确4染色。

得出这种结论的还有《一种试探式的平面图四染色》 [3] 中的CK图,仍然是H-M-1构形。

2011年,我国敢峰先生在《4CC证明》 [4] 中,详细演绎了H-M-1构形的生成过程,即经过施行连续的16步H染色程序(4个循环节),由15个无解的非十折对称构形逐步生成十折对称的H-M-1构形。

2018年,我们找到了与H-M-1构形同胎的另外3个周期循环的构形,组成H-M构形族 [5] ,如图21所示;同时,发现了四色地图中的一个重要定理“四色四边形及其性质定理”,运用这个性质定理,确立了与敢峰先生15个非十折对称几何结构的无解染色困局构形相互对应的15个非十折对称几何结构的有解染色困局构形,完善了《肯普证明的完善》 [6] ,给出四色猜想的一个创新证明。

2. 正文

2.1. 相关定义、定理

定义1:四色四边形,三色四边形。

在正确4染色构形中,如果由四个不同色顶点组成一个最小四边形,这个四边形称之为四色四边形;

如果由三个不同色顶点组成一个最小四边形,这个四边形称之为三色四边形。

定理1:在正确4染色构形中,不可避免地存在至少一个最小四色四边形。

证明:(反证法)在正确4染色构形中,如果不存在至少一个最小四色四边形,即所有最小四边形都是三色四边形,这时,组成这个三色四边形中一定有两个对角同色,所以组成这个三色四边形的两个三角形染色一定相同,那么整个构形之所有三角形顶点也一定是这样的3色染色,即整个构形中的顶点也都是这样的3色染色,与正确4染色的条件矛盾。【证毕】

定义2:色链与相反色链:在正确4染色构形中,如果用边连接至少两个不同染色的顶点,那么称之为色链,如A-B链、C-D链,等。当一条色链呈现封闭的圈时,称为环链,简称环。如果两条色链没有一色相同,那么称这两条色链互为相反色链。

定理2:四色四边形性质定理:

1) 四色四边形的两条对角链互为相反色链。

证明:因为四色四边形中的4个顶点不同色,所以两组不相邻顶点连成的对角链没有相同染色,一定互为相反色链。

2) 在四色四边形中,任意改变其中一条对角链,只能破坏原来构形的几何结构,而不破坏原来构形的色点的组合,即色图。

证明:因为改变四色四边形中的对角链,只是改变了原来构形中边的组合,即几何结构,并没有改变原来构形中的色图。

2.2. 染色困局构形的最小可约集

下面,我们应用“改变H-M族构形中的四色四边形对角链”的方法,通过反复实践,构造了非十折对称几何结构的染色困局构形的最小可约集合。

我们的构造法则是:在最小H-M族4个构形(即图21中给出的4个图)之第二个五边形(即最外、最内两个五边形之间的那个)中,改变其5条边所在的四色四边形的对角链,以便破坏构形的十折对称而不破坏色图,从而得到非十折对称的可约的染色困局构形。

图2~16用“张”姓的第一个汉语拼音字母Zi ( i = 1 , 2 , 3 , , 15 )表示,每一个构形中的粗黑线表示改变了虚线所示的对角链以后形成的非十折对称几何结构的构形。

Figure 2. Z1 (Reverse dyeing 2 times)

图2. Z1 (颠倒染色2次)

Figure 3. Z2 (Reverse dyeing 3 times)

图3. Z2 (颠倒染色3次)

Figure 4. Z3 (Reverse dyeing 4 times)

图4. Z3 (颠倒染色4次)

Figure 5. Z4 (Reverse dyeing 5 times)

图5. Z4 (颠倒染色5次)

Figure 6. Z5 (Reverse dyeing 6 times)

图6. Z5 (颠倒染色6次)

Figure 7. Z6 (Reverse dyeing 7 times)

图7. Z6 (颠倒染色7次)

Figure 8. Z7 (Reverse dyeing 8 times)

图8. Z7 (颠倒染色8次)

Figure 9. Z8 (Reverse dyeing 9 times)

图9. Z8 (颠倒染色9次)

Figure 10. Z9 (Reverse dyeing 10 times)

图10. Z9 (颠倒染色10次)

Figure 11. Z10 (Reverse dyeing 11 times)

图11. Z10 (颠倒染色11次)

Figure 12. Z11 (Reverse dyeing 12 times)

图12. Z11 (颠倒染色12次)

Figure 13. Z12 (Reverse dyeing 13 times)

图13. Z12 (颠倒染色13次)

Figure 14. Z13 (Reverse dyeing 14 times)

图14. Z13 (颠倒染色14次)

Figure 15. Z14 (Reverse dyeing 15 times)

图15. Z14 (颠倒染色15次)

Figure 16. Z15 (Reverse dyeing 16 times)

图16. Z15 (颠倒染色16次)

根据上述构造法则,一共构造出图2~16十五个非十折对称几何结构的染色困局构形。

2009年8月8日,敢峰先生在《四色定理简证》(文献 [4] )中,详细解析了H-M-1构形经过连续颠倒染色20次以后,使得其色图与几何结构旋转到初始位置。其中连续施行H染色程序4个循环节以后,已经得到一个完整的H-M构形,如图21中第一个构形H-M-1所示。

这时得到的H-M-1构形还差144度才能旋转回初始位置,作者继续在H染色程序第五循环节中给出H-M构形的4个连续转化无解的不同构形。我们又在这个循环节中,构造了4个非十折对称几何结构且有解的染色困局构形,如图17~20所示。

但是,由于这4个构形的解法与图2~5的解法相同,所以按照解法不同的归类法则,可以归纳于图2~16组成的15个染色困局构形。

Figure 17. (Belong to the Z1)

图17. (属于Z1)

Figure 18. (Belong to the Z2)

图18. (属于Z2)

Figure 19. (Belong to the Z3)

图19. (属于Z3)

Figure 20. (Belong to the Z4)

图20. (属于Z4)

图21中,粗实线A-C链与粗虚线A-D链显示在4个同胎构形中的不同相交情形,比较4个构形,它们的色图各不相同,只有几何结构相同,都是十折对称的,对它们施行H染色程序时,都发生周期性循环,由此不难证明,构形的十折对称几何结构是使得H染色程序循环的充要条件,这个问题将在2,4中详细论述。

H-M-1 H-M-2 H-M-3 H-M-4

Figure 21. H-M family configuration

图21. H-M族构形

以上得到的15个非十折对称的染色困局构形,再加上如图21所示具有十折对称几何结构的H-M族构形,一共得到16个符合染色困局模型且解法各不相同的染色困局构形,组成一个染色困局构形最小可约集。

2.3. 染色困局构形最小可约集的完备性证明

以上就是我们通过长达一年的实践得出的结论。这样的结论能否得到一个理论的证明呢?

我们的证明如下:

我们通过“改变H-M族4个构形中单个四色四边形之对角链”的有限性,得出所有不同非十折对称构形的有限性,从而有效地证明这个结论的正确性。

考察图22中H-M族4个构形,因为每一个H-M构形中处于第二五边形的边数为5,H-M-1至H-M-4四个构形一共有5 × 4 = 20条边,可以用它们的相反对角链替换的只有4 + 3 + 4 + 4 = 15条,如图22中粗实线者所示,打短横线者,表示被替换的边;其余5条边,要么包含于相交的A1-C1、A1-D1两条链,要么包含于3色四边形,不可以被替换。这样只能得到15个非十折对称几何结构的染色困局构形,然后分别对它们施行逆时针H染色程序,按照颠倒染色次数由少到多依次排列,与我们前面构造的图2~16所示可约构形完全吻合,实现了理论与实践的统一。【证毕】

Figure 22. Distribution of Z1 - Z15 in H-M configuration

图22. Z1~Z15在H-M族构形中的分布

2.4. 染色困局构形的可约证明

以上得到的最小染色困局构形集里面的16个构形的可约证明方法大体可以分为两种:

1) 对于15个非十折对称几何结构的染色困局构形,我们运用具有周期性的H染色程序证明了:经过有限次颠倒染色后可约。

在Z1~Z15的可约证明中,由于它们颠倒染色次数从2连续递增到16 (见图2~16下面小括号中的颠倒染色次数),所以颠倒染色次数的连续性显示了这些构形的连续性——相邻构形之间的非此即彼性。

限于篇幅,这里只给出颠倒染色次数最多的Z15的详细可约过程,如图23所示:打小横线者表示已知的或者生成的极大链,粗实线表示颠倒染色的色链,颠倒染色遵循B-D,D-A,A-C,C-B的顺序。且每一步确保消去两个同色之一,直至消去两个同色。加()的表示孤点的颠倒染色,图形之间的箭头表示构形染色变化的顺序。以下同。

2) 对于十折对称几何结构的H-M族构形,因为对它们施行H染色程序时,H染色程序与构形都发生周期性循环,无法证明其可约。但是我们发现,四个构形都有一个共同的染色特征,那就是:在H-M-1,H-M-2中,都包含A-B环;在H-M-3,H-M-4中,都包含C-D环。因此,运用张彧典染色法(简称为Z染色程序)可约。

对包含已知A-B环的H-M-1,H-M-2,只要颠倒这个环外C-D链的染色,就可以使得构形转化为肯普证明了的简单构形,这里只给出H-M-1在H染色程序第一循环节中的4个构形的可约过程,如图24所示;

若已知的是第(1) [或(3)]图时,先颠倒A-B环外C-D链的染色,生成新的互不相交的A-C,A-D (或B-C、B-D)极大链,再颠倒孤点色B(D)、B(C) [或A(D)、A(C)],使五边形顶点染色数减少到3。

若已知的是第(2) [或(4)]图时,先颠倒A-B环外C-D链的染色,生成新的B-C (或A-D)极大链,颠倒孤点色A(D) [或B(C)],使五边形顶点染色数减少到3。

Figure 23. The reducible proof process of Z15

图23. Z15的可约证明过程

Figure 24. The reducible proof process of H-M-1

图24. H-M-1的可约证明过程

对包含已知C-D环的H-M-3,H-M-4,只要颠倒这个环外A--B链的染色,就可以使得构形转化为肯普证明了的简单构形。为了节约篇幅,这里只给出H-M-4在H染色程序第一循环节中4个构形的第一个构形可约过程,如图25所示:

Figure 25. The reducible proof process of H-M-4

图25. H-M-4的可约证明过程

现在回答,对于包含任意点、边的染色困局构形,运用具有周期性的逆时针(或者顺时针) H染色程序经过有限次颠倒染色,是否也一定可约呢?文献 [3] 中已经通过H-M-1证明了一个引理,这就是:

“引理3.1:当初始染色为CK0时,算法2.1循环,并以20种不同染色序列为一个周期”。

这个引理中所说的“初始染色为CK0”,就是构形的初始色图,“算法2.1”就是H染色程序。我们通过H-M族中的4个构形周期循环性分析,证明了它们周期循环的根本原因,不仅是因为构形初始染色,而且是因为它们都具有的十折对称性几何结构。为什么认识有差别呢?理由是:文献 [1] 、 [3] 、 [4] 只是考虑到H-M族中的一个构形即图21中H-M-1的共性——色图CK0循环,我们则与文献 [2] 一样,不仅考虑到色图循环,而且考虑到H-M族中的四个构形的共性——几何结构也循环。所以引理3.1已经被证明为:

引理3.1’:“当具有十折对称几何结构的初始染色为CK0时,算法2.1循环,并以20种不同染色序列为一个周期”。

其逆否定理也一定正确。那就是:

如果算法2.1 (H染色程序)不循环,那么初始染色为CK0的几何结构一定不具有十折对称性。

通过对最小不可避免集中的15个非十折对称几何结构构形的可约证明,证明了这个逆否定理的逆定理成立,也就是文献 [3] 中引理3.1的否定理成立,那就是本文中的第三个定理。

定理3:“当初始染色的CK0不具有十折对称几何结构时,算法2.1不循环。”

把定理3推而广之,得到推论:

“如果任意放大的染色困局构形不具有十折对称几何结构时,那么H染色程序一定不循环,即经过有限次的颠倒染色后使得构形可约。

这个推论对于点与边无限、非十折对称几何结构的任何复杂染色困局构形的可约提供了理论证明。文献 [6] 中给出的图2~图9就是点数不尽相同的非十折对称构形的可约证明,或者阅读《H-M族构形的放大》 [7] ,可以验证这个推论的正确性。

对于H-M族构形的放大构形,用Z染色程序仍然可约,论述可见文献 [5] 。

2.5. 可约构形集完备性的验证

以上,我们已经从实践与理论的结合上证明了“非十折对称染色困局构形只有15个”。为了进一步从实践上检验其正确性,下面,我们找出H-M族4个同胎构形中除去第二五边形边之其它所有可以改变的四色四边形对角链,一共49条,可以得到49个非十折对称构形,如图26所示:除去两个标记为K的构形,属于染色困局构形的只有47个了;加上改变第二五边形边得到的15个,一共62个。在62个不同几何结构的染色困局构形中,分别对它们施行逆时针颠倒的H染色程序,得到的4染色结果表明:

没有一个构形的解法能够逃出已经确立的15类构形的解法集合,证明62个构形的解法大部分已经重复了。这样,从全局也就证明了15个非十折对称的构形集是完备的。

图26中,划粗黑线者表示相交的A1-C1、A1-D1两条链,划粗虚线者表示包含于3色四边形的对角链,打短横线者表示处于第二五边形中可以改变的四色四边形对角链;

Figure 26. Distribution of 49 reducible configurations in H-M family configurations

图26. 49个可约构形在H-M族构形中的分布

4个构形之每一个五边形围栏内部的细实线用箭头指出,箭尾标记的字母表示这条对角链被改变以后得到的构形解法归类,其中两个标记为K的是直接转化为Kempe已经证明了的A1-C1、A1-D1两条链相离(连)的构形(即K构形)。

从选择单条可以改变四色四边形对角链所形成的构形,得出的定理3的推论,进而可以推断:当选择多条可以改变四色四边形对角链(即15个对角链的所有不同组合)形成的不同构形,因为它们仍然具有非十折对称几何结构,所以对它们施行逆(顺)时针颠倒的H染色程序时,一定可约。

3. 结论

综上所述,文献 [3] 通过H-M-1构形证明了引理3.1成立,我们通过H-M-1至H-M-4四个构形证明了引理3.1’成立,又通过15个最小非十折对称的不可避免染色困局构形可约,证明了定理3成立,从而证明了“包含任意点、边的无穷染色困局构形,也可以用H染色程序可约;同时,用Z染色程序证明了H-M族染色困局构形及其放大构形可约。到此,解决了Kempe证明四色猜想中的“陷阱” [8] 问题,完成了四色猜想的一个实践与理论相统一的证明。

在论文完成过程中,英国兰开斯特大学图论大家A.Lehoyd寄来了文献 [2] ,新加坡万春如先生为我们翻译了多篇有关四色猜想的证明论文,北京的敢峰先生及时提供了他的研究成果《4CC和1 + 1的证明》,雷明先生提供了Z9、Z15等构形,在此一并致谢。

文章引用

张彧典,张利翀. 四色猜想的创新证明
Innovative Proof of Four-Color Conjecture[J]. 运筹与模糊学, 2019, 09(01): 52-64. https://doi.org/10.12677/ORF.2019.91007

参考文献

  1. 1. Kittell, I. (1935) A Set of Operations on Partially Stained Maps. Bulletin of the American Mathematical Society, 41, 407-413. https://doi.org/10.1090/S0002-9904-1935-06104-X

  2. 2. Holroyd, F.C. and Miller, R.G. (1992) The Example That Heawood Shold Have Given. The Quarterly Journal of Mathematics, 43, 67-71.

  3. 3. 万春如. 一种试探式的平面图四染色[Z]. 中国博士网数学论坛, 2017-09-05.

  4. 4. 敢峰. 4CC和1+1的证明[M]. 北京: 北京理工大学出版社, 2011: 22-30.

  5. 5. 张彧典. 十折对称图形解析[Z]. 中国博士网数学论坛, 2018-03-03, 2018-05-06.

  6. 6. 张域典. 肯普证明的完善[J]. 山西忻州师范学院学报, 2004(2): 64-68.

  7. 7. 张彧典. H-M族构形的放大[Z]. 中国博士网数学论坛, 2018-12-10.

  8. 8. 张忠辅. 数学的陷阱——四色猜想的各种“证明”. 自然杂志, 1991, 14(5): 379-382.

期刊菜单