本文關(guān)鍵詞：圖上短圈及其相關(guān)問題的研究　出處：《中央民族大學》2017年碩士論文　論文類型：學位論文

  更多相關(guān)文章： 最短路徑 廣探樹 基本圈 最短圈 Π-嵌入圖

【摘要】：本文主要是通過廣探樹找曲面嵌入圖中幾類最短圈,這些研究在圖論的研究中有著重要的地位.本文在第三章中重點研究如何找連通圖的廣探樹問題,對邊權(quán)相同的賦權(quán)連通圖和邊權(quán)不同的賦權(quán)連通圖,分別進行了研究.在對圖進行廣度優(yōu)先遍歷的過程中找到了一棵廣度優(yōu)先樹,并總結(jié)出:對于邊權(quán)相同的圖而言,至多在O(n)階多項式步驟下可以找到圖的一棵廣探樹;對于邊權(quán)不同的圖而言,至多在O(n2)階多項式步驟下可以找到圖的一棵廣探樹.本文在第四章中重點研究如何找n-嵌入圖的最短圈問題,對可嵌入到曲面上邊權(quán)相同的賦權(quán)連通圖和邊權(quán)不同的賦權(quán)連通圖,分別進行了研究.第一節(jié)中具體的結(jié)論如下:對于嵌入到曲面上的邊權(quán)相同的圖而言,如果Π-嵌入圖上存在n-雙側(cè)圈,那么至多在O((n+m2)n)階多項式步驟下可以找到圖的一個最短Π-雙側(cè)圈.如果n-嵌入圖上存在可分離圈,那么至多在O((n+m2)n)階多項式時間下可以找到圖的一個最短n-可分離圈.另外,對于一種特殊的曲面嵌入圖——大邊寬嵌入圖而言,其中圖G的邊權(quán)相同,如果G的圍長g(G)≥5,那么至多在O((n+m)n 階多項式步驟下可以找到圖G的一個最短曲面可收縮圈.第二節(jié)中具體的結(jié)論如下:對于嵌入到曲面上的邊權(quán)不同的圖而言,如果Π-嵌入圖上存在Π-雙側(cè)圈,那么至多在O(n2+m2)n)階多項式步驟下可以找到圖的一個最短Π-雙側(cè)圈.如果Π-嵌入圖上存在Π-可分離圈,那么至多在O((n2+m2)n)階多項式步驟下可以找到圖的一個最短Π-可分離圈.另外,對于一種特殊的曲面嵌入圖——大邊寬嵌入圖而言,其中圖G的邊權(quán)不相同,如果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