四色问题讲座：第十二讲 非E—图的H—构形最大转型次数上界值的确定（理论证明）

雷明85639720

四色问题讲座：第十二讲  非E—图的H—构形最大转型次数上界值的确定（理论证明）
雷  明
首先要明确这种非E—图的H—构形是已经经过证明是可约的，且转型次数一定是有限的。这是根据E—图构形转型的无穷周期循环性，用“原命题的逆否命题与其原命题同真同假”的逻辑关系进行判断证明的。现在这里主要是要确定这个“有限的”上界值是多少的问题，而不是研究这种构形是否是可约的问题。
H—构形是可以向逆时针方向和顺时针方向两个方向进行转型的。一个构形设逆时针方向转形了m（m≤20）次，达到了转型的终了（指空出了颜色给待着色顶点着上时），顺时针方向转型了n（n≤20）次，也达到了转型的终了。那么两个终了构形（图）之间（包括两个终了图）一共有m＋n＋1个构形（图），式中的这个“1”就是指原构形。其中，有m＋n＋1－2×3个构形（图）是H—构形（因为各个方向转型的最后三个图都不是H—构形而是K—构形，所以要减去2×3）。
那么，分别从这两个转型的最后第四个构形开始，按相反方向进行转型，一直达到转型终了时，应是m＋n＋1－4次的转型（或交换。最后的两次所谓的“转型”实际上是属于连续的移去两个同色的K—交换）。这就是该构形当有一个方向进行一次转型就转化为可约的K—构形时，而向另一个方向转型时的最大转型次数。我们已经找到了转型次数为25次的具体构形，证明了其转型的最大次数是大于5—轮构形的固有周期（即5—轮构形的围栏顶点的转型周期）20次的，以及也大于E—图构形的转型周期20次的构形是存在的。那么，现在要问，还有没有比这个转型次数更大的构形呢？最大的转型次数是多少呢？
我们在转型过程中发现，这种转型次数大于20次的构形，经过20次转型，属于原E—图中的所有顶点都回到了原来的初始状态，而在E—图中所增加的顶点（增加了这些顶点后，E—图就转化成了非E—图的H—构形了。如前面的图26—1和图27—1，都是在E—图的基础上增加了两个顶点的），却没有回到初始状态。这说明构形虽然进入了E—图构形的第二个循环周期，但整个构形还没有回到初状态，根本不能判断是否是产生了循环转型。至此，E—图构形的第三个循环周期还没有到来，也是不可能到来的。因为我们所研究的这种构形已经证明是在有限次转型之内，就可以转化成K—构形，是可约的，根本就不可能产生循环转型的。
既然E—图的第三个循环周期不可能到来，那就只能在E—图的第三个循环周期到来之前的第40次转型前，转型过程就必须结束。采用反证法：如果说转型过程有可能进入E—图构形的第三个循环周期之内，就说明原E—图的转型就进入了周而复始的E—图构形的无穷周期循环了，不管在E—图中增加的顶点反回不反回到原着色状态，都说明整个图的转型是无穷的了。这与我们在这里所研究的构形本身是有限次转型就可以转化成可约的K—构形的条件则是格格不入的。所以说该构形的转型是不可能进入E—图的第三个循环周期的。
既然进入不了E—图的第三个循环周期，就说明了我们原来所说的“那就只能在E—图的第三个循环周期到来之前的第40次转型前，转型过程就必须结束”这一假设还是正确的。最大的转型次数就只能是40次了。这就是把非E—图的H—构形最大转型次数的上界值确定为40次转型的原因。
这里又从理论上证明了上面提出的，非E—图构形的H—构形最大的转型次数的上界值，是不大于40次的猜想是正确的。

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，