我与某朋友微信上交流四色问题

雷明85639720

我与某朋友微信上交流四色问题
雷  明
（二○二一年元月十五日）

1、研究四色问题的重点是解决颜色冲突问题
颜色冲突问题就是与待着色顶点相邻的围栏顶点已占用完了四种颜色的情况。
解决颜色冲突问题就是要把构形中围栏顶点占用的颜色数由四种减少到三种，空出一种颜色来给待着色顶点着上。在解决之前一定要把待着色顶点移至度是小于等于5的顶点上，也是一定可以做到的。因为任何平面图中一定存在着度是小于等于5的顶点，极大图也不例外。
四色问题因给地图染色而引起，证明时还得先从地图着手。地图是3一正则的平面图，即各顶点的度都是3。给地图中面的染色就是对地图的对偶图——极大平面图（即每个面都是三边形面的平面图）的顶点着色。这就把一个地理问题转化成了数学问题。
如果四色猜测是正确的，那么任意的极大图就都是可4—着色的。那么可4—着色的极大平面图经去点或减边后所得到的任意平面图的色数只会减少，而不会再增加，所以也就引出了平面图的四色猜测。虽然如此，但证明四色猜测时还得先从地图的对偶图——极大平面极开始。
2、坎泊提出的“构形”概念
只有一个顶点未着色，而其他顶点都已4—着色并符合着色要求的极大平面图叫“构形”，未着色的顶点叫“待着色顶点”，与待着色顶点相邻的顶点叫“围栏”顶点。由于极大图的每个顶点都是处在一个轮的中心，所以极大图的构形都是“轮构形”。
由于平面图中一定存在着顶点的度是小于等于5的顶点，所以极大平面图的“不可避免构形”是轮幅数（即围栏顶点数）小于等于5的轮构形。这就把一个轮幅数可以是任何数的无穷向题转化成了有穷的问题了。只要研究这几种不可避的构形的“可约性”（可约性即待着色顶点可以着上图中已用过的四种颜色之一）就可以了。各不可避免的构形都可约了，四色问题也就解决了。猜则也就是正确的了。否则，只要一个不可避免构形不可约，四色猜测就是不正确的。
围栏顶点占用完了四种颜色的情况叫颜色冲突现象。必须把围栏顶点所占用的颜色数由四种减少到三种，才能空出一种颜色来，给待着色顶点着上。这就是解决颜色冲突的过程。
围栏顶点数小于等于3的构形都是不会发生颜色冲突的，颜色冲突现象只可能发生在围栏顶点数是4或5的4—轮构形和5—轮构形中，这就是不可避免的颜色冲突构形。
无双环交叉链的构形坎泊早已证明了是可约的，而具有双环交叉链的构形只可能发生在5—轮构形中。所以目前证明四色猜测时，主要就是解决5—轮构形中具有双环交叉链的构形的可约性的问题。
所谓的“双环交叉链”是指BAB型的5—轮构形中的对角链A—C和A—D都是连通的，并且都与待着色顶点共同构成了一个“环”，所以叫双环交叉链。
3、坎泊的“颜色交换技术”
用两种颜色交替着色的道路叫“色链”，简称“链”。两条链中的两种颜色均不相同的链叫“相反链”。一对相反链由于颜色均不相同，所以是不能相互“穿过”的。但同一条链中的两种颜色是可以“交换”的，这就是坎泊的“颜色交换技术”。使用颜色交换技术时，要看轮构形的对角链是否连通。不连通时才能交换，空出颜色。连通时则不能交换，是空不出颜色的。
在构形中，若有一对对角顶点的颜色构成的链是连通的，那么另一条相反链则一定是不连通的，一定可以交换，空出颜色。这就是坎泊解决4—轮颜色冲突构形的原理。解决5—轮构形与解决4—轮构形时的道理是相同的，都是用坎泊的颜色交换技术，不过要视具体情况的不同使用不同的交换罢了。
使用颜色交换技术时，要看交换的链的长短，链长，则换色的顶点就多，链短，则换色的顶点就少。最少时就是只换一个顶点的颜色。
4、不可避免的颜色冲突构形的解决办法
具有双环交叉链的5—轮构形，有4个关键的顶点，即双环交叉链的共同起点（着A色）和交叉顶点（也着A色），以及双环交叉链的末端顶点（分别着C色和D色）。这四个顶点只要有一个顶点的颜色发生了改变，图中就不存在双环交叉链了。如果有一条环形链经过了某一个关键顶点，则该环形链又可把其相反链中的关键顶点分隔在环形链的两测时，就叫“有经过了关键顶点的环形链的构形”，否则就是“无经过关键顶点的环形链的构形”。有经过了关键顶点的环形链的构形，还可视构成环形链的颜色分为有A—B环形链的构形和有C—D环形链的构形两种。
有经过了关键顶点的环形链的构形解决时，用的是“断链交换法”。即在环形链内或外交换经过关键顶点的与环形链呈相反色链的链，构形就会转化成无双环交叉链的、坎泊早已证明过是可约的构形了。问题就得到了解决。
对于无经过关键顶点的环形链的构形，则不能再用断链交换法了，而采用“转型交换法”。对于BAB型的构型，即从一个B色顶点交换与其对角顶点的颜色构成的色链，使构型转型。不同方向的转型分另可转化成DCD型的构形或CDC型。然后再根据转型后的构形类型情况进行分析：若是转化成了可约的构形，问题也就得到了解决；若是转化成了有经过了关键顶点的环形链的构形，再按解决有经过了关键顶点的环形链的构形解决就行了；若转型后仍然是无经过关键顶点的环形链的构形，仍然得不到解决，那就继续的按同方向的转型继续转型，一定是可以在“有限次”的转型之内解决问题的。但这个有限次转型的“上界”是多少，还没有确定下来。在这方面我与张彧典先生还是有一定的分岐。
我说了是“有限种”的颜色冲突构形，你想想有双环交叉链的5—轮构形中，除了“有经过了关键顶点的环形链的构形”与“无经过关链顶点的环形链的构形”外，还有没有其他的可能构形呢？在“有”与“无”之间还有第三条路吗？这二者就是不可避免的颜色冲突的5—轮构形。现在这两种构形的可约性问题解决了，也等于就解决了任何5一轮构形的可约性问题。
5、不可避免的颜色冲突构形的两种分类及解决办法
我认为把有双环交叉链的构形分为有和无经过关键顶点的环形链的构形两类，各分别用上述的办法解决。
而张彧典先生则主张把有双环交叉链的构型分为“十折对称构形”和“非十折对称构形”两类。十折对称的构形用Z—换色程序（即断链交换法）解决，非十折对称的构形统一用H—换色程序（即转型交换法）解决。因为十折对称的构形使用转型法时，出现了以20次转型为一个周期的无穷循环；但这种构形中却又含有经过了关键顶点的环形链，所以就改用了断链交换法。而非十折对称的构形中也却有一部分构形在转型20次之后，却并不产生循环转型现象；但这种构形中也有经过了关键顶点的环形链，所以张先生也把这类构形用断链交换法处理。注意，现在已经出现了不同类型的构形用相同的处理办法了。既是这样为什么不把它们归为一类呢？统一叫做“有经过了关键顶点的环形链的构形”呢？
对于其他的非十折对称构形，不管其中是否有经过了关链顶点的环形链，张先生都统一用转型交换法，并构造了由15个构形构成的Z—构形集，单方向转型的最大转型次数是16次。两个方向转型中，总有一个是小于等于9次的，所以就认为最大的转型次数的“上界”是9。硬拼凑够了他原来的八个构形中最大交换次数是“9”的数字。
张先生的这个分类方法是很混乱的，解决问题的办法又是相互交错的，太复杂了。我问了张先生三次他是如何判断刘千栋的图2是否是十折对称的（因为张先生已经指出了刘千栋的图是用断链交换法解决的），但他始终没有回复。是否是没有办法判断呢（的确十折对称与非十析对称之间是没有明显标志的）？不太明白。如果是这样，我们两人认识的统一可能就为时不远了。
因为对于无经过关键顶点的环形链的5—轮构形的有限次转型次数的上界还没有确定，所以说没有上界的有限仍然是无限。只要有一个图出现了这样的结果，就不能说四色猜则是正确的！但也没有象你说的那样进入了迷阵，只是从理论上还没有确定有限次的上界而已，有限肯定是有限的了。
我对无经过关键顶点的环形链的构形的有限次转型次数的上界，经过理论的证明和实践的证明，都己经确定在5了。不过我现在还在研究其证明方法是否合理和可行的问题。由于这些原因，所以我认为你说我们已证明了四色猜测是正确的还为时过早。
我和张先生都得出了有经过了关键顶点的环形链的构型用断链交换解决，是可约的；而无经过关键顶点的环形链的构形用转型交换法解决，也一定在有限次转型之内都可以解决，只是两人对有限次要不要证明上界的存在，如何证明，证明的结果是多少，还存在着分岐。但这并不影响我们认为四色猜测的正确性。但作为证明来说，对已下结论的“有限次”没有一个上界，总觉得不太完满！
6、朋友提出的另一种证明方法
你的基本想法是对的，这就是图论中的“顶独立集”理论，每个顶独立集中的顶点都是互不相邻的，当然用同一种颜色是可以的。但你划分顶独立集时只能用具体图，即就是你所划分顶独立集的图都只有四个顶独立集，但你还是不能把所有的图都划分完，当然就不可能说明四色猜测是正确的。所以说这个想法，不如用“构形”证明比较合适。不能对前人的一切都否定，要用自已的脑子去分析，取其正确的，丢掉错误的。
当然，你如果能从理论上证明任何平面图的顶独立集数都不大于4时，当然也是可以的。但要用理证明，不要对具体图进行划分顶独立集，具体图你是划分不完的！你提出的当然也是一种证明方法，并不是简接证明，问题是你如何能证明任何平面图的顶独立集数就是一定不大于4呢？
你说，平面图的顶独立集数最小是4，那就还应有大于4的。一个顶独立集用一种颜色，那不就还有色数大于4的平面图吗？那不是就说明四色猜测是错误的吗？你还证明它干什么？你这不等于已经证明说四色猜测是错误的吗？
找顶独立集的方法与解决构形可约性的方法一样，最后总有一个顶点的围栏顶点分别属于4个不同的顶独立集的情况，也是要把围栏顶点再调整到3个顶独立集中去，也是一定能调整到的。如果你调不到，就说明你的技术水平低，说明你就根本没有看明白我给你的图着色的方法和步骤。
你说了几次平面图的顶独立集数最小是4，这是不对的。如果你能证明围栏顶点所属的顶独立集数不可能由4个调整到3个，那你就证明了四色猜测是错误的。你可以宣布你已证明了四色猜测是错误的。你也就是证明了四色猜想的世界第一人！
7、其他
图可分为两大类，一类是亏格数为0的平面图（即把图画在平面上时，在除了顶点以外再也没有边与边相交叉的情况的图），另一类是亏格数大于0的非平面图。四色问题研究的范围就是亏格为0的平面图，K1，K2，K3，K4也都是平面图呀！其顶独立集数分别是1、2、3和4。赫渥特的多阶曲面上的地图着色公式中，当图或曲面的亏格都为0时，公式就是四色猜测的表达式。

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

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

雷明85639720

，，，，，，，，

晋源泉

按照"相邻的顶点分在不同的顶独立集，不相邻的顶点分在同一个顶独立集。”的规则。一个顶点数为Q的地图对偶图可以有Q，Q-1，Q-2，Q-3……（3或4）个顶独立集。当一个顶点数为Q的地图对偶图的所有顶点的围栏数是偶数时，最后一个顶独立集数等于3；当一个顶点数为Q的地图对偶图的所有顶点的围栏数中有是奇数时，最后一个顶独立集数等于4。
所以，我说肯普和赫伍德构形的顶独立集数等于4。而且，如果这４个顶独立集组成一个团集Ｍ，则Ｍ≥１。并且Ｑ越大，Ｍ越大。

雷明85639720

1、一个图只应有一个顶独立集数，且是最小的。如果一个图划分顶独立集时得到的顶独立数有多个，就应该取最小者，但这个最小者是不是就是该图的最小顶独立数，还不能确定？
2、对于平面图来说，任何图的顶独立集数可能是1，2，3或4四种，最大的最4。我这个叙述应该说说得是很明白的。但你上面的叙述很不明白，很混乱，不知你在说什么，Q，Q一1，Q一2，Q一3都不知是什么意思？还有“最后一个顶独立集数”更不知是什么意思？特别是“如果这４个顶独立集组成一个团集Ｍ，则Ｍ≥１。并且Ｑ越大，Ｍ越大。”就更不明白是什么意思了？
3、如果你要把构形分为“坎泊构形”和“赫渥特构形”，那么可以说坎泊构形是没有双环交叉链的构形，而赫渥特构形则是有双环交叉链的构形。但都是平面图的不可避免构形。

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，