[讨论]关于图的顶独立集

雷明85639720

关于图的顶独立集
——回答一棵小草
雷  明
（二○一○年六月九日）
1、6月7日一棵小草留言：
尊敬的雷明网友，感谢您在百忙中评论我的文章。最近几天我都在学习您的四色问题的文章。有些不懂的地方必须及时请教，以便更好地沟通。昨天直到现在，我发不出评论；不得已写一篇下文。你在评论中说：“你终于走上了我所说的图顶点同化的道路上来了。一个图同化的最终结果心是一个完全图K（n），这就是原图的最小完全同态。K（n）中的这n个顶点分别都代表着原图中的若干个互不相邻的顶点，可以说原图的最小顶独立数就是n。由于同一个顶独立集内的顶点均不相邻，所以可以着同一颜色。原图有n个顶独立集，着色时至少就得用n种颜色，其色数也就是n”。您这里“最小顶独立数就是n”与“原图有n个顶独立集”的n是同一个数吗？我正在拜读您的文章【图论法证明四色猜测】（二○一○年三月十六日）1、图的色数、顶独立集、完全同态的关系，在这里我遇到问题：----任何图的色数γ就等于图的【最少顶独立集的个数β】【？】请帮助解读【】内的意思。应有γ＝β＝α的关系。3、单条道路向最大团的同化。对其中“图1的b图中当n为偶数时，就成为图2的d图了”感到原图有误，似乎应为：（图不画了——雷明注）请核实为盼。
2、6月7日我回答：
一棵小草：看了你的博文，现回答如下：一个图有最小顶独立数是n，收这个图也一定有n个顶独立集，不过这个顶独立集个数是所有的顶独立集划分中最少的。这个n就应是该图的色数。你看的三月十六日的《图论法证明四色猜测（摘要）》一文是我为准备八月分到徐州去参加全国第四届组合数学与图论学术会议专写的论文，你提出的问题是不存在的，图1，b是没有错的。雷明，2010，6，7，于长安
3、6月8日一棵小草留言：
已见到您发来的顶独立集的定义。
为了学会您的同化方法和独立集的概念，然后再对话。下面我用图来练习一下；将过程写出来，您看对否？以4轮图为例。
点d与b不相邻，重合后得：
点a与c不相邻，重合后得：
以上是4轮图的
4、6月9日一棵小草留言：
关于“顶独立集”已收到；但还是看不懂；为尽快沟通成功，请看我同您讨论四色问题的文章，及时解读我那里的疑难。从而我好知道您的同化思路。我不先搞清这些问题，无法进一步交流。
5、6月9日我回复：
顶独立集是图论中的一个专业术语，不是我个人的创造。顶独立集就是：把图中不相邻的顶点各划分到一个集合中去，这样每一个集合中的顶点在原图中均是不相邻的，或者说每一个集合中的顶点在该集合中都是独立的（互不相邻——没有关系），这样的集合图论中就叫做顶独立集。一个图可能划分成不同数目的顶独立集，但总有一个划分中的顶独立集数是最少的，这个最少的顶独立集划分中的顶独立集个数，就是该图的最小顶独立集数。这样你就能明白为什么图的色数就等于其最小顶独立集数的原委了。
你6月8日留言中的4—轮，你的同化方法是对的，其最后就是一个由a（c）、b（d）、e三个顶点构成的3—圈，也就是一个K3图，这就是4—轮（偶轮）的最小完全同态，其顶点数是3，所以上述4—轮的色数就是3。这里的顶独立集一共有3个，即顶点a和c（在原图中不相邻）构成一个顶独立集，顶点b和d构成一个顶独立集，顶点e一个就是一个顶独立集，共3个顶独立集。现在看到了什么呢，就是色数、最小顶独立集数和最小完全同态的顶点数三者是相等的。同时还可以看出，求顶独立集的过程也就是顶点同化的过程，那么最小完全同态得到了，则最小顶独立集数也就得到了，因为最小完全同态的每一个顶点都是由若干个不相邻的顶点同化所得到的，或者说它们就分别代表着这若干个不相邻的顶点，这些顶点所构成的这个集合，就是一个顶独立集，那么，最小完全同态有几个顶点，原图不就是同样有几个顶独立集吗。完全图的色数与其顶点数是相同，给其每一个顶点着上一种颜色，然后把这个完全图按同化时的相反方向连同各顶点已着上的颜色再展开成原图，同化前的原图不就着色完成了吗。这时的色数一定是最少的，不可能再少了。当然了，这在理论上一定是这样，但一个复杂一点的图，能不能用同化的方法得到最小完全同态，不是每一个人都能做到的。这正象1＋1＝2这样的算术题，有的孩子会做对，而有的孩子却做不对一样，是一样的道理。所以说真正的证明，不是对一个个的图去进行着色，也不是对一个个的图去进行同化。只要明白了以上这个道理，即知道图的色数、最小顶独立集数、最小完全同态的顶点数三者是相等的，就可以不对任何图进行同化，也不对任何图去进行着色，就要能从理论上证明四色猜测是正确的，这才是真正的证明。以前的着色法证明都只能说是对猜测的验证，它始终没有把所有的图验证完，所以也就得不出猜测是正确还是错误的结论，猜测始终还是猜测。雷明，2010，6，9，于长安。

雷明85639720

6月10日一棵小草看了我的回复后留言：您的解读与帮助令我十分满意。说老实话，关于最少顶独立集我没有用过，也就是不懂；我又不能装懂，只好利用这个机会向您学习。我在书上看到独立集，说的是任意两点均不相邻.......一点实践也没有。这次交流与沟通，是我向您学习的极好机会，浪费您的时间了，多谢！祝贺您外出开会交流成功，硕果累累！