我研究四色问题的主导思想

雷明85639720

我研究四色问题的主导思想
雷  明
（二○二一年三月十八日）
（这里我发不上来图，请到《中国博士网》中去看）

1、我主张用不画图不着色的方法来解决四色问题：
我不是用对一个个的、无穷多的具体的图的可4—着色去研究四色问题，而是只对有限个的、非具体图的、非极大图的、平面图的不可避免的构形的可约性进行研究，以代替对无限多个具体平面图的可4—着色。因为着色解决的只是个别的图的可4—着色问题，而不能解决全体的、一般的平面图的可4—着色问题；而对平面图的不可避免的构形的可约性的研究，则是可以代表对全体的、一般的平面图的可4—着色问题。
2、极大平面图的构形：
地图的对偶图是一个极大图，把只有一个顶点未着色，而其他顶点均已进行了可4—着色的极大图叫做构形。由于极大图的每个顶点都是处在一个轮的中心位置，所以极大图的构形也叫轮构形。构形中未着色的顶点叫待着色顶点，与待着色顶点相邻的顶点叫围栏顶点。围栏顶点以外的顶点可以多，也可以少，是一个变数，也可能是无穷多个。这样的构形就构成了不是具体图的、也不是极大图的构形了。
3、极大平面图的不可避免构形：
由于在任何平面图中都一定至少存在着一个顶点的度是小于5的，所以在对具体图着色时，遇到了待着色顶点的度是大于等于6时，一定是可以通过破圈法，把待着色顶点移动到度是小于等于5的顶点之上的。所以对于极大平面图来说，只要研究度是小于等于5的构形的可约性就可以了。这就是极大平面图的不可避免构形，而待着色顶点的度是大于等于6的构形则就是可以避免的构形了。这就把一个待着色顶点的度可以是无穷大的问题，转化成了只研究待着色顶点的度只是小于等于5的五种有限的构形的有穷问题了。
所谓破圈法，就是把围栏顶点中用得次数最少的颜色，直接给待着色顶点着上，把原来围栏顶点的色圈进行了破坏，而在原围栏顶点中又产生了一个或多个新的待着色顶点，当新的待着色顶点的度仍是大于等于6时，再继续进行同样的破圈过程，总是可以找到一个度是小于等于5的待着色顶点的。
4、可发生颜色冲突的不可避免构形：
待着色顶点的度是1，2，3时的不可避免构形，其围栏顶点一定是不会占用完四种颜色的，总还有至少一种颜色可以给待着色顶点着上；而当待着色顶点的度是4和5时，其围栏顶点就有可能占用完四种颜色的情况，似乎待着色顶点已无色可着了。这种情况就叫发生了颜色冲突现象。如何解决颜色冲突问题，是解决四色问题的一个非常重要的问题。
5、坎泊早已解决了无双环交叉链的颜色冲突问题：
所谓的双环交叉链，即是在BAB型的5—轮构形中，连通的A—C链和A—D链不但有共同的起始顶点（着A），中途还有共同的交叉顶点（也着A），它们分别又与待着色顶点V构成了一个闭合的环，所以叫双环交叉链。
在可能发生颜色冲突问题的4—轮构形和5—轮构形中，只有在5—轮构形中才有可能会出现双环交叉链的情况，而在4—轮构形中是不会出现双环交叉链的。1879年坎泊已经解决了无双环交叉链的颜色冲突问题，但却漏掉了有双环交叉链的颜色冲突问题。1890年和1921年赫渥特和埃雷拉分别构造了有双环交叉链的H—图和E—图构形，虽然1935年欧文和1992年雷明已分别都用断链交换法（断链交换法见后面的8中）解决了E—图和H—图的可约性问题，但却一直未能得到数学界的公认。所以说，目前解决四色问题的重点还是研究如何解决有双环交叉链的颜色冲突问题。
6、有双环交叉链只是构成赫渥特构形的必要条件而非充要条件：
把坎泊已经解决了可约性问题的构形叫做坎泊构形（K—构形），而把坎泊未能解决可约性问题的构形叫做赫渥特构形（H—构形）。H—构形中都有双环交叉链，这也就是说没有双环交叉链是构不成H—构形的；但有了双环交叉链的构形，却不一定就都是H—构形。比如有双环交叉链的“九点形”构形中，有些就是可以连续的移去两个同色的可约构形，就是属于K—构形。所以说有双环交叉链只是构成赫渥特构形的必要条件而并非是充要条件。现在就只剩下了不可连续的移去两个同色的5—轮颜色冲突构形一种情况需要研究了。
7、发生了颜色冲突的赫渥特构形中的四个关键顶点：
赫渥特构形因有双环交叉链而产生，那么只要想办法断掉双环交叉链，也就使得看似不可约的H—构形转化成了可约的K—构形。如何断开双环交叉链呢？先来看一看双环交叉链A—C和A—D上的四个关键顶点：两链的共同起始顶点A和共同相交顶点A,以及两链的末端顶点C和D，其中有三个都在围栏顶点之上。这四个顶点中，只要有一个顶点的颜色发生了改变，图中就不再存在双环交叉链了，图也就从看似不可约的H—构形转化成了可约的K—构形。但这看似很简单，其实却并不简单。不是你想改就能改动的，而是要看图中有没有一定的条件，即图中有没有经过了关键顶点的环形链。
8、用断链交换法解决含有经过了关键顶点的环形链的构形：
如果图中有一条经过了至少一个关键顶点A的A—B环形链，该环就一定会把另外的两个关键顶点C、D与双环交叉链中的其他C、D顶点分隔在环的两侧，交换经过了关键顶点C和D的C—D链，双环交叉链就会断开；又如果图中有一条经过了关键顶点C和D的C—D环形链，该环也一定会把另外的两个关键顶点——双环交叉链的共同起始顶点A和共同交叉顶点A分隔在环的两侧，交换经过任一个关键顶点A的A—B链，双环交叉链也就会断开。
这里的交换方法，目的并不是为了空出颜色（实际上也空不出颜色），而是为了使双环交叉链断开，所以叫做断链交换法。现在就剩下最后一个问题了，即在没有经过关键顶点的环形链的情况下，如何使构形可约呢？
9、用转型交换法解决不含有经过关键顶点的环形链的构形：
不含有经过关键顶点的环形链的构形中，因含有双环交叉链，使得A—C链和A—D链不可能进行交换；又因为构形中不含有经过关键顶点的环形链，而使得A—B链和C—D链也不可能进行交换；且构形本身又是不可连续的移去两个同色的，所以B—C链和B—D链也不可能连续的进行交换。既然B—C链和B—D链不可连续的进行交换，那么我们先交换一个关于B的链，总是应该是可以的。这种交换的结果使得构形峰点的位置和颜色都发生了改变，把BAB型的5—轮构形转化成了DCD型或CDC型的5—轮构形。所以把这种交换叫转型交换。
既然该构形是不可连续的移去两个同色的构形，那么，移去了一个同色后，就应该是一个峰点位置和颜色都发生了变化的、但仍是含有双环交换叉的构形。这个构形也可能是可以连续的移去两个同色的可约构形，或者是含有经过了关键顶点的环形链的构形。只要转化成了这两种构形，就都是可约的了。如果二者都不是，就只有再次进行连续的转型了。
可以连续的移去两个同色的构形，继续转型的结果，必然是移去了两个同色，问题就得到了解决；但含有经过了关键顶点的环形链的构形，如果没有及时改用断链交换法，继续转型的结果，还有可能得到可以连续的移去两个同色的构形，或者含有经过了关键顶点的环形链的构形。但这个连续转型的过程必须要在构形峰点的位置和颜色变化的第二个周期（即第八次转型）形成之前结束，即最大在第七次转型（包括第七次在内）就得结束，才不会产生无穷的循环转型，以至于空不出颜色来。这里之所以不会产生无穷循环转型的现象，是因为该构形不具有象E—图那样的经过了双环交叉链共同起始顶点A的这个关键顶点的环形的A—B链，或者说构成E—图构形的所有特征，对于该构形来说，都是不具备的。
10、转型交换的最大转型次数是有限次的逻辑证明：
现在，对以上的结论——转型交换的最大转型次数一定是有限次的——再用逆否命题与原命同真同假，以及逆命题与原命同真，逆命题为真是原命题成立的充要条件进行逻辑证明如下：
设A是“某类构形经有限次转型后”这句话。B是“可以转化成可约的构形”这句话。这里，某类构形是指“无经过关键顶点的环型链的构形”；可约构形是指“可以连续的移去两个同色的构形，或者含有经过了关键顶点的环形链的构形”；有限次指的是“7次转型”。
则原命题A到B是：无环形链的构形经有限次转型就可以转化成可约的构形。其逆否命题—B到—A是：通过转型转化不成可约构形的构形一定是无穷转型的构形。这个逆否命题是真的。具体的说就是有E族构形这样的例子存在。的确，E族构形的转型次数是无穷的，E族构形永远也不可能通过转型转化成可约的构形。
根据原命题与其逆否命题具有同真同假的性质，可以判定无环形链的构形经过有限次转型是可以转化成可约构形的原命题是真命题。证毕。
现在还可以进行验证如下：
原命题的逆命题B到A是：通过转型可以转化成可约构形的构形，其转型次数一定是有限的。这个逆命题是真命题。无环形链的构形都是这样的。原命题与其逆命题同真，说明其逆命题为真是原命题成立的充要条件。没有逆命题成立，原命题一定不成立，有了逆命题成立，则原命题也一定成立。
这就用不同的方法都证明了无环形链的构形的转型次数一定是有限的结论是正确的。
11、四色猜测是正确的：
到此，应该说四色猜测的证明已经结束了，四色猜测是正确的。
在对构形的分类过程中，都是采取了只有两种可能的办法，非此即彼，避免了漏洞的出现。
我在1992年于陕西省数学会第七次代表大会暨学术交流会（西安空军工程学院）上所作《赫渥特图的4—着色》的学术论文报告最后所提出的“不画图不着色证明四色猜测”的想法最终实现了。

附录：用着色实践检验上术结论是否正确：
为了检验无经过关键顶点的环形链的构形转型交换的最大次数的正确性，我们再举几个实际着色的例子，看看其转型次数与上面正文中用逻辑推理所得出的结果是否一致。
1、用非极大图的构形进行验证

图3是一个无经过关键顶点的环形链的BAB型的含有双环交叉链的非极大图的构形。对该构形进行不同方向的连续转型，如果某次转型从一个同色顶点交换了与其对角顶点的颜色构成的色链后，不能新生成从另一个同色顶点到其对角顶点的连通链时，应该说问题就已经得到解决，可以连续的移去另一个同色，空出两个同色顶点用过的颜色，给待着色顶点着上。颜色冲突问题就可以得到解决。
但我们却有意的不去这样做，而是在平面图许可的范围内，增加顶点或边，人为的构造从另一个同色顶点到其对角顶点的连通链，使图仍是一个不可以连续的移去两个同色的构形，再继续的进行转型。如果在后续的某次转型后，不再可能人为的构造从另一个同色顶点到其对角顶点的连通链时，这时的转型次数再减去1，就是转化成可以连续的移去两个同色的最大的转型次数。结果两个方向转型的最大转型次数都是5次，也都是小于7次的。
2、用极大图的构形进行验证

图4是我仿敢峰先生构造E—图构形（敢峰先生称其为终极图）时的转型演绎法，由最简单的双环交叉链构形开始，构造的一个属于极大图的无经过关键顶点的BAB型的含有双环交叉链的极大图构形。该构形好象是含有经过了关键顶点——双环交叉的A—C链和A—D链的两个末端顶点C和D（图中的两个加大顶点C和D）——的C—D环形链，但该环形链却并没有把另一对关键顶点——双环交叉的A—C链和A—D链的共同起始顶点A和交叉顶点A（图中的两个加大顶点A）——分隔在该环的两侧，所以不是含有经过了关键顶点的环形链的构形。
这个构形两个方向转型的最大次数只是4次，也都是小于7次的。逆时针方向转型时，不用转型（即转型次数是0时）就是一个可以连续的移去两个同色B的BAB型的可约构形；顺时针方向转型时，1至4次转型的结果全部都是含有经过了关键顶点的A—B环形链的构形，都可以改用断链交换法提前结束转型；而且第4次转型的结果既是一个可以连续的移去两个同色B的可约构形，也是一个含有经过了关键顶点的A—B环形链的构形。
3、用具体图着色实例进行验证

①  1935年欧文给出的那个无经过关键顶点的环形链的构形（如图5，待着色顶点V是隐型画法），由于其中的A—B链和C—D链都是对于构形的峰点A与5—轮构形的两个底角顶点C和D（即两条双环交叉链的末端顶点）的中点的连线呈对称状态的，所以无论从那个方向转型时，转型次数都是4次，也不大于7。且都在第3次转型时就得到含有经过了关键顶点的环形链的构形，也都可以用断链交换法提前结束转型。
②  张彧典先生的Z—构形中，Z1到Z5和Z11到Z15的十种Z构形都是属于无经过关键顶点的环形链的构形，转型次数都是在小于5次时，就转化成了可以连续的移去两个同色的可约构形或是转化成了含有经过了关键顶点的环形链的构形。
③  张先生的第八构形的放大图也是无经过关键顶点的环形链的构形，但该构形中却含有局部的环形链，也是可以用断链法使其中一条双环交叉链断链的，从而转化成只有一条连通链的可约构形。
④  前面的图3是标准的无经过关键顶点的环形链的构形，A—B链和C—D各都只有一条，且是非树状的单条道路。各条链中相同颜色的首、尾顶点间，只隔着一个与其呈相反色链中的顶点，改变该顶点的颜色为其相反色链中的颜色时，图就转化成了含有经过了关键顶点的环形链的构形，也就可以直接使用断链交换法了。由此也可以看出，无经过关键顶点的环形链的构形，也是可以直接转化成含有经过了关键顶点的环形链的构形的。但这是个个别的现象，还是普遍的规律，我们现在还不知道。可以作为一个猜想提出，如果真是这样，平面图的4—着色就更加方便了。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，