关于一些图类的亏格问题

摘要

本论文主要研究了图的最大亏格的下界问题以及有向图类在可定向曲面上嵌入的亏格分布。
　　 曲面S是拓扑学中的无边缘的2维紧闭流型。亏格为I的可定向曲面Si可以通过在球面上添加I个手柄得到。图在曲面S上的嵌入是指把图画在曲面上,使得G中的边只在公共的端点相交,且它的每个面都同胚于平面上的一个开圆盘。
　　 连通图G的最大亏格rM(G)定义为使G在亏格为k可定向曲面上有2-胞腔嵌入的最大整数k。显然一个图G的最大亏格有上界γM(G)≤|β(G)/2|,β(G)=|E(G)|-|V(G)|+1称为图G的Betti数,这里[α]表示不超过α的最大整数。E.Nordhaus、B.Stewart和A.T.White在文献[1]中引入了连通图G的最大亏格γM(G)的概念以来,图的最大亏格和上可嵌入性问题引起了广泛关注。但是还有很多图类(例如某些2-边连通图、3-边连通图)都不是上可嵌入的。因此,最大亏格的下界的问题引起了人们的广泛关注。
　　 另一方而,两个嵌入f:G→S和g:G→S是等价的,当存在一个同构映射h:S→S,使得h(o)f=g,否则称为不等价的。图的嵌入分布就是要确定图在曲面上的不等价嵌入的数目。Gross和Furst[2]最早提出了亏格的问题。此后,很多学者围绕这一问题进行了研究并得到了一些结论,但大部分图类的亏格多项式还是未知的,且许多关于亏格分布问题的结果是对无向图,对于有向图来说,其亏格分布方面的结果还非常少。
　　 本论文主要研究了连通四正则图的最大亏格的最优下界以及两类有向图在可定向曲而上嵌入的亏格分布。
　　 第一章对图的最大亏格、在可定向曲面上的嵌入的相关概念及研究背景进行简要介绍。
　　 第二章利用非上可嵌入图的结构特征对连通4-正则图进行了拆分,然后通过反证法得到了连通4-正则简单图以及连通4-正则无环图的最大亏格的下界,并举例证明了此下界的最优性。
　　 第三章把图的嵌入的联树模型推广到了有向图在可定向曲面上的嵌入上,研究了n次三连环有向图和n次四方环有向图在可定向曲面上的有向嵌入,分别得到了它们的嵌入亏格分布,并由此得到相应的有向嵌入的最大亏格。同时还由递推关系得到此两类图的亏格分布相同。

目录

文摘

英文文摘

致谢

第一章 绪论

第二章 两类图的最大亏格的下界

1 连通四正则简单图最大亏格的下界

2 连通四正则无环图最大亏格的下界

第三章 两类有向图的可定向嵌入亏格分布

1 三连环有向图的可定向嵌入亏格分布

2 四方环有向图的可定向嵌入亏格分布

参考文献

附录A 第三章第一部分D1的16种联树

作者简历

学位论文数据集