[原创]图最小完全同态的亏格一定小于等于原图的亏格

雷明85639720

[watermark]

图最小完全同态的亏格
一定小于等于原图的亏格
雷　明
（二○一四年元月九日）
一个图同化时，最终结果一定是一个顶点数不能再少的完全图，这就是图的最小完全同态。该最小完全同态的顶点数就是原图的色数。这是无凝的，但现在的问题是这个最小完全同态的亏格与原图的亏格是一个什么样的关系呢。
若给一个亏格为n的图，嵌入在亏格也为n的曲面上时，一定在顶点之外没有边与边相交情况。这个图的密度ω一定是已知的，图中的有联存在的不可同化道路的条数S也一定是已知的（至于ω和S能不能找到，这不是主要的，因为任何图中一定存在着这两个参数），那么该图的色数与最小完全同态的顶点数就是一定是ω＋S。
若以上所给的图的顶点数是v，如果图中没有饱和道路，那一定也没有不可同化道路，那么该图的最小完全同态一定就是Kω，说明该图的最小完全同态与图的最大团是相同的，其亏格也一定是相同的。
如果图中有饱和道路，但不是不可同化道路，该图的最小完全同态也一定是Kω，但最小完全同态的亏格可能就要小于原图的亏格了，比如一个密度是4的非平面图的亏格是1，密度是4，但其中的饱和道路又不是不可同化道路，同化后的最小完全同态一定是K4，K4又是平面的，其亏格是0，最小完全同态的亏格比原图的亏格就小了。这是一个例子；又一个例子是K3，3图，密度是2，其中的饱和道路也都不是不可同化道路，同化后的最小完全同态则一定是K2，这也是一个平面图，其亏格是0，最小完全同态的亏格也比原图的亏格小。
通过以上这两点可以说明，图同化后的最小完全同态的亏格不但是可以与原图的亏格相同的，而且是可以小于原图的亏格的。但图同化后的最小完全同态的亏格可不可以大于原图的亏格呢。回答是：不可以。现在证明如下：
任何图只要图已给出，那么其色数，亏格，最小完全同态及其顶点数就已是确定的了。用赫渥特公式计算出来的色数最大值，不但是是该亏格下的图色数的最大值，实际上也是该亏格下的图的最小完全同态顶点数的最大值，那么就说明图的最小完全同态的亏格与图的亏格是相等的，这就说明任何图的最小完全同态的亏格都一定是不会大于其原图的亏格的。
若一个亏格是n的、密度是ω的、也能嵌入到亏格为n的曲面上的图是一个完全图Kω，那么这个图的最小完全同态也一定是Kω，着色时一定得要用ω种颜色，即其色数是ω，那么该最小完全同态的亏格也一定就是n。现在假设最小完全同态的亏格可以大于原图的亏格成立，那么已知图的最小完全同态的亏格就应是n＋1。从已证明是正确的赫渥特着色公式中知道，曲面亏格的增大，就意味着可嵌入其中的图的最大色数也在增大，已给完全图的色数将成为ω＋1，这是不可能的，与已给图的色数是ω是产生了矛盾，所以要否定假设。因为已知图一经给出，其色数就已确定了下来，这是一个客观的事实，是谁也改变不了的。证毕。
要使已给图的最小完全同态的亏格大于原图的亏格，由于原图已是一个完全图，最大团已是Kω，这个Kω团也是该图的最小完全同态，其顶点数是ω。已知由赫渥特公式计算出来的最大色数也就是同亏格的图的最小完全同态的顶点数的最大值，要使已给图的最小完全同态的亏格大于原图的亏格，其顶点数至少比原图的最小完全同态的顶点数要大1，才能使最小完全同态成为一个Kω＋1团，那么图中至少也要有一条不可同化道路，才能使该图同成化成一个Kω＋1团。
原图已经是一个最大团是Kω（密度是ω）的完全图，嵌入在亏格为n的曲面上，而这个团Kω＋1肯定是不可能再嵌入到原图所嵌入的亏格为n的曲面上了，否则图中必然会出现在顶点之外的交叉边，而要嵌入到亏格比n大的曲面上才能保证该最小完全同态Kω＋1中的边在顶点之外没有相交叉的情况。图的最小完全同态都不能嵌入到亏格为n的曲面上去了，那么原图还能嵌入到该亏格的曲面上吗。肯定不能。这与原给出的图的亏格是n产生了矛盾，要么原图的亏格就应是n＋1，要么就是该图同化的结果就不会出现最小完全同态的亏格大于原图亏格的情况。二者只能取其一。只有小亏格的图可以嵌入到大亏格的曲面上的事，不可能有小亏格的曲面能嵌入大亏格图而在顶点之外没有边与边相交叉的情况。所以，最小完全同态的亏格比原图的亏格大的情况是不会出现的。这也就证明了任何图的最小完全同态的亏格一定是不会大于其原图的亏格的。
但有这种情况，图同化后的最小完全同态的顶点数（或其密度）比原图中的最大团的顶点数（或图的密度）大，这说明了原图中一定存在着不可同化道路，也说明原图的最大团的顶点数（或图的密度）是小于按赫渥特的着色公式：γn（ω）≤ （n≥0）计算出来的最大色数（或密度，最大团的顶点数）的值的，说明该图的密度一定是小于按赫渥特公式计算出的完全图的密度的。
所以任何图的最小完全同态的亏格一定是小于等于原图的亏格的。

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