有环形链的染色困局一定可解的机理

雷明85639720

有环形链的染色困局一定可解的机理
雷  明
(二○一九年十月十六日)
（图发不上来，请到＜中国博士网＞中去看）

人们常把有双环交叉的5—轮构形叫做染色困局（如图1），把有经过构形围栏顶点的环形链的构形叫做有环形链的构形（如图2和图3），当然没有经过构形围栏顶点的环形链的构形就是无环形链的构形了（如图4）。各图中除了各围栏顶点间和顶点6与7间是单边外，其他的两顶点间都可以认为是由该两顶点的颜色所构成的色链或是其他顶点的道路。

各图中的双环交叉链A—C和A—D链中各有几个关键的顶点：即顶点1和顶点8，这是两链的共有顶点；还有顶点5和顶点6，顶点4和顶点7，分别是A—C链和A—B链的另一端点顶点和中途顶点，且除了顶点4和5是围栏顶点必然相邻外，顶点6和7也一定是相邻的，否则就不是染色困局构形了。这说明了双环交叉链A—C和A—D在中途不但有交叉顶点，还也有相邻顶点的。
这6个顶点中的任何一个顶点的颜色如果改变了，显然就不存在双环交叉链了，没有双环交叉链，构形就不再是染色困局了，而成为坎泊已证明过的是可4—着色的构形了。问题就可得到解决。
图2中任意交换经过5C和4D或者6C和7D的任何一条C—D链，图就变成了非染色困局构形了；图3中任意交换经过2A或者8A的任何一条A—B链，图也就变成了非染色困局构形了。
这就是有环形链的染色困局一定可解的机理。
无环形链的构形由于没有环形链，不可能使双环交叉链断链，所以只能使用连续转型法进行解决，并且一定要证明一个转型次数的上界。只有这样才能说明任意的无环形链的构形都是可解的，四色猜测也才能得到证明是正确的。

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

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