论文摘要
图在曲面上的可嵌入性是拓扑图论的主要问题.其中图的最小亏格问题是NP-困难的,所以对解决任意图的最小亏格仍需很长的一段距离.基于此,本文主要是在刘彦佩提出的联树模型的基础上,选择考虑了有趣且有意义的图类来研究其最小亏格问题.除此之外还计算了特定图类的可定向嵌入的亏格分布.本文所考虑的图类对已研究最小亏格或亏格分布的图类有一定的推广作用,所用方法提升了计算技巧,从而为更广泛图类的最小亏格及亏格分布问题的研究提供了更广阔的前景.对图的最小亏格的研究,主要是在联树模型的基础上,通过一个图在曲面上的嵌入可用其联树,进一步其关联曲面来表示,然后把关联曲面逐层分段,在层分割上建立调位运算.通过对任一关联曲面作一系列调位,从而可得最小亏格的关联曲面,此亏格即为所求图类的最小亏格.进一步依据给定图类的特点,通过关联曲面之间的关系可求得其最小亏格的表达式.而众所周知,对称性比较弱的图类用已知商嵌入的方法来解决却是不可能.这部分内容主要集中在前五章.第一章首先对这两方面的研究背景作了简要的介绍.随后,给出了一些与之相关的定义和性质.第二章首先利用异于以前的方法得到了完全二部图的最小亏格.然后基于完全二部图关联曲面的特点进行推广,构造了对称性比较弱的新图类J（m,n）且得其最小亏格,最后对完全二部图不同最小亏格嵌入的数目作了估算.第三章构造了对称性比较弱的新图类T（n,l,m）且得其最小亏格.作为推论得到了完全三部图Kn,n.l（l≥n≥2）的最小亏格.最后对完全三部图Kn,n,l不同最小亏格嵌入的数目作了估算.第四章研究了边合并图的最小亏格.文献分别讨论了完全图与完全图,完全二部图与完全二部图边合并的最小亏格问题,本章给出了n个特定图边合并的最小亏格.第五章讨论了几类图与一节点的联图的最小亏格.而平面图与一节点的联图亦为apex图.众所周知,apex图是拓扑图论中比较重要的一类图,在图的最小亏格问题研究中具有强大的作用.Mohar证明了apex图的最小亏格问题是NP-困难的.本章考虑了几类平面图与一节点的联图,即为apex图,以及两类未必是平面的图与一节点联图的最小亏格.第二部分表述在第六章,推广了中“珠子”的类,构造了异于目前已知亏格分布的图类.所用方法主要是根据给定图类的特点,选择确切的支撑树,把关联曲面集合进行分类,建立递推关系式,进而得给定图类的可定向嵌入亏格分布的显式表达式.由此可进一步考虑具有任意多节点且其度大于3和4的此类正则图的可定向嵌入亏格分布.第六章首先构造了推广的项链图,循环项链图以及推广的另三类图,其次得其可定向嵌入亏格分布的显式表达式.最后把上面图类进一步推广,得到了一类更一般的图,并对其可定向嵌入的亏格分布进行了刻画.第七章介绍了图的最小亏格及亏格分布领域中一些需要更进一步研究的问题,如如何利用联树模型计算完全图的最小亏格,以及如何通过刻画最小亏格关联曲面的特性来确定更广泛图类,乃至任意图类的最小亏格问题等等.