重新构图与张彧典先生再商榷

雷明85639720

重新构图与张彧典先生再商榷
雷  明
（二○一六年十一月十六日）

我在《构造成一个图与张彧典先生商榷》（以下简称《构图与商榷》）一文中，原本是想构造成一个与张先生的第八个构形有相同特征的图，但由于我的疏忽，却把图构成了具有张先生的第七构形（或第三构形）特征的图了。张先生在回复（擂台6）中已经指出了，我也作了回复。现按我的回复，再构造如下：
1、《构图与商榷》一文中所构的图
我在《构图与商榷》一文中所构的图如图1所示。

    这个图就是张先生说的属于他的第七个构形的图。从顶点1B交换B—D后，不会产生由顶点3到顶点5的连通链B—C，而从顶点3B交换了B—C后，却会产生由顶点1到顶点4的连通链B—D，从而用“有先后顺序”的、先从顶点3B开始交换B—C，再从顶点1B开始交换B—D，可同时移去两个同色B给待着色顶点V着上。也可以象张先生那样交换，给待遇着色顶点V着上D。
2、张先生打擂6所画的图
张先生打擂6所画的图如图2所示。这是一个赫渥特图，因为图中有环形的且经过C5—D4和C6—D7的C—D链。


3、构造一个可以同时移去两个同色B的图
去掉图2中的最上面的C—D边，连接A2和最下面的B，使图中的A—B链整个变成连通的，且A—B链中的环把C—D链分成了环内、环外两部分，如图3。图中，A8即图2中的A2，C6和D7分别是图2中的C2和D2，图中所增加的顶点用加大的黑点表示。这个图也就是张先生的Z2构形。该图从顶点1B交换了B—D链后，不能生成从顶点3B到顶点5的B—C连通链，从顶点3B交的换了B—C链后，也不能生成从顶点1B到顶点4的B—D连通链。所以，这个图是可以通过交换两个关于B的链（不分先后次序），同时移去两个同色B的。
4、重新构造张先生第八构形的图（不能同时移去两个同色B）

在图3这个图基础上，再增加一些顶点后，得到了图4的图。这个图中有A—C和A—D两条既连通，又有共同起始顶点2A，在中途又相交于8A的A—B链；A—B链只有一条（如图5中的红色链），虽然有几个环形的部分，但B1—A2—B3没有与A8在一个环上，也没有一个A—B环把经过顶点5C—4D和顶点6C—7D四个顶点的C—D链分隔在环的内、外两侧；C—D链虽是多条，但经过顶点5C—4D和顶点6C—7D四个顶点的C—D链仍是在连通的一条之上，也没有构成环形链。这就是我要构造成的具有张先生第八构形特征的图。


图4从顶点1交换了B—D，便产生由顶点3到顶点5的连通链B—C（如图6），从顶点3交换了B—C，也会产生由顶点1到顶点4的连通链B—D（如图7）。不能同时移去两个同色B。

解决这样的构形问题，只能使用“转型法”了，通过逆时针颠倒或顺时针颠倒，使图变成DCD型或者CDC型的其他类型的5—轮构形，再用解决其他5—轮构形的办法去解决。
5、用转型法对图4着色
对图4先从顶点1交换B—D，得到图8。图中原有的从顶点2到顶点5的A—C连通链仍然存在，又产生了从顶点3到顶点5的B—C连通链，两链既有共同的起始顶点C5，又有相交叉的顶点C6，构形由BAB型变成了DCD型，同时图中还有环形的A—B链，把把两连通链的起点C5和交叉顶点C6分隔在两条不同的C—D链内（如图9），从C5和C6中的任一个顶点交换C—D链，都可使图变成坎泊构形而可约，如图10。


若对图4先从顶点3交换B—C，则得到图11。这虽是一个类似于图4的图（也是张先生的第八构形的图，因为A—B链与C—D链都不是环形链），但实际上是一个有选择性的交换关于两个同色C的链C—A和C—B，可同时移去两个同色C的CDC型构形，类似于第一和第三构形。从顶点5交换C—A，不产生从顶点3到顶点1的连通链C—B（如图12），是一个坎泊构形的图，再从顶点3交换C—B，可空出C给待着色顶点V着上；或者从顶点1交换B—C，也可空出B待着色顶点给V着上（图读者自已画）。这一方法也就是张先生用的顺时针颠倒法。



6、用颠倒法对图4着色
先用逆时针颠倒：

四次逆时针颠倒（分别如图13，图14，图15和图16）后，得到一个坎泊构形，再经过一次交换后，可以空C或A，给待着色顶点V可着上。


再用顺时针颠倒：
这种方法与上面“5、用转型法对图4着色”中的先从顶点3先交换B—C的方法是相同的。两次顺时针颠倒后，就得了一个坎泊构形，再经过一次交换后，可给待遇着色顶点V着上C或B。

最后请张先生提出意见，并看把图4归入那一类比较合适。


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

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