我研究四色问题的思想方法——与张彧典先生商榷

雷明85639720

我研究四色问题的思想方法
——与张彧典先生商榷
雷  明
（二○一七年元月十日）

1、把一个无限问题变成有限的问题
图有平面图，有非平面图；平面图中又有道路，树，圈，轮，完全图，极大图等多种种类；每一种类中又有无限多的图，每个图的顶点又可以是无限的，每个顶点的度也可以是无穷多的；四色问题是与这些无限取值的参数交织在一起，也成了一个无限问题。
1、1  平面图的着色
不管平面图是如何的复杂，着色时总是一个一个的顶点去着色，当遇到待着色的顶点的相邻顶点已占用完了四种颜色时，总可以把该顶点周围的色圈想法断开，这就是“破圈”。
1、2  破圈着色法
可以把待着色顶点外面的色圈中使用次数最少的颜色的顶点，作为切入点，把该顶点的颜色去掉，并把该种颜色给这个待着色的顶点着上。与此同时，又将产生一个或多个待着色的顶点。新的待着色顶点周围若仍占用完了四种颜色时，就再继续的“破圈”，否则，新的待着色顶点就可着上图中已用过的四种颜色之一。
1、3  待着色顶点的着色
当图中除了待着色顶点外，所有的顶点都已着上了四种颜色的一种，也不存在相邻两顶点着有同一颜色的情况，有以下几种情况：
1、3、1  当待着色顶点的相邻顶点所占用的颜色少于四种或者该顶点的度小于等于3时，直接就可以给该顶点着上四种颜色之一；
1、3、2  当待着色顶点的相邻顶点已占用完了四种颜色且其度大于等于6时，就用破圈法，一直破下去，一定能找到一个新待着色顶点的度是小于等于5的，因为任何平面图中一定存在至少一个顶点的度是小于等于5的。
1、3、3  以度小于等于5的顶点构成的轮形构形，就是平面图的不可避免构形，5—轮的中心顶点叫做待着色顶点，用V表示，轮沿顶点叫做围栏顶点，简称“围栏”。这些不可避免的构形只要是可约的，即是可4—着色的，平面图的四色猜测就是正确的。由这些不可避免的构形构成的集合，就是平面图的不可免集；
1、3、4  若最后一个待着色顶点的度是小于等于4的，一定是可以着上四种颜色之一的，因为坎泊已经用他创造的颜色交换技术的三种作用之一——空出颜色的交换，证明了这种构形是可约的。
1、3、5  所谓颜色交换技术，就是把由两种颜色交替进行着色的道路（这种道路在着色中叫做色链，简称“链”）中各顶点所着的颜色互换，就叫做颜色交换，简称“交换”。把可空出颜色给待着色顶点的交换，即通过交换可以从围栏顶点中空出一种颜色来，给待以顶点着上的交换就叫空出颜色的交换。这种交换一定是从围栏顶点开始的，交换的链是由两个对角围栏顶点的颜色构成的色链，但该链在两个对角围栏顶点间却是不连通的，否则是不能空出颜色的。
1、3、6  但是，在有些平面图中却不一定都存在度小于等于4的顶点，如正二十面体所对应的图，各顶点的度都是5，没有小于等于4的顶点，所以证明5—构形是否可约也就成了一个关键；
1、4  5—轮构形
把5—轮构形的轮沿顶点的名称用1，2，3，4，5表示，相应的各顶点所着的颜色用B，A，B，D，C表示。这样的5—轮构形可表示成123—BAB型5—轮构形。
1、4、1  1879年，坎泊只证明了5—轮构形中的无连通链，只有一条连通链，有B—C和B—D两条交叉的连通链，有A—C和A—D两条连通的、有共同的起始顶点2A、但中途没有交叉顶点的这几种情况下，5—轮构形都是可约的；而没有证明A—C和A—D两链既有共同的起始顶点2A，中途又相交叉时的情况是否可约；
1、4、2  A—C和A—D两链既有共同的起始顶点2A，中途又相交叉时的情况中，也有可以同时移去两个同色B，空出B的给待着色顶点着上的构形。如“九点形”构形中的含有A—B环形链，和既不含有A—B环形链，也不含有C—D环形链的情况，都可以同时移去两个同色B。其他的情况则是不能同时移去两个同色B的构形；
1、4、3  不能同时移去两个同色是赫渥特图型构形的特点，把这种构形叫赫渥特构形，用H—构形来表示；而把坎泊已证明是可约的构形和所有可以同时移去两个同色的构形统一叫做坎泊构形，用K—构形来表示。所以就目前看，证明H—构形是否可约就是证明四色猜测的一个最关键的问题了。
到此，我们就把一个无限的四色问题变成了一个有限的问题。
2、5—轮构形都是可约的
2、1  H—构形
2、1、1  H—构形又有四种情况：只含有一条A—B环形链的，只含有一条C—D环形链的，既含有A—B环形链，又含有C—D环形链的，以及任何环形链都不含的，共四种。H—构形中，A—C链和A—D链是连通的，不能交换，因为它空不出颜色，所以A，C，D三种颜色均不可能空出；B—C链和B—D链又不能同时交换，所以也不能空出B。但可以想办法破坏连通链A—C和A—D，使之成为不连通的，使构形变成K—构形而可约。
2、1、2  含有A—B环形链的构形，A—B环必然把C—D链分成环内、环外互不连通的两部分，交换环内、环外的任一部分C—D链，都可以使A—C和A—D链断开，使构形变成为K—构形。这种情况与含有A—B环形链的“九点形”构形则是不同的，这里是不能移去两个同色的，而“九点形”则是可以同时移去两个同色的构形；
2、1、3  含有C—D环形链的构形，C—D环也必然把A—B链分成环内、环外互不连通的两部分，交换环内、环外的任一部分A—B链，也都可以使A—C和A—D链断开，使构形变成为K—构形。赫渥特图就是这样着色的。这就是赫渥特图型的H—构形。 这种情况与含有C—D环形链的“九点形”构形的解法是相同的，用的都是断链法；
2、1、4  既含有A—B环形链，又含有C—D环形链的构形，既可以交换A—B环内、外的任一条C—D链，也可交换C—D环内、外的任一条A—B链，都可以使构形变成为K—构形。敢峰—米勒图就是这样着色的。这也就是敢峰—米勒图型的H—构形；
2、1、5  这里虽然也用的是坎泊的颜色交换技术，但其交换的目的不是空出颜色，而是断链，这就是坎泊的颜色交换技术的第二种作用——断链的交换。这种交换并不是为了空出颜色给待着色顶点，而是为下一步空出颜色的交换作好技术上的准备。这种交换不一定是要从围栏顶点开始的；
2、1、6  在H—构形中，唯独不含A—B和C—D任何环形链的构形是不能用这种断链的方法处理的，这就是张彧典先生的第八构形，我们叫它Z—构形，或叫张彧典第八构形型的H—构型；
2、2  Z—构形
2、2、1  Z—构形的特点：在不含任何环形链的H—构形——Z—构形中，A—C链和A—D链都是连通链，不能交换；A—B链和C—D链也都是直链，且只有一条，也不能交换，就是交换了只等于整个链中的两种颜色互换了一下位置，不起任何作用；B—C链和B—D链又不能同时交换。那么我们就只有先交换一个关于B的链。
2、2、2  转型交换：从任一个同色顶点B进行交换时，5—轮构形的类型就会发生改变：若从顶点1交换了B—D链，构形就由原来的123—BAB型变成了451—DCD型；若从顶点3交换了B—C链，构形则也由原来的123—BAB型变成了345—CDC型。这也是在进行坎泊的颜色交换，但交换的目的却是在于使构形进行转型，所以把这种交换叫做转型的交换。注意，这种转型的交换也是从围栏顶点开始的，且必须是两个同色中的一个同色顶点B；
2、2、3  从“九点形”构形看，可以同时移去两个同色的构形与H—构形是可以相互转化的，而Z—构形与“九点形”中可以同时移去两个同色的构形又有相同的特点，即A—B链和C—D链都是直链且只有一条，它一定也应是可以转化为H—构形的。理论和实践都已经证明了这一点是正确的（因为Z—构形的最简模型是一个“十五点形”，其中就有一个缺少一个B色顶点的A—B圈，当从顶点1（或3）交换了B—D（或B—C）后，正好就使得这一缺少B色的顶点变成了B，形成了一个A—B环形链），也证明了Z—构形是可以通过转型交换转化成为赫渥特图型的H—构形的。这是一个必然的结果，而并非偶然；另外，实践和理论也能证明，Z—构形不但可以通过与以上的交换是相反方向的一次转型交换后，可以直接转化成为可以同时移去两个同色的K—构形。总之，说明了Z—构形都是可以转化为K—构形的，是可约的。
2、2、4  到此，坎泊的颜色交换技术的三种作用都已经设及到了。现在还要说的一点是：当图是可以同时移去两个同色的构形时，一定是要进行两次交换才能达到同时移去两个同色的目的。第一次交换是属于转型交换，把123—BAB型的构形转化成为451—DCD型的构型，或者转化成为345—CDC型的构形，而第二次交换则是属于空出颜色的交换。空出来的颜色B对于原来123—BAB型的构形来说，是两个同色B之一的B，而对于新的构形类型来说，则是非两个同色C之外的B。
到此，我们也就证明了所有的5—轮构形都是可约的。
3、四色猜测是正确的
到此，平面图的所有不可免的构形都是可约的了，当然平面图的四色猜测也就是正确的了；平面图的顶点着色又相当于是对地图的面在染色，这也就证明了地图的四色猜测也是正确的；这也就证明了四色猜测是正确的。
4、与张彧典先生交换意见
4、1  我证明四猜测的思想方法是分析构形的可能的结构类型，然后针对每种类型的结构特点，用有针对该类结构特点的单独着色方法去进行解决。分析了由四种颜色所能构成的六种色链的各种情况下的各种构形，并且证明了再也没有其他的结构特点的构形了，也证明了这些构形都一定是可以转化成为坎泊的K—构形的，也就证明了这些构形都是可约的，四色猜测也就得到了证明是正确的。
4、2  你的证明的根本思想却是根据你的图6.1“Z—换色程序”里的所谓的“八次大循环”思想而来的，你所用的“颠倒法”也就是我这里所说的“转型交换”的方法。你不是去分析构形结构上的特点，而是只要凑够了你的颠倒次数在八次以内的构形，就凑够了你所谓的不可避免集。因而你也就把链的结构特点相同、而顶点数多少不同的图凑成了不同的类型（见后面的4、3）。我也说了你在这里的证明也是不充分的，是不能令人满意的；或者说你根本就没有证明只有这八个构形才是平面图的不可免集。关于这一点，我已多次提到过你的证明是不充分的问题。所以当你在遇到了敢峰—米勒图以后，发现对其无限次的颠倒，总不能解决问题时，看到了光用颠倒法是不行的，是没有办法解决该图的着色问题的。所以你只得在你原有的八个构形之外，又增加了一个无限循环的构形，用了与颠倒法完全不同的另一种所谓的Z—换色程序的方法。其实这种Z—交换程序方法就是另外的一种断链方法。赫渥图中用的是交换A—B链的方法来断A—C链和A—D链的，你这里用的是交换C—D链的方法来断A—C链和A—D链的。
4、3  除此之外，还有你的第一和第三到第七的六个构形，在链的结构上都有完全相同的特点，你却因为各个图的顶点数不同，颠倒的次数不同，而把它们分别当作一类，共六个类型。但实际上他们都是属于可以同时移去两个同色B的构形，都可以只颠倒两次，就可以空出两个同色B给待着色顶点（第一构形用从顶点1开始的逆时针颠倒，第三到第七的五个构形都用从顶点3开始的顺时针颠倒）。当我给你提出了这一点时，你却把第三到第七的五个构形归为了一类（注意，这是从链的结构相同上来归类的），而把第七和第八两构形归为一类（注意，这又是从颠倒次都是2来进行归类的。张先生多次强调了这两个构形从顶点3开始进行顺时针颠倒，都是只颠倒两次的），使构形总数由八种变为三种，这种变化未也免有点太大了吧。
4、4  你的构形集共九个构形，它们之间从构形的结构上讲，并没有什么规律性的联系，第三到第七五个构形又是有同样的链的结构特点，但图的顶点数又不同；九个构形解决的办法也是不一样的（第一到第八构形都是用逆时针颠倒的方法，唯独第九构形用的是Z—交换程序）。构形结构没有规律，没有内在的联系，解决的办法又不同，这能说明是用数学归纳法来证明的吗。另外，我多次提出你的图6.1的“Z—换色程序”图中的图，画得有很大的问题，在进行颠倒时，同时又把图中顶点的相邻关系改变了，这是很不合适的。不知你对此是作何反应的。


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

注：此文已于二○一七年元月十一日在《中国博士网》上发表过，网址是：

leisurely

敢峰—米勒图？
发个这图上来可好，看有意思没有。多谢！

雷明85639720

敢峰—米勒图如下：

该图是一个待着色顶点隐去的图，着色时只要使最外的五边形上变成了三种颜色即可。看来你至少没有看过张说典的书《四色问题探秘》，更没有看过敢峰的《4CC与1＋1的证明》一书。
雷明

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

,,,,,,,,,

ptemj645

非常谢谢楼主，顶一下












凤凰中越军事新闻

雷明85639720

谢谢支持。