构造一个图与张彧典先生商榷

雷明85639720

构造一个图与张彧典先生商榷
雷  明
（二○一六年十一月十三日）

1、张彧典先生的打擂图
张彧典先生在他的《四色猜想构形擂台赛5》一贴中，目的是想构造与他的第八构形有同样特征的图，但他却构造了与他的第二构形有同样特征的图。我认为他的图是第二构形一类，是因为他们有相同的特征：C—D链是环形的，A—B链无环，被C—D链隔成了多段。用我的“断链法”，只交换两步就可空出颜色给待着色顶点V。
张先生虽然也用了与他的第二构形同样的颠倒次数，但没有看到他的图与他的第八构形是不同的。他的第八构形中没有环形链，A—B链和C—D链都是直链（道路），而他在这里构造的图中却有多条环形的C—D链，把A—B链分成了多段。
（见我的《应战张彧典先生专为我设置的擂台5》一文，网址是：，也可以见我的博客，网址是：）
    2、我以前构造的一个图
我想在张先生构造的图的基础上，进行一下改动，目的是想改成与张先生的第八构形有相同特征的图：没有经过顶点B1—A1—B2三个顶点的A—B环形链，也没有经过C1—D1和C2—D2四个顶点的C—D环形链，A—B链和C—D链都是直链。但一时还没有达到目的。后面我还要继续构造。
虽然在张先生图的基础上想改没有成功，但可以根据要求：没有经过顶点B1—A2—B3三个顶点的A—B环形链，也没有经过C5—D4和C6—D7四个顶点的C—D环形链，A—B链和C—D链都是直链。自已又重新构造了一个图，如图1。这就是我在《5—轮构形可约性的再研究》一文中的一个构形。网址是：，也可见我的博客，网址是：。
图1，a是一个由图1，e只保留了关键的色链简化得到的，而图1，c又是由图1，a只保留了关键的顶点得到的。三个图实际上是完全一样的。只是图1，e非关键顶点多，图看不清楚，而简化图后的图都是关键的色链和关键的顶点，图容易看明白而已。图1，b与图1，d的关系与以上相同，只是没有画出图1，d的三角剖分图。
图1，c中没有任何连通链，从顶点1进行逆时针颠倒后，仍是一个与原图类似的图，即还是一个类赫渥特构形，如图2，a。再行一次逆时针颠倒，得到图2，b。该图是一个可以先从顶点交换2交换A—C链，再从顶点4交换A—D链，可同时移去两个同色A的、顶点2、3、4分别着A、B、A的ABA型的非类赫渥特构形。交换的结果如图2，c和图2，d。
图1，c若从顶点3进行顺时针颠倒后，则得到图3，a。该图是一个含有两条有两个相交顶点（顶点4和顶点7）的D—A和D—B的、顶点3、4、5分别着C、D、C的CDC型的类H—构形，但图中有一条环形的A—B链，把C—D链隔成了两部分，具有赫渥特图的特征，可任意交换任一部分C—D链，使连通链断开，使构形变成坎泊构形而得解，如图3，b。
图1，d与图1，c的解法正好是相反的，因为这两图虽对称，但着色却左右不同。






3、与张彧典先生共同探讨
这种图与九点形是大不相同的，与九点形的解法也不相同。原因在于九点形的关键顶点间的链都是单边，而这里的构形则不是，链与链之间相互穿过的机会多一些，所以着色的步子就要比单纯的九点形图要多一些。这是一种特殊的解法，我叫它“转型法”，即构形的类型发生了转化，实际上就张先生的“颠倒法”。所谓转型就是进行逆时针颠倒后由BAB型转化成了DCD型，或者顺时针颠倒后由BAB型转化成了CDC型等。转型后，再按新类型的构形的解决办法去解决即可。
张先生的四个Z构形中，正好就没有这一类。四个图中，Z1一类是可以同时移去两个同色的构形（应属坎泊的K构形），Z2一类是赫渥特图类构形，Z3和Z4两类是敢峰—米勒图类构形，就是没有这一类构形。
张先生把这一类归为赫渥特图类构形，原因是该图4—着色时，也只是颠倒了两次，与赫渥特图类颠倒的次数相同。这好象也能说得过去，但我总觉得这不太合适。请张先生再想想此事。
4、在张先生图的基础上再构造图
根据前面图1中的关键链的关系，我终于在张先生原图的基础上改成了与图1中的图有相同结构的图，如图4。构图的原则就是按构图的要求：没有经过顶点B1—A2—B3三个顶点的A—B环形链，也没有经过C5—D4和C6—D7四个顶点的C—D环形链，A—B链和C—D链都是直链。的确也按要求达到了。但实际上图中还是存在着几处A—B环，但这些环都不是经过B1—A2—B3三个顶点的A—B环，整个A—B链是只有一条，由于有A—B环，所以C—D链就被分成了四段，但没有C—D环，更不会有经过C5—D4和C6—D7四个顶点的C—D环了。为了便图成为三角剖分和不产生C—D环，在张先生原图中去掉了最上面的C—D边，同时又增加了一些顶点（增加顶点图中用大黑点标出）。该图只画了一个，是与上面的图1，b和图1，d类型相同的，着色时，用与图1中给图1，a和图1，c相反的方法颠倒转型就可以了，或者仍按逆时针颠倒也可以。这里就不再说了。

这个图中虽然有A—B环，但却不经过B1—A2—B3三个顶点，而张先生构造成的图中却存在着经过C1—D1和C2—D2四个顶点的环形链C—D，已经具有赫渥特图构形的特征，所以可以用“断链法”进行解决，而我这里的图只能用“转型法”进行解决了。
这个图可以简化成图1，b和图1，d的十五点形，也可以简化成九点形构形，其着色方法或解决办法都是相同的。
这个图为什么只能用转型法解决，关键的问题是：①  A—C和A—D链都是连通的，是不能交换的：②  A—B链和C—D链都是直链，就是交换了，也只是两种颜色交换了一下位置，不能起到任何作用；③  B—C链和B—D链虽不连通，但又不能同时交换，不能同时移去两个同色B；④  现在只有一个办法了。B—C和B—D不能同时交换，那么总可以只交换其中的一个，先移去一个B，使构形变型了；⑤由于B—C和B—D在图中分布的位置不同，于是就产生了逆时针和反时针颠倒（交换）的问题。这些才是“颠倒法”的实质。至于图是不是三角剖分都是无关紧要的小事情。关键的链的关系已经摆好后，再在图中增加一些顶点和边，把图变成三角剖分就是了。我在你的图的基础上构造成图时，不是就增加了顶点和边吗。但这些顶点和边，增加不增加也是没有关系的，他们是不会参加到交换中去的。关键的链已有了，照样也能通过各种交换使问题得到解决。
    请张先生用你的方法，对这个图进行一下着色分析，看需要进行几次颠倒，是属于那一类型。
5、构造各类型5—轮构形图的方法和四色猜测的证明
坎泊构形在这里就不说了，只说说类赫渥特图型的构形：首先安排好要构造成的图的各关键链的相互关系，然后再在这些链之外添加顶点和边使之成为三角剖分图（其实不添加也可以）。
这种构形的共同特征是：
有两条连通且有共同起始顶点（顶点2A）和中途相交叉（在顶点8A）的，到达顶点5C和4D的A—C和A—D链，这是必须的。
第一，构造成一个赫渥特图型的坎泊构形：该构形除上术链外，另外还有一条经过三个顶点1B—2A—3B的环形链A—B，只要有了这些，其他地方任意增加顶点和边，只要所着颜色符合着色要求就行了。
第二，构造成一个赫渥特图型的赫渥特构形：该构形除上术链外，另外还有一条经过5C—4D和6C—7D四个顶点的环形链C—D，只要有了这些，其他地方任意增加顶点和边，只要所着颜色符合着色要求也就行了。
第三，构造一个赫渥特图型的敢峰—米勒构图构形：该构形除上术链外，另外构形中既有经过三个顶点1B—2A—3B的环形链A—B，又有与其不连通的非环形的A—B链，A—B链既不连通，必有环形的C—D链将其隔开，当然也就还有另一部分直链的C—D。这样，构形中两种相反色链就各是两条以上（包括两条），既有环形链，有又直链（道路），这就构形了敢峰—米勒图的其本骨架。然后与上面相同，随便去加点去吧。
第四，构造一个需要转型的构形，即我上面的图或是张先生的第八构形：该构形除上术链外，另外构形中既没有经过三个顶点1B—2A—3B的环形链A—B，也没有经过5C—4D和6C—7D四个顶点的环形链C—D。构造时，把两条链均按环形链分别画好后，然后把每条环形链打开一个缺口，让两链的两个部分都连通起来即可。上面我在张先生图的基础上就是这样构造我这里的图的。
现在看来，A—B链与C—D链的相互关系就只有这么四种：①　只有经过三个顶点1B—2A—3B的环形链A—B，把C—D链分为两个不连通的部分；②　只有经过5C—4D和6C—7D四个顶点的环形链C—D，把A—B链分为两个不连通的部分；③　既有经过三个顶点1B—2A—3B的环形链A—B，又有经过5C—4D和6C—7D四个顶点的环形链C—D，两链既有环形部分，又有直链部分，且互不连接；④　经过三个顶点1B—2A—3B的A—B链和经过5C—4D和6C—7D四个顶点的C—D链都是一条直链，没有环形链。除此之外，好象再也没有别的情况了。
张先生朋友，你说是不是这样就可以构造成出任意多顶点的构形来了呢。除了以上四种情况以外，再没有别的情况了，这就说明了再没有别的构形了，他们既都是可约的，那么，四色猜测也就被证明是正确的了。

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

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

雷明85639720

，，，，，