具体的平面图进行4—色与非具体图的不可避免构形可约性的证明的区别是什么？

雷明85639720

具体的平面图进行4—色与非具体图的不可避免构形可约性的证明的区别是什么？
雷  明
（二○二二年七月十二日）

1、具体平面图的4—着色：
对具体平面图进行4—着色时，只是对某一个个别的图进行的着色，不能代表全体。先是把除了一个顶点外的所有的顶点都进行了4—着色，把这个未着色的顶点也可以叫作待着色顶点。在待着色顶点外的围栏顶点已占用了四种颜色的情况下，然后再看在待着色顶点的对角围栏顶点间有没有连通的对角链：
如果没有，就从任何一个围栏顶点开始，交换与其对角顶点的颜色所构成的色链，则这个交换的起始顶点的颜色一定会变成与其对角顶点相同的颜色。这就把围栏顶点所占用的颜色数减少了一种，把减下来的这种颜色给待着色顶点着上，这个具体平面图的4—着色就成功了。
如果在某两个对角围栏顶点1和3间有连通的对角链时，那么与该对角顶点共同相邻的围栏顶点2与其对角顶点4或5的颜色所构成的色链，就一定是不连通的。因为这是两种相反的色链，是不能相互穿过的。现在已有一种链已经连通了，另一种链一定是不能连通的。这时再从已有连通链的那两个对角顶点中间的那个围栏顶点2开始交换与其对角顶点的颜色构成的色链，也就可以把围栏顶点2的颜色空出来，给待着色顶点着上。这个具体平面图的4—着色也就成功了。
从以上的交换中可以看出，交换颜色的顶点只是所交换的链中的顶点，非交换的链中的任何顶点都是牵扯不到的，那些顶点有与没有都是无所谓的，构形中只要有了交换的链中的顶点就可以了。
2、不可避免构形的可约性：
对非具体的不可避免构形可约性的证明则是按以上过程的相反方向进行的。不是先着色，而是只先画一个围栏顶点已占用了四种颜色的轮形图，轮的中心顶点是待着色顶点，轮沿顶点是围栏顶点。其围栏顶点以外处，并不是再没有别的顶点了，而是还有无数个顶点，也不知其具体数目，但却已知都是已经进行了4—着色的顶点，只是没有画出来。这是一个非具体的图，是能够代表全体的。
上面的着色方法是找对角围栏顶点间有没有连通的对角链，而现在不但是不能找，而且也找不到。只得假设在对角围栏顶点间是有或是没有连通的对角链。如果假设没有连通的对角链，那么就可以从任何一个围栏顶点开始交换与其对角顶点的颜色所构成的色链，也可以空出一种颜色来给待着色顶点着上，该构形就是可约的。请注意，这里的链中都认为是只有一个顶点的链。
如果假设在某两个围栏顶点1和3间有连通链，就用一条边把这两个围栏顶点1和3连接起来。用一条单边链来代替由若干个顶点构成的多边链，至于这条链在图中应怎么分布，实际是怎么分布的，可以不去管它，只知道从顶点1 到顶点3间有一条连通链就行了。很明显的可以看出，这两个顶点中间的围栏顶点2与其对角顶点4或5的颜色所构成的色链一定是不连通的。这样就可以从顶点2交换与其对角顶点的颜色构成的色链，空出围栏顶点2所用的颜色，给待着色顶点着上。该构形也就是可约的。
把在各种情况下的不可避免构形都证明是可约的后，四色猜测也就被证明是正确的了。这里的关键问题，是要把各种情况下的链的连通情况都要考虑进来，不能遗漏。这就是要证明不可避免构形集的完备性问题。
3、平面图不可避免构形的分类：
分类的原则：为了避免遗漏，对构形要进行多级分类，每一级分类中只能分成非此即彼的两类。其中一类是可以解决问题的构形，另一类是需要再进行下一级分类的。直到下一级分类所得到的两类构形都是可约的时候为止。
首先要考虑构形是可避免的，还是不可避免的。主要只是研究不可避免的构形能否可约就可以了。在不可避免的构形中还要考虑是否是可以直接给待着色顶点着色的构形。可直接着色的构形，问题也就解决了。不可直接着色的构形，还要考虑有没有连通链的问题，有什么样的连通链的问题，有几条连通链的问题，连通链是不是相交叉的问题，能不能连续的移去两个同色的问题和能不能从围栏顶点中空出某一种颜色的问题等等。
能从围栏顶点中可空出颜色的构形是坎泊在1879年就已经证明过是可约的K—构形。而不能从围栏顶点中空出任何一种颜色的构形则是在坎泊的证明中被遗漏了的构形，是1890年赫渥特发现的，是其中含有双环交叉链的H—构形。H—构形还可以再分为有没有经过围栏邻角顶点的环形链的构形两类。
有环形链的构形再可以分为两类：含有经过构形峰点和两个同色顶点的环形链的构形，用交换经过双环交叉链的两个末端顶点的色链的办法，使构形转化成可约的K—构形；含有经过双环交叉链的两个末端顶点的环形链的构形，用交换经过构形峰点和两个同色顶点的两种颜色构成的色链，或者交换经过双环交叉链的交叉顶点的、同样是由构形峰点和两个同色顶点的颜色构成的色链，使构形也可以转化成可约的K—构形。二者都再用前面解决K—构形的办法解决就可以了。
无环形链的构形就不能再分类了，只能是一类了。这一类构形只能用先移去一个同色的办法，使构形转型。再看转型后的构形是否含有经过了围栏邻角顶点的环形链：若有时，再转化成可约的K—构形而结束转型；若没有时，继续连续的进行同方向的转型，最后一定可以在已经经过证明是正确的和有限的40次转型之内，直接转化成可约的K—构形，解决该构形的4—着色的问题。
以上各类不可免构形在各种情况下都已经是可约的了，四色问题也就被解决了，四色猜测也就被证明是正确的。

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

   

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，