论文部分内容阅读
本论文主要研究的是一些图类的曲面嵌入亏格.曲面在拓扑学中,就是无边缘的紧2-维流形,分为可定向曲面和不可定向曲面.图G在曲面上的一个嵌入是指存在一个1-1连续映射h:G→ S,即G的每个顶点对应S上不同的点,然后将图G的边作为连接S上相应端点之间的连续曲线,使得所有代表边的曲线自身无重点,且除端点外不与其它曲线相交.若S-G中每个连通部分都同胚于一个开圆盘,则图G嵌入到曲面S上称为2-胞腔嵌入.一个图G的亏格是指图G可嵌入的所有可定向(不可定向)曲面中最小的曲面的亏格,记为γ(G)((γ)(G)).相似的,有图G的最大亏格γM(G)((γ)M(G)).记gi((g)i)为图G在可定向曲面Si(不可定向曲面Ni)上的不等价的嵌入个数,i≥0(i≥1),则序列gγ(G),gγ(G)+1,…,gγM(G)((g)(γ)(G),(g)γ(G)+1,…,(g)(γ)M(G))为图G的(不可定向)亏格嵌入分布.亏格作为研究网络复杂性的重要依据,能够指示出网络设计的效率,亏格越小,设计越有效率. 下面简要介绍本文各章的内容. 第一章:简要回顾了图的嵌入理论的起源和发展,之后介绍了一些相关的基本概念,以及文章涉及的已有结论. 第二章:首先,基于对平衡超立方体图的研究,算出它的最小亏格.其次,分析了折叠超立方体的结构,优化其最小亏格的上界,它们的最大亏格由四边连通性直接得到. 第三章:利用覆盖矩阵,导出一类类循环图在可定向曲面上的亏格分布. 第四章:给出两类图,广义petersen图P2n,2和星图的并置Gn,用不同的方法计算它们在射影平面上不同的嵌入个数. 第五章:对文章进行总结,并展望今后要做的工作.