[原创]图的亏格与密度的关系

雷明85639720

[watermark]

图的亏格与密度的关系
雷  明
（二○一二年十月三十一日）
图的亏格与图的密度间的关系是一个非常复杂的问题，我们目前还弄不明白其中的关系是否有一个函数关系式，但我们可以从不同的角度去对其地行研究。若一个已知密度为ω的图，其色数与其密度相等，也就是说该图的最小完全同态的顶点数也与其密度和色数均相同，在这种情况下该图的亏格也应是一定的，设为n，现在来研究在保证图的密度不发生变化的情况下，若图中的边与顶点发生了变化时，图的亏格将会有什么样的变化呢。以下从两个方面来分析：
㈠ 从对一定密度的图中某最大团外的不可同化道路的条数多少来研究：
在研究图的同化与图的色数的关系中，我们已经得到了任意图顶点着色的色数γ顶点与图的密度ω的关系，即任意图顶点着色色数的界
ω≤γ顶点≤                                   （1）
另外我们还可以直接从多阶曲面上图的欧拉公式推导出了赫渥特多阶曲面上的地图着色公式，即
γn≤                                   （2）
式中γn是亏格为n的图的色数。
由于任意图顶点着色的色数是与图的最小完全同态的顶点数相同的，该完全同态的顶点数a最小完全同态也一定是大于等于原图的密度值，而又小于等于原图的密度的1.5倍并向下取整的值的，即ω≤a最小完全同态≤ ，也即ω≤a最小完全同态≤1.5ω。而用公式（2）计算出来的多阶曲面上地图的着色数实际上就是能嵌入该亏格曲面上的图的最小完全同态的顶点数a最小完全同态，即有a最小完全同态≤ ，也即有a最小完全同态≤ 。所以就有以下两个关系式：
（1）ω≤
     2ω≤7＋
     2ω－7≤
     4ω2－28ω＋49≤1＋48n
     4ω2－28ω＋48≤48n
      ≤n
      ＋1≤n
即           n≥ ＋1
再向上取整得
             n≥
（2）1.5ω≥
3ω≥7＋
3ω－7≥
9ω2－42ω＋49≥1＋48n
9ω2－42ω＋48≥48n
≥n
＋1≥n
即          n≤ ＋1
把上式再向上取整得
            n≤
把上二式写在一起则是
        ≤n≤                        （3）
公式（3）就是图的亏格与图的密度之间的关系。也可以说是相同密度的图的亏格的界。
按公式（3）求密度从4到10的图的最小亏格和最大亏格如下表。
图 的 密 度45678910
最小
亏格取整前00.16670.511.6672.53.5
取整后0111234
最大
亏格取整前0.51.31252.54.062568.312511
取整后12356911
例如，表中可以看出，密度为6的图的最小亏格是1，最大亏格是3。若有一条不可同化道路时，其最小完全同态的顶点数是7，其亏格仍是1；若有两条不可同化道路时，则其最小完全同态的顶点数则是8，亏格是2；若有三（最多了）条不可同化道路时，则其最小完全同态的顶点数则是9，亏格是3。其余密度的图的亏格可以次累推。
㈡ 从对一定顶点数的完全图的某一个面中增加一个顶点和若干条边来研究：
某亏格下的图总存在有一个最大的完全图，其密度和顶点数都是ω＝v＝ ，在保证图的密度不发生变化的情况下，在图中增加一个顶点时，最多只能增加v－1条边，否则图的密度就会增大。若这个完全图在其亏格下又是一个极大图时，所增加的v－1条边中最多只可能有v－3条边可能会使图的亏格增大（因为在所增加的v－1条边中，至少有两条边是在同一个3—边形面内的，这两条边是不会与其它边相交叉的，是不会使图的亏格增大的，所以最多只可能有v－3条边可能会使图的亏格增大），即图的亏格就有可能会增大到n＋v－3，因为在完全图中有v＝ω的关系，所以又有图的亏格最大可能是n＋ω－3。由于ω＝ ，所以增加了顶点和边的该完全图的最大亏格可能是 ＋ω－3＝ ＝ ，再向上取整得 ，这又是一个亏格与密度的关系式，即同一密度下图的亏格的最大值。比如完全图K7（亏格是1，又是极大图），在其中一个面内增加一个顶点，在保证图的密度仍是7不变的情况下，在所能增加的v－1＝6条边中，最多只有v－3＝7－3＝4条边会使图的亏格增加的，Δn＝4，则图的亏格将由原来的n＝1增加到n＝5。这里我们只考虑了在完全图的某一个面内增加一个顶点的情况，如果是在同一个面内增加两个以上的顶点，或在不同的面内都同时增加顶点时，只要图的密度不发生变化，这种情况下图的亏格将会发生什么变化，我们目前还是无法知道的。
所以我们在上面才说，图的亏格与图的密度间的关系是一个非常复杂的问题。

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