图的曲面嵌入与交叉数

【作者】 马登举；

【导师】 任韩；

【作者基本信息】 华东师范大学 ， 运筹学与控制论， 2004， 硕士

【摘要】 本文主要研究图在曲面上的2-胞腔嵌入与交叉数问题，讨论了广义置换图与广义Petersen图的最大亏格问题，确定了两类广义Petersen图的Euler亏格，利用循环图在环面上的2-胞腔嵌入给出了它的交叉数的上界，并且确定了几类循环图的交叉数，具体结果如下： 1．证明了如果一个广义置换图G(n,k)至多有两个奇长的次圈，那末它是上可嵌入的。 2．证明了当k→∞时，广义置换图G(n,k)最大亏格不小于[β(G(n,k))/3]+1的概率趋于1。 3．证明了广义Petersen图P(n,m)是上可嵌入的。 4．确定了广义Petersen图P(2m+1,m)(m≥3)的Euler亏格是1。 5．确定了广义Petersen图P(2m+2,m)(m＞4)的Euler亏格为2。 6．利用循环图在环面上的2-胞腔嵌入给出了它的交叉数的上界。 7．确定了循环图C(2m,m)(m≥3)，C(2m+1,m)，C(2m+2,m)(m≥3)的交叉数分别是1，1，m+1。更多还原

【Abstract】 This paper mainly studies embeddings of graphs and their crossing numbers.Chapter 1 is devoted to basic concepts of embeddings and crossing numbers of graphs.In chapter 2, we prove the generalized permutation graph G(n, k) with no more than two subcycles whose length are odd number is upper embeddable, and show the probability that the maximum genus of G(n, k) is no less than tends to 1 when k - .In chapter 3, we prove the generalized Peter sen graph P(n, m) is upper embeddable, and show that the Euler genus of P(2m + 1,m)(m > 3) is 1. Also, we show that the Euler genus of P(2m + 2,m)(m > 4) is 2.Chapter 4 provides an upper bound for crossing number of circular graphs using their 2-cell embeddings in the torus. Simultaneously, crossing numbers of circular graphs C(2m, m)(m > 3), C(2m +1, m) and C(2m + 2, m)(m > 3) are determined as 1,1 and m + 1, respectively.更多还原