[讨论]我与朋友一棵小草关于同化与收缩的讨论

雷明85639720

我与朋友一棵小草
关于同化与收缩的讨论
雷  明
（二○一二年六月十八日）
我6 年月15 日对一棵小草《关于图的运算》一文的评论：
你这里的的最后一句话，不知是你自已的话还是别人的话：“对任何的偶数阶轮图Wn（n>、=4），有X(Wn)=4”，恐怕说得不对，因为他说的是“偶数阶轮图”，这是一个单轮图，而不是某个图中的分子图。若是一个单轮图时，偶轮只用3 种颜色就够用了，不需要四种颜色；奇轮才需要四种颜色的。如果该轮是在一个图中做分子图，图中除此又不含有奇轮，最多只有偶轮，这个图也只用三种颜色就够了；若图中还含有奇轮，则该图一定需要四种颜色。你可以画一画。
6月16 日一棵小草回复说：
雷明：这不是我自己的话，是【1】的原话。在这本书中把中心顶点也计入轮图的阶数n,我注意到了这一点。因此，这里说的正好与我们以往了解的相反；没关系。像我们以往认识的书也有。这就是现在的图论书不统一造成的，具体用时说清楚就是了。
再有，我们一起谈到的“收缩”概念，或运算，图论书中已有。
6月16 日我又回复：
朋友，我刚发出评论后，就发现“偶数阶轮图”就是我们平时所说的奇轮，所以又给你发了一个留言要你把它删掉，你说“删不删都无所谓”，那么我就再说两句，做一个说明，以使我俩的讨论原封不动的保留下来。雷明
6月16日一棵小草回复我：
曾记否，以前我向您请教过。它涉及到Hadwiger猜想是否被证明了的问题。我查了一下，我写过“谈谈我对Hadwiger猜想的初步认识”。我的判断是已被解决。您曾留心过这个问题吗？它也涉及四色问题的研究。
6 月18日我回复说：
一棵小草，看了你6 月16日的回复，我专门翻看了一下你的《谈谈我对Hadwiger猜想的初步认识》，却无意中发现了你的《同网友雷明讨论四色问题》一文，但已经忘记了以前是否看过，却好象对里面有些问题还又有印象，更不知给你回复过没有。为了对朋友负责，我再一次的对有些问题进行回复如下：
1、您这里“最小顶独立数就是n”与“原图有n个顶独立集”的n是同一个数吗？
是我掉了一个“集”字，就使“最小顶独立集数”成了“最小顶独立数”，你看得很细。两处的“n”是同一个数。图论书中只有“顶独立数”的概念，它的意思是指在一个图尽可能划分的所有顶独立集中，顶点数最多的那一个顶独立集中的顶点数。而我这里的“最小顶独立集数”是我自已定义的，图论书中是没有的，它的意思是指一个图可能划分出的顶独立集中，独立集个数最少的那个顶独立集划分中的独立集个数，这里主要突出的是顶独立集的个数，是“数”字，且是“最小”的。
2、对其中“图1的b图中当n为偶数时，就成为图2的d图了”感到原图图2的d有误。
我再一次的查了我那篇文章，没有错，应该是对的。
3、以上是4轮图的同化过程，您能帮我写出哪些点是顶独立集，最小顶独立集，及最小顶独立集数β是几吗；让我仔细体会一下有关顶独立集的概念。谢谢！
好象以前回复过。你对4—轮的同化过程是对的。你对三个独立集的回答也是对的。但要注意的是，顶独立集划分说的是相邻的顶点不能划分在同一个独立集内，但没有说不相邻的顶点必须划分在同一个独立集内，这就如同着色一样，相邻的顶点必须用不同的颜色，但不相邻的顶点不一定就必须要用同一颜色一样的道理。
4、“色数大于4，……图已不再是平面图”，这个命题的成立，根据是什么？是一般人能接受的吗？
    朋友，也可能是你理解错了，或者也可能是我没有说明白。从“色数大于4，……图已不再是平面图”看，这当然不一定能成立，但色数大于4的图，的却都是非平面图。但这并不是说色数不大于4 的图都一定是平面图，比如K3,3图的色数是2，不大于4，但它却是一个典型的非平面图。这一理解只是我现在的理解，以前我还没有认识到这样的程度。你上面所引的我的话，我是从我所画的那几个在最大团K4以外各有一条饱和道路的图看，他们都是非平面图，他们中的两个那条饱和道路是可同化的，其色数是4 ，还有两个的那条饱和道路是不可同化的，其色数是5。所以我就说了一句当密度为ω＝4的图的“色数大于4 时，图已不再是平面图了”。从目前我们证明了猜测是正确的以后看，那么这句话“色数大于4，……图已不再是平面图”的确是正确的，的确也没有那个平面图的色数是大于4 的。当然了，这句话是不能作为“平面图的四色猜测是正确的”理由，只能是在进行证明了猜测是正确的之后，才可得出的结论。
5、关于“色数n与K(n)的等价性”的问题，我认为K(n)是一个完全图，各顶点均是相邻的，着色时一定要用n种颜色，一种也不可缺少，那么完全图K(n)的色数就一定是n。任何图同化的最终结果一定是一个完全图，该完全图的色数一定是该完全图的顶点个数。既然平面图同化的结果都是顶点数小于等4的完全图，那么平面图的色数也就一定是小于等于4的。既然K(5)是典型的非平面图，而且从库拉图斯基定理中知，图中包含有K(5)作其分子图的图也都是非平面图，这些图同化的结果一定是n大于等于5的完全图K(n)，那么，这些图的色数一定是大于等于5 的，所以就应有“色数大于4的图不是平面图”的结论。请你看看这里面有没有循环论证的迹象。
雷明，二○一二年六月十七日于长安
6 月18日我补充回复说：
朋友，关于是用同化还是用收缩的问题，我好象以前给你谈过我的观点，现在再说一下。我认为用同化好一些，这并不是我发明的名词，而是《图论的例和反例》一书中已经用过的名词。收缩我总认为是在沿着某个东西（边）在收缩，它与我们这里所讲的不相邻顶点间的同化从字意上讲还是有所区别的。所以我还认为用同化好。
6月18日一棵小草回复：
雷明：看到了“最小顶独立集数”是您自已定义的。对您又一次的回复，实在该谢谢。
                                 雷  明
二○一二年六月十八日整理于长安
附：一棵小草的文章《同网友雷明讨论四色问题》
同网友雷明讨论四色问题
尊敬的雷明网友，感谢您在百忙中评论我的文章。
最近几天我都在学习您的四色问题的文章。有些不懂的地方必须及时请教，以便更好地沟通。昨天直到现在，我发不出评论；不得已写一篇下文。
你在评论中说：“你终于走上了我所说的图顶点同化的道路上来了。一个图同化的最终结果必是一个完全图K（n），这就是原图的最小完全同态。K（n）中的这n个顶点分别都代表着原图中的若干个互不相邻的顶点，可以说原图的最小顶独立集数就是n。由于同一个顶独立集内的顶点均不相邻，所以可以着同一颜色。原图有n个顶独立集，着色时至少就得用n种颜色，其色数也就是n”。您这里“最小顶独立数就是n”与“原图有n个顶独立集”的n是同一个数吗？
我正在拜读您的文章【图论法证明四色猜测】（二○一○年三月十六日）
1、图的色数、顶独立集、完全同态的关系在这里我遇到问题：----任何图的色数γ就等于图的【最少顶独立集的个数β】【？】请帮助解读【】内的意思。应有γ＝β＝α的关系。
3、单条道路向最大团的同化。对其中“图1的b图中当n为偶数时，就成为图2的d图了”感到原图图2的d有误，似乎应为：
一、接受同化思想
先选定一个最大团，然后把该团外顶点都向最大团中进行同化。同化的过程就是把不相邻的顶点放到一起。任何图中最大团的顶点数ω就是图的密度。同化的最终结果是最小完全同态；最小完全同态的顶点数用α表示。
雷明网友的同化结果与本人的同色变换操作结果虽然是一样的，但他的方法更先进，其功能更多；这是后者所不及的。
我正在消化同化思想与有关概念，已见到您发来的顶独立集的定义。
为了学会您的同化方法和独立集的概念，以便对话。下面我用图来练习一下；将过程写出来，您看对否？以4轮图为例。
以上是4轮图的同化过程，您能帮我写出哪些点是顶独立集，最小顶独立集，及最小顶独立集数β是几吗；让我仔细体会一下有关顶独立集的概念。谢谢！
近日收到您的留言，图的顶独立集是：把图中不相邻的顶点放在一起，所构成的顶点集合，这个集合中的顶点在原图中都是不相邻的。一个图若把一个顶点划为一个集时，原图就有与其顶点数相同数目的顶独立集，但一个图总有一个最少数目的顶独立集，这个最少数目的顶独立集的个数就是该图的最小顶独立集数β。由于各个顶独立集内的顶点在原图中都是不相邻的，所以同一个顶独立集内的顶点着同一种颜色是没有问题的。这样，一个图的最小顶独立集数是多少，该图的色数也就应该是多少。雷明，2010，6，5，于长安。
说老实话，关于最少顶独立集我没有用过，也就是不懂；我又不能装懂，只好利用这个机会向您学习。我在书上看到，说的是任意两点均不邻.......。这次交流与沟通，是我学习的极好机会，浪费您的时间了，多谢！
我的同色变换操作很粗糙，不需最大团，更不与其密度发生关系，根本得不到色数的界。您确实有无师自通的能力，采用创新理念；最后得到任意图色数γ的界是
ω ≤ γ ≤ < 1.5ω >
从无界到有界，这需要做很多工作；也是十分艰辛的过程。应该向您表示祝贺，这确实是一个突破，过去我没有看得那么详细。对照您的同化结果，再展开回去，恰恰把原图4着色。而我的方法很粗糙，它是从简单朴素的拓扑变换（把点的连线看成长短可变化的橡皮筋）思想出发，将不相邻的顶点搬到一起就是了。当添线后再还原就出了问题，着色数比实际多了，也就是不可逆了。所以我要吸取您的长处，不必添线，直接按步骤操作即可。
你说，我对4—轮图同化方法是对的（即图3）。于是，我猜出了您的同态过程。其最后就是一个由a（c）、b（d）、e三个顶点构成的3—圈，也就是一个K3图，这就是4—轮（偶轮）的最小完全同态，其顶点数是3，所以上述4—轮的色数就是3。这里的顶独立集一共有3个，即顶点a和c（在原图中不相邻）构成一个顶独立集，顶点b和d构成一个顶独立集，顶点e一个就是一个顶独立集，共3个顶独立集。
现在看到了什么呢，就是色数、最小顶独立集数和最小完全同态的顶点数三者是相等的。同时还可以看出，求顶独立集的过程也就是顶点同化的过程，那么最小完全同态得到了，则最小顶独立集数也就得到了，因为最小完全同态的每一个顶点都是由若干个不相邻的顶点同化所得到的，或者说它们就分别代表着这若干个不相邻的顶点，这些顶点所构成的这个集合，就是一个顶独立集，那么，最小完全同态有几个顶点，原图不就是同样有几个顶独立集吗。
完全图的色数与其顶点数是相同，给其每一个顶点着上一种颜色，然后把这个完全图按同化时的相反方向连同各顶点已着上的颜色再展开成原图，同化前的原图不就着色完成了吗。这时的色数一定是最少的，不可能再少了。当然了，这在理论上一定是这样，但一个复杂一点的图，能不能用同化的方法得到最小完全同态，不是每一个人都能做到的。这正象1＋1＝2这样的算术题，有的孩子会做对，而有的孩子却做不对一样，是一样的道理。所以说真正的证明，不是对一个个的图去进行着色，也不是对一个个的图去进行同化。只要明白了以上这个道理，即知道图的色数、最小顶独立集数、最小完全同态的顶点数三者是相等的，就可以不对任何图进行同化，也不对任何图去进行着色，就要能从理论上证明四色猜测是正确的，这才是真正的证明。以前的着色法证明都只能说是对猜测的验证，它始终没有把所有的图验证完，所以也就得不出猜测是正确还是错误的结论，猜测始终还是猜测。（雷明，2010，6，9，于长安。）
二、我的一己之见
我学习了您的关于“顶独立集”的论述，把图中不相邻的顶点放在一起，所构成的顶点集合，这个集合中的顶点在原图中都是不相邻的。一个图若把一个顶点划为一个集时，原图就有与其顶点数相同数目的顶独立集，但一个图总有一个最少数目的顶独立集，这个最少数目的顶独立集的个数就是该图的最小顶独立集数β。由于各个顶独立集内的顶点在原图中都是不相邻的，所以同一个顶独立集内的顶点着同一种颜色是没有问题的。这样，一个图的最小顶独立集数是多少，该图的色数也就应该是多少。雷明，2010，6，5，于长安。
您是从最少数目的顶独立集的个数的视角来说明原图至少着n种颜色的道理，用同化结果只是为了找独立集的个数；您与我的出发点不同，我则关注同化结果的功能。其实还是您做得好，理论根据充分，更有说服力。要求您挖掘出同化结果完全图K(n)的功能，那是我的一己之见，后面还要谈到这个问题。
三、关于证明
好在您的证明文字不长【6、四色猜测的证明】
已知平面图的密度是不大于4的，这就有可能使我们把仅有的四种密度值代入到任意图着色色数的界中，结果得到任何平面图的色数都是小于等于4的。初看起来在ω＝4时，其色数有可能大于4，但在这种情况下的图已不再是平面图了（如图3，a图的色数是5，b图的色数是4，但两图都不是平面图，因为图中出现了交叉边。）。由此可以得出任何平面图着色时，其色数一定不会大于4，即γ平≤4。这就证明了平面图的四色猜测是正确的。
您对“其色数有可能大于4”只指出“图已不再是平面图”便置之不理！这在一般情况下是完全可以的（因为我们研究的是平面图，非平面图不是我们研究的范围）；但这里却并不一般！暂且放下。请问，引号内文字是否是：“平面图的四色猜测是正确的”理由之一。若承认是，您就不能轻描谈写。
“色数大于4，……图已不再是平面图”这个命题的成立，根据是什么？是一般人能接受的吗？
现在接着说同化结果的功能。显然，前面提到的根据就在同化结果的功能里；你要估计到，不研究这个问题的人是不懂这个结果的。就算人家知道，您不论述，他故做不知；尤其是专家！所以我说，您要深挖同化结果的功能，对咱是有利的。不要小看了这个结果——它还揭示了图的色数n与K(n)的等价性。还有......,只要把前者宣传好了，问题的解决就有了着落。因为“色数n与K(n)的等价性”，再借助定理“K(5)是非平面图”，才有。站在巨人的肩膀上，更容易达到目的！
由“K（5）不是平面图”到“色数>4不是平面图”这一小步，它的道理是需要论证一番的。
四、证明的注意事项
像四色问题这类的大难题，最忌讳循环论证；请看本人博客。