跳到主要內容

臺灣博碩士論文加值系統

(216.73.216.81) 您好!臺灣時間:2025/10/07 00:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:郭榮裕
研究生(外文):Kuo, Jung-Yu
論文名稱:發展快速平面圖形嵌入演算法於圖形分割之研究
論文名稱(外文):The Development of an Efficient Planar Craph Embedding Algorithm for Graph Partitioning
指導教授:邱創乾邱創乾引用關係
學位類別:碩士
校院名稱:逢甲大學
系所名稱:自動控制工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1997
畢業學年度:85
語文別:中文
論文頁數:53
中文關鍵詞:圖形分割平面分割定理
相關次數:
  • 被引用被引用:0
  • 點閱點閱:245
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0

圖形的點分割是利用"分解並克服"的方法以解決圖形相關問題。這個方法的基本概念是將大型的圖形問題分割成獨立且大小相近的子問題,這些子問題可被一一求得解決,經由整合這些子問題的答案可求得原始問題的解答。其中一種可應用的方法為平面圖形分割,此方法的基礎是源自於1979年Lipton與Tarjan所提出的平面分割定理;然而,對於分割一個有大量圈點的圖形時,有一個瓶頸產生,這個瓶頸出現在平面圖形嵌入的部份。當圖形被分割時,必需獲得圖形的平面性及平面圖映在平面上的組成,而此過程將耗費大量的時問及記憶體空間。本研究的主要目的即是發展一個快速平面圖形嵌入演算法以改善平面圖形分割的效率。本研究的主要貢獻有三:藉由修改Hopcroft 與Tarjan所提出複雜度為σ(N)的平面測試演算法以找出平面圖映在平面上的組成,並以此演算法代替過去所使用Demoucron等人所提出複雜度為σ(N2)的平面測試演算法,N為圖形圈點總數;所發展的演算法可用於平面圖形分割並獲得效率上的改善;發展出一個圖形介面的操作軟體用以實現並展示圖形理論演算法則。


Vertex partitioning of graphs is applied to the "divide-and-conquer" approaches for solving combinatorial problems. The underlying concept in the method is to divide the original problem into independent multiple subproblems for roughly the same size. The subproblems are then solved recursively and combined to provide a solution to the large problem. The planar separator theorem of Lipton and Tarjan provides a basis of this approach. However, there is a "bottleneck" in the process of partitioning a very large graph, this bottleneck appears in the planarity testing operation. Before a graph is partitioned, certain planarity breaking arcs need to be extracted, and the planar embedding for a large graph is extremely time and space consuming. The main purpose of this research is to develop an efficient planar embedding algorithm for planar graph partitioning.
The major contributions of this thesis are summarized: (1) The planarity testing algorithm proposed by Hopcroft and Tarjan with complexity σ(N) is modified in order to make the construction of a planar representation. This approach is to replace the previous algorithm which was the Demoucron el al. planar embedding algorithm with complexity σ(N). where N is the total number of vertices in the graph. (2) The proposed algorithm is used to improve the efficiency for planar graph partitioning. (3) A graphical interface is developed to provide user-friendly operation environment for graph-theoretic algorithms.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top