数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 2799|回复: 1

埃雷拉(Errera)图问世100年 研究成果综述

[复制链接]
发表于 2021-11-24 11:58 | 显示全部楼层 |阅读模式
本帖最后由 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部分)。



发表于 2021-11-26 20:50 | 显示全部楼层
对张彧典《Errera图问世100年》
一文的解读与评论
雷  明
(二○二一年十一月二十六日)

1、关于埃雷拉E—图是不是敢峰先生的所谓“终极图”的问题:
我认为E—图就是敢峰先生的终极图,因为二者未着色时的“裸图”的结构是完全相同的,部分4—着色后的“构形”中各对应顶点的着色也是完全相同的。
但埃雷拉E—图是在1921年构造的(怎么构造出来的不清楚),而敢峰先生构造“终极图”却是在1992年的事。这时敢峰先生是还没有看到过E—图的,甚至连1992年的米勒的图(也是与E—图完全相同的一个图)也是没有看到过的。因为我在2010年后看到了米勒图和敢峰先生的终极图时,认为这是同一个图。曾向敢峰先生提及过他的终极图与米勒图是同一个图后,而敢峰先生曾问过我知道不知道米勒图是怎么得来的。几年后,当我们知道了E—图是埃雷拉在1921年给出的以后,敢峰先生也还问过我E—图是怎么构造出来的。
敢峰先生一至现在还认为他的终极图与E—图不是同一个图,就因为他不知埃雷拉E—图是怎么构造出来的。明明两个图的几何结构与部分4—着色都是相同的,敢峰先生却硬要说不是同一个图,不知这是为什么?
因此,我认为张彧典先生说的敢峰先生是在“专门研究这个A.Errera构形的生成原理”的结论是不对的。敢峰先生根本就不是在研究E—图是怎么构造出来的问题,而是在“寻找”所谓的“二阶四色不可解线路集合基准图”中,最后得出的一个实际上仍是四色可解的图(构形),即敢峰先生所说的最后三阶四色可解。所以说敢峰先生的“四色不可解线路集合基准图”一词用得也是不科学的。
这里我仍要说证明四色猜测与某图是如何得来的是没有关系的问题,不管某图是怎么构造出来的,它都是客观存在的。难道说埃雷拉没有说明E—图是怎么构造出来的,这个图就不存在了吗?明明是从1921年就存在到现在整整一百年了嘛!
再者,我仿用与敢峰先生同样的方法在个别步骤上,小的地方操作有所不同(先生先是在某连通环的一侧对着有另外两种颜色的所有顶点进行换色,然后再构造连通链的可控换色;而我则是先构造连通链,然后再施行坎泊的颜色交换技术的构图—着色办法),但最后也得到了与先生终极图完全相同的图。
我在仿敢峰先生的构图中,也有与敢峰先生的操作有大的不同的地方(先生在第二步演绎中,走的是绕大圈的弯路,而我则走的是不绕弯的捷径),最后得到的结果却不相同(见我的《仿敢峰先生的转型演绎法构造一个无经过围栏顶点的环形链的有双环交叉链的颜色冲突问题的模型》一文):先生得到的是终极图,是属于有经过了构形的关键顶点的环形链的构形;而我则得到的是属于没有经过经过了构形的关键顶点的构形。先生得到的构形是只能用断链交换法解决,而不能用转型交换法最终解决的构形,而我得到的构形却是既可以用转型交换法最终解决,又可以用断链交换法最终解决的构形。
即就是敢峰先生本人,也还是用了四环演绎和三环演绎两种不同的演绎方法,却也分别都用了十五步得到了相同的终极图。
所有这些,不都是说明了相同的图是分别有多种构造办法的,证明四色猜测时,是与图是如构造出来的是完全没有关系的吗?
说到这里,还要说,图或构形只能分成不可避免的各种类别,没有什么“终极图”的存在。各不可避免的构形都是可约的了,四色问题也就解决了。“终极图”只是属于含有经过了构形的关键顶点的环形链的构形一类(当然还有不经过构形的关键顶点的另一类)中含有A—B环形链一类(当然也还有C—D环形链的另一类)中的经过了双环交叉链的共同起始顶点A的一种(当然也还有经过了双环交叉链的交叉顶点A的一种,以及同时经过了双环交叉链的这两个关键顶点A的又一种),并不能代表所有的有双环交叉链的构形。
所以,只研究了一个终极图是可约的,还是不能最终的解决四色问题的。这一建议是不是请网友与敢峰先生慎重的考虑一下。
2、关于埃雷拉E—图的解决的时间问题:
张彧典先生说:美国的琼·哈钦森和斯坦·瓦贡(n Hutchinson and Stan Wagon)1998年2月发表在《美国数学月刊》(e American Mathematical Monthly)《肯普再研究》(mpe re-study)一文是“专门研究这个A.Errera构形的解法”,“他们给出一种KK算法,巧妙地解决了A.Errera构形的正确4-染色问题。敢峰先生也在文献【1】中给出同样的解法。”
这种提法也没有大错,可以说该文是专门研究E—图的解法的。但这个解法却早已由欧文·基特尔(IRVING-KITTELL)1935年在《美国数学学会会刊》上发表的《对部分4—染色地图的一组操作》一文中出现过了。当时欧文·基特尔虽没有过多的论述为什么使用该方法就可以解决E—图的可约性问题,但必竟是把E—图的可约性问题解决了。而且《肯普再研究》一文中的KK算法实质上就是欧文所用的叫做“对顶切链换色法”(也叫ε—操作)。这在《肯普再研究》一文中也特别的进行了说明:“有一个更好的方法可以处理Errera反例。正如Kittell 于1935年所观察到的那样,如果我们对由5度顶点的邻点组成的环上的相关联顶点所决定的色链上进行换色,那么我们可能会使肯普方法成功。Kittell用“正切链”的术语来指由相关联顶点所决定的色链。”以后的敢峰先生,张彧典先生,雷明先生和懂德周先生对E—图的解决方法也都与欧文的解法是相同的。
3、关于H—换色程序、2.1算法和E—图的周期循环问题:
我认为实际上H—换色程序与2.1算法是同一回事,按二者进行操作的结果就都会产生E—图的周期循环。不存在谁与谁是互逆定理的问题,H—换色程序与2.1算法连续操作的结果必然是E—图的周循环。
该循环有两个,一个是以构形顶点的颜色循环为周期的构形类型的小循环,即BAB型—DCD型—ABA型—CDC型—BAB型的逆时针循环或BAB—CDC型—ABA型—DCD型—BAB型的顺时针循环,因为图中只有四种颜色,所以小循环的周期是4,即4次H—换色程序的转型就是一个小循环;另一个是以构形的围栏顶点所着的颜色为周期的各顶点所着颜色的大循环,因为这里所研究的5—轮构形有5个围栏顶点,所以是由5个小循环构成了一个大循环,其周期是5×4=20,也即20 次H—换色程序的转型就是一个大循环。
由于这样的原因,也就不存在张先生后面所说的原定理与逆定理的说法。
4、关于张彧典先生的九大构形的不可免集的问题:
张先生说:2004年,他“把赫伍德反例的类型按照解法的不同分成两类:一类是用4次逆时针颠倒染色程序可解的(按照4—染色地图中包含的6种色链之不同数量组合与相交组合确立了8个构形),一类是用Z—染色程序可解的A.Errera构形。写了《肯普证明的完善》【6】发表于山西省忻州师范学院学报(自然版)第二期64-68页。”
这里的前一类构形就是张先生在二○一○年出版的《四色问题探秘》一书中的九大构形集中的前八个构形,后一类则就是第九个构形——E—族图类构形。但这里说的有点出入,前面说的前一类是“用4次逆时针颠倒染色程序可解的”与原构形集不符。实际上原构形集中的构形,后一个是要比前一个依次增加一次颠倒次数的,最后的第八个构形最高达到了九次颠倒,这里说4次是不符合实际的。
5、关于E—族构形的来历问题:
张彧典说他“用两种不同的方法(不知是两种什么方法——雷明注)找到了与A.Errera构形同态的另外3个构形,组成A.Errera族4构形,简记为E—族构形—E1、E2、E3、E4。其中E1就是A.Errera构形。这4个构形与敢峰先生文献【1】中第17—20步得到的4个构形完全一样。”实际上在进行H—换色程序(即2.1算法)4 次时,分别得到的结果就是E2、E3和E4,加上原有的E—图(也就是E1),即E—族构形共有这四种。
6、关于四色四边形的问题:
张彧典说:他“发现了‘在正确4-染色的极大平面图存在至少一个四色四边形’的定理1;还发现了‘四色四边形中的两条对角链不能同时存在于同一个四色四边形的性质定理2。”
这里的定理1成立不成立,我们来看一个4—染色的图——正八面图的顶点4—染色图(见图1),图中的所有四边形都不是用四种颜色染色的,有2—色的,也有3—色的,唯独没有4—色的。这就说明了“在正确4-染色的极大平面图存在至少一个四色四边形”的定理是错误的。

至于定理2“四色四边形中的两条对角链不能同时存在于同一个四色四边形”中,这句话说得有点问题,也是错误的。四边形的两条对角线不能同时存在于同一个四色四边形中,难道能同时存在于2—色四边形和3—色四边形中吗?四边形的两条对解线是不能同时存在的,而只能存在一条这谁不知晓呢?
这两个“定理”张先生还把它作为后面研究H—构形的分类的根据,前面的根据都错了,后面的研究还能是正确的吗?因此也就产生了他用改变E—族构形中的四色四边形的对角线的方法得出的15个非十折对称的Z—构形中,也同样含有经过了构形的关键顶点的环形链,与E—族构形有了相同的特征链,且又遗漏了不含有经过了构形的关键顶点的环形链的构形(后面“关于构型有的分类问题”一节中还要谈及这一问题)。
7、关于构形分类问题:
张先生在单独研究E—图构形时,连续进行4次H—换色程序,分别得到的4个构形中都含有A—B环形链,他把注意力都集中到环形的A—B链上了,4个构形只要交换了A—B环内、外的任一条C—D链(这就是张先生的Z—换色程序的最原始用法,也就是雷明的断链交换法),都可以使构形转化成可约的K—构形,E—图的可约性问题得到了解决。
当他得到了E—族构形并都整理成标准的BAB型构形后,已发现了E1和E3都含有环形的A—B链,而E2和E4都含有环形的C—D链,他并不认为这是施行断链交换法的关键特征,仍要坚持把构形分为所谓“十折对称”的E—族类构形和“非十折对称”的非E—族类构形。而看不到在他的两类构型中却都有含有经过了构形的关键顶点的环形链的构形这一现象,而产生了“你中有我”和“我中有你”的局面,而且对有共同特征的构形解决时却也采用了不同的方法。虽然非十折对称的构形中也有含有经过了构形的关键顶点的环形链,但解决时却不用简单快捷的Z—换色程序和断链法,而只得用多次连续转型的H—换色程序。他用改变所谓的四色四边形的对角线的办法得到的十五个Z—构形中,也既含有经过了构形的关键顶点的环形链的构形,也含有不经过构形的关键顶点的环形链的构形。请问,不是用改变四色四边形的对角线的办法得到的不含有经过了构形的关键顶点的构形的解决办法是什么呢?张先生却没有回答。
我是这样对构形进行分类的:首先把构形分为含有经过了构形的关键顶点的环形链的构形和不含有经过了构形的关键顶点的环形链的构形。前者用断链法进行解决,E—图只是其中的一种;后者用连续的转型交换法进行解决,一定是会在有限次转型后得到解决(后面还要进一步谈到)。而对于有A—B环形链的构形,则用交换C—D链的办法解决;对于有C—D环形链的构形,用交换A—B链的办法进行解决。对于无环形链的构形也有两中解法,可以用交换对角链法进行解决,也可以用交换邻角链法进行解决。没有出现任何构形被遗漏,证明是完备的。
8、关于H—换色程序和转型交换法是否要证明其操作次数的上限值的问题:
十折对称的E—族图构形用H—换色程序解决时会出现无穷的周期循环,我们也已经发现了有转型次数大于20次以上的非十折对称的构形。是否所有的非十折对称的构形的转型次数都是有限的呢,必须给出一个证明出来。否则,不知道上界是多少的“有界”就有可能成为“无界”的无穷循环。只说是有限的,但没有上界还是不行的。
我的证明就是,因为十折对称的的E—族图构形用H—换色程序解决时,产生无穷周期循环的原因就是因为图中有一条经过了构形的关键顶点的环形链,而我们这里所要证明上界值的构形却是不含任何经过了构形的关键顶点的环形链的构形,没有产生无穷周期循环的条件。但这只是说了是“有界的”,不会是无穷的,但这里的“界”却没有一个具体的数值。所以还是要证明“上界值”的。我用四环演绎法和三环演绎法都已证明了其上界值是5(可见我的《不含有经过了关键顶点的环形链的构形的最大转型次数》一文)。
9、关于十五个Z—构形与敢峰先生的十五个四色可解构形一一对应的问题
张先生说:“为了验证这个结论的正确性,他(指张先生本人——雷明注)对E—族4构形中的62个(在4个构形中的分布依次为17、15、15、15)(不明白这里说的15和17是什么意思——雷明注)四色四边形对角链进行变换,得到62个非十折对称几何结构的构形,然后对它们分别施行H-染色程序,最多颠倒染色16次就可以得到正确4-染色,按照颠倒染色次数从少到多,一共可以得到15个有解构形,与敢峰先生的文献【1】中的前15个无解构形,形成一一对应关系。”
敢峰先生的文献《四色定理登顶证明》中的15个无解构形一部分(10个)是可以用连续的移去两个同色的方法解决的,另一部分的(5个)则是用连续的H—换色程序解决的,而你在这里的15 个Z—构形却全是用连续的H—换色程序解决的(其中有5个还可以用Z—换色程序解决),怎么能形成一一对应的关系呢?
10、关于我对构形分类的依据——构形的四个关键顶点的问题:
在含有双环交叉链的H—构形中,连通且交叉的A—C链和A—D链是不能交换的,B—C链和B—D链又不能连续的交换,四种颜色所能构成的六种色链中就只有A—B链和C—D链可以交换了。这样的两条链在构形中可以是直链,也可以是环形链。但两链却不可以相交叉,因为这两种链是相反链,没有相同颜色的顶点。
另外,具有双环交叉链的H—构形中,两条双环交叉链的共同起始顶点A和两链的两个末端顶点C和D,以及两链的交叉顶点A,都是处在一种特殊的位置,这四个顶点中的任一个顶点的颜色只要发生了变化时,双环交叉链也就断开了,破坏了形成H—构形的必要条件,构形也就转化成了可约的K—构形了。把这四个顶点就叫构形的关键顶点。
如果构形中有了一条这样的A—B环形链,该链就可以把经过了双环交叉链的末端顶点的C—D链与其他的C—D链分隔在环形的A—B链的内、外两侧,交换了经过双环交叉链的两个末端顶点的C—D链,或者A—B环另一侧的C—D链,双环交叉的A—C链和A—D链就都会断开,构形也就转化成了可约的K—构形了。
如果构形中有了一条这样的C—D环形链,并把双环交叉链的共同起始顶点A和交叉顶点A分隔在环形的C—D链的两侧,交换了任一侧的一条A—B链,也都可以使双环交叉链断开,构形也就转化成了可约的K—构形。
对于不含有经过了构形关键顶点的环形链的构形,前面已经说了,就用H—换色程序或转型交换法解决,其转型的次数最大不会超过5 次。

随便的说了一通,请张先生考虑,是否正确,请张先生指正!

雷  明
二○二一年十一月二十六日于长安

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-10 18:52 , Processed in 0.090800 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表