【作者】 熊畅；

【导师】 黄元秋；

【作者基本信息】 湖南师范大学 ， 运筹学与控制论， 2013， 硕士

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

【Abstract】 Graph Theory is an important branch of mathematics, its main targets is the graph. The graphics of Graph theory posed by certain given point and a line connecting two points, and usually used to describe somethingcertain relation-ship between things. The points often represent things, the line connecting the two points represents this relationship between the corresponding two things. With further research, the topology graph theory and algebraic graph theory gradually developed into graph theory two most important branches, and this paper is belong to the scope of the topological graph theory.How to imbed a graph into surfaces is a very important researching di-rection in topological theory.Depending on the different genus, figure can be embedded into the spherical space; For the genus of zero, Figure can be em-bedded spherical surface.For the genus of one,Figure can be embedded Torus or projective plane.For the genus more than one.we will cover it to the space of the hyperbolic disc or Klein bottle. This Figure quantitative but also a quanti-tative abstract relations, has a very wide application value. Graph embedding problem has a very important significance in many areas of computer science Researching of the figures on the different surfaces of genrus becomes one of the important branches of the genus distribution and totally genus distribution.Recently, Many new results have been known by using the imbedding model of joint tree which professor Yanpei Liu introduced. Fixing a spanning tree of a graph G, we get the joint tree of graph G by cutting every co-tree edge into two edges. Starting at a vertex, we trace all the edges of joint tree according to the rotation systems and T. Then we write down the letters of co-tree edges in order. It is the associated surface of G. There are one to one relationship between the associated surfaces and its imbeddings.It has been known that imbedding distribution is a NP-problem. For many graphs, we haven’t known its imbedding distributions and total imbedding dis-tributions yet. However, there is always relation among the imbeddings on surfaces of different genus. Therefore, it has significance to the study of imbed-dings on some surfaces. In particular, it is important for investigating on the imbedding on sphere, torus, projective plane, Klein bottle. In this thesis, we research on the imbeddings of some graphs on surfaces with small genus, es-pecially on projective plane. In the following, we will introduce the content of each chapter briefly.In Chapter1, we firstly state the concept of surface, imbedding and how to represent surfaces by polygons. Then we introduce the very important results and theory system of graph imbedding. In the following, the background of this thesis is presented.In Chapter2, we firstly introduce the imbedding model of joint tree. Then some important lemmas or theorems are introduced or proved. It includes the polygonal representations of projective plane and Klein bottle.In Chapter3, we study on the embedding number of circular graph C(2n.2) on the projective plane.One of the most critical factors is the classification discussion for edge sequence.counting the number of embedded with a thought of Combinatorial Enumeration.In Chapter4, we study on the embedding number of circular graph Hn+bn on the projective plane.Overall prove ideas is similar to the chapter Ⅲ.In Chapter5, we firstly summarize the results of this thesis. Then we prospect the future research work.更多还原