分析H—构形，研究四色问题

雷明85639720

分析H—构形，研究四色问题
雷  明
（二○一八年八月十七日）
（图发不上来，请去＜中国博士网＞中去看）

1、H—构形的分析
现以BAB型的H—构形（5—轮构形）为例进行分析。V是待着色顶点，1，2，3，4，5是五个围栏顶点，着色分别是1B、2A、3B、4D和5C。H—构形的围栏顶点已占用完了四种颜色。1879年，坎泊已经证明了所有的K—构形（即坎泊构形）都是可约的，即都是可4—着色的。所以，从目前看，解决四色问题的主要问方向是：要把所有H—构形的围栏顶点所用的颜色数量由四种减少到三种，空出一种颜色来给待着色顶点着上。四色问题才能得到最后的解决，也才能证明四色猜测是正确的。
1、1 构成H—构形的必要条件是：有两条连通且交叉的对角链。但这两条对角链必须是A—C链和A—D链，即包括顶点2A在内的两条对角链（如图1，a）；如果B—C链和B—D链分别连通且相交叉（如图1，b），但这样的构形却不是H—构形。原因是A—C链和B—D链是一对相反链，A—D链的B—C链也是一对相反链，而相反链是不能相互穿过的。所以只要有连通的B—C链和B—D链存在，就不可能再有连通的A—D链和A—C链的存在。这种B—C链和B—D链分别连通且相交叉的构形是可以通过一次换色交换，一定可以空出A、C、D三色之一给待着色顶点V着上的，所以它不是H—构形。相反的，只要有A—C链和A—D链是连通的，则B—C链和B—D链也一定不连通。
1、2  构成H—构形的充分条件是：既要有两条连通且交叉的A—C和A—D对角链，还要是不可连续的移去两个同色B的构形。即无论怎么交换，都不能空出一种颜色给待着色顶点的构形，才是H—构形。如图2，a不能连续的移去两个同色B，所以是一个H—构形；而图2，b就可以连续的移去两个同色B，所以不是H—构形，而是一个K—构形。这是因为在图2，b中，从顶点1B（或3B）交换了B—D（或B—C）后，可以生成从顶点3B（或1B）到其对角顶点5C（或4D）的连通的B—C（或B—D）链，所以才不可能连续的移去两个同色B。

同样的道理，图3的两个图也不是H—构形而是K—构形。但图3的这两个图中，图3，a必须先从顶点1B开始交换B—D链，再从顶点3B开始交换B—C链，才能连续移去两个同色B；而图2，b则必须先从顶点3B开始交换B—C链，再从顶点1B开始交换B—D链，也才能连续移去两个同色B。交换的顺序如果错了，就不可能连续移去两个同色B了。这就是有选择性交换的可以连续的移去两个同色B的构形。

1、3  从图2中可以看出，属于H—构形的图2，a中有一条经过5—轮的两个相邻轮沿顶点4D和5C的环形的C—D链（如图4，a），而不属于H—构形的图2，b中却有一条经过5—轮的三个相邻轮沿顶点1B、2A和3B的环形的A—B链（如图4，b）。可以肯定，只要有一条经过5—轮的两个相邻轮沿顶点4D和5C的环形的C—D链的构形，一定都是H—构形（如图2，a、图4，a和图5，a）。这样的构形我们叫它第一类H—构形，1890年赫渥特构造的赫渥特图就是这一类构形的一个代表。赫渥特图的简化图就是图2，a和图4，a这样的“九点形构形”。
而有一条经过5—轮的三个相邻轮沿顶点1B、2A和3B的环形的A—B链的构形，却不一定都是可以连续的移去两个同色B的K—构形。如图5，b就是一个H—构形，而不是可以连续的移去两个同色B的K—构形。这样的构形我们叫它第二类H—构形，1992年敢峰先生通过二十步大演绎得到的终极图（同一时期英国的米勒也构造了同样的图）就是这一类构形的一个代表。

1、4  图3中的两个图，既没有经过5—轮的两个相邻轮沿顶点4D和5C的环形的C—D链，又没有经过5—轮的三个相邻轮沿顶点1B、2A和3B的环形的A—B链，它们都是可以连续的移去两个同色B的K—构形。那么，是不是只要有这种特点的构形都是可以连续的移去两个同色B的K—构形呢。也不是。如图6的两个图就是不能连续移去两个同色B的H—构形。象这样的构形我们叫它第三类H—构形，2010年张彧典先生构造的第八构形就是这一类构形的一个代表。

1、5  含有经过5—轮的三个相邻轮沿顶点1B、2A和3B的环形的A—B链的H—构形，环形链A—B有经过两条连通且交叉的A—C链和A—D链的交叉点（如图5，b和7，a中加大了的着A色的顶点），也有环形链A—B不经过两条连通且交叉的A—C链和A—D链的交叉点的（如图7，b和图7，c）。含有经过5—轮的两个相邻轮沿顶点4D和5C的环形的C—D链的H—构形，一定经过5—轮的两个轮沿顶点4D和5C（如图2，a，图4，a，图5，a和图7，a），但还有一种情况，图中虽然也有环形的C—D链，但环形的C—D链却不经过5—轮的两个轮沿顶点4D和5C（如图7b）。图7，b的这种构形，虽含有环形的C—D链，但该环形链却不经过5—轮的轮沿顶点。所以图7，b的构形不是第一类H—构形，而只能是属于第二类H—构形，因为图中所含有的环形的A—B链，却经过了5—轮的三个相邻的轮沿顶点。图7，b的构形实际上就是敢峰先生的终极图。
1、6  由于A—B链和C—D链是两条相反的链，所以两链不可能相交叉，所以环形的A—B链和环形的C—D链的相互关系只能是相离关系和大环套小环的关系。图7，a和图7，c中的环形的A—B链和环形的C—D链是相离关系，而图7，b则是大环套小环的关系。同样的，也是因为A—B链和C—D链是相反的色链，所以在有大环套小环关系的构形中，只能有一个环形链是经过了5—轮的轮沿顶点的。如图7，b中是A—B环经过了5—轮的轮沿顶点，而C—D环是不经过5—轮的轮沿顶点的。敢峰先生的终极图就是这样的图。
2、各类H—构形的4—着色
2、1  含有经过5—轮的两个相邻轮沿顶点4D和5C的环形的C—D链的第一类H—构形，可以交换环形链C—D内、外的任一条A—B链，可以使两条连通且交叉的A—C链和A—D链的一条或两条都断开，使图成为K—构形而可约。至少也有经过5—轮的三个轮沿顶点1B、2A和3B的A—B链是可以交换的（因为2A是两条连通且交叉的A—C链和A—D链的共同起始顶点，2A顶点换了颜色，该两链也就断开了），和另一条经过两条连通且交叉的A—C链和A—D链的公共交叉顶点（着A色）的A—B链也是可以交换（交叉顶点A的颜色换了，该两链也就断开了），使图成为K—构形而可约。
2、2  含有经过5—轮的三个相邻轮沿顶点1B、2A和3B的环形的A—B链的第二类H—构形，不管该环形链中包含不包含A—C链和A—D链的交叉顶点，都可以交换环形链A—B内、外的任一条C—D链，可以使两条连通且交叉的A—C链和A—D链的一条或两条都断开，使图成为K—构形而可约。至少也有经过5—轮的两个轮沿顶点4D和5C的C—D链可以交换，使图成为K—构形而可约。因为5C和4D分别是两条连通且交叉的A—C链和A—D链的终点顶点。该两链的终点的颜色换了，该两链也就断开了。
2、3  以上解决第一类H—构形和第二类H—构形中的2、1和2、2的交换，都使得了连通且交叉的A—C链和A—D链的一条或两条断开了，所以把这种交换也叫做“断链交换”。这种交换所交换的是5—轮的邻角顶点的颜色所构成的链，或者交换的链中根本就不含有5—轮的轮沿顶点。相应的，我们把坎泊过去用过的只交换5—轮的对角顶点的颜色所构成的对角链，而从5—轮的轮沿顶点中空出一种颜色的交换，就叫做“换色交换”。
以上解决第一类和第二类H—构形的过程，我们就不再画图了，读者可以自已画一画。
2、4  不含任何环形链的第三类H—构形中，A—C、A—D、A—B和C—D链都不能交换，交换了也空不出颜色来。B—C链和B—D链又不能连续交换，所以，现在也就只有先交换一个关于B的链了。这种交换，可以使构形的类型发生变化，所以把这种交换就叫做“转型交换”。有两种转型的办法：一是从顶点1B交换B—D链，构形转化成DCD型的构形；二是从顶点3B交换B—C链，构形转化成CDC型的构形。注意，“转型交换”只能是从5—轮轮沿顶点的1B或3B开始，交换对角链B—D或B—C，比“断链交换”与“换色交换”所受的局限性都要大。
因为图6的两个图的左边和右边正好是相反的，所以我们下面只研究图6，a一个构形就可以了。

2、5  图6，a先从1B交换B—D时，构形转化为DCD型的、峰点是5C的、可以连续移去两个同色D的K—构形（如图8，a），三次交换就可以解决问题。这时要注意的是，下一步连续移去两个同色D的操作，一定要先从顶点4D开始进行，后从左顶点1D开始进行。因为若先从顶点1D开始进行换色交换，图将又会返回到原来的BAB型的状态，走了回头路；若对图6，a先从3B交换B—C时，构形转化为一个CDC型的、峰点是4D的、有经过5—轮两个轮沿顶点1B和2A的A—B环形链的第一类H—构形（如图8，b），再按第一类H—构形的解决办法处理就可以了，也是三次交换就可以解决问题。对图6，b进行转型交换，所得到的转型后的构形正好与图6，a进行转型交换后所得到的转型后的构形相反。

2、6  以上的第一类和第二类H—构形，都是对称图形，而只有第三类H—构形是非对称图形。而对称的第三类H—构形如图9，图中有A—B链的一部分作为图的对称轴。这类构形的代表就是1935年美国人Irving Kittell构造的图（如图9，a），这是一个H—构形。而图9，b则是一个可连续移去两个同色B的K—构形。解决图9，a这种构形时，必须先进行两次同方向的连续的转型交换，使图转化为不对称的第三类H—构形，再按第三类H—构形的解决办法去处理即可。总共只进行五次交换即可解决问题。图10是分别进行了两次逆时针方向转型交换的对果。两次转型后的图10，b是一个ABA型的、峰点是3B的构形，整理后的图11，a则是一个非对称的第三类H—构形。再对图11，a从顶点2A开始进行一次逆时针方向的A—C的转型交换，得到图11，b的CDC型的、峰点是1D的、有经过5—轮两个轮沿顶点3A和4B的环形A—B链的第一类H—构形，再按第一类H—构形的解决办法去处理就行了。总共只需要五次交换。
由于对称与不对称的第三类H—构形着色时，用的都是转型交换，虽然所用的交换次数多少不同，也就把它们归为一个类别，不再单独分类。

3、H—构形的不可免集
含有经过5—轮的两个相邻轮沿顶点4D和5C的环形的C—D链和含有经过5—轮的三个相邻轮沿顶点1B、2A和3B的环形的A—B链的情况，环形的A—B链和环形的C—D链在图中的分布情况除了①只含有A—B环形链，②只含有C—D环形链，③两条环形链都没有三类情况的构形外，好象应该还有④A—B环形链和C—D环形链同时存在情况的构形（如图7，a和图7，c）。但它们都分别既有第一类H—构形的特征——含有经过5—轮的两个相邻轮沿顶点4D和5C的环形的C—D链，又有第二类H—构形的特征——含有经过5—轮的三个相邻轮沿顶点1B、2A和3B的环形的A—B链，可分别归入该两类H—构形中。不再单独作为一类。除了以上这三种情况外，再也没有别的情况了。所以这三种情况的构形就是H—构形的不可免构形。由这三类构形构成的集合就是H—构形的不可免集。看来这个不可免集是完备的。
4、四色猜测是正确的
至此，我们已经证明了H—构形的不可免集中的每一个不可免构形都是可约的（即可4—着色的），再加上坎泊在1879年已证明了的所有K—构形也都是可约的，就得到了平面图的任何不可免的构形都是可约的。这也就证明了四色猜测是正确的。
5、平面图构形类型的判断方法
因为构形是只有一个顶点未着色的图，所以首先要看所给的图是不是构形，是构形的图，才可判断其是哪种类型的构形，否则就不可能进行判断。
第一步，看图中有没有连通且交叉的A—C链和A—D链：若没有，则一定是K—构形；若有，再进行第二步判断。
第二步，看图是否可连续的移去两个同色B：若能，则仍是K—构形；若不能，则一定是H—构形。
第三步，看图中是否含有经过5—轮两个轮沿顶点的环形的A—B链：若有，则是第一类的H—构形；若没有，再进行第四步判断。
第四步，看图中是否含有经过5—轮三个轮沿顶点的环形的C—D链：若有，则是第二类的H—构形；若没有则就是第三类的H—构形了。
第五步，看图中是否是有以一段A—B链作为图对称轴：若没有，就是非对称的第三类的H—构形；若有，则是对称的第三类的H—构形。
明确的判断了构形是属于哪一种类型的构形，就按哪一种类型的解决办法去处理就行了，一定是可以给待着色顶点着上图中已用过的四种颜色之一的。
当各类H—构形的顶点数减少到“九点形构形”时，第一类H—构形就变成了图2，a的“九点形”，图中仍然有经过5—轮两个轮沿顶点的C—D环形链，仍是一个第一类的H—构形；第二类H—构形则变成了图2，b的“九点形”，虽然图中仍然有经过5—轮三个轮沿顶点的A—B环形链，但却是一个可以连续移去两个同色B的K—构形；同样的，非对称性的第三类H—构形就变成了图3的“九点形”，是一个有选择性的可连续移去两个同色B的K—构形；而对称性的第三类H—构形则变成了图9，b的“九点形”，也是一个可连续移去两个同色B的K—构形。

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

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

雷明85639720

，，，，，，，，

朱明君

波斯猫猫着色

请波斯猫猫给此图着色
      明君先生，由内到外按顺时针方向填图，1--2（占据第二三圈）34--2（占据第二三圈）12123231--3（弓形）--4。你的图不是正规地图：即（1）有一个顶点是四段弧的交点，或（2）有一个区域包围了其它一些区域。

雷明85639720

朱明君 发表于 2018-8-22 12:00
波斯猫猫着色

请波斯猫猫给此图着色

你只要能着上不大于4种的颜色就行了，不要管人家的图是不是正规地图。问题是他那全的图画得不清晰，那个所谓4—度顶点，是不是4—度的，要让人家朱明君说了才能算数。

雷明85639720

朱明君朋友，我在这里不会发图，只好另给你作为一篇文章发出，题目是《给朱明君的一个图的4—着色》，你的图中右上角处有一个顶点好象是4—度的，但又好象是两个3—度的顶点，我只是按4—度顶点给你的图进行了面着色。如果是两个3—度顶点，请指出来，还可以再着。你看如何。你的图是一个空白图，即无有任何顶点着色的图。给这样的图着色更容易些。希望你以后再出题时，只要有一个顶点未着色就可以了。把只是你认为对某个顶点没有办法着上图中已用过的四种颜色之一的图拿出来就可以了。你只拿出一个空白图，实在是好着色的很。

雷明85639720

，，，，，，，，

雷明85639720

朱明君朋友，我已给你的图进行了４着色，你得要表个态呀，是对还是不对呢。

雷明85639720

不知你说的是什么意思．你画的这个图不就是这样的吗，来要分什么区呢．为什么要分呢．既是任意的，还要什么公式呢．你的目的是导出关于那一方面的公式呢，你的语言说得不明不白的．还搞什么四色问题的研究呢．

雷明85639720

朱明君朋友，是你点名要我对你的图进行着色的。我按要求已经给你着了色。但你不表态我着的是对还是不对，却又要我给你导出什么公式。我就这样听你的任意摆布吗。你已经看到了我的图，也把我的图复制到了这里来了，为什么不说是对还是不对呢。

朱明君

四色定理之所以能成立,内环和外环两区域或多区域可共用1个顶点.