【作者】 董广华；

【导师】 刘彦佩；

【作者基本信息】 北京交通大学 ， 运筹学与控制论， 2009， 博士

【摘要】 拓扑图论最初是研究怎样把图画在曲面上使得任何两条边互不相交,这个直观的几何问题随着其它数学分支,特别是代数拓扑、群论、组合计数理论以及算法分析等的介入而变得丰富多彩.目前拓扑图论的研究领域可分为两个主流:一是研究图在曲面上嵌入的性质;另一个研究地图计数问题.本文研究属第一个方面,即研究图的嵌入的最大亏格问题.连通图G在紧的闭曲面S上的嵌入指存在一个同胚映射Φ:G→S使得S-Φ(G)的每个连通分支都同胚于一个开圆盘,这样的嵌入称为胞腔嵌入.根据S是可定向曲面或者是不可定向曲面,这样的嵌入又分别称为可定向嵌入或不可定向嵌入.图G的最大亏格指图G所能嵌入曲面的亏格中最大的那一个.因为图的任何嵌入必至少含有一个面,由欧拉公式易得图的最大亏格的一个上界:其中符号[α]指不超过α的最大整数,|E(G)|-|V(G)|+1被称为图G=(V(G).E(G))的Betti数并用符号β(G)表示.如果γ_M(G)=[(?)],则图G被称为上可嵌入的.最大亏格问题起源于Nordhaus、Stewart和White1971年的文章[31],刘彦佩[21]和Xuong[38]于1979年分别独立地得到了关于图的嵌入的最大亏格的经典定理,随后,由于诸多学者对这一问题的关注与研究使得这一问题取得重大进展.其研究分为两个方面:一是图的上可嵌入性的研究;二是对非上可嵌入图的最大亏格的界的研究.因为任意图在不可定向曲面上总是上可嵌入的,因此最大亏格问题只讨论图在可定向曲面上的嵌入.在本论文中,一方面,借助已有的研究成果对图的最大亏格问题进行了深入地研究,得出了一些新结果,改进了一些已知结果;另一方面,借助刘彦佩提出的联树法,对最大亏格问题从另一个方面进行了一些尝试性的研究,并取得一些初步进展.本文可分为以下几个部分:第一章介绍图的最大亏格问题的背景知识以及一些基本概念和术语.第二章研究了直径-3图中的加边运算与最大亏格.第三章结合图的围长以及相邻顶点或非邻顶点的度和研究图的上可嵌入性.第四章研究非上可嵌入图的最大亏格的下界问题.第五章借助联树模型研究图的最大亏格.第六章介绍了一些需要进一步研究的问题.更多还原

【Abstract】 To study the drawing of a graph on a surface such that no two edges cross, which is an intuitive geometric problem, is the primitive objective of topological graph theory. Armed with other mathematical branches such as algebraic topology and group theory, and enumerative combinatorics, and the analysis of algorithms. topological graph theory has been becoming more and more meaningful.There are two fields in topological graph theory: one is the study of the properties of graph embedding. and the other is the enumerative theory of maps. This paper concerns the maximum genus of graphs which belongs to the first field.The embedding of a graph G on a surface S is such a homeomorphismΦ:G→S that each connected component of S-Φ(G) is homeomorphic to a open disk. According to S is orientable or nonoricntable surface, the embeddingΦof G on S is called orientable embedding or nonorientable embedding respectively. The maximum genusγ_M(G) of a connected graph G is the maximum integer k such that there exists an embedding of G into the orientable surface of genus k. Since any embedding must have at least one face, the Euler characteristic for one face leads to an upper bound on the maximum genuswhere the number |E(G)|- |V(G)|+1 is known as the Betti number (or cycle rank) of the connected graph G and is denoted byβ(G). A graph G is said to be up-embeddable ifγ_M(G)=(?).The idea of the maximum genusγ_M/(G) of a connected graph G was introduced by Nordhaus. Stewart and White [31] in 1971. In 1979, Liu[21] and Xuong|38] obtained the classical Theorem on the maximum genus independently. From then on. many researchers have studied the problem and obtained many interesting results. The research on maximum genus is mainly focused on two aspects: one is the study of the up-embeddability of graphs, and the other is the lower bound on the maximum genus of non-up-embeddable graphs. Because every graph is up-embeddable on non-orient able surfaces, the maximum genus problem only study orientable embeddings.This thesis consists of two parts: one is the deeper study of the maximum genus via the results obtained in the foretime: the other is an attempt on the studying of the maximum genus through joint tree, which is established by Liu Yanpei. The thesis are composed of the following six chapters:In chapter 1, the background of the maximum genus and some definitions and terminologies are provided.In chapter 2, the relation between the maximum genus and the edge-adding operation on graphs of diameter 3 are discussed.Chapter 3 is focused on the study of up-embeddability of graphs via girth and the degree-sum of adjacent vertices or nonadjacent vertices.In chapter 4 the lower bound of the maximum genus of graphs non-upembeddablc is discussed.Chapter 5 focuses on the study of the maximum genus of graphs via joint tree model.Chapter 6 consists of some problems worth studying further.更多还原