[原创]“构形”与“不可免构形集”

雷明85639720

[watermark]

“构形”与“不可免构形集”
——兼论四色猜测的证明
雷  明
（二○一四年二月三日）
1、“构形”与“不可免构形集”
“构形”及“不可免构形”的术语是坎泊早在1879年就提出的。坎次在证明四色猜测的过程中，不但首先提出了用两种颜色的交替着色法和颜色交换技术。而且也首先提出和证明了任可地图中至少存在一个区划的相邻区划数小于等于5（相当于图论中的任何平面图中一定存在至少一个顶点的度小于等于5）的情况，还首先提出和证明了任何地图中都不存在5个以上两两区划都相邻（相当于图论中任何平面图的最大团的顶点数一定是小于等于4）的情况。除此之外，坎泊还首先使用了“构形”与“不可免构形”的术语。
构形一词的出现是与图的着色相联系的，当然离开了着色就无所谓“构形”了。所以说构形就是除了一个顶点未着上图中已用过的四种颜色之一的一个未完成着色的图。地图的对偶图是一个极大图，其每一个顶点都是处于一个轮的中心顶点位置，所以就把以该未着色的顶点为中心顶点的轮叫做一个构形，而省去了该轮以外的所有顶点。如果除去该未着色的顶点，剩下的图是可4—着色的。
由于平面图中一定存在着一个顶点的度是小于等于5的，所以度从0到5的顶点所构成的六种轮（0—轮，即K1图；1—轮，即K2图；2—轮，即K3图；3—轮，即K4图；4—轮和5—轮）就共同构成了平面图的不可免构形集。这六种构形在平面图中一定是不可避免的存在的。
四色猜测的证明就是只要证明了平面图的六个不可免构形中的待着色顶点（即轮的中心顶点）能够着上图中已用过的四种颜色之一，就能说明四色猜测是正确的。因为我们在对平面图着色时，总可以从图中找到一个度小于等于5的顶点，留下最后再对其着色。构形能够4—着色时（即轮中心顶点能着上图中已用过的四种颜色之一），坎泊当时称之为“可约”， 当然不能4—着色时就称为不可约。
2、几种对构形和不可免构形集的错误提法
有的人（如张彧典）为了说明平面图的不可免构形集中的元素（构形）都是可约的，而用了“可约不可免构形集”一词，这就错了。言下之意是不是平面图中还应有“不可约的不可免构形”了。即然有这样的构形存在，“不可约”就是不可4—着色，这不就已经说明了四色猜测是不正确的吗。你何心还要花大力气去再进行证明呢。所以说，在使用技术术语时一定是要慎重的，不能随便乱用。
也还有人（如阿贝尔等）在定义构形时，可以使一个构形内存在多个待着色顶点，这也是不合适的。着色总是一个顶点一个顶点的去着，那么你这个构形中的待着色顶点也同样是一个一个的去着色的，最后只剩下一个时才是真正的构形。但这个构形是不是不可免的，也就不能确定了。难怪阿贝尔用了2000多个构形，原来他就没有从平面图的不可免集去入手。况且他用了1904年Wernicke构造的两个构形来替代5—轮构形，能替代得了吗。这两个构形分别是“两个5次的相邻顶”和“一个5次一个6次的两个相邻顶”（引号中是王树禾《图论》书中的用语）。这两个构形中均有两个待着色顶点，阿贝尔着色的结果也说明这两个构形是可约的。然而这两个构形中均有5—轮构形存在，那不也就说明了5—轮构形是可约的吗。为什么要绕开5—轮走呢，难道5—轮就那么害怕吗。我在这里说阿贝尔的证明中已说明了5—轮是可约的，并不是说他的的思想就是正确的，因为他在这里用的是“穷举法”，是在无穷的进行验证，并不是在利用平面图的不可免构形集在进行证明。我不认为验证得越多，就越能说明猜测就是正确的。所以说他的证明是错误的，也并没有解决猜测的证明问题。
3、四色猜测的证明
对于平面图的不可免构形集中的每一个构形来说，只要其围栏顶点（即轮沿顶点）所占用颜色总数未大到4，该构形中的待着色顶点也总是可以着上图中已用过的四种颜色之一的，即该构形也一定是可约的。但当构形的围栏顶点所占用的颜色总数已达到了4时，就得想办法从其中减少一种，空出其给待着色顶点着上。减少围栏顶点占用颜色总数的办法，只能是用坎泊所创造的颜色交换技术。
如果构形的某两个对角顶点的两种颜色构成的色链，对于这两个对角顶点来说是连通的，那么即就是施行了颜色交换技术也是空不出颜色来的；而只有该色链是不能连通时，在施行了颜色交换技术后才可以空出颜色来。四种颜色中由某两种颜色构成的色链连通时，而由另两种颜色所构成的色链则一定是不连通的，交换这条不连通的链后，就可以空出一种颜色来。但在5—轮时，由于每一个顶点都有两个对角顶点，当某一个顶点的两条对角链都是连通的时，则与各色链颜色不同的另外两种颜色构成的色链则一定都不连通，这时可施行两次交换，一定可空出5个围栏顶点中用过两次的那种颜色来。但当两条对角链又相交叉时，即就是按上述交换了另外的两条链，也仍是空不出颜色来的。如赫渥特图那样。怎么办，就得想办法把已连通的链断开，然后再施行颜色交换技术。断链的方法也是要用到坎泊的颜色交换技术。看来任何链能否断开，也就成了四色猜测证明的关键了。
设四种颜色A、B、C、D，若A、B构成的色链为A—B，则A和B在A—B链以外，只能与C和D相邻，构成A—C和A—D链，或者B—C和B—D链，从A—B链上的任何一个顶点A或B开始交换以上的任何一种链，都可使该链上的该 顶点变成C或D，使A—B链断开。这样就可以从5—轮中的一个顶点A或B交换A—B链，空出A或B来。
到此，就可以说明图中的任何链都是可以断开的，也就证明了四色猜测是正确的。
证明就是这么简单，不知为什么有人说要证明四色猜测没有20页以上是不行的。这是一个什么样的结论嘛。四色问题至今不能解决，就是因为把实验室宣传得太神秘的结果。
雷  明
二○一四年二月三日于长安