如何求一个已知图的亏格

雷明85639720

如何求一个已知图的亏格
雷  明
（二○一九年十二月十五日）

我们可以通过多阶曲面上的图的欧拉公式v＋f－e＝2（1－n）（其中n是图的亏格，v，f，e分别是图的顶点数，面数和边数。图的亏格是图可嵌入的曲面的最小亏格。球面上有若干个孔洞穿过后所形成的曲面，就是多阶定向曲面。穿过球面上的孔洞数就叫多阶定向曲面的亏格。球面，其上没有孔洞穿过，亏格就是0；若有一个孔洞从球面上穿过，就是轮胎面，亏格是1；若有两个孔洞从球面上穿过，就是“8”字形麻花面，亏格是2。……，总之，有几个孔洞穿过后，形成的曲面的亏格就是几）推导出赫渥特多阶曲面上的地图着色公式γn≤＜（7＋√（1＋n））/2＞（其中＜ ＞表不其中的数字向下取整）。由于图的色数又等于图的最小完全同态的顶点数，所以上式实际上也就是图的最小完全同态的顶点数公式，即有亏格为n的图的最小完全同态的顶点数是v≤＜（7＋√（1＋n））/2＞，把这个公式用v表示n时，则是n≥［（v－3）（v－4）/12］（v≥3）（其中［ ］表示其中的数字向上取整），由于图的亏格是其所能嵌入的曲面的最小亏格，所以上式只用等号就可以了，即n＝［（v－3）（v－4）/12］（v≥3）。知道了图的最小完全同态的顶点数或色数，图的亏格就可以通过上式计算出来了。
如何求出图的最小完全同态的顶点数呢？这就得用同化方法求图的色数了。
同化就是把图中不相邻的顶点凝结成一个顶点的过程。着色时不相邻的顶点着上同一颜色也是完全可以的。一个已知图的最大团的顶点数是ω（即图的密度是ω），当某一最大团外的一条道路中的各个顶点都与最大团中的同一个ω－2团K2中的各顶点相邻，且道路的两个端点顶点又分别与最大团中的另外两个顶点相邻时，道路中总有一个顶点是同化不到最大团中去的，把这样的道路叫饱和道路或不可同化道路。当不可同化道路的条数是S，各道路间又形成了成联时，由于联中各顶点都是相邻的，所以各条不可同化道路中的不可同化的顶点因其原本就相邻也不可能再同化为一个顶点，所以S条不可同化道路就有S个顶点同化不到最大团中去。因为S条道路的联中的最大团的顶点数是2S个，所以有2S≤ω，即有0≤S≤ω/2。这就是密度是ω的图中的不可同化道路的条数。S个顶点同化不到最大团中去，说明图的最小完全同态的顶点数vn或色数γn就是ω＋S，即0≤vn（γn）≤1.5ω个。代入公式n＝［（vn－3）（vn－4）/12］（vn≤3）中，就可以求出密度是ω的图的亏格了。
下面我们计算一下密度分别是2，3，4，5，6，7的图的各种亏格：
当ω＝2时，S＝0，1，v＝2，3，两种情况下都是n＝0；
当ω＝3时，S＝0，1，v＝3，4，两种情况下也都是n＝0；
当ω＝4时，S＝0，1，2，v＝4，5，6，当v＝4时，n＝0，当v＝5，6时，n＝1；
当ω＝5时，S＝0，1，2，v＝5，6，两种情况下也都是n＝1；
当ω＝6时，S＝0，1，2，3，v＝6，7，8，9，当v＝6，7时，n＝1，当v＝8，n＝2，当v＝9时，n＝3；
当ω＝7时，S＝0，1，2，3，v＝7，8，9，10，当v＝7时，n＝1，当v＝8时，n＝2，当v＝9，n＝3，当v＝10时，n＝4。
上面是我们用各密度情况下的可能会出现的不可同化条数来计算的，当然是较容易的。但现在是给一个任意的图，不可明显的看出有几条不可同化道路。怎么办，那就只有对图进行同化，最后得到该图的最小完全同态，这时其顶点数或色数就清楚了，只要所得到的最小完全同态真的是最小的，计算出的亏格一定就是正确的。

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

注：此文已于二○一九年十二月十五日在《中国博士网》上发表过，网址是L

雷明85639720

，，，，，，，，

wangyangke

（笑话）继鲁思顺——定理：鲁思顺是个二百五！——之后，陕西雷明举重若轻，轻松证明哥德巴赫猜想

雷明85639720

wangyangke真上无耻！

雷明85639720

wangyangke真上无耻！

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，