|
本帖最后由 zhangyd2007@soh 于 2021-11-28 11:02 编辑
埃雷拉(Errera)图问世100年 研究成果综述
四色之巅
四色问题是图论中最被广泛研究的一个问题,1852年提出:任何平面图形都可以用不超过4种颜色而正确颜色。肯普(Kempe)1879年发表了第一个证明,赫伍德(Heawood)1890年给出一个反例构形(简记为H-构形),指出这一证明的错误。随后,许许多多的研究人员对这一问题进行了大量的研究。这些研究者包括阿莱尔--斯沃特(Alaire—Swart),阿佩尔--哈肯(Appel--Haken),伯克霍夫(Birkhoff),希施(Heesch) ,叩斯(Ore), 罗伯逊(Robertson)等,萨蒂--伊能 (Saaty --Inen),泰特(Tutte)以及惠特尼(Whitney)。
其中,许多数学家还重点研究了埃雷拉图(下面称埃雷拉构形,简记为E构形)。
琼.哈钦森和斯坦.瓦贡(Joan Hutchinson and Stan Wagon)在1998年《美国数学学月刊》 (The American Mathematical Monthly)105卷第2期中披露,A.Errera构形是A.Errera于1921给出的,到今年2021年已经历时整整100年了。
在这个漫长的百年时段,不知耗费了多少著名数学家以及数学爱好者的时间与心血。为什么会有这么多的数学家对这个构形的研究乐此不疲呢?这是因为,这个构形不仅是一个非常特殊的赫伍德反例构形,即在五边形外围逆时针排列B-A-B-C-D的情形中存在A-C链与A-D链至少一次相交的共性,而且仅包含16个顶点、具有十折对称几何结构这样的个性。
由于这个A.Errera图历时百年,比四色猜想的诞生只差69年,况且有这么多人研究过,所以非常有必要把对A.Errera图的研究成果总结一下。
归纳起来,不外乎以下4类重要成果。
第一类成果是:专门研究这个A.Errera构形的生成原理。这方面以中国北京的敢峰先生为典型代表。
他早在1992年,就用演绎推理的方法(即每一步顺时针肯普颠倒染色使得构形无法走出困局),一共经过16步顺时针的肯普颠倒染色以后,得到了A.Errera图。今年已经92岁高龄了,但是他的研究仍然不停,写了长达十万的长篇论著《四色定理登顶证明》【1】 ,在美国出版,充满了从一般到特殊、从量变到质变的哲学思想。
第二类成果是:专门研究这个A.Errera构形的周期循环与促成其周期循环的颠倒染色程序之间的内在联系。这方面以美国的 欧文-基特尔(IRVING-KITTELL)1935年在《美国数学学会会刊》上发表的“对已部分染色地图的一组操作”(Bulletin of the American Mathematical Society)【2】 、加拿大的哈米斯.卡尔和威廉.科凯在《组合数学 组合计算机》46 (2003),97-112上发表的“一种试探式的平面图四染色”( A tentative plan 4 - dyeing)【3】、英国的弗雷德.霍罗伊德和罗伯特与格兰丁。米勒1992年在牛津数学季刊发表的“应该知道的赫伍德范例”( The Herwood paradigm that you should know)【4】等人为典型代表。
其中,
(1)文献【2】着重研究了9种操作(即9种颠倒染色方法)对A.Errera构形的变化规律性(解析以及图示可见该文献中的),只是给出6种演变构形(图2—图7中,图2与图7、图3与图4重复了,与图6左右对称的情形漏掉了);
(2)文献【3】着重研究了A.Errera构形的周期循环引起算法2.1 (即4次颠倒染色)周期循环的规律性,得到了
引理3.1:“当初始染色为CK0时,算法2.1循环,并且以20为一个周期”
(证明以及图示可见该文献)。
(3)文献【4】着重证明一个定理:
“4次逆时针赫伍德颠倒染色(实际是算法2.1)的周期循环,使得A.Errera构形的周期循环”。其规律性论述以及图示可见该文献。
显然,文献【3】、【4】的研究方向是互相可逆的,即互为逆定理。
张彧典在他的研究中,把引理3.1作为原定理,那么文献【4】中的定理可以称为引理3.2 (见后面),是引理3.1的逆定理。
第三类成果是:专门研究这个A.Errera构形的解法的。这方面以美国的琼.哈钦森和斯坦.瓦贡(n Hutchinson and Stan Wagon)1998年2月发表在《美国数学月刊》(e American Mathematical Monthly)肯普再研究(mpe re-study)为典型代表【5】。
他们给出一种KK算法,巧妙地解决了A.Errera构形的正确4-染色问题(论述以及图示可见该文献)。敢峰先生也在文献【1】中给出同样的解法。
第四类成果是 :综合以上5个文献的片面研究成果,对这个历时100年的A.Errera构形,给出完整地研究,得到最新的结论。这方面以山西省盂县县委党校数学高级讲师张彧典以及西安市的高级工程师雷明先生为典型代表。
张彧典早在1992年已经发现,在赫伍德反例“BAB”式模型中,沿着B-D、D-A、A-C、C-B四种逆时针颠倒染色顺序对它施行时,五边形外围五个顶点就会顺时针旋转144°(可见发表于《教学与管理》杂志1994年第二期61页的论述以及图示),该文认为不会存在周期循环的构形。但是1999年,他收到英国兰开斯特大学A.Lehoyd教授寄来的文献【4】,其中的范例2否定了他在该文中的认识,使他第一次知道,有这种经过“4次逆时针颠倒染色程序”(下面简称为“H染色程序”)就会发生周期性循环的构形存在,大开了眼界----发现了构形不能用具有周期性的H染色程序求解了。但是,当他认真研究了这个构形的染色特征以后发现,其中包含了一条A-B环链,于是产生了一种新的解法-----“张彧典染色程序”(简记为“Z-染色程序”)。后来才知道这个构形及其解法,文献【1】、【3】、【5】中早就已经给出, 那就是A.Errera构形以及邻角链法。
2004年,他把赫伍德反例的类型按照解法的不同分成两类:一类是用4次逆时针颠倒染色程序可解的(按照4-染色地图中包含的6种色链之不同数量组合与相交组合确立了8个构形),一类是用Z-染色程序可解的A.Errera构形。写了《肯普证明的完善》【6】发表于山西省忻州师范学院学报(自然版)第二期64-68页。
2017年,他收到新加坡万春如先生为他翻译的文献【2】、【3】等几篇外国数学家有关研究四色猜想的论文,使得他对A.Errera构形有了清晰的完整的认识。
张彧典 用两种不同的方法找到了与A.Errera构形同态的另外3个构形,组成A.Errera族4构形,简记为E-族构形—E1、E2、E3、E4。其中E1就是A.Errera构形。这4个构形与敢峰先生文献【1】中第17—20步得到的4个构形完全一样。
仔细分析,它们都具有相同的几何结构即都是十折对称的,只是特征链A-C、A-D的相交情形不同;而且4个构形在施行H染色程序时,构形都会发生周期性循环。这种规律性的认识,他认为,引起E-族构形周期性循环的因素不只是构形的4-染色图,还有更重要的因素是它们相同的十折对称几何结构。
此时,他把前人关于“构形”的定义完善为“几何结构+4染色图”。
依据构形的这种完整定义,他发现了“在运用4色正确染色的极大平面图中存在至少一个四色四边形”的定理1;还发现了“四色四边形中的两条对角链不能同时存在于同一个四色四边形”的性质定理2。
然后,依据以上新的认识,他认为文献【3】中引理3.1的条件(只强调构了形的4-染色图即色图,忽略了构形的几何结构)是不完备的,于是,他把引理3.1完善为:
“当具有十折对称且初始染色为CK0时,算法2.1循环,并且以20为一个周期。”
把引理3.2完善为:
“在4次赫伍德颠倒染色(简称H染色程序)时,具有十折对称的E1构形染色发生周期循环。”
利用文献【3】中的引理3.1与引理3.2互为逆定理,命题的4种分类以及它们真假性的4种分类,判定这两个定理的否定理也是正确的,于是得到新的
定理3:
当非十折对称且初始染色为CK0时,算法2.1不循环。
这个定理,对于所有染色困局构形中几何结构非十折对称的构形的求解,得到一个理论性证明。“算法2.1不循环”就是“H-染色程序”不循环,表明对于非十折对称的构形的可约或者叫正确4-染色,施行H-染色程序,次数是有限的。西安市的雷明先生提出必须解决上限值是多少?我认为没有必要。
为了验证这个结论的正确性,他对E-族4构形中的62个四色四边形(在4个构形中的分布依次为17、15、15、15)的对角链进行变换,得到62个非十折对称几何结构的构形,然后对它们分别施行H-染色程序,最多颠倒染色16次就可以正确4-染色,按照颠倒染色次数从少到多,一共可以得到15个有解构形,与敢峰先生的文献【1】中的前15个无解构形,形成一一对应关系。
同时,通过他的论文【文献6】中的前8个非十折对称构形也可以得到验证。
对于十折对称的E-族构形以及放大构形的可约,他用数学归纳法给出证明。
首先对最小的16点式的E-族4构形进行归纳基础证明:
他发现4个构形中,由于包含两两相同的特征链,即E1、E2的特征链为A-B环,E3、E4的特征链为C-D环。所以决定了前人与他在文献【6】中的解法是片面的,不完整的,于是,他用不同的邻角链法(统称为Z-染色程序,可以作为定理4)解决了E-族4构形的正确4-染色问题。
紧接着,进行归纳假设证明: 即把E-族4构形作为n=k时 ,定理4成立,证明N=K+1时定理4仍然成立。
他分别从内(或外)部嵌入一个四色构件,证明了在放大构形中定理4都是成立的。
以上定理3与定理4,解决了所有非十折对称染色困局构形或者十折对称染色困局构形两大类染色困局构形的正确4-染色问题,弥补了肯普有缺陷的证明,完成了四色猜想的一个简短证明,既实现了清华大学林翠琴教授“只要能够证明在任意极大平面图中经过有限次颠倒染色即可正确4-染色,就足够了。”的预见,也实现了给出机器证明的作者阿佩尔(Appel)“四色猜想的一个简短证明总有一天会被发现”的预见。
雷明先生在认可张彧典完整研究成果的基础上,仔细分析了E-族4构形的构形特征环A-B或C-D的顶点的位置的特殊性,即特征环A-B环一定经过五边形外围的3个顶点,C-D环一定经过五边形外围的两个顶点。于是以特征环的顶点特征作为判断是否染色困局构形的分类标准,把所有染色困局构形分成两大类,分别用他的断链法(实质是Z-染色程序)与构形转换法(实质是H-染色程序)证明它们分别可约。他的分类标准与张彧典的分类标准(依据构形几何结构是否十折对称分类)稍有不同,基本一致。
【特别说明】如果想完整了解这篇文章,请看发布于数学中国“哥德巴赫猜想难题”栏目中的“转发张彧典的《四色猜想中染色困局构形的4-染色》”(3部分)。
|
|