给极大平面图着色时是必然会遇到颜色冲突问题的

雷明85639720

给极大平面图着色时是必然会遇到颜色冲突问题的
雷  明
（二○二○年九月二十三日）

四色问题是因给地图的染色而提出的。地图本身是一个3—正则的平面图（每个顶点都连有三条边），它的对偶图是一个极大的平面图（每个面均是三角形，即均有3条边），所以给地图的面的染色就相当于对其对偶图——极大图平面图——的顶点的着色。
对极大平面图着色时，总是一个顶点，一个顶点的着，也总会遇到最后一个要着色的顶点，这个顶点一定是处在一个轮的中心，且与其相邻的轮沿顶点也都已着了颜色。有两种情况：
1、一种情况是轮沿顶点所占用的颜色数小于四种，这种情况下，没有问题，这最后一个顶点一定是可以着上图中已用过的四种颜色之一的。
2、第二种情况是轮沿顶点所占用的颜色数已经达到了四种，这就叫颜色冲突问题。但这种情况下的这最后一个顶点还能不能着上图中已用过的四种颜色之一呢？回答是肯定的，能。否则四色猜测就是不正确的了。
解决这种问题的办法有很多，也决不只是一种。常用的一种是坎泊链法。找出各种情况下的颜色冲突情况，研究针对各种颜色冲突情况下的解决办法。并证明在除了这些情况的颜色冲突之外，再也没有别的颜色冲突情况了。这就是四色猜测证明时的不可避免构形集方法。当所有的不可免构形（即颜色冲突问题）都能可约（解决）了，四色猜测也就证明是正确的了。
还有一种是避免发生颜色冲突的方法，即当使用坎泊链法解决颜色冲突只涉及到与最后的待着色顶点相邻的前一个已着色的顶点时，可以对这前一个顶点先不着色，而先对应该是最后一个着色的顶点着色，这样就可以避免出现颜色冲突的问题。但这只能是在这一种情况下才可以使用，如果在使用坎泊链法解决颜色冲突时，涉及交换的顶点多了时，就不可能再返回多个顶点重新着色了，也就只能用坎泊链法解决问题。实际上这种办法还是没有避免发生颜色冲突问题的，而是已经看到了将要发生颜色冲突时，提前一步进行了解决罢了。
这种研究解决颜色冲突问题的办法，既是证明四色猜测的方法又是对极大平面图4—着色的方法。但也可以从不同的角度入手，单从理论上对四色猜测的证明，但在对具体图着色时还是会遇到颜色冲突问题的，还得要再研究解决颜色冲突的办法。
如果有一个已知的奇轮，我们知道一定得用四种颜色。但这个轮并不是极大图，要使其成为极大图还得增加一个顶点，并与所有轮沿顶点相邻，这就是一个菱形体。这增加的一个顶点与原来轮的中心顶点并不相邻，着同一颜色是可以的，图中还是只用了四种颜色。若在这个图的任何一个面内增加一个顶点，该顶点只可能与三个顶点相邻，一定是还有一种颜色可着的，图中还是四种颜色。还有一种情况是若在这个图的任何一条边上增加一个顶点，把一条边分成了两条，该项顶点就已与两个顶点相邻了；要保证图仍是极大图时，这个顶点还可与另外的两个顶点有边相邻。这时，这个顶点已是处在一个4—轮的中心顶点了。若该4—轮的轮沿顶点所占用的颜色数小于4时，该顶点一定还有一种颜色可着；若该4—轮的轮沿顶点所占用的颜色数等于4时，就得用坎泊链法进行解决，也一定能够解决。以后再继续的在图中增加顶点，可以得到任意的极大平面图，但图中所用的颜色数却总是四，不会增加。这也就证明了四色猜测是正确的。但这里也是遇到了颜色冲突问题的，所以说颜色冲突是不可避免的。

雷  明
二○二○年九月二十三日于长安

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

朱明君

照《地图四色着色指南》着法不会遇到颜色冲突问题，

雷明85639720

1、如果遇到了，你怎么办呢？
2、是从来一次，还是想办法解决颜色冲突的问题呢？
3、解决了，以后若再遇到同样类型的颜色冲突问题，就可以用同样的方法去解决；难道你遇到一次颜色冲突问题，就从来一次吗？
4、所有的颜色冲突问题都能解决了，四色问题也就解决了！
5、可以让明，颜色冲突问题的种类是有限的。

雷明85639720

．．．．．．．．

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，