再谈赫渥特类构形的种类并对四色猜测进行证明

雷明85639720

再谈赫渥特类构形的种类并对四色猜测进行证明
雷  明
（二○一六年元月二十五日）

解决四色问题目前主要是要解决类赫渥特类构形有多少的问题。这一问题解决了且证明他们都是可约的，那么四色问题也就解决了，也就能说明四色猜测是正确的。
为了清楚，方便阅读，我们用表格的形式进行表述。先画一个5—轮构形的图，标出5—轮的顶点名称，围栏顶点的着色情况等，如图1。用数字代表顶点名，用字母代表颜色。由两种颜色的顶点所构形的道路叫做色链，简称链。有对角链与邻角链之分，也有相邻链与相反链之分。所谓相邻链是有一种颜色相同的链，而相反链则是两种颜色都不同的链。

四种颜色A，B，C，D，可能构成的色链有A—B，A—C，A—D，B—C，B—D和C—D六种。对于5—轮对角顶点的色链来说，不连通的链交换后才能空出颜色，给待着色顶点V着上。其他的色链交换虽不能空出颜色，但可以为下一步的交换空出颜色作好准备。
若所有构形中至少都有一条链可以交换，构形就是可约的，四色猜测就是正确的；若某构形中六条色链一条都不可能交换时，则该构形就是不可约的，那么四色猜测也就不可能是正确的。
1、各构形的4—着色
序号        构  形  名  称   连  通  链  的  情  况        可 以 进 行 交 换 的 链        图        例        备  注（建议使用方法）
1        K构形        无连通链        A—C和A—D均可交换，也可同时交换B—C和B—D链移去B。         任意交换一条
2        K构形        有一条连通链A—C（或A—D）        可以交换A—D（或A—C）         交换其一
3        K构形        有一条连通链B—C（或B—D）        A—D和A—C均可交换      交换其一
4        K构形        有两条连通链A—C和A—D但不相交叉        B—C和B—D同时交换     断链
5        K构形        有两条连通链B—C和B—D只交叉，但无相同的端点        A—C和A—D均可以交换，也可以交换A—B进行断链，使构形变成没有连通链的一种情况。          交换其一
6        非H构形        A—C和A—D两链连通且相交叉，A—B链是环形链，C—D链是直链。        同时交换B—C和B—D，空出颜色B给待着色顶点着上，也可采用颠倒法。         同时移去两个同色B
7        半H构形        A—C和A—D两链连通且相交叉，A—B和C—D链都是一条道路（直链）        同时交换B—C和B—D，空出B给V，实线先换1B—7D，虚线先换3B—6C，也可采用颠倒法。即张先生的构形1，3，4，5，6，7        同时移去两个同色B
8        H构形        A—C和A—D两链连通且相交叉，C—D链也是环形的链        交换任一条A—B链使连通链断链，使构形变成一个K—构形的情况，当然也可采用颠倒方法。即张先生的构形2将        断链
9        M构形        A—C和A—D两链连通且相交叉，A—B链是多嵌套环和一条直链；C—D链一个环链和多条直链        交换任一条C—D链使连通链断链，使构形变成一个K—构形的情况，当然也可以采用颠倒法。即张先生的构形9         断链
10        Z构形        A—C和A—D两链连通且相交叉，A—B链和C—D链又分别都是一条直链（道路）。        只能交换B—C和B—D两链之一，采用颠倒法了，颠倒后只能变成半H构形和H构形两类，并都是可约的。即张先生的构形8        也只能颠倒了
2、类H—构形的种类数
Z—构形在从顶点1和7进行了B—D链交换的颠倒后，产生了从顶点3到5的B—C连通链，而原来从顶点2到5的A—C链也是连通的，形成了一个顶点5是C色的DCD型的可以同时移去两同色的非H—构形；而在从顶点3和6进行了B—C链交换的颠倒后，产生了从顶点1到4的B—D连通链，而原来从顶点2到4的A—D链也是连通的，形成了一个顶点4是D色的CDC型的H—构形（一种可约构形）。两种颠倒只能分另形成这两种可约的构形，不可能再循环而产生Z—构形。
从上表和这里的分析看，类赫渥特类构形就只可能有三种，即赫渥特的H—构形，米勒的M—构形和张彧典的Z—构形（雷明构造的两种L—构形和Z—L构形分别是H—构形，M—构形和Z—构形中的一种）。其他的可同时移去两个同色的构形都是非H—构形。
3、四色猜测的证明
5—轮构形的对角链共有四种，即2A—5C，2A—4D，2B—5C和1B—4D，当对角链不连通时，可以交换其一支，就可从5—轮沿中空出一种颜色，给待着色顶点V着上。四种对角链中2A—5C和2A—4D，以及2B—5C和1B—4D分别是两对相邻链。
5—轮构形的邻角链有两种，即1B—2A—3B和5C—4D，这正好是一对相反链。交换邻角链时，可以使连通的其他链断开。一条邻角链成环形链时，另一条相反的邻角链一定被分隔成两部分。
5—轮构形中，一条对角链连通时，另一条相反的对角链一定不连通，是可以交换的；一对相邻链都连通时，另一对相反的相邻链一定都不连通，都可以进行交换。
相邻链B—C和B—D均连通时，只可能有交叉顶点，不可能在5—轮轮沿顶点上有相同的端点顶点，这时相反的相邻链A—D和A—C均可交换。
相邻链A—C和A—D均连通时，一种情况是只有同一个起点顶点1A，而没有交叉顶点，这时，可以同时交换两个相反的相邻链B—C和B—D，同时移去两个同色B，给V（以上都是坎泊已经证明过的K—构形，都是可约的）：还有另一种情况是两链还有交叉顶点8A时：
㈠  当邻角链A—B是环形链时（是非H—构形），则可同时交换相邻链B—C和B—D，同时移去两个同色B，给V着上；
㈡  没有任何环形的邻角链时（是半H—构形），可以有先后次序的交换相邻链B—C和B—D，同时移去两个同色B，给V（以上都是非H—构形，但坎泊的证明中并没有涉及这些情况）着上；
㈢  当邻角链C—D是环形链时，又有三种情况：
①  当邻角链C—D是环形链时（如H—构形），交换相反的邻角链A—B，构形变成非H的K—构形；
②  当邻角链A—B有环形链时（如M—构形），交换相反的邻角链C—D，构形变成K—构形；
③  没有任何环形的邻角链时（如Z—构形），两对邻角链都不能交换，且有一对相邻链A—C和A—D也不能交换，另一对相邻链B—C和B—D又不能同时一前一以后的交换，只能交换其一，即施行赫渥特颠倒，使构形转型，变成半H型构形或H型构形。
在5—构形时，六种链可能组合而成的构形，就只有表中那么多种类，每一种都只少是有一条链可以交换的，每种构形都是可以4—着色的，都是可约的。这也就证明了四色猜测是正确的。
4、5—轮构形的4—着色的程序
5—轮构形4—着色的程如图2。

    这个流程图也可以看作是对四色猜测证明的流程图。

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

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，，