若干图类的亏格分布研究

发布时间：2018-06-02 08:25

本文选题：亏格分布 + 部分亏格分布　；参考：《湖南师范大学》2016年博士论文

【摘要】：图的亏格分布是由著名的图论学家Gross上世纪80年代引入的,它是从整体上刻划图在给定的可定向曲面上的嵌入数量的分布情况,是图的一个重要拓扑不变量.其理论在判断图同构、复代数曲线模空间计算、理论物理中的量子场论、弦理论等领域中有应用.自上个世纪以来,国内外许多著名学者投入到这一领域的研究.如Gross、Mohar、 Stahl、Robertson、Seymour、Whiter、Tucker、Bonnington等等,以及国内刘彦佩、黄元秋、杨元生、蔡俊亮、任韩、郝荣霞、陈仪朝等人.但是Thomassen已经证明了计算一般图的亏格分布是一个NP-完备问题.由于其难度,到目前为止有关亏格分布的结果并不是很丰富,且能确定其亏格分布的图类基本上结构比较特殊,很多方法无法直接推广到一般的图形上.本文试图用一些新的方法探讨若干图类的亏格分布,已经取得了以下几个方面的结果：1.2011年,Gross在文献[15]中研究了根点u,v度均为2的双根图(G,u,v)在其根点自粘合后所得新图的亏格分布.本文第二章,利用删点、加边原理,多种乘法法则,自粘合定理给出了一个双根图在其中一个根点的度为任意大的情形下根点自粘合后图的亏格分布.从而推广了Gross在文献中[15]“两个根点度均为2”的相应结果.2.研究两个简单图的笛卡尔积的亏格分布问题是拓扑图论的核心问题.本文第三章引入一种新的加边运算,结合图的部分亏格分布,得到了D3×Pn(双极图D3与路Pn的笛卡尔积图)的亏格分布的递推表达式.3.计算外平面图的亏格分布是拓扑图论关注的一个问题.本文第四章考虑一类5-正则外平面图On的亏格分布.由n个基础图(R1,p,q)迭代粘合可得到一条开放链(Rn,p,q),对图(Rn,p,q)进行修改的加边运算可得到图On.本文利用根-图得到了图(Rn,p,q)的部分亏格分布与图On的亏格分布的迭代计算公式.4.本文第五章结合运用传递矩阵法与向量积矩阵法,得到了由双路图串联构建而成的两类闭链图的亏格分布计算公式及递推公式.
[Abstract]:The genus distribution of graphs was introduced by the famous graph theorist Gross in the 1980s. It is a global description of the distribution of the number of graphs embedded on a given orientable surface. It is an important topological invariant of a graph. Its theory has been applied in the fields of judgement graph isomorphism, complex algebraic curve module space calculation, quantum field theory in theoretical physics, string theory and so on. Since the last century, many famous scholars at home and abroad have devoted themselves to the research in this field. For example, Grossn Mohart, Stahln Robertsonn Seymourn Seymourt, Tucker Bonnington and so on, as well as Liu Yanpei, Huang Yuanqiu, Yang Yuansheng, Cai Junliang, Ren Han, Hao Rongxia, Chen Yi Chao and others in China. But Thomassen has proved that calculating the genus distribution of a general graph is an NP-complete problem. Because of its difficulty, up to now, the results about genus distribution are not very rich, and the graph class which can determine the genus distribution is basically very special, and many methods can not be directly extended to the general graph. In this paper, we try to study the genus distribution of some graph classes by some new methods. The following results have been obtained: 1. In [15], 2011 Gross studied the genus distribution of the new graphs obtained by the root point self-bonding. In the second chapter, by means of censored point, edge-adding principle, multiple multiplication rules and self-bonding theorem, we give the genus distribution of a biradical graph in the case that the degree of one of the root points is any large. In this paper, we generalize the corresponding result of Gross in [15] that the degree of two root points is both 2 ". The study of genus distribution of Cartesian product of two simple graphs is the core of topological graph theory. In chapter 3, a new edge-adding operation is introduced. Combining with the partial genus distribution of graphs, the recursive expression of genus distribution of D3 脳 Pn (dipole graph D3 and Cartesian product graph of path PN) is obtained. Calculating the genus distribution of outerplanar graphs is an important problem in topological graph theory. In chapter 4, we consider the genus distribution of a class of 5-regular outerplanar graphs on. An open chain can be obtained by means of the iterative bonding of n basic graphs R1 / PX), and the edge-adding operation for the modification of the graph RnnPU (Q) can be obtained by the edge-adding operation on the graph On. In this paper, by using root-graph, the iterative formulas of partial genus distribution and genus distribution of graph on are obtained. In the fifth chapter, by using transfer matrix method and vector product matrix method, the formulas of genus distribution and recursion of two kinds of closed chain graphs are obtained.
【学位授予单位】：湖南师范大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】