新浪博客

四色问题的彻底解决！（较长篇幅）

2021-04-29 09:40阅读：

http://blog.sina.cn/dpool/blog/u/1638843823


四色问题的彻底解决！
雷 明
（二二一年四月十九日）
1、把无穷问题转化成有穷的问题
四色问题从给地图的染色而提出，证明时还得从给地图的染色开始。地图（一个含有“无顶环”的无割边的3—正则的平面图）的对偶图是一个带有悬挂顶点的极大平面图。这里的“无顶环”和悬挂顶点都是指实际地图中的“国中之国”。给地图的面上的染色就是对其对偶图的顶点着色。这就把一个地理问题转化成了数学问题。
对极大平面图进行着色，着色过程中或到最后，总能遇到与要着色顶点所相邻的顶点全都已着上了四种颜色之一的情况。由于极大平面图的每一个顶点均是处在一个轮的中心位置，所以就把这种还有一个顶点未着色，且该顶点又是处在一个轮的中心位置的图叫做“构形”。未着色的顶点叫待着色顶点，与待着色顶点相邻的顶点叫围栏顶点。
由于任何平面图中都一定含有一个顶点的度是小于等于5的，所以小于等于5的顶点就是平面图的不可避免顶点。以不可避免顶点为待着色顶点的构形就是平面图的不可避免构形。可见平面图的不可避免构形的待着色顶点的度都是小于等于5的，由这五种度的待着色顶点的构形所组成的集合，就是坎泊已经给出的不可避免构形集。也就是说，平面图中6度以上待着色顶点的构形是可以避免的。因为在着色时，总可以把待着色顶点放在度是小于等于5的顶点之上；或者在着色过程中，遇到了6度以上的顶点作待着色顶点时，总是能够通过移动的方法把待着色顶点移动到度是小于等于5的顶点之上的。
研究平面图的着色，只要研究度是小于等于5的待着色顶点是否可约（即是否可4
—着色）就可以了。这就把待着色顶点的度可以是无穷大的一个无穷问题，又转化成了待着色顶点的度只是小于等于5的五种构形的有穷问题了。只要证明了这五种不可避免的构形都是可约的，极大平面图的四色问题也就解决了。当然地图的四色问题也就解决了。因为可4—着色的极大平面图，经去顶或减边后得到的任意平面图的色数，只会比极大图更少而不会再增大，所以解决了极大平面图的四色问题，同样也就解决了任意平面图的四色问题。
2、含有双环交叉链的颜色冲突构形
把围栏顶点占用的颜色数等于4的情况，叫做待着色顶点遇到了颜色冲突的情况。可以看出，度分别是1，2，3的待着色顶点是不会遇到颜色冲突情况的，而只有度为4和5的待着色顶点才有可能遇到这种颜色冲突的情况。4度待着色顶点发生了颜色冲突的情况，坎泊早在1879年就已经解决了，可以不去管它。而5度待着色顶点发生了颜色冲突的情况，坎泊却只解决了无双环交叉链时的情况，而把有双环交叉链时的情况遗漏了。所以现在研究四色问题，主要就是要解决有双环交叉链的5度待着色顶点的颜色冲突情况。
什么是双环交叉链，我们先来看图1和图2两个同样都是BAB型（双B夹A型）的5—轮构形（以后我们所说的构形，开始时都是指BAB型的）。图1中有连通的B—C链和连通的B—D链，两链在中途又有相交叉的着色为B的顶点。各链又都与待着色顶点构成了一个“环”，所以叫做双环交叉链。这是一种情况下的双环交叉链；图2中也有连通的A—C链和连通的A—D链，两链在中途也有相交叉的着色为A的顶点。这也是又一种情况下的双环交叉链。
四色问题的彻底解决！（较长篇幅）
可以看出，若把图1中的交叉顶点的颜色由B改成A，图1就变成了图2；把图2中的交叉顶点顶点的颜色由A改成B，图2也就变成了图1。这说明了5度待着色顶点的两种双环交叉链A—C与A—D和B—C与B—D是可以相互转化的，这是因为两种双环交叉链中的两种不同颜色都是C和D的原因。图1是一个可以移去A，C，D三色之一的K—构形，而图2却是一个表面上看，似乎是不能移去任何一种颜色的H—构形。可以想象得到，5度待着色顶点的这两种双环交链的可以相互转化，对把H—构形直接转化成可约的K—构形是有一定作用的（到后面就可以看到其应用）。
不但双环交叉链不同的构形，有的是K—构形（如图1），有的是H—构形（如图2）；即就是同样都含有双环交叉链A—C和A—D的构形，也存在有的是K—构形（如图3，图4和图5），有的又是H—构形（如图2）的情况。把图2中的交叉顶点A改换成B，实际上就是在环形的C—D链一侧，从双环交叉链的交叉顶点A开始交换了A—B链，使构形由H—构形直接转化成了可以移去A，C，D三色之一的可约的K—构形的。把图2中的A变成B后就得到了图1，图1只所以不能连续的移去两个同色B，是因为图1中又产生了双环交叉的B—C链和B—D链。
四色问题的彻底解决！（较长篇幅）
从图3，图4和图5中可以看出，有A—C和A—D双环交叉链的颜色冲突构形，有四个关键的顶点：即两链的共同起始顶点A，交叉顶点A，以及各自的末端顶点C和D。这四个关键顶点若有一个顶点的颜色发生了改变，构形就失去了双环交叉链。没有了双环交叉链，构形就转化成了可约的K—构形。这四个关键顶点，其中有三个都在围栏顶点上，只有一个位于双环交叉链的交叉顶点上。破坏双环交叉链的连通性和交叉性，这就是我解决H—构形的基本的思想。
3、颜色冲突构形的解决办法
但关键顶点的颜色的改变是要有条件的，不是说想改就可以改得了的。如果构形中含有经过了关键顶点C和D的环形的C—D链，则该环一定把另外两个关键顶点A（双环交叉链的共同起始顶点A和相交叉顶点A）分隔在环的两侧（如图6，图6就是图2），交换环的任一侧的经过了关键顶点A的A—B链，构形中就不存在双环交叉链了；如果构形中含有经过了至少一个关键顶点A的A—B环形链，则该环也就把由双环交叉链的两个末端顶点C和D构成的C—D链和其他的C—D链分隔在了环的两侧（如图7），同样的，也是交换了环的任一侧的任一条C—D链，构形中也就不存在双环交叉链了。如果两种经过了关键顶点的环形链同时都存在，则用其中的任何一种办法都是可以解决的。
四色问题的彻底解决！（较长篇幅）
以上这种解决有经过了关键顶点的环形链的构形的方法，因为其交换的主要目的是为了使双环交叉链断开，所以就叫做断链交换法。
还有一种根本就不存在经过关键顶点的环形链的情况的构形（如图8），这时就得采用转型交换法进行解决了。因为该构形中，A—C链，A—D链，A—B链，C—D链，都不能交换，而B—C链和B—D链又不能连续的交换，所以就只有先交换一条关于B的链了。但交换该链后，构形峰点的位置和颜色都会发生改变，由原来的BAB型变成DCD型（交换B—D链）或CDC型（交换B—C链），所以把这种交换就叫做转型交换法。然后再看转型后所得到的构形是个什么样的构形，是否可约。
四色问题的彻底解决！（较长篇幅）
对图6，图7和图8的构形，分别用上面所说的方法处理后的构形如图9，图10和图11。图9和图10都已转化成了可约的K—构形；图11虽然仍有双环交叉链D—A和D—B，但却是含有经过了关键顶点（双环交叉链的两个末端顶点A和B）的A—B环形链的构形，可以再象图6那样交换A—B环两侧的任一条C—D链，使构形转化成可约的K—构形。三个构形都得到了解决。从图8中还可以看出，把A—B链中的那个加大的顶点的颜色由B改成D后，也就转化成了一个含有经过了双环交叉链A—C和A—D的两个末端顶点C和D两个关键顶点的C—D环形链的构形了（如图8**）。也可以与图6一样，用交换C—D环内、外的任一条A—B链，使构形直接转化成可约的K—构形。
图9说明了有经过了关键顶点的C—D环形链的H—构形，是可以直接转化成可约的K—构形的。转化后的图，由原来的含有A—C和A—D双环交叉链变成了含有B—C和B—D双环交叉链了，是一个只能移去A，C，D三色之一，而不能连续的移去两个同色B的可约构形。
四色问题的彻底解决！（较长篇幅）
图6是一个左右对称的图，而图7和图8则不是左右对称的，所以就还应有与图7和图8只是左右不同的另外两个构形（如图7*和图8*），解决的办法只是与图7和图8左右形式的不同罢了。
4、转型交换法的最大转型次数
在图11中，我们是对图8先进行了B—C链的交换，是顺时针方向转型的，得到了一个含有经过了关键顶点的环形链的构形。若从逆时针方向先交换B—D链时，看是一个什么情况呢？请看下面的分析。
图12（即图8）的构形，一次转型后的图13再相按同方向继续转型时，得到的是一个可以连续的移去两个同色D的DCD型的可约的K—构形，应该说到此问题也就得到了解决。但是为了寻求转型交换的最大转型次数，我们在平面图的范围内，再人为的构造从另一个同色顶点到其对角顶点的连通链，使构形仍是一个H—构形，一直到在平面图范围内不能再构造连通链为止，看最大的交换次数是多少。
四色问题的彻底解决！（较长篇幅）
四色问题的彻底解决！（较长篇幅）
四色问题的彻底解决！（较长篇幅）

第一次转型后是不需要人为的构造连通链的，以后的第二，三，四，五次转型，都是可以人为再构造出连通链的（图中的加粗边及顶点就是连通链中人为构造的部分）。第六次转型后，在平面图范围内就不可能再构造出连通的D—B链了，因为图中已有一条连通的A—C链，两条相反链是不能相互穿过的，连通的A—C链已把D—B链的连通隔断了。这就说明了第五次转型后的构形是一个可以连续的移去两个同色D的DCD型的可约的K—构形。这五次转型每一次得到的都是一个无经过关键顶点的环形链的构形，也都是一个可以连续的移去两个同色的构形。第六次转型实际上只是移去了一个D，而第七次交换再移去另一个D，从而空出了颜色D。最后的图20并没有进行交换，而只是把颜色D给待着色顶点着上。一共转型了五次，共七次交换。
为什么最大的转型次数是5呢？因为5—轮构形中有5个围栏顶点，每转型一次，构形的峰点就换一个地方，5个围栏顶点都作了一次峰点时，最大也就只是转型5次，就是一个周期，就应可以空出颜色D来了。以上是逆时针方向转型的结果，若对图12再进行一次顺时针方向的转型，同样的，也不管是生成还是不生成有经过了关键顶点的环形链，只要是在平面图范围内，能再构造出另一条连通链时，就继续构造，直到不能再构造为止。最后的结果与逆时针转型也是相同的，最大的转型次数也是5次，最大的交换次数也是7次（这里也就不再画图了），只是最后待着色顶点的着色是C而不是D。
5、用交换邻角链的方法解决无经过关键顶点的环形链的H—构形
以上我们研究无环形链的构形的转型交换时，都是用的对角链的交换，现在再用邻角链进行交换，看一看是什么情况。以前对B—C（或B—D）链进行交换时是从右（或左）B开始进行交换的，现在则要从左（或右）B开始进行交换。
对图8（如图2

我的更多文章

下载客户端阅读体验更佳

APP专享