构形的类型与链的关系

雷明85639720

构形的类型与链的关系
雷  明
（二○一七年十二月十二日）

解决四色问题，主要是要证明5—轮构形是否都是可约的问题。现在我们就直接从5—轮构形谈起。
1、有共同起始顶点A的A—C链A—D链的中途是否相交叉，只是产生H—构形的必要条件，但不是充分条件。
5—轮构形中对角顶点间的对角链可以连通的只可能有A—C、A—D、B—C、B—D四条对角链，这正好是两对相反的链（即每对链中各链中的颜色均不相同）。相反链是不能互相穿过的，所以A—C链与B—D链只可能有一条是连通的；A—D链和B—C链也只能有一条是连通的。四条同时连通是不可能的。

若B—C链和B—D链都连通（中途一定相交叉，交叉点着B色），就不可能再有A—C链和A—B链的连通，这是一个K—构形，可以空出A、C、D三种颜色中的任何一种给待着色顶点（如图1）；若A—C链和A—D链都连通（两链有共同的起始顶点2，着色为A），则有两种情况：
一种是两链只有共同的起始顶点，中途并不交叉（如图2），这也是一个K—构形，可以同时移去两个同色B给待着色顶点；
另一种是两链除了有共同的起始顶点外，中途还有交叉顶点8（如图3），这种情况既然不能空出A、B、C三种颜色的任何一种，那么，是否可以空出B来呢。

这里又分三种情况：
一种是交换了1B—7D（或3B—6C）后，不再产生新的从顶点3（或1）到顶点5（或4）的B—C（或B—D）链（如图3），就可以同时移去两个同色B给待着色顶点，先移去那一个B都能得到相同的结果。这种构形是一个K—构形；
另一种是交换了1B—7D（或3B—6C）后，则又产生了新的从顶点3（或1）到顶点5（或4）的B—C（或B—D）链（如图4），这时不光是不能空出A、B、C三种颜色之一，就连颜色B也是空不出来的。这就是H—构形；
第三种情况是交换了1B—7D后，不产生从顶点3到顶点5的连通链B—C，而交换了3B—6C后，却产生从顶点1到顶点4的连通链B—D（如图5），或者是交换了3B—6C后，不产生从顶点1到顶点4的连通链B—D，而交换了1B—7D后，却产生从顶点3到顶点5的连通链B—C（如图6）。图5必须先交换1B—7D，先从顶点1上移去一个B（如图7），后从顶点3交换B—C，再移去第二个B（如图8）；而图6则必须先交换3B—6C，先从顶点3上移去一个B（如图9），后从顶点1交换B—D，再移去第二个B（如图10）。否则图将都仍是一个空不出任何颜色的H—构形。



可以看出，没有A—C链和A—D链的相交叉，是不会构成H—构形的，但含有A—C链和A—D链相交叉的构形并不都是H—构形。所以说有共同起始顶点A的A—C链A—D链的中途是否相交叉，只是产生H—构形的必要条件，但不是充分条件。因此，我认为张彧典先生把只要是含有A—C链和A—B链的图都认为是H—构形是不合适的。
2、H—构形的可免集中只有三类构形：
解决这类H—构形的问题，我们首先想到的是使连通的A—C链和A—D链两条或一条变得不连通，图就变成K—构形了。
a类构形：如果在图4中，还存在环形的A—B链（如图11），这时可以分别交换4D—5C或6C—7D，可使相交叉的A—C链和A—D链均变得不连通（如图12和图13），图变成K—构形，问题得到解决。


b类构形：如果在图4中，存在环形的C—D链（如图14，当然也就不可能再有环形的A—B链了），这时分别从A—C链和A—D链的共同起始顶点1A或交叉顶点8A交换A—B链，也可使相交叉的A—C链和A—D链也均变得不连通（如图15和图16），图也变成K—构形，问题同样也就得到了解决。
c类构形：如果在图4中，A—B链和C—D都不存在环形链，即都是直链（彩色道路，如图17和图18），则A—B链和C—D链都是不能交换的。即就是交换了也起不到什么作用，图仍不能变成K—构形。这时，我们就只好先移去一个B，使图变型，变成别的构形，再进行分析并着色（图17和图18这两个图实质上是相同的，只是A—B链和C—D链的左右分布不同，两图都是只取了图11和图14的一半。所以我们就只对图17进行研究就可以了。

对图17先从顶点1交换了B—D链，图就变成一个DCD型的构形（如图19），是一个可以同时移去两个同色的K—构形（如图20到图 22。但必须先从顶点4交换D—A链，后从顶点1（或3）交换D—B链，移去两个同色D（或B）。否则，先从顶点1交换了D—B链，图就又变回到了17）。
若对图17先从顶点3交换了B—C链，图就变成一个CDC型的构形了（如图23），这是一个b类H—构形，因为图中存在着环形的A—B链（请注意，由于这里是CDC型构形，所以这里的A—B链并不是原来的BAB型构形中的A—B链，而只是相当于图17中的C—D链）。再交换环形的A—B链内、外的任一条C—D链，都可使两条相交叉的D—A链和D—B链断开，使图变成K—构形（如图24和图25）。


同样的，若对图18也进行与图17相同的以上操作，也会得到同样的结果，不同的是图18从顶点1交换了B—D后得到的是b类H—构形，而图17则是从顶点3交换B—C后得到的是b类H—构形。
在H—构形中，5—轮的对角链A—C、A—D、B—C、B—D四条链均不能交换，可交换的只有A—B和C—D两条相反的相邻链。这两种链在图中的分布只可能有三种，即有A—B环形链，则C—D链就被分隔在A—B环的内、外两侧；有C—D环形链，则A—B链也被分隔在C—D环的内、外两侧；第三种情况是A—B链和C—D链都是非环形的直链（彩色道路）。除此三种情况外，再无别的分布形式。所以说，以上的a、b、c三种类型的H—构形就是H—构形的不可免集。
3、各类H—构形可约性的证明：
①  有环形链的H—构形可约性的证明：
（1）当图中有环形A—B链时的情况：因为在A—C链和A—D链中，至少有4D与5C两个顶点是直接相邻的顶点（如果没有这两对顶点的直接相邻，图就不可能再是5—轮构形了），所以，无论A—B环形链是从哪个地方穿过A—C链和A—D链（也无论是只穿过一条还是两条都穿过），A—B环形链的某一侧至少是存在着4D与5C两个顶点是直接相邻的。这就保证了把4D与5C两顶点的颜色交换后，就一定可以使A—C链和A—D链的两条（或一条）断开，使构形转化成K—构形。
（2）当图中有环形的C—D链时的情况：因为在A—C链和A—D链中，至少有顶点2A和顶点8A是两条链的公共顶点（如果没有这两个公共顶点，图也就不可能再是H—构形了），所以，无论C—D环形链是从哪个地方穿过A—C链和A—D链（也无论是只穿过一条还是两条都穿过），C—D环形链的某一侧至少也是存在着这样的两个公共顶点之一的。这就保证了无论从其中的哪一个公共顶点进行A—B链的交换时，也都可以使A—C链和A—D链的两条（或一条）断开，使构形转化成K—构形。
到此，这就证明了有环形链的H—构形一定是能够转化成为坎泊的K—构形的。
②  无环形链的H—构形可约性的证明：
（1）从图3、图4、图5可以看出，只所以这三个图可以同时移去两个同色B，关链的问题是都至少有一个B色顶点，从该顶点交换了B—D（或B—C）链后，不会产生从另一个B色顶点到其对角顶点的连通的B—C（或B—D）链，再从这另一个B色顶点开始交换B—C（或B—D）链，便可同时移去两个同色B。而图17从顶点1交换了B—D后所得的图19，正好就有这样的特征，再从顶点4交换了D—A后，不会生成从顶点1到顶点5的连通的D—B链，所以也就可以同时移去两个同色D（或B）。所以c类H—构形通过一次转型交换一定是可以转化为K—构形的；
（2）从图11中可以看出，b类H—构形的特点是有一条由BAB型构形中的A—C链和A—D链中的两种不同颜色C和D构成的环形链C—D，而图17从顶点3交换了B—C后所得的CDC型的H—构形的图23中，正好也有一条由CDC型中的D—A链和D—B链中的两种不同颜色A和B构成的环形链A—B。所以图23是一个b类H—构形。b类H—构形是可约的，当然图23 也就是可约的，进而图17也就是可约的了。所以c类H—构形通过一次转型交换也一定是可以转化为b类H—构形的，进而也就可以转化为K—构形。
到此，这也就证明了无环形链的H—构形一定是能够转化成为坎泊的K—构形的。
③  各类型H—构形相互转变的证明：
H—构形中，如果在没有任何环形链的情况下（如图17和图18），解决的过程是先交换1B—7D或3B—6C，把构形由BAB型转变成DCD型或CDC型。因此，我们把交换含有B色的链叫做转型交换。从图4、图11、图14、图17、图18的各种H—构形中可以看出：交换了1B—7D后，使顶点7变成了B，破坏了从顶点2到顶点4的A—D链的连通性，但又新产生了从顶点5到顶点3的C—B连通链，而原来从顶点5到顶点2的C—A连通链仍然存在，这时图就由原来的123—BAB型的H—构形转化成了451—DCD型的H—构形了（如图26）；而交换了3B—6C后，使顶点6变成了B，破坏了从顶点2到顶点5的A—C链的连通性，但又新产生了从顶点4到顶点1的D—B连通链，而原来从顶点4到顶点2的D—A连通链也仍然存在，这时图就由原来的123—BAB型的H—构形转化成了345—CDC型的H—构形了（如图27）。

4、其他
①  当图中既有环形的A—B链，又有环形的C—D链时，构形具有a类构形和b类构形的共同特征，我们把它归入a类，用交换A—B环内、外的任一条C—D链的办法进行解决。
②  基本的H—构形是左右对称的，各链也是对称的。当图中含有环形链时，也是对称的。但当不含任何环形链时，构形有时是对称的，有时是不对称的。不对称的构形，通过一次交换或一次转型，就可以使图变成可约的K—构形；而对称的构形，最多四次转型就可以使图转化成K—构形。

以上所述，是本人在对四色猜测的证明过程和着色的过程中总结出来的规律，若有不对之处，请爱好者网友指正。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，