图上短圈及其相关问题的研究

发布时间：2018-01-05 14:18

  本文关键词：图上短圈及其相关问题的研究　出处：《中央民族大学》2017年硕士论文　论文类型：学位论文

  更多相关文章： 最短路径 广探树 基本圈 最短圈 Π-嵌入图

【摘要】：本文主要是通过广探树找曲面嵌入图中几类最短圈,这些研究在图论的研究中有着重要的地位.本文在第三章中重点研究如何找连通图的广探树问题,对边权相同的赋权连通图和边权不同的赋权连通图,分别进行了研究.在对图进行广度优先遍历的过程中找到了一棵广度优先树,并总结出:对于边权相同的图而言,至多在O(n)阶多项式步骤下可以找到图的一棵广探树;对于边权不同的图而言,至多在O(n2)阶多项式步骤下可以找到图的一棵广探树.本文在第四章中重点研究如何找n-嵌入图的最短圈问题,对可嵌入到曲面上边权相同的赋权连通图和边权不同的赋权连通图,分别进行了研究.第一节中具体的结论如下:对于嵌入到曲面上的边权相同的图而言,如果Π-嵌入图上存在n-双侧圈,那么至多在O((n+m2)n)阶多项式步骤下可以找到图的一个最短Π-双侧圈.如果n-嵌入图上存在可分离圈,那么至多在O((n+m2)n)阶多项式时间下可以找到图的一个最短n-可分离圈.另外,对于一种特殊的曲面嵌入图——大边宽嵌入图而言,其中图G的边权相同,如果G的围长g(G)≥5,那么至多在O((n+m)n 阶多项式步骤下可以找到图G的一个最短曲面可收缩圈.第二节中具体的结论如下:对于嵌入到曲面上的边权不同的图而言,如果Π-嵌入图上存在Π-双侧圈,那么至多在O(n2+m2)n)阶多项式步骤下可以找到图的一个最短Π-双侧圈.如果Π-嵌入图上存在Π-可分离圈,那么至多在O((n2+m2)n)阶多项式步骤下可以找到图的一个最短Π-可分离圈.另外,对于一种特殊的曲面嵌入图——大边宽嵌入图而言,其中图G的边权不相同,如果G的围长g(G)≥5,那么至多在O((n2+m)n)阶多项式步骤下可以找到图G的一个最短曲面可收缩圈.
[Abstract]:In this paper, several types of shortest cycles in curved surface embedding graph are found through extensive tree exploration, which plays an important role in the study of graph theory. In the third chapter, we focus on how to find the extensive tree problem of connected graph. The weighted connected graph with the same edge weight and the weighted connected graph with different edge weight are studied, and a breadth-first tree is found in the process of breadth-first traversal of the graph. It is concluded that, for graphs with the same edge weight, at most, an extensive tree can be found under the order polynomial step. For graphs with different edge weights, at most, we can find a general tree of graphs under the polynomial steps of order Ohn 2. In Chapter 4th, we focus on how to find the shortest cycles of n-embedded graphs. The weighted connected graph with the same edge weight and the weighted connected graph with different edge weights are studied respectively. The concrete conclusions in the first section are as follows: for the graph with the same edge weight embedded on the surface. If there are n-bilateral cycles on a graph, then at most one of the shortest 蟺 -bilateral cycles of a graph can be found under the polynomial step of order n ~ (2). If there is a detachable cycle on the n-embedded graph. At most, a shortest n- detachable cycle of a graph can be found at the polynomial time of order n ~ (2). In addition, for a special surface embedding graph-large edge width embedding graph. Where the edge weight of graph G is the same, if the girth of G is 鈮，

本文编号：1383479