[讨论]图论中的“收缩”与“同化”是两个不同的概念和“运算”.

雷明85639720

图论中“收缩”与“同化”
是两个不同的概念和“运算”
——与网友“一棵小草”交换意见
雷  明
（二○一一年八月二十七日）
1、在一般的图论书和数学辞典或数学手册中都提到了图的一种运算——收缩，都解释为：把两个相邻顶点a和b间的边e无限的收缩（即缩短），使边e的所谓“长度”变成0，实际上就是使顶点a与b重合在一起，并且用新的名称w来替代该两顶点的名称a和b，把这样一个过程就叫“收缩”，这也是图的一种“运算”。可以看出“收缩”不是随便进行的，而是必须“沿着”某一“路径”进行的，这一“路径”就是顶点a和b间的连线——边。每进行一次“收缩”，图中至少就要减少一个顶点和一条边（因收缩后a和b相重合，也可能使得从另一顶点c出发、分别与a和b相邻的另外两条边发生重合，使图中也相应多减少一条或多条边的情况）；无限的把“收缩”进行下去时，任何一个连通的单图（只有一个分支的无环且无平行边的图）都将变成一个孤立的顶点，即K1图，也叫平凡图。
2、在聂祖安翻译过来的由美国人著的《图论的例和反例》中还有另一种运算——同化，其解释是：把两个不相邻的顶点a和b重合在一起，用新的名称w来替代该两顶点的名称a和b，把这样一个过称就叫“同化”，这也是图的一种“运算”。可以看出，“同化”过程是比较随便一点的，只要是“不相邻”的顶点都是可以进行“同化”的。每进行一次“同化”，图中也至少就要减少一个顶点（也因为同化后a和b相重合，同样也可能使得从另一顶c点出发、分别与a和b相邻的另外两条边发生重合，使图中也相应多减少一条或多条边的情况）；每“同化”一次所得到的图就叫原图的一个“同态相”；无限的把同“同化”行下去时，任何一个连通的单图（只有一个分支的无环且无平行边的图）的“同态相”都将成为一个完全图Kn（n≥1，n是完全图的顶点数），这就是图的“完全同态相”，简称“完全同态”。“同化”一词也只有在《图论的例和反例》一书中才可以看到，别的有关图论的书和文献中是没有的。
3、鉴于以上两点，我认为你在文章中用的“收缩”一词，与你所说明的问题是不一致的，你实际上是在进行着“同化”运算，而你却用了“收缩”一词。这是概念上的错误，容易使别人对你的理论进行曲解。
4、在李修睦所著的《图论导引》一书中还有一个“联边凝缩”的概念，这一过程是首先在两个不相邻的顶点间连接一条边（即“联边”），然后再沿这条边把该两顶点“收缩”成一个顶点（即“凝缩”），李教授把这一“联边凝缩”的过程叫做“收缩与联边的原则”。李教授的这一“联边凝缩”过程实际上是进行了两个运算——联边和收缩，它最终所得到的结果与我们这里所说的“同化”过程的结果是一样的，但它没有我们的同化过程简单。李修睦教授在书中只简单的提出了这个方法，认为“可以联边凝缩”的两顶点是可以着同一颜色的，但再没有进行更深层次的研究，所以也就不可能得出由此可以求得图的色数的结论。
5、我对图论中“同化”运算的研究得到了任何图“同化”的最终结果一定是这样一个完全图（也就是完全同态）Kn，其中n≥ω。这里ω是图的“密度”。“密度”一词也是《图论的例和反例》一书中的术语，即图中“最大团的顶点数”。但“最大团的顶点数”在一般的图论书和数学辞典或数学手册中都被叫做“团数”。我认为用“最大团的顶点数”定义“密度”比较科学一些。而用“最大团的顶点数”来定义“团数”的概念是模糊不清的，它只可能理解成是“团的个数”，但图中有各种各样的团，是对联种团呢，不能确定，不可能理解成是“最大团的个数”， 更不可能理解为是“最大团的顶点数”。因此我认为用“最大团的顶点数”定义“密度”比定义“团数”好些。看来《图论的例和反例》的译者聂祖安还是有水平，有一种逆潮流的气魄和精神。
6、在由李建中所翻译的美国人所著的《图论导引》一书中也有“密度”一词，该书对“密度”的定义是：图的“密度”是图的边数与顶点数的比值。我认为这个定义也不太科学，比如若干个都含有相同最大团的图，不能因其边数与顶点数的比值的不同，而就说它们不是同一类图，也不能说它们没有共同的特点。具有相同的最大团，这就是它们的共同特点。相反，还会有这种情况，虽然各图的最大团不同，但却有相同的顶边数与顶点数的比值。我想这不能说它们是有共同的特点吧。正因为如此我才也认为李建中所译《图论导引》一书中对图的“密度”下这样的定义也是不太科学的。
7、一个图“同化”的最终结果，不光看是不是得到了一个完全图，更重要的还是要看这个完全图的顶点数是不是最少的。我的研究结果是，图的“最小完全同态的顶点数”（β）与其“密度”（ω）的关系是：β≤＜1.5ω＞，这就基本上把图的最小完全同态的顶点数量化起来了。因为图的“最小顶独立集数”（α）与图的“最小完全同态的顶点数”（β）是相等的，所以也就有α＝β≤＜1.5ω＞。又因为图的“色数”（γ）与图的“最小顶独立集数”（α）是相等的，所以又有γ＝α＝β≤＜1.5ω＞（＜　＞表示其中的数字向下取整，因为图的“最小完全同态的顶点数”（β）、图的“最小顶独立集数”（α）、图的“色数”（γ）都只可能是整数）。由于平面图的密度均不大于4，把ω≤4代入γ≤＜1.5ω＞得：密度小于等于3的平面图的色数都是不大于4的；密度等于4的图虽有可能色数大于4，但在这种情况下的图就不是平面图了，所以仍有密度是4的平面图的色数不大于4的结论。从而得到任何平面图的色数都是小于等于4的结论，即有γ平面图≤4。
8、《图论的例和反例》一书中只提到了“完全同态”的概念，但没有再继续深入探讨下去，没有再进一步研究图的完全同态的顶点数与图的密度的关系。但书中又提到了一个“图的消色数”的概念，作者是这样定义“消色数”的：“图的消色数”就是图的“完全同态的顶点数”。这只是一个定性的概念，不可能作到量化，因为一个图是有多个“完全同态”的，那么一个图也就有多个“消色数”，这与平时说的“色类数”有什么曲别呢。一个图的最小色类数就是其色数，也只可能有一个，提出“消色数”一词实在是没有任何意义。另外“消色数”中的“消”是什么意思，很不明确。当然了，图的所谓“消色数”是一定包含了图的“色数”在内的。我的文章中的“最小完全同态”和“最小完全同态的顶点数”的概念，是我在《图论的例和反例》中的“完全同态”一词的基础上提出来的。任何图只可能有一个“最小完全同态”，当然其中的顶点数也一定是最少的。所以我定义的“图的色数等于其最小完全同态的顶点数”也是合适的、科学的。
9、关于“最小顶独立集数”的问题：顶独立集，图论是这样定义的：若在图的一个顶点子集合中，各顶点在图中均是不相邻的，这样的顶点子集合就是图的顶独立集。或者说图中两两均不相邻的顶点所构成的子集合，就叫一个顶独立集。图论中还有一个术语，叫“顶独立数”，它的定义是：顶点数最多的那个顶独立集中的顶点数，就叫做“顶独立数”。在我的文章里所说的“最小顶独立集数”与这里的“顶独立数”却是不同的概念，它不同于图论中“顶独立数”。我的“最小顶独立集数”定义为：一个图在进行顶独立集划分时，当一个图的所有顶点都被分划到某一个顶独立集里面时，并且所得到的顶独立集的数目是最少时，这个数目就是图的“最小顶独立集数”。请注意，我这里的“最小顶独立集数”是一个图的顶点被划分成若干个顶独立集时的“顶独立集的最少个数”，而不是对一个图任意找其一个顶独立集时的“顶独立集内的最大顶点数”。由于每个顶独立集内的顶点都是不相邻的，所以着色时着同一颜色是可以的，这样，一个图的“最小顶独立集数”是多少，这个图着色时就必须用多少种颜色。这就可以把图的“顶独立集”与图的“着色”联系起来了，也把图的“最小顶独立集数”与图的“色数”联系了起来。所以我认为我所定义的“图的色数等于其最小顶独立集数”也是合适的、科学的。我的“图的最小顶独立集数”是我在用图论方法证明四色猜测的过程中自已提出的，在图论文献资料中是找不到的。
10、图的最小完全同态中的每一个顶点所代表的若干个顶点在原图中都是不相邻的，当然最小完全同态中的每一个顶点也就代表着一个顶独立集；由于最小完全同态的顶点数是最少的，所以其所代表的顶独立集数也就是最小的；这样就可得到图的最小顶独立集数等于图的最小完全同态的顶点数的结论；从而也就有图的色数等于图的最小顶独立集数，也等于图的最小完全同态的顶点数的结论。所以图的色数γ，图的最小顶独立集数α，图的最小完全同态的顶点数β，与图的密度ω间均有相同的关系：即γ＝α＝β≤＜1.5ω＞。

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

注：此文已于二○一一年十月十三日在《数学中国》网上发表。