H—构形最大转型交换次数的确定

雷明85639720

H—构形最大转型交换次数的确定
雷  明
（二○二○年二月十六日）

对于BAB型的H—构形来说，由于图中有连通的A—C链和A—D链，且两链在中途还有相互交叉的顶点（同着A色）；B—C链和B—D链又不可连续的进行交换，所以用坎泊的空出颜色的K—交换是不能给待着色顶点着上A、B、C、D四种颜色之一的。
由A、B、C、D四种颜色可以构成的六条色链中还有A—B链和C—D链，我们可以把H—构形按其是否是含有经过了构形的围栏顶点的环形的A—B链或C—D链，将H—构形分为有环形链的构形和无环形链的构形。对于有环形链的构形，交换环形链内、外的任一条相反链，都可以使连通且交叉的A—C链和A—D链断开，构形成为坎泊的K—构形而可约。这就是所谓的断链交换法（四色问题专家张彧典先生称做Z—换色程序）。
对于无环形链的构形，由于A—B链和C—D链均是直链，不可进行交换，也空不颜色来。这时就只能先交换一个有关B的链（B—C链或B—D链），使构形转型（所谓转型，就是使得构形的峰点与两个同色都发生变化的交换），再看转型后的构形，是否可以通过断链交换或坎泊的空出颜色的K—交换解决问题。
但这个最大的交换次数是多少呢？
有这样一个构形叫做埃雷拉图（也叫E—图，这是一个着了色的色图，但其中还有一个顶点未着色，所以该图也是一个构形），其中含有经过了围栏顶点的A—B链，用断链法是可以解决问题的。但这个图如果进行转型交换时，却是一个无穷转型也空不出颜色的构形。这个无穷转型却有一个特点，它每转型20次是一个周期，并以这个周期无穷的循环下去。这就为我们寻找无环形链的构形转型交换的最大次数提供了方便。
我们在着色时也知道，大量的构形都是有限次转型就可以解决问题的。所以对于构形来说，从转型交换的次数的有限与无限来分，也可把构形分成有限转型的构形和无限转型的构形。对于E—图来说，当我们还不知道其是无穷周期循环转型的构形时，进行转型一定要在至少进行了两个周期（转型次数是2×20＝40次）后才能确定其是否是周期循环转型的无限转型的构形。
而对于有限转型的构形来说，转型的次数就应该在E—图转型的两个周期之内解决问题，也就是说有限转型的构形或者无环形链的构形，最大的转型次数就是40。这时得到的图（或者叫构形）是一个可以连续的进行两次、关于两个同色的链的、坎泊的空出颜色的K—交换，空出两个同色给待着色顶点。问题得到解决。这样，总的交换次数就是42次，因为一次转型也是在进行了一次交换。
任何一个构形，从两个不同的方向（逆时针方向或顺时针方向）都可以进行转型，最后都一定可以得到可以连续的移去两个同色的构形，再进行两次无须泊的空出颜色的K—交换，就即可空出一种颜色给待着色顶点。这两个方向的转型次数的和也是不会大于40次的，整个的交换次数是不会大于44次的。这一情况说明了，一定是存在这样一个构形（不可我们现在还没有构造出这一构形），它是可以按一定的方向（逆时针或顺时针）连续的移去两个同色的构形。对这个构形按其连续的移去两个同色的相反方向进行转型时，一定是在第40次转型时也能得到同样的是一个可以连续的移去两个同色的构形（该构形连续的移去两个同色时的方向与前者是相反的）。两个构形之间是39个不可空出任何颜色的H—构形。
到此，就从理论上说明了无环形链的H—构形是能够在有限的转型交换内解决问题的，最大的转型次数是40，最大的交换次数是42；对于任一个无环形链的H—构形，两个不同方向转型的次数之和也一定不会大于40次，两个方向转型的总交换次数的和也不会大于44次。
对于无环形链的H—构形，在进行转型交换的过程中，也可以转化成有环形链的构形，这时就可以直接改用断链交换法解决问题，不必再继续进行转型了。这就是我们前面说的“再看转型后的构形，是否可以通过断链交换或坎泊的空出颜色的K—交换解决问题。”的意思所在。
只有解决了这样的最大交换次数的问题，才能彻底的解决四色问题。现在每一类H—构形都有其相应的解决问题的办法，加上坎泊已经解决过的K—构形，四色问题也就得到了解决。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，