关于图在小亏格曲面上嵌入的研究

《关于图在小亏格曲面上嵌入的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要IMLIIIIqLqlIMIIIIIIIHIqUlY2326529确定图G在给定曲面上的不等价的嵌入个数是拓扑图论中一个重要的研究方向，这一问题也被称为曲面嵌入的分类问题．1987年，Gross和Furst引入了图在可定向曲面上的亏格分布，随后Gross和Chen等人又将亏格分布推广到了完全亏格分布．2003年，刘彦佩教授创建了嵌入的联树模型，许多专家学者利用嵌入的联树模型，得到了很多新的结果．研究表明，图的亏格分布是NP．难问题，对于大部分图类，我们尚不能得到其亏格分布和完全亏格分布，但图在不同亏格曲面上的嵌入个数往往存在着一定的相关关系

2、甚至是递推关系，因此对于暂不能得到其亏格分布和完全亏格分布的图类来说，研究其在小亏格曲面，如球面，环面，射影平面，Klein瓶上的嵌入个数就尤为重要了．本文研究了两类图：分别是在鹅卵石路图和图以上加边构造而成．鹅卵石路图和图风，Chen和郭已分别得到其完全亏格分布，但加了一条边之后的图，在研究其亏格分布时就困难重重了．本文利用嵌入的联树模型，分别对其在球面及射影平面上的嵌入进行了细致地研究．下面简要地介绍本文各章节的主要内容：第一章首先对曲面，曲面嵌入，曲面的多边形表示等概念进行了叙述，并对拓扑图论中关于曲面嵌入的重要结论，理论体系及本文的研究

3、背景进行了介绍．第二章首先介绍了嵌入的联树模型理论，并列出或证明了一些本论文中所需要的相关的引理．第三章研究了图G。在球面及射影平面上的嵌入，利用嵌入的联树模型和组合计数的方法，得出了其在球面及射影平面上的嵌入个数．第四章研究了图R在球面及射影平面上的嵌入，利用嵌入的联树模型和组合计数的方法，得出了其在球面及射影平面上的嵌入个数．第五章对研究成果进行了总结．关键词：曲面；亏格；嵌入；联树ABSTRACTTodetermineagraphGthatthenumberofinequivalentembeddingonagivensurfaceisa

4、nimportantresearchdirectionintopologicalgraphtheory．Thispt‘oblemisalsoknownaStheclassificationproblemofsurfaceembedding．In1987，GrossandFurstintroducedgenusdistributionthatthegraphWasembeddedinorientablesurface．ThengenusdistributionwasextendedtothetotalgenusdistributionbyGros

5、sandChen．In2003，ProfessorYanpeiLiucreatedtheembeddingmodelofjointtree．Manyexpertsandscholarsobtainedalotofnewresultsbyusingofit．Researchshowedthat，thegenusdistributionofagraphWasaNP．hardproblem．Formostgraphs，westillcannotgetthegenusdistributionandtotalgenusdistribu-tionyet．H

6、oweverthenumberofembeddingagraphindifferentgenussurfacesoftenhaveacertainrelationshiporevenrecurrentrelations．Sotothegraphwhosegenusdistributionandtotalgenusdistributioncannotbeobtainedtern-porarily．Studyingonsmallgenussurfaces，suchasspherical，torus，projectiveplane，Kleinbott

7、le，isparticularlyimportant．Thispaperstudiestwoclassesofgraphswhichareconstructedincobblestonepathandthegraph眠byaddingedgesrespectively．ChenandGuohadobtainedthetotalgenusdistributionforthetwographsrespectively．ButitisSOdifficulttostudythegenusdistributionfortwonewgraphs．Inthi

8、spaper，usingtheembeddingmodelofjointtree，theembeddingonthesphericalandproje