给leisurely朋友几个图的着色

雷明85639720

给leisurely朋友几个图的着色
雷  明
（二○一六年十二月二十三日）

1、我在前几天发出了《四色猜测的最简单证明》一文，在与leisurely讨论的时候，他发来了如下几个彩图。图前并有短贴如下：
暂时方便传图，我以前大部分时间都在找无法破坏的图，下面的图有两个D点挨着的你就看成一个点。
这个图里有两个相交环AD 和BD，通过简单变换是无法同时都破坏掉的。
当然我用发现的规律破坏掉了。你的构型也完全可不用这么染色，只想说，如果要是环里做变换，必然有奇怪的事，所有一切必须证明。
这个简单图我可以有上百种不同染色，因为被证明了。纯逻辑的。




2、这几个图中，最外面都有一个大园环，且只经过了一个顶点C1（注意，图中的数字是我为了研究方便，给几个主要的顶点所编的序号，即顶点名称），在四色问题的研究中是没有这种环边的，它的存在与不存在，对我们的研究没有什么影响。
另外，这几个图中都有两个相邻的顶点是着了同一颜色D的，我把我标有V的那个D色顶点看成是一个待着色顶点，这样处理的结果，就相当于如何能给这几个5—轮构形中的待着色顶点V着上图中已用过的四种颜色之一的着色问题了。
从图中可以看出，以V为中心顶点的，并以1C，2D，3C，4B和5A为轮沿顶点的5—轮中，缺少了顶点1C到顶点5A的边，是一个不完全的轮。不过我们可以把它看成有这第一条边就可以了，并不会影响对该图的着色。
3、以上这几个图，就各图对于以V为中心的5—轮而言，其外都有连通的D—A链和D—B链，两链有共同的起始顶点2D和交叉顶点8D，也都有3C和6A，4B和6A的直接相邻，但没有从1C到7B的C—B链，也没有从5A到7B的A—B链，也没有从1C到8D的C—D链，该图是一个可以同时移去两个同色B的构形。这几个图实际上是同一个图，其所着的颜色是大同小异的。我们只要对其中一个图进行着色，其他三个图的着色方法都是与之相同的。

①　对原图（如图2，a）先从3C交换C—A链（如图2，b），再从1C交换C—B，空出B给V着上（如图2，c）；或者先从3C交换C—A链后，再从4B交换B—C，也可空出B给V着上（如图2，d）。
②　对原图（如图3，a）先从1C交换C—B链（如图3，b），再从3C交换C—A，空出C给V着上（如图3，c）；或者先从1C交换C—B链后，再从5A交换A—C，也可空出A给V着上（如图3，d）。

除了已进行交换了的顶点的颜色外，其他未进行交换的顶点的颜色按原样着上，就可以完成该 图的4—着色。这几个图的确是一个很好着色的图，因为其中没有C—D链与A—B链与D—A链和D—B链相穿插叉的情况。
雷  明
二○一六年十二月二十三日于长安

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

leisurely

我没说明白，就是你说的C1 ，我在外面画了一个圆，是指这个点和外面那个圆所有的包围的裸露的点A,B都有联线的，就是除了A5,v外还和上面一个A,一个B直接有连线，就是共同边界。所以这个C1 是无法简单换成A或B或D的。
C1直接有和A5联。
C1通过最外面的B和里面的7B联成CB链。
C1通过D2 和D8形成一个CD链相连。

我把字母写在数字前了，相信不影响理解。

你举例让我知道了构型是怎么用的，就是说你的构型是指要着色的点和已有着色的点的关系图吗？然后只要能把这个要着色点着色就行了。那构型中的什么K型请举个例。然后怎么证明所有你说的H型包括了所有可能？

leisurely

你的3C和6 A交换，注意，6A除了3 C外，还和其它C相连，所以会引起连锁反应，但我构造的这个图它们被一个大的BD链环包围，这个传导不会跑到BD环外，可是你没有解释。
而1C是根本无法简单换掉的。

雷明85639720

leisurely朋友：
1、你的图没有说清，是你的错误。但我按你画的图及我的分析，已经对这个图着上了不超过四种的颜色。你若不相信，你按我的着法（即我交换的方法），去做一下，你看是不是对的；
2、你光这样说不行，你要具体的把你所想画图的意图用图表现出来，别人才能更好的理解，也才能有目的的对症下药，解决你的问题；
3、你图中明明C1和A5没有相邻，你怎么硬要说是相连的呢。如果是这样，那么如何能做到你现在说的 “ v外还和上面一个A,一个B直接有连线  ”  呢，这不就成了非平面图了吗，这超出了四色问题是在平面图范围之内研究的限制；
4、“  所以这个C1 是无法简单换成A或B或D的。”  这句话说的是C1呢，还是说的V 呢？不管你说的是那一个，既无法换成四种颜色之一，那么，你说说四色猜测是正确呢还是错误呢。是该下结论的时候了呀；
5、“  C1通过最外面的B和里面的7B联成CB链。”  这一条件对着色是没有用的，因为C1所连的C—B链，并没有连结到以V为中心顶点的5—轮的另一个轮沿顶点上，这只能说明了完全是可以从C1开始交换C—B的，把C1变成B；
6、“  C1通过D2 和D8形成一个CD链相连。”  图中根本就看不到这一点，请你再画一下图，光用嘴说是没有用的。即就是有一条C—D链，不形成环形链，也是没有作用的；
7、看来你并没有认真的看我的文章，你连构形是什么也不明白，还能证明四色猜测吗。不管怎么样，总算你现在有了一点理解，这也是收获。因此，我对我昨天对你的图的着色所写的的文章能起到一点作用感到高兴；
8、K—构形就是在1879年坎泊已经证明过的是可约的所有构形，K是坎泊名字的第一个字母。1890年，赫渥特构造成了一个图——赫渥特图，很有特色，不但赫渥特不能对其中的待着色顶点V着上图中已用过的四种颜色之一，就连坎泊也不能对其进行4—着色。象赫渥特图这样的一类构形，就叫H—构形，同样的，H也是赫渥特名字的第一个字母。你这个图是一个K—构形，是一个可约构形，它离H—构形还差得远呢；
9、“  你的3C和6 A交换，注意，6A除了3 C外，还和其它C相连，所以会引起连锁反应  ”，当然是会引起连锁反应的，那你就一直交换下去就行了，直到该C—B链交换完为止，不会对着色有什么别的影响的，客观存在是不会穿过A—D链的；
10、“我构造的这个图它们被一个大的BD链环包围，这个传导不会跑到BD环外，可是你没有解释。”  我可看不到你的大C—D环在什么地方。你说我没有解释，这话说得太差劲了。你的图你不说清楚，为什么要我解释呢。应该是你向我解释明白，而不是我向你解释。启有此理；
11、“  而1C是根本无法简单换掉的。”  我不是在我的着色中，很简单的把1C换掉了吗。请你把你这个图的着色模式拿出来吧。你明明是对它不能4—着色，还要说你对其进行了上百个着色模式，请拿出来看看嘛；
雷明

leisurely

C1 在最外边吧？那么现在你可以把C1顺时针依次连接A,B,A5。
然后看看能不能做个构型图！！！！
确实是我没说明白，但我的证明里是都连着的。
而且我是从任意内部分割点，所以C1实际上是整个包围里面所有点的。这个极小图是为了举例。实际上更复杂的还有。所以碰巧C1可以不完全包围V点。

我只看你说的最简单证明，那个证明里没解释的我肯定不懂。因为我不相信已有的方法能解决问题，如果要按前人的方法，你证明是给大家看，也许好多人确实不知道前人怎么做，最好把前人的逻辑说明完整。

leisurely

我的证明里是把所有颜色链都破坏掉的。
我能染色很简单，都不用我发图，你把颜色去掉，重新随便染，就发现根本染色就遇不到这种情况。
问题是我发几种染色有什么意义。我证明是整个破坏掉它的链，在另一个染色的这幅地图上做的。

雷明85639720

eisurely朋友：
关于构形，我还想再给你讲一点有关的知识：
1、所谓构形，就是指图中只有一个顶点未着色，以这个顶点为轮中心的轮的轮沿顶点已占用完了四种颜色。轮以外的其它顶点（可能是无数个）也都用了四种颜色着色之一，但相邻顶点也都没有使用同一颜色的，完全符合着色的要求。具有这样特点的l的图，就叫构形。
2、构形是有无限多的，但平面图中的确有着不可避免的构形，这就是任何一个平面图中总存在着至少一个度（顶点所连的边数叫度）小于等于5的顶点，这是可以证明的，你看看图论书就知道了。正是因为这样，所以平面图才有不可免的构形集合，这个集合就是：{0—轮，1—轮，2—轮，3—轮，4—轮，5—轮}，这样的轮在任何平面图中总是可以找到的；
3、由于有了以上2，所以我们在着色时，总可以把度小于等于5的顶点放在最后，作为待着色的顶点。因此，只要证明了这样的6种不可免构形都是可约时，那么平面图的四色猜测就是正确的，这就是利用构形证明四色猜测的原理；
4、坎泊已证明是可约的那部分构形叫K—构形，他还没有证明是可约的构形就叫H—构形，即赫渥特图型构形；
5、现在为了解决四色问题，主要就是要证明各种情况下的H—构形都是可约的，也就能说明四色猜是正确的了，否则，猜测就是不正确的。二者必居其一。
雷明

leisurely

我说的是BD环，红色的阻止AC兑换蔓延，如果全图AC兑换，那和没换是一样的。没意义。
至于说C1到D8的CD链，沿着绿线找

leisurely

我有空再看构型这种方式是否可行吧。你先把C1 和外围点都连上的构型发上来让我看看构型怎么解决问题吧。
我发两个这图的其它解决办法。可以看出原来的链环全破坏掉了。这图能上几百种不同染色是我证明的，没必要用这个图。如果你发个小图，10几个点的我倒可以染十几种色让你看

leisurely

我有空再看构型这种方式是否可行吧。你先把C1 和外围点都连上的构型发上来让我看看构型怎么解决问题吧。
我发两个这图的其它解决办法。可以看出原来的链环全破坏掉了。这图能上几百种不同染色是我证明的，没必要用这个图。如果你发个小图，10几个点的我倒可以染十几种色让你看