论文部分内容阅读
图论[Graph Theory]是数学的一个数学分支,它的研究对象主要是图.图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系.随着研究的深入,拓扑图论和代数图论逐渐发展成图论的两个重要分支,本文则属于拓扑图论的研究范畴.
图的曲面嵌入是拓扑图论的一个重要研究方向.根据亏格的不同,可以给出图在球面、欧氏和双曲空间中无边交叉的实现.对于亏格为0的图,可以将其嵌入到球面空间;对于亏格为1的图,可以将其嵌入到环面或射影平面;对于亏格大于1的图,我们将其覆盖空间嵌入到双曲圆盘中或者Klein瓶中。这种对图的量化,也是对于抽象关系的一种量化,有着非常广的应用价值。图的嵌入问题在计算机科学等很多领域都有着非常重要的意义.研究图在不同亏格曲面上的不等价的嵌入个数成为其中一个重要的分支,这即是图的亏格分布和完全亏格分布问题.
联树模型的思想,起源于刘彦佩教授,他吸收了前人用多边形来表示曲面的思想,形成了一套完整的多面形理论.给定图G的一棵生成树,把每条非树边从中间切断为两条边,即得到一个图的联树.从任意一个节点出发沿T和旋走遍联树所有边,依次记录非树边的字母,则得到图G的关联曲面S.图G的关联曲面与其曲面嵌入之间存在着一一对应的关系.因此,联树模型成为研究嵌入分布的一种非常重要的方式,也是本文主要应用的方法。
总所周知,图的亏格分布是NP-HARD问题,对大部分图类,我们暂时还不能得出其亏格分布和完全亏格分布.然而,图在不同亏格曲面上的嵌入个数往往有一定的相关关系甚至递推关系,从而研究图在某些类型曲面上的个别嵌入亦有着重要的意义,特别地,研究图在球面,环面,射影平面,Klein瓶等小亏格曲面上的嵌入更加有着显而易见的实际意义,本论文利用嵌入的联树模型,专门对一些图类在小亏格曲面上的嵌入进行研究,重点研究了图在射影平面上的嵌入.下面简要地介绍本论文各章的主要内容:
第一章首先对曲面,曲面嵌入,曲面的多边形表示等概念进行叙述,并对拓扑图论中关于曲面嵌入的重要结论和理论体系进行了介绍,随后介绍了本论文的研究背景.
第二章首先介绍了嵌入的联树模型理论,并给出或证明了一些本论文要用到的重要引理以及一些基本定理,包括射影平面和Klein瓶的多边形表示形式等.
第三章通过联树模型,研究了Hn在射影平面的嵌入.其中最关键因素即使对边序列进行分类讨论,用组合计数思想总结嵌入个数。
第四章通过联树模型,研究了Hn+bn在射影平面上的嵌入.其总体证明思想与第三章类似。
第五章则对研究成果进行了总结,并展望今后的研究工作.