关于一些图类亏格问题.pdf

学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索, 提供阅览服务,并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明) 学位论文作者签名:1凰飞△签字日期:pI,年‘月I胡导师签名:槠. 签字日期:b卜年石月l L日中图分类号: UDC: 学校代码:10004 密级:公开北京交通大学硕士学位论文关于一些图类的亏格问题 On genus problems ofsome kindsof伊aphs 作者姓名:周玎导师姓名:郝荣霞学位类别:理学 I[II Y1780741 学号:08122149 职称:教授学位级别:硕士学科专业:运筹学与控制论研究方向:图论及其应用北京交通大学 2010年6月致谢本论文的工作是在我的导师郝荣霞教授的悉心指导下完成的,郝荣霞教授学识渊博,她严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢!年来郝荣霞老师对我的关心和指导。在这里还要衷心感谢何卫力教授的指导,何卫力老师对于我的科研工作和论文都提出了许多的宝贵意见,在此表示衷心的感谢。同时,也要感谢理学院的全体老师们,在交大的6年时光里,老师们的指导和帮助一直伴随着我,督促我学****和成长。在实验室工作及撰写论文期间,张锐、李文俏等同学对我论文中的研究工作给予了热情帮助,在此向他们表达我的感激之情。另外也感谢我的家人,他们的理解和支持使我能够在学校专心完成我的学业。中文摘要摘要:本论文主要研究了图的最大亏格的下界问题以及有向图类在可定向曲面上嵌入的亏格分布。曲面S是拓扑学中的无边缘的2维紧闭流型。亏格为i的可定向曲面s:可以通过在球面上添加f个手柄得到。图在曲面S上的嵌入是指把图画在曲面上,使得G 中的边只在公共的端点相交,且它的每个面都同胚于平面上的一个开圆盘。连通图G的最大亏格‰(G)定义为使G在亏格为k的可定向曲面上有2一胞腔嵌入的最大整数k。显然一个图G的最大亏格有上界嘞(G)≤I华l, ∥(G)=lE(G)l_P(G)|+1称为图G的Betti数,这里L口j表示不超过口的最大整数。 、【1]中引入了连通图G的最大亏格rM(G) 的概念以来,图的最大亏格和上可嵌入性问题引起了广泛关注。但是还有很多图类(、)都不是上可嵌入的。因此,最大亏格的下界的问题引起了人们的广泛关注。另一方而,两个嵌入/:G—S和g:G专S是等价的,当存在一个同构映射 h:SjS,使得hof=g,否则称为不等价的。图的嵌入分布就是要确定图在曲面上的不等价嵌入的数目。Gross和Furst[2]最早提出了亏格的问题。此后,很多学者围绕这一问题进行了研究并得到了一些结论,但大部分图类的亏格多项式还是未知的,且许多关于亏格分布问题的结果是对无向图,对于有向图来说,其亏格分布方面的结果还非常少。本论文主要研究了连通四正则图的最大亏格的最优下界以及两类有向图在可定向曲而上嵌入的亏格分布。第一章对图的最大亏格、在可定向曲面上的嵌入的相关概念及研究背景进行简要介绍。,,并举例证明了此下界的最优性。第三章把图的嵌入的联树模型推广到了有向图在可定向曲面上的嵌入上,研究了n次三连环有向图和n次四方环有向图在可定向曲面上的有向嵌入,分别得到了它们的嵌入亏格分布,并由此得到相应的有向嵌入的最大亏格。同时还由递推关系得到此两类图的亏格分布相同。关键词:图;最大亏格;亏格分布;联树;曲面分类号: jE塞銮迢态堂亟±堂僮途塞△旦墨!壁△￡! ABSTR ACT. AB STRACT Inthispaper,the lowerbound problerm ofthe maximum genus andthegenus distributionsofdigraphs inorientable surfaces are topologieal graphtheory, thesurface S is acompact 2-dimensional rmnifold without orientable surface ofgenus i,denoted by S{,is thesphere with handles G is sam tobeembedded in as