一些图类的亏格分布及单峰性

发布时间：2018-04-14 19:50

本文选题：图 + 联树　；参考：《北京交通大学》2015年硕士论文

【摘要】：本文主要研究了一般田图的亏格分布及一些梯图亏格分布的单峰性。这里考虑连通无向图在曲面上的可定向的胞腔嵌入,这里的曲面指的是无边缘的2-维紧流形。自从1987年图的亏格分布提出以来,此问题即引起学者们的关注。研究的图类从闭梯、莫比乌斯梯、Ringel梯、圆体及鹅卵石路等几类特殊图类,扩展到一般梯图、3-正则图及4-正则图等较为复杂的图类。用来求图的嵌入的亏格分布的方法主要有组合的方法、Jackson公式、矩阵法、基于联树的曲面生成法和曲面分类法及分布分解法。本文在刘彦佩老师提出的联树法的基础上,通过运用曲面分类法,分类一类新图类的可定向嵌入曲面,计算一些曲面集的亏格分布,把一般田图的亏格分布转化为这些曲面集的线性组合,从而求出这类图的可定向嵌入的亏格分布。推广了Gross等关于P3□Pn亏格分布的计算,并把他们的结果简单地导出。最后,给出一些梯图的亏格分布的单峰性。第一章对图的亏格分布、在可定向曲面上的嵌入的相关概念及研究做简要介绍。第二章首先求出一些曲面集的亏格分布的递推表达式,在联树的基础上,运用曲面分类法把一般田图的亏格分布转化为这些曲面集的线性组合。对P3□Pn,用联树法及分布分解法,求出其亏格分布的递推表达式,然后运用计算机编程计算出其亏格分布。另外,得到了几类梯图的亏格分布。第三章本章主要研究了多项式序列的单峰性和对数凹之间的相关关系。第二部分,得到了关于有限个单峰序列的线性组合是否单峰的准则；第三部分,回顾了梯图曲面集的亏格分布是单峰的或对数凹的,并给出梯图曲面集亏格分布的峰点公式；第四部分,证明了一些梯图的亏格分布的单峰性,并给出这些梯图亏格分布的峰点公式。
[Abstract]:In this paper, we mainly study the genus distribution of general field graphs and the unimodal properties of some ladder graph genus distributions.In this paper, we consider the orientable cell embedding of connected undirected graphs on surfaces, where the surfaces refer to 2-dimensional compact manifolds without edges.Since the genus distribution of graphs was put forward in 1987, this problem has attracted the attention of scholars.The graphs are extended from the closed ladder, Mobius ladder Ringel ladder, circular body and cobblestone path to the general ladder 3-regular graphs and 4-regular graphs.The methods used to find the embedded genus distribution of graphs include the combination of Jackson formula, the matrix method, the surface generation method based on the combined tree, the surface classification method and the distribution decomposition method.In this paper, on the basis of the combined tree method proposed by Liu Yanpei, the genus distribution of some surface sets is calculated by using the surface classification method to classify the orientable embedded surfaces of a new class of graphs.The genus distribution of a general field graph is transformed into a linear combination of these surface sets, and the directed embeddable genus distribution of this kind of graph is obtained.In this paper, we generalize the calculation of P3-Pn genus distribution by Gross et al, and simply derive their results.Finally, the singularity of genus distribution of some ladder graphs is given.The first chapter briefly introduces the genus distribution of graphs, the related concepts and research of embedding on orientable surfaces.In the second chapter, the recursion expressions of genus distribution of some surface sets are obtained. On the basis of the combined tree, the genus distribution of the general field graph is transformed into the linear combination of these surface sets by using the surface classification method.For P3-Pn, the recursive expression of genus distribution is obtained by using the method of combined tree and the method of distribution decomposition, and then the genus distribution is calculated by computer programming.In addition, the genus distributions of several kinds of ladder graphs are obtained.In chapter 3, we study the correlation between the unimodal property and logarithmic concave of polynomial sequences.In the second part, we obtain the criterion of whether the linear combination of finite unimodal sequences is unimodal, in the third part, we review that the genus distribution of ladder graph surface set is unimodal or logarithmic concave, and give the peak point formula of the genus distribution of ladder graph surface set.In the fourth part, we prove the unimodal property of the genus distribution of some ladder graphs, and give the peak point formula of the genus distribution of these ladder graphs.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】