评张彧典先生需要十四次颠倒的图

雷明85639720

评张彧典先生需要十四次颠倒的图
雷  明
(二○一八年六月十九日)

张彧典先生在网上发了一个需要十四次逆时针颠倒的图，并且说，用顺时针颠倒时需用要五次颠倒。据此他提出了一个最多只要十八次颠倒的“最后猜想”。
1、张先生需要颠倒十四次的图在第五次逆时针颠倒时，图的方向有所变动，但顶点间的相互关系没有变。这样的变动在第九次颠倒，第十三次颠倒时都有所发生。这就增加了读者阅读看图的难度。不明白张先生为什么要这样做，这样你在画图时不是也同样的麻烦吗。
2、这个图如果顺时针颠倒时，交换四次即可着上色（即颠倒两次就变成了可同时移去两个同色的K—构形，再交换两次就可以给待着色顶点着上颜色）。不是张先生说的需要五次颠倒（交换）。十四次逆时针颠倒也是到第十二次时，就是一个可同时移去两个同色的构形。两个可同时移去两个同色的构形间颠倒次数共十四次，两个方向颠倒都给待着色顶点着上颜色时，共计交换十八次。严格的说，应是颠倒十四次，交换（包括颠倒在内）十六次。因为总要把一头的K—构形的两次交换去掉的。
3、逆时针第一次颠倒后是DCD型，没有任何环形链，是C类。
4、第二次颠倒后是ABA型，没有任何环形链，是C类。
5、第三次颠倒后是DCD型，既有环形的A—B链，又有环形的C—D链，既是A类，又是B类，交换各环内、外的相反链都可使连通且交叉的两链断链，变成K—构形。
6、第四次颠倒后是BAB型，有环形的C—D链，属B类，交换其内、外的A—B链，使连通且交叉的两链断链，变成K—构形。
7、第五次颠倒后是DCD型，有环形的C—D链，属A类，交换其内、外的A—B链，使连通且交叉的两链断链，变成K—构形。
8、第六次颠倒后是ABA型，有环形的C—D链，属B类，交换其内、外的A—B链，使连通且交叉的两链断链，变成K—构形。
9、第七次颠倒后是CDC型，既有环形的A—B链，又有环形的C—D链，既是A类，又是B类，交换各环、内外的相反链都可使连通且交叉的两链断链，变成K—构形。
10、第八次颠倒后是BAB型，没有任何环形链，是C类。
11、第九次颠倒后是DCD型，有环形A—B链，是B类。交换其内、外的C—D，使连通且交叉的两链断链，变成K—构形。
12、第十次颠倒后是ABA型，没有任何环形链，是C类。
13、第十一次颠倒后是CDC型，有A—B链，B类。交换其内、外的C—D，使连通且交叉的两链断链，变成K—构形
14、第十二次颠倒后是BAB型，没有任何环形链，是C类。又是可以同时称去两个同色B的K—构形。
15、第十三次颠倒后是DCD型，有环形的A—B链，既是A类，也是K—构形。
16、第十四次颠倒，同时移去了两个同色B（对十二次颠倒后的构形而言）。或者空出C（对十三次颠倒后的构形而言）。
共进行了十四次交换（包括颠倒内，颠倒也是交换）。顺时针颠倒时，四次交换可以空出颜色，二者之和共计十八次交换。实际上顺时针颠倒时，第二次颠倒就是一个可同时移去两个同色的K—构形了。
这个图按张先生进行的逆时针颠倒，有非常多的机会都可以变成K—构形而可约，不知张先生为什么一定要进行这么多达十四次的颠倒呢。
我现在用张先生的图也构造一个图，按你的连续逆时针颠倒，需要十六次颠倒（交换）才能着色的图，用顺时针只需两次交换就可同时移去两个同色B，二者之和还是十八次交换。请你进行一下着色交换，看是不是这样的。


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

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

附：
我的《评图》一贴发出后，张先生与我的对话：
张先生回复我：
“我的14次逆时针颠倒的构形顺时针颠倒须5次，在原文中说的明白了。你构造了一个颠倒16次的构形，又一次逼近我的猜想值18，即颠倒次数最多为19次。欢迎你打破这个值。”
我又回复：
“张先生：
“1、我构造交换次数十六次的目的在于说明没有颠倒次数的上界的，进而也说明不能按颠倒次数的多少对构形进行分类的。
“2、任何一个图，逆时针颠倒，如果是x次交换，顺时针颠倒是y次，则一定可以构造出来一个交换次数是（x＋y－2）次的构形的。
“3、如何构造，就是向一个方向（如顺时针方向）进行颠倒，把空出颜色给待着色顶点着上这最后一次交换前的第三次交换后的图，作为一个新的构形，把该构形的类型（可能这时是CDC型等）人为的换成（把顶点颜色进行互换改变）BAB型的构形即可。
“4、这样构造的构形，再按另一个方向（如逆时针方向）进行颠倒时，一定是在交换（x＋y－2）次后，就可空出颜色给待着色顶点着上。
“5、构造这样的构形，可以给原图增加顶点，也可以不增加顶点，但增加顶点一定是在一个三角形内增加一个3度的顶点，是不会影响所构造的构形的交换次数的。我所构造的交换十次的构形就是在你的第八构形的基础上增加了一个顶点而成的，这次构造的需要交换十六次交换的构形，就是在你的十四次交换的构形的基础上不增加顶点构成的。
“6、构造一个构形很难，我是想了好久才想出用这个办法构造需要交换十次的图的。我想你构造了那八个构形，特别是后面几个构形，你也一定是费了很大的精力的。
“7、我也不想构造你提出的最多只需要十八次交换的构形了，即就是构造出来又有什么用呢，仍然不能证明其交换次数就是最多的，还是解决不了问题嘛。我只要知道我在上面所说的构造方法就可以了。
“8、我仍然坚持我认为的，这样的最多交换次数的构形是找不到的，按你的以交换次数多少划分构形类型的原则，这个换次数是没有上界的。敢峰—米勒图就是一例。
“9、你可能会说敢峰—米勒图是出现了构形类型的循环，是的，是这样的。但你没有看一看你连续颠倒过的构形中，有那一个不是出现了构形类型的循环呢。
“10、有一个术语我认为应改变一下更合适一些。即就是过去我们常说的“同时移去两个同色”，应改为“连续移去两个同色”比较科学一些。因为交换是一次一次进行的，着色是一个顶点一个顶点着的，所以用“连续”二字比用“同时”二字好一些。的确，实际操作也是不可能是同时交换两个链的，而是紧跟着、一前一后的交换两个链的，这就是用“连续”二字的合理意义。
“11、不说了，该吃饭了。再见。”