重发给张晓宇朋友几个图的着色

雷明85639720

重发给张晓宇朋友几个图的着色
雷  明
（二○一七年元月七日）

leisurely（张晓宇）朋友给出的几个图都是同一个图，只是着色的主要部分都完全相同，其他非主要部分着色虽有所不同，但都不影响对该图的着色，张晓宇虽给出了四个图，我这里只给其中之一着色就表代了。他的基础图4如下图1所示。



这个图中有两个D色顶点，我把其中一个看成是待着色顶点V，使图变成了一个5—轮构形。图中还多了一条经过一个顶点C的环边，按张晓宇朋友说的，这个环代表顶点C与环内最外层各顶点都是相邻的，所以我就把这个顶点C与其应该、也可以相邻的顶点都用边连接了，并去掉了环，使图变成了一个极大图。我把图中很关键的几个顶点又用字母和数字增加了顶点名称，如图2。



图2是一个以顶点V为待着色顶点的5—轮构形，其中顶点2D与顶点6A和顶点7B都是直接相邻的，顶点6A和7B也是直接相邻的。从顶点2D到顶点4B有一条连通的红色D—B链，从顶点2D到顶点5A有一条连通的兰色D—A链，D—B链和D—A链相交叉于顶点8D（两链的共同起始顶点是2D），从顶点1C交换了C—B链后，不会产生由顶点3到顶点5的连通链C—A，不具有赫渥特图的特征，是一个可以先从顶点1交换C—B，再从顶点3交换C—B，能同时移去两个同色C的坎泊构形（K—构形）。从顶点1交换了C—B后得图3，再从顶点3交换了C—A后得图4，从V的相邻顶点中空出了C给V着上。若对图3从顶点5开始交换A—C，则可以空出A给待着色顶点V着上，如图5。该图的着色并不难，是坎泊早已证明了的可约构形。







张晓宇朋友，也请你拿出你的着色方法来吧。

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

注：此文已于二○一七年元月七日在《数学中国论坛》上发表过，网址是：

leisurely

你的B1 连着上面的B呢。有空我发我的过程。
但你的过程这么清楚怎么会失误，下次仔细点

leisurely

你要上自己博客，错了的图和解释最好都删掉留下最后正确的

雷明85639720

我已经改过了，谢谢你。请看。

leisurely

好的，等我的

leisurely

先上图，确认图上来再解释。最后一个是结果，前面是步骤

leisurely

先上图，确认图上来再解释。最后一个是结果，前面是步骤

leisurely

原图有两个D点需要换掉一个，它们都和两个C相连。只要找到这两个C之间有AC或BC链就行，没有必然是存在一个AD链环和一个BD链环过这两个D点。这个图是唯一一种链环无法简单破坏的情况。

所以图一，直接把AD链环的任意一个点改成B或C点，这样形成BC链和两个D点构成环，在这个环分割的一个区域做AD变换，形成图一，红色点是原图AD变换过的，蓝线是BC环。

图二，由于前面暴力改点形成两个C点相连的情况，这是证明里正常的分割状态。红线部分，它们分别都和BA相连，只要找到两点的AB链就行，没有说明存在一个CD链环把它们分成两个区域，在其中一个区域做AB变换，形成图二，绿线是CD链环，红点是AB变换后的情况

图三，两个C点都和B点相连，找到一个BD链和两个C形成一个环。在这个环分割的一个区域做AC变换形成图三。红点是唯一的变换点C变成A，蓝线是BD链。

我的证明很简单，在球面上的四色地图上的任意一点，分割成两点后，可以变换后还是四色地图。任意相邻两点合并后也可以是四色地图。

整个证明就是讨论要分割点周围形成环的情况和链的情况。六个引理，纯逻辑。所以不存在不可证伪也无法证明的任何情况。
而且证明了地图染色方法数量惊人。上面这个图至少有2的20次方种染色方法。而且可以互相变换。

意味着如果应用四色地图变换，可以在加密方面，可以在社科建模方面，等等……
更重要的是其实可说明P和NP是两码事……

zengyong

你们好!
我怎么发现图6还是有问题的呢?
现把图6再贴上(并标注两个邻接的顶点都是A-A)

雷明85639720

还是太粗心，没有交换完。谢谢，我马上改过来。