[原创]关于几个图的4-着色

雷明85639720

[watermark]

关于几个图4—着色的信
雷 明
（二○○九年五月十日）
现在我把我在一九九二年初对中科院应用所堵丁柱研究员及该所信访处来信所提问题的答复发表如下：
回答中国科学院应用数学研究所
堵丁柱研究员及该所信访处提出的几个问题
雷  明
（一九九二年初）
我在接到堵丁柱先生来信的同一天还接到了应用数学研究所信访处的一封来信，一并回答如下：
问题1、“在一个着色图中，并不是所有的不相邻顶点着同一颜色，如下图。该图色数为4，但总有一对顶点着不同颜色，这样在你的第4步中就存在如何选择不相邻顶点进行联边收缩的问题。”

回答：图的着色要求的只是相邻的顶点不用同一颜色，并没有要求所有不相邻的顶点都要用同一颜色，而只是说不相邻的顶点可以用同一颜色。你画的这个5—轮（属平面图），一共有六个顶点，着色时用六种、五种、四种颜色当然都是可以的，都是能满足着色要求的。但用色最少的是四种，不能再少了。图的着色不但要求相邻的顶点不用同一颜色，而且还要求所用的颜色数是最少的。一个图着色后，只要所用的颜色种数是最少的，图中还有没有不相邻的顶点未能着上同一颜色是无关紧要的，重要的则是着色时所用的颜色数是最少的。关于如何选择不相邻顶点的问题，这的确是一个问题。比如，一条道路，既可以凝缩成只剩下两个顶点的K2图，也可以凝缩成有三个顶点的K3图，甚至是顶点数更多一些的完全图。但任何一个图（包括平面图和非平面图）在进行联边凝缩时却都一定存在着一个顶点数最少的最终结果——最小的完全同态。给这个最小的完全同态着色时，因为其中所有的顶点都是相邻的，所以其有多少个顶点就得用多少种颜色。这个最小的完全同态的顶点数也就是该图着色时的色数。完全同态中的每一个顶点都是由不等数量的顶点凝缩在一起的，在图中它们都是不相邻的，所以着同一颜色是完全符合要求的。5—轮，是一个奇轮，奇轮着色时都得用四种颜色。轮的密度都是3，而所有奇轮联边凝缩所得到的最小完全同态都一定是一个K4图，K4图着色时必须得用四种颜色，所以5—轮也就是一个4—色图。至于一个图联边凝缩的最后结果——最小完全同态的顶点数与图的密度的关系，本人已有证明。这里先说其结果：即图的最小完全同态的顶点数，大于等于图的密度，而小于等于其密度值一点五倍的整数部分。
问题2、“平面图经过任何一次联边凝缩是不是还是平面图，考虑下图。
图中顶点A与B 经过联边凝缩，还会得到一个平面图吗？如果这不正确，则你的第5步就不会正确。”

回答：联边凝缩，我后来把它叫做不相邻顶点间的同化。它只说明不相邻的顶点可以通过同化凝结成一个顶点。对于任何一个平面图（其密度一定都是小于等于4的），其同化的最终结果一定是顶点数n小于等于4的完全图K4（关于这一点我也已有证明），所以任何平面图的色数一定都是小于等于4的。你在上一个问题中已提到了选择不相邻顶点的问题，是的，必须要选择好，否则就不会得到顶点数最少的完全同态。至于你画的图，若先对A、B两顶点进行联边凝缩时，最后也能得到一个平面图（你要是只把A、B 两顶点凝结在一起，再不向下继续进行，那当然就不是平面图了），但其顶点数不是最少的。该图联边凝缩的最后结果应是一个K2图，而按你提出的先从A、B两顶点开始进行联边凝缩，最后就只能得到K3图，而这也是一个平面图。现在按你提出的先由A、B 两顶点进行联边凝缩如下：
1、把你的图各顶点编号如下图1，该图是一个平面图，图中只有K2团，其密度是2。

2、把A和B联边凝缩，同时也把A1和B1，A2和B2，A3和B3也联边凝缩，得到图2，这时图中出现了交叉边，只能说这时的图不再是平面图了，而是一个非平面图。但这时的图既不是原来的图，也不是原图联边凝缩的最终结果，因为还没有把联边凝缩进行完毕。但图2中的密度确变成了3，因为其中有了K3团。这是由于这一步联边凝缩进行得不正确，所以才使图的图的密度由2变成了3。这就决定了该图着色时至少得用三种颜色才能满足两相邻的顶点不用同一颜色。
从这一点可以看出，因联边凝缩步骤的不正确，一个平面图通过联边凝缩最终得到一个密度大于等于5的非平面完全图都是可能的。
4、再把1和12，2和22，B（A）和B2（A2），11和13，21和23，B1（A1）和B3（A3）进行联边凝缩，得到下图3，这时图中又不存在交叉边了，又变成了一个平面图，但密度还是3，是不可能再变回2去的。

从这一点可以看出，一个密度不大于4的非平面图，通过联边凝缩，可以得到一个与原图同密度的平面图，这是因为密度小于等于4的完全图都是平面图。而密度大于等于5的非平面图联边凝缩时则是不可能得到平面图的，仍只能得到非平面图，这也是因为密度大于等于5的完全图一定都是非平面图。
5、再把1（12）和23（21），2（22）和B3（A3，B1，A1），B（A，B2，A2）和13（11）进行联边凝缩，得到图4，这就是联边凝缩的最终结果，因为它再也不可能进行联边凝缩了。这是一个K3图，它虽不是最小的完全同态，但仍还是一个平面图。

6、这个K3图着色要用三种颜色，那么将其各顶点连同已着的颜色再按与原联边凝缩的相反方向返回到原图时，图中也就有了三种颜色。虽然如此，由于图4不是原图的最小完全同态，其用色也不是最少的。该图的其色数不应是3而应该是2。
现在我再进行联边凝缩如下：
1、首先把A和2，1和B，A1和21，11和B1，A2和22，12和B2，A3和23，13和B3进行联边凝缩，得到图5，图中没有出现交叉边，仍是一个平面图，其密度仍是2；

2、再把A（2）和A2（22），1（B）和12（B2），A1（21）和A3（23），11（B1）和13（B3）进行联边凝缩，得到图6；
3、再把A（2，A2，22）和13（B3，11，B1），A3（23，A1，21）和1（B，12，B2）进行联边凝缩，得到图7，这是一个K2图，是最小的完全同态，是该图联边凝缩的最终结果。
4、这个K2图着色时只要用两种颜色，那么原图着色时两种颜色也一定够用了。


5、关于你上一问题中提到的选择顶点的问题，从这里已看得很清楚了，联边凝缩的原则是从距离最近的两个不相邻顶点开始进行，也就是说要联边凝缩的两顶点间只能相隔一个顶点，只有这样一步步的进行下去，才能得到图的最小完全同态。而你的第一步联边凝缩的两个顶点间却是相隔着两个顶点，这是不符合联边凝缩的原则的。
问题3、“还有一个理论上的问题，联边凝缩前后，图的着色数应不会增加，也不会减少，这个你能给出证明吗？”
回答：每个图在理论上必然存在着一个最小的完全同态。联边凝缩只是图的一种运算方法，通过这种方法可以求出任意图（包括非平面图和平面图）的这个最小完全同态。一个图的最小完全同态有多少个顶点，其着色就得用多少种颜色，当然原图着色时也就一定得用相同的颜色种数。理论上确定一个图的色数就是这样进行的，所以不存在一个图在联边凝缩前后的色数不同的问题。至于是不是给图着色时一定要进行联边凝缩，这就不一定了。通过联边凝缩确定了何意图的最小完全同态的顶点数（或者说是其色数）与其密度的关系后，只要知道某个图的密度（每个图中的最大团的顶点数就是该图的密度值），再根据图中的某些结构，就能确定该图的色数，然后再用Kempe的着色理论着色就行了，不要再进行联边凝缩求其最小的完全同态。如果要进行联边凝缩求其最小完全同态，也不是不可，问题就是所得到的完全同态不一定就是最小的，而且你也不可能知道它是不是最小的。在直接给图着色时，这里要注意的是，一定要控控制好颜色总数，不能超过已确定的色数，在某些顶点难以着色时，一定要使用Kempe创造的颜色交换法，空出已确定的颜色之一给其着上。
因为平面图只是图的一个子集合，用联边凝缩求任意图的最小完全同态，确定任意图的色数与图的密度的关系，这只是在证明平面图四色猜测之前的一步，有了这一步，把平面图的密度不大于4这个特点代入到所得到的任意图顶点着色数与其密度的关系的公式中，就可以得到任何平面图着色时四种颜色就够用了的结论。
问题4（信访处某先生的提问）、“如果将下图中顶点1、2加边收缩，再将3、4加边收缩，得到的图将包含K5。”

回答：这个图是一个平面图，其密度是3，图中有8个顶点，其中有4个顶点位于5—轮的中心，4个顶点位于4—轮的中心。由于该图中含有奇轮，其联边凝缩的最终结果——最小的完全同态一定是一个K4图，顶点等于其密度值加1即等于4（图的密度值＝3，密度为3的平面图的最小的完全同态的顶点数≥3，而≤＜1.5×图的密度值＞，即≤＜1.5×3＞≤＜4.5＞≤4，图中无奇轮时是下线3，有奇轮时则是上线4，这一点我已有证明）。但由于不同的人联边凝缩的路线不同，同一个图不同的人可能就会得到不同的完全同态。该图若按提问者指出的路线，最终结果的确得到的是一个K5图，但这不是该图联边凝缩应得到的最终结果——K4图。这正如一条道路，本来其最小完全同态是K2，但也可以把它联边凝缩成K3，K4，K5，K6等等一样，但它们都不是最小完全同态，不是我们所要得到的结果——K4图。这一个问题，我的回答也同时回答了堵丁柱先生提出的第2个问题。
现在我来对该图进行联边凝缩：
1、我把该图的顶点编号补充完全，如下图8；
2、把顶点1和2联边凝缩得到图9；


3、再把顶点②和4联边凝缩得到图10；
4、再把顶点①和④联边凝缩得到图11；
5、再把顶点③和3联边凝缩得到图12，这是一个K4图，是该图联边凝缩的最终结果；

6、提问者所画图的着色：由于提问者联边凝缩得到的是K5图，所以他只能认为这个图就是一个5—色图，然而该图的确是一个4—色图。如果我给顶点4和②用★代表其颜色，给顶点①和④用▲代表其颜色，给顶点3和③用■代表其颜色，给顶点1和2用●代表其颜色，则图12着色为图13，把图12连同各顶点已着的颜色返回到原图时，提问者所给出的图就已着色完毕，色数仍是4，如图14。

7、不进行联边凝缩，直接用Kemep的方法着色如下：
① 先给顶点①着★色，其轮沿顶点4、③、1、3、2分别着▲、■、▲、■、●色，这时再给以顶点1为轮心的轮的轮沿顶点②着上用该轮轮沿顶点①已用过的颜色★（着色时必须增加颜色时才可增加，否则就很难保证所用颜色数是最少的），如图15；
② 现在只剩下顶点④未着色，可是与顶点④所相邻的顶点已经用完了★、▲、■、●四种颜色，这时就得用Kemep所创造的颜色交换法，在图15中将顶点2和①的●—★色链进行交换，使得与顶点④所相邻的所有顶点只占用★、▲、■三种颜色（如图16），而空出颜色●可以给顶点④着上；

③ 给顶④着上已空出的颜色●即可，该图的4—着色完成，如图17。
④ 也可在图15中对顶点②的★进行★—●色链的交换（注意：一个顶点是一条色链的特殊形式，这条★—●色链上只有一个着★色的顶点），也能空出一种颜色★给顶点④着上，如图18。

  雷  明
二○○七年八月十四日于长安
（注：在1991年底接到堵丁柱先生和应用所信访处的来信后，我记得好象是作了答，但现在却找不到留底，所以二○○七年八月又写了这一回答。特作说明。）
附堵丁柱先生的信：
    在我的第一篇用图论方法证明四色猜测的论文《用图论方法证明四色猜测的正确性》一文及附信发出后，很快就收到了中国科学院应用数学研究所堵丁柱研究员1991年12月14日的回信，信中的内容如下：
“雷明同志：
“你好！
“你的关于四色定理的证明我已收到。每年我都会收到好多这些著名的古典问题的证明，但迄今还没有一篇是正确的。不过他们对数学之热心与专研很令我感动。我也是一个从普通工人经过自学直接上研究生，然后才能今天的，我从内心希望他们能够成功。”
堵先生通过画图和我讨论了几个问题（即以上的几个问题）后继续写道：
   “我仅能提出这三个问题，如果你打算给予答复，请尽早回复，因为我明年2月份要出国讲学。
“祝成功！
                                                      
“ 堵丁柱
                                    “ 91，12，14。”

雷明85639720

图见DOC原件中