[原创]任意图的平均度与最小度

雷明85639720

[watermark]

任意图的平均度与最小度
雷  明
（二○一二年十月十二日）
    不同亏格的图的顶点平均度和最小度各都是不同的，现在我们讨论入下：
1、任意图平均度的上界：
若在一个完全图Ｋω中增加顶点，在保证图的亏格n和密度ω都不变的情况下，在图中每增一顶点至少可以增加3条边。若大于三条边时，当完全图Kω又是极大图时，图中就一定会产生交叉边，使图的亏格增大。所以，在图中增加一个顶点时，至少可以增加的度是2×3＝6。当增加的顶点数为m时，该图的平均度则是
d平均＝ ＝ ＋               （1）
上式中当m趋于无穷大时，对该式取极限得
d平均＝ ( ＋ )
＝
＝0＋6
＝6                                       （2）
公式（2）说明任何亏格任何密度的图的平均度上界极限都是6。但是很明显亏格大于0的多阶曲面上的完全图的平均度的确又是大于等于6的，这似乎是一个矛盾，其实并不矛盾。我们用公式（1）d平均＝ ＋ 在亏格n为某一值（这时该亏格下最大完全图的密度也就已经固定不变了）时，对顶点数m作图，得到如图1的多条曲线。可以看出，图的亏格大于1时，图的平均度是一个减函数，只是当m趋近于无穷大时，它的极限是6，这只是平均度上界的下极限，其平均度的最大值（即上线）就是该亏格下最大完全图的顶点数（也即最大完全图的密度）减1。而对于亏格为0的球面（平面）图来说d平均＝ ＋ 则是一个增函数，当m趋近于无穷大时，它的极限也是6，这是其平均度上界的上极限，平均度是决不会达到6的；对于亏格为1的K7图，其平度均度曲线却是一条度为6的水平线；对于亏格仍是1而密度是6和5的图来说，其平均度上界也是一个增函数，其上极限也是6。

多阶曲面上的图用赫渥特公式计算出来的色数，也就是可嵌入该曲面上顶点数最大的完全图Kv的顶点数，所以有v＝γn＝ 的关系，所以在亏格大于等于1时的完全图的平均度则是v－1，因为完全图的密度就是完全图的顶点数，所以也有该完全图的平均度又是其密度ω最大－1。从图1可以看出，任何亏格的图的平均度都是处在其亏格下的最大完全图Kv的顶点数减1（即v－1）和6之间的，它是一条以6 为极限的曲线。注意，在图1中，n＝0，ω＝1，n＝0，ω＝2和n＝0，ω＝3的曲线分别在顶点数v＝6，v＝5和v＝4之后是与n＝1，ω＝6，n＝1，ω＝5和n＝0，ω＝4的曲线是重合的。这也说明了公式（1）对于亏格为1而密度是6和5 的图以及亏格为0而密度分别是1，2，3，4的图来说，都是增函数，也说明了这些图有共同的特点，尽管密度不同，但其平均度上界的上极限都是6，平均度的上界都是5。例如正8—面体和正20—面体的密度是3，而平均度则分别是4和5；而K6图的密度是虽是6，但其平均度也是5。
只所以亏格大于等于1且密度大于7的图的平均度上界的曲线是一个减函数，而亏格小于等于1且密度小于7的图的平均度上界曲线是一个增函数，而亏格等于1且密度等于7的图的平均度上界曲线是一个常数6，完全是因为图的亏格大于等于1 时亏格每增大1，其按赫渥特的地图着色公式计算出来的色数的增加是小于等于1的，而图的亏格小于等于1时亏格每增大1，其按赫渥特的地图着色公式计算出来的色数的增加是大于等于1的原因。两种平均度上界曲线的极限值均是6，所以亏格等于1且密度等于7的图的平均度上界，不管图中有多少个顶点，其平均度上界的上下线都是6。
2、任意图平均度的下界：对于任何图，在保证图的亏格n和密度ω都不变的情况下，给图中每增一顶点最少也可以使图增加1条边，增加2度。当增加的顶点数为m时，该图的平均度则是
d平均＝ ＝               （3）
同样的，（3）式中当n趋于无穷大时，对该式取极限得
d平均＝  
＝ （ ＋ ）
＝
＝2                                          （4）
（4）式就是任意图的平均度的下极限值，是一个常数2。说明任何图的平均度的下极限都是相同的，都是2，它与其上极限不同，图的平均度的下极限与图的密度ω是没有关系的。
3、任意图的最小度：对于任何图，其最小度一定是小于等于其平均度的，即
    δ≤d平均                                       （5）
于是就有：当图的亏格大于等于1且密度大于等于7时，其最小度等于小于图的密度减1，当图的亏格小于等于1且密度小于等于6时，其最小度均等于小于5。用公式表示则是

由于亏格大于等于1且密度等于大于7的图的密度就等于该亏格下的最大完全图的顶点数，而各亏格下最大完全图的顶点数v就等于用赫渥特的地图着色公式γn＝ 计算出来的色数γn，即有v＝γn，所以就有亏格大于等于1且密度大于等于7的图中一定有一个顶点的度最小为小于等于v－1的结论，亏格不同，图的最小度是不同的；而对于亏格小于等1且密度小于等于6的图的最小度则没有这个结论，其最小度均是小于等于5的，但这只是一个界，如密度为3的正八面体和正二十面体的最小度和平均度分别都是4和5，而密度是2 和1的图的最小度则是不可能达到5 的。这就是亏格为小于等于1 的图与亏格为大于等于1的图的最小度的不同之处。
（注：图与公式请见DOC文件中）
雷  明
二○一二年十月十二日于长安