[讨论]我与一棵小草关于断链法的讨论

雷明85639720

互换，使五边形五个顶点染色数减少到3。见图3-9（1）、（3）图解。
几天来，我针对他给出的四个连续用H换色程序得到的图 ，思考“Z解法”的思想到底是什么？它的实质还是“断链”！看了您的文章之后，我也试着断链，还可以得到不同的断链方法。如果把你们的断链思想应用到K构形也是有效的。
断链法的长处是，换色次数最少；短处是方法不唯一，因人而异。
目前，我正试着用根据5邻点的构形，比如CDC构形，理解为一个模块，它的相反链是：A-B，理解为另一模块。这两模块看做就像魔方一样可以变换对接，用来达到断链之目的。这是借助“相反链与构形”的符号，来研究断链法。以便于叙述起来更直接、明了。
学习了你们的文章，我要取你们的长处----断链法思想！
12,16,我回复：
朋友，谢谢你的鼓励。我的这个断链的思想，也是我在最近对我以前给图着色的一个总结。以前我提的是从什么地方开始对什么链进的连通性的破坏，后来我发现实质上就是把连通链断开，所以才改提叫“断链法”。我的这个方法可不可以成为你要求的钥匙呢。雷明
12,17,一棵小草：
雷明：
（1）你的这次看法很好，思想更精练了。实际是思维换了方向----不走肯普换两个同色的道路。而是去考虑3个单色顶点的不连通性！这也是你以前破圈法的进步。我以为，还可再精炼下去--达到图的运算级别！到那时，就好用语言描述了。我们才能可与别人一起使用了。慢慢来，别着急。
（2）我想借你的图，我们共同理解一个定理，对我们都会有益的。
《警钟长鸣》提到证明不成立的原因（2）（我略去，你自己查），我总觉得与下面的定理有关。
怎样理解定理“奇圈和奇数阶轮图都是3-色图，而偶数阶轮图为4-色图。”，引自北大耿素云等编著的《离散数学教程》，可见我的博客《关于图的运算》。
我的初步感觉是：既然书上有了这个定理，《警钟长鸣》（2）的提法就是矛盾的，否则，就是我的理解有问题。请你琢磨琢磨！
12,17,我回复：
朋友，你应把你要与我共同讨论的问题写祥细一点讲给我，我还一下子看不出来你要说的是什么问题。但我要说的是，别人所说的奇阶轮与我们所说的奇轮是不一样的，奇阶轮是指全轮共有奇数个顶点（即图的阶是奇数），而奇轮是指轮中有奇数个轮沿顶点。所以说奇阶轮就是偶轮，偶阶轮也就是奇轮。我们说奇轮是四色的，偶轮是三色的，而他们说奇阶轮是三色的，而偶阶轮是四色的。这两种提法实际上是等价的。由于图论中翻译的专业术语极不统一，某些相同的东西各人的叫法也不尽相同，所以常有这样的事发生。因此，在提到某个专业名词时，首先必须向读者说明白。雷明
12,17,一棵小草：
雷明：你关于那个定理中的术语的说明我看了，过去你说过。这一点很必要！趁热打铁，请接看（3）你画的第13图--17图，都很好。在此基础上，你可以再提升对“断链的思考”：选其中任意一图，只保留V、1、2、3、4、5及它们之间的连线。假设2--4或2--5之间有连通链，你还能断链吗？
有问题，可看我的博客《关于图的运算》，我们共同学习。你暂时放下上个帖子的（2）.以后再说。
12,17,我再次回复：
一棵小草朋友：
1、我只所以坚持说是赫渥特错了，主要就是因为他明知不能交换的链他却硬要去进行交换，怎么能空出颜色来呢；再是他不想办法把用得次数少的颜色移去，却硬要把用了两次的颜色移去；坎泊并没有说一定能够移去两个同色，他却硬要说不能移却两个同色就是说明坎泊的方法错了。
2、我一直不把交换与约当曲线连系在一起，是因为没有约当曲线的图也存在着交换的问题，如一个5—轮图，5个轮沿顶点用去了四种颜色，显然这里没有约当曲线，难道都不进行交换了吗，难道这个5—轮的中心顶点着不上已用过的四种颜色之一吗。这里关键的问题是，所交换的链一定要是不连通的，而不是有没有约当曲线的问题。
3、不连通链交换后才能空出颜色来，而连通的链则即就是交换了也空不出颜色。怎么办，只有想办法对连通的链进行破坏，这就是断链法，有了不连通的链，当然就可以交换而空出颜色了。
4、82615471一伙，他们只是书呆子，一味的相信书本。他们除了对用三连通的三次平面图都是3—边着色的理论证明猜测（这就是早已被否定了的泰特的证明）外，几乎所有的证明方法他们都反对了，要他们拿出理由来，他们却都给的是书本名和页码，这算什么理由嘛。他们也没有看一看人家书上是在说什么，只要有人说的与书上的不相同，他们就统统说成都是错的。难道与书上说得不同就都是错的吗。书本上的东西难道都一定是正确的吗。历史上后来者否定前者的例子还少吗。
5、“假设2--4或2--5之间有连通链，你还能断链吗？”你说的这种链有两种，一种是相交的，一种是不相交的。相交的一定要断链而且可以断链，一种是从任一个交叉的顶点处断链，另一种是从两链不相交的另一端断链，两种方法都可以，但是要在不同的情况下才使用不同的方法的（如我上文中的几个图中的断链那样）；不相交的也可以断链，也可以不断链，由于在这种情况下，两链的起点是同一个顶点，所以从这一顶点也可以断链，但不断链同时移去两个同色也是可以的（这就是坎泊证明已用过的方法）。这说明，着色时，有时要用到断链的方法，有时则不一定都得用此方法。象我在上面2中说的5—轮中的交换，图中根本就没有连通链，该断什么呢。所以说要灵活的使用。
雷明，2012,12,17,
12,18,一棵小草：
雷明：你好。
你谈的这5条，在大方向上看，都是对的；我早已接受。之所以要求你再提升“断链的思考”，是因为那些图都是你亲自画的，如果没有画图经历，我是不会提出这个思考的。对于连图都不会画的人，就像用Kempe的范式交换颜色一样-----这么理解存在“还需要选择”的过程呢！
你已经在着色问题上提高一大步了，我很高兴。我们仍需努力，在大目标（5邻点4着色）不动条件下，看-----还能怎么断链？虽然难一些，不要紧；只要我们肯登攀！因为我们不能满足于就咱一、两个人会断链。
下面介入《警钟长鸣》提到
（2）第 5，6 种证明方法，不能成立的原因，在于
在有 n 个面的平面图 G 为 4-面可着色，而外部面着第 4 色时，与外部面相邻的面所形成的环才最多着 3 色。
在与第 n+1 面相邻的 G 的 5 个面（包括外部面）已着 4 色时，无法证明第 n+1 面也可着这 4 色中的某一色！
（注意 ---- 这是运用“数学归纳法”，证明四色问题时，不可缺少的关键一步！）
我从书本上抄来个 定理：“奇圈和奇数阶轮图都是3-色图，而偶数阶轮图为4-色图。”，引自北大耿素云等编著的《离散数学教程》，可见我的博客《关于图的运算》。
既然书上有了上面这个定理，《警钟长鸣》（2）的第二句话本身就有毛病。否则，就是我的理解有问题。请你琢磨琢磨！
12,19,我回复：
朋友，你说了两次“提升‘断链的思考’”，我一直不明白其中的含义是什么。可以说你今天说的“之所以要求你再提升‘断链的思考’，是因为那些图都是你亲自画的，如果没有画图经历，我是不会提出这个思考的。对于连图都不会画的人，就像用Kempe的范式交换颜色一样-----这么理解存在“还需要选择”的过程呢！”我还看不明的是在说什么，请你把问题说得明白一点，或者谈一个具体的问题，我们共同商讨可能好一些。
82615471的上述第二句话“在与第 n+1 面相邻的 G 的 5 个面（包括外部面）已着 4 色时，无法证明第 n+1 面也可着这 4 色中的某一色！”是他自已说的，他说的当然就不一定是对的。且他在这里说的是他“无法证明第 n+1 面也可着这 4 色中的某一色！”，但并不能代表别人也不能对其进行证明。这完全说明了他才是那种只要与他的观点不相同，他就认为别人都是错误的。所以他就一口气说出了十种与他不同的观点（当然也包括以上的5、6两种观点在内）都是错误的。他应该在否定人家之前，说出人家的证明中具体在那些地方有错误的才行，不不应笼统的说都是错误的。我就是非常反对这种作法。雷明
12,19,一棵小草：
雷明：
（1）谢谢你关于《警钟长鸣》提到“在与第 n+1 面相邻的 G 的 5 个面（包括外部面）已着 4 色时，无法证明第 n+1 面也可着这 4 色中的某一色！（注意 ---- 这是运用“数学归纳法”，证明四色问题时，不可缺少的关键一步！）”的琢磨。我是觉应该直接用定理“奇圈和奇数阶轮图都是3-色图，而偶数阶轮图为4-色图。”推出：第（n+1)面是可以着上4色中之一色的！因为偶数阶轮图为4-色图。你认为这样推理有问题吗？
既然书上有这个定理，《警钟长鸣》的作者难道不知道？
（2）我在等待你的回复时间里，又仔细看了你的图2.因为我在同时学习两个人的思想，你的断链法和张彧典的“Z解法”的思想。我简单谈一点感觉，你看我感觉得对不对。图是你画的，字母是张的。图2的第2图，我们习惯将D2写成D1（因为B1与D1互换），而图上的写法与图表解中一样---沿用第1图两个联通的B1-D2.这在张的文章中很普遍。第一次见着，我很奇怪；因为它是联通的。你有这个感觉吗？现在第2图已转换为半非H图了（属于DCD构形）。有意思的是，我们让A1-D1互换，得到DBD构形。这个DBD构形图，B2至A1是断开的。究竟我的感觉对不对？等待你的回复。这算我对断链的思考吧！
（3）对“Z解法”的思考。对图13、图14、图16，都互换4、5两色，图转为K构形，可解；而图17，互换1、2、3，同理可解。
12,20,我回复：
朋友：
1、82615471说的“在与第 n+1 面相邻的 G 的 5 个面（包括外部面）已着 4 色时，无法证明第 n+1 面也可着这 4 色中的某一色！”这句话本身没有图就是很难明白的。这句话我理解是图G有有n＋1个面，其中第n＋1个面是与外部面相邻的，且与第n＋1个面有5 个面相邻，包括这个外部面在内。把这个图画成对偶图时，仍是待着色顶点与5 个已着了四种颜色的顶点相邻，这时就不存在什么外部不外部面的问题了。这我们不是已经证明了这样的待着色顶点是可以着上其他顶点已用过的四种颜色之一吗。所以我说是他不会着色，就说别人的证明方法不对，他才是一个唯我主义者。他到现在一百产十多年后，还在与坎泊同样在使用地图的术语在证明猜测，不是也太的落伍了吗。放着容易明白的给图顶点的着色方法他不去用，而硬要在用难以理解的给地图（平面图）的面上的着色去证明呢。
2、你说的（2）、（3），我得好好的看一看，然后再给你回复，因为按你说的，我还得对照我与张的文章和图，慢慢的来。但不管怎么说，只要我们对那些图都能4-着色，就是胜利。我还要说一次，不同的双×夹×型其实都是一回事，难道双B夹A型，我们把A、B二色互换，不就成了双A夹B型了吗，不就都是你所说的5邻点4着色吗，为什么要在什么夹什么上去多纠缠呢。
雷明
12,20,一棵小草：
雷明：你好。你的回复我看过了。第1条说的有一定道理。对第2条，你慢慢看，我不着急。看到杨博士要帮助您，我很高兴。期待您的成功！
12,20,我回复：
谢谢你。我明天要去山西，可能对你的回复要在一星期以后了。
12,20,我留言：
朋友，为什么过去82615471的［警钟长鸣］和现在的xyz-xyz的［*］总是在《数学中国》网页的最上边呢，也看不到别人有贴子发上去，就自动向上移动了，不知是为什么。我想这里面一定有人在作怪。
12,20,一棵小草回复：
雷明：你好，祝你一路顺风。xyz-xyz的《警钟长鸣》我早已注意到，已录下几个贴子。慢慢看见。
12,21,我留言：
朋友，我看了几次张彧典的书，但都不明白所谓的H—换色程序、Z—换色程序和Z撇—换色程序道底是什么样的程序。是不是就是米勒所说的“逆时针希伍德颠例”呢。请明示。雷明
12,21，一棵小草：
雷明：你好。
1），什么是“H换色程序”？你只看书的某一段，恐怕是找不到。我没有书，在他的图表解中，你看第六（H构形简化集及不同解法。其中图3-1、图3-2，下面都有文字说明。你看完说明，就可明白H程序的过程了。因为他不认为希伍德反例图有毛病，所以他是通过因势利导（不去交换，换色进行不下去）法得到的换色程序。而我有了根据以后，认定希伍德反例图有毛病。故直接可以继承肯普的原来的方法，再依新的构形-----两同色夹一色，继续使用肯普的方法。只要记住那个模式就行了。我们两个的方法其实是一样的。由于得到的过程不同每个人起的名字不一样罢了！可以说是殊途同归。
2）Z解法，也在这部分。图3-9的拓扑转换图下面 的文字说明就是。就是一句话。
3）他的这些运算都包含希伍德颠倒！
4）读了他的文章，我有一个感觉：数学证明好比是一种信仰。思则有，不思则无。数学证明就在每个人的头脑中。用理性的语言表达，证明就是理解的过程。之所以需要沟通，无非是用一种共同的语言去理解！然而，由于存在差异，很难找到共同的语言。证明的过程，就是学习（本身就是同化的过程）的过程。
12,22,我回复：
朋友。你好。
1、我按照你的指引，看了张的“图表解”中的第六个问题的图和说明。我的结论是：他的书上没有这个图3—1和图3—2。我看了下，这个图3—1、图3—2分别就是他前面的“六种色链之不同数量组合”中的图3—1和图3—2，分别就是我在本文中图1中的非H—图型和H—图型。对于他的图3—1，完全是可以同时移去两个同色B的，只交换两次，他这里也是交换了两次；而图3—2我用的是断链法， 顶点A2开始交换A—B链，把顶点A2改着成B色（这就是张所说的“孤点换色”），使图3—2变成一个非H—图型的图，再交换一次就可以空出一种颜色来，一共只须用两次交换，而张先生则用了三次交换，比我多了一次。
2、张先生对图3—2所用的办法，就是米勒对赫渥特图的那种被张先生翻译成“逆时针赫伍德颠倒”（我理解这里的“颠倒”就是“交换”的意思，即把某条链中各顶点的颜色相互“颠倒”一下，也就是交换）的方法，即每次交换都是从“两个同色”所夹的“一色”顶点开始，逆时针转的那个“同色之一”顶点开始进行关于“同色”的链的交换，进行了两次“逆时针赫伍德颠倒”后，才使图3—2变成了非H—图的图。我认为他所说的H—换色程序就是这个玩意儿。但要看到，他所进行的每一步交换都是在应用着坎泊的颜色交换技术。
3、张先生对图3—2的着色方法以及米勒对赫渥特图的着色方法都是用的那种叫做“赫伍德逆时针颠倒”方法，他们的着色过程实际上就是在把H—图型的图转化为半H—图型的图，并用对半H—图着色的方法空出一种颜色来的过程。
4、你多次提到张的所谓“因势利导法”，我一直不明白其中的含义是什么。今天你又在该术语后用括号加注“不去换色，换色进行不下去”更是叫人无法理解了。张先生的每一步都明明是在“换色”，你却怎么说是“不去换色”呢。他“换色”的结果不也是空出了颜色吗，你又怎么说是“换色进行不下去”呢。我的头也越来越大了。
5、对于图3—9，张用了Z＇换色程序，什么是这一换色程序，你说就是该图后面的文字说明，我看了一下，这不还就是在进行着断链吗。虽然变成的非H—图型的图中还有两条连通的链，但并不是原来的链了。我在本文中对该图着色的办法也是这样。米勒构造出的这个图应该说还是有一定的代表性的，着色是有着一定的难度的，与赫渥特的图有着同样的作用，但其着色的方法最终仍没有离开坎泊所创造的颜色交换技术。应该说我们解决了赫渥特图的4—着色问题，是对坎泊证明中的“漏洞”的一个补充，而对米勒图的4—着色问题的解决，则是寻找到了对类赫渥特图中的较难着色的一种图的着色方法。我的“断链法”思想也是在对米勒图的着色过程中产生的。以前我的提法是对连通链的破坏，而只是在最近我才明确提出了“断链”的方法。我认为“断链法”应时你要找的钥匙，不管张先生用了多少种方法，如H—换色程序，Z—换色程序、Z＇换色程序等，最终都是在进行“断链”。如果说我的这个“断链”的思想就是你说的那么一把“钥匙”的话，那就得证明所有的链是否都可以断开，如果所有的链都能断开，那就能够证明任何一个构形都一定是可约的。你说是不是这样呢。
6、米勒的图与我们以前分折的图的不同之处不在于这个图中的基本条件——有两条相互交叉的连通链——都是满足了的，而在于图中却既有环形的A—B链，又有环形的C—D链，而两订环链的顶点数也都是大于4的，两链的关系是A—B环链与C—D环链的相互嵌套，互不相交，因而又造成了C—D环链不可能经过5C和4D两个顶点，A—B环链也不可能同时经过A1和A2两个顶点。这是与我们以前分折的只有A—B环链而没有C—D环链或者只有C—D环链而没有A—B环链，两环链都只有4 个顶点，且C—D环链直接经过5C和4D两个顶点，以及A—B环链一定同时经过A1和A2两个顶点的H—图型和非H—图型是不同的。就是因为这些原因，才造成了该图既不能从两个同色顶点进行交换同时移去两个同色，也不能从两交叉链的任一个交叉顶点进行交换而破坏其连通性。而只能从两链的端点顶点进行交换破坏其连通性。两链中除了共同的A色顶点外，已知C—B和D—B两链是不能交换的，所以只能从两条连通链中的其他的C色顶点（或D色顶点）开始进行交换，无论那个C或D顶点都可以的，并不一定要从5C和4D进行交换。例如从另一条环形的C—D中的任一个顶点开始进行D—C链的交换，图也就变成了非H图型的图了。你可以试着一下。
7、朋友，不知这一贴的回复还能不能达到兼对你上一贴的回复，如果能达到我就不再专门回复你的上一贴的问题了，否则我可再花一点时间专门再回复你一次。另外我建议，我们俩的交换意见，如果发到别的地方去了，就要用留言方式告诉对方，不则，对方很难发现和看到，也就很难达到交流的目的。常去你那里的、与82615471是一伙的那几个人，以及张彧典先生都主张只有通过着色才能证明猜测的正确与否，但他们却又反对进一步研究很有研究价值的赫渥特图。请问不研究能得出“断链”的升华吗，张先生一直在研究的米勒的图不也是一个很有价值的图吗。米勒的“赫伍德逆时针颠倒”只是一个解决赫渥特图（或H—图型的图）4 着色的方法，但不能无限的进行下去，米勒能在对赫渥特图只进行了两次“赫伍德逆时针颠倒”后，就停了下来，再进行别的交换空出颜色，难道就不能对米勒的图在进行了一两次“赫伍德逆时针颠倒”后也停下来找别的办法空出颜色呢。我在本文中不也对他的四个图分别都空出了颜色（进行了4—着色）了吗。
8、我现在才发现你在转发了我的“九构形的着色问题”之后，自已在其后面的评论。其中说（1）“如图1.若由2至4的链是连通的，则可将V4、V5二色互换，这样并不改变（G-V）的4着色，因此是允许的！类似若有两条链是连通的，也可作如上的处理。”和（2）“这样，2--4链就一定不是连通的！用肯普链法极易使v的5邻点染三色。从而使v着上4色之一色，图的可约性得证。”对于你的第一句话（1），可以说在只有一条链连通的情况下，这样交换是可以的，达到了破坏“由2至4的链是连通”的目的，但两条链都是连通的情况下，你能达到破坏其连通性的目的吗。请你对我在本文中的图1中的H—图型的图用你以上的说法处理一下，看会是怎么样的结果呢。对于你的第二句话（2），我简直不知你是在说什么，为什么“2--4链就一定不是连通的！”的呢，难道因为“2--4链就一定不是连通的！”就能得到结论“从而使v着上4色之一色，图的可约性得证。”的结论吗。请你再着摸一下。
雷  明，2012,12,22,
12,24,一棵小草回复：
雷明：你的这个回复很好。就这几个问题暂时不必回复了，我已经清楚了。最后我说说你的第4条，关于因势利导法。这是张彧典回复我给他图表解的评论时说的。我给你解释一下：由于张不认为H反例有毛病，所以张得到的方法叫做“H换色程序”。你见过H给出过什么换色程序吗？没有！这个程序从表面看就是肯泊的换色嘛。H程序是由于H及类H图给逼出来的。由于交换完1-4后，3-5成了连通的了。怎么办？“如果”不去交换吧，下一步无法进行。他只好因势利导---看看3-5以外，还有没有可交换的了？这就是把刚才得到的图理解为转换了构形（如由ABA转到了DCD），再从两个D开始，再做换色操作！你看，加个“如果”，好理解了吧。这就与张的一直进行的交换不矛盾了。如果张能发现H图的一丁点瑕疵，（我们两个讨论约当曲线的时候，如果他也来讨论），他就会很轻松地得出现在的程序。不必因势再利导了。这就是认识是第一位的道理。你现在对“断链”的认识，比“破圈法”高明多了，哪里来的？靠提高认识升华来的。
12,25,我回复：
朋友，就按你说的，我们就“断链”的讨论先暂搞一段落吧。再见，以后再聊。雷明
雷  明
二○一二年十二月二十一日整理于长安