跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.169) 您好!臺灣時間:2025/02/18 20:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林修懿
研究生(外文):Lin, Shiou-Yi
論文名稱:沒有任何連通度為四的平面圖形是一個可見圖
論文名稱(外文):No 4-Connected Planar Graph Could Be a Visibility Graph
指導教授:陳秋媛陳秋媛引用關係
指導教授(外文):Chen, Chiuyuan
學位類別:碩士
校院名稱:國立交通大學
系所名稱:應用數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:1993
畢業學年度:81
語文別:英文
論文頁數:18
中文關鍵詞:計算幾何學可見的可見圖平面圖
外文關鍵詞:Computational geometryvisibilityvisibility graphplanar graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:137
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
可見圖的判斷問題是: 給一個圖形, 判斷這個圖形是否是一個多邊形的可
見圖. 到目前為止我們仍不知道這個問題是否能在多項式時間內解出 .
一個圖形是可見圖的必要條件是: 必須存在至少一個漢彌頓循環, 而這
漢彌頓循環恰對應至多邊形的邊界. Tutte 證明了每一個連通度為四的平
面圖形都有漢彌頓循環, 但是在這篇論文裡我們將證明: 沒有任何連通度
為四的平面圖形會是一個可見圖. 此外我們也提出了一個多邊形具有平面
可見圖的充分必要條件.

The recognition problem for visibility graphs is, given a
graph, to determine whether this graph is the visibility graph
of a simple polygon. It is not known whether this problem could
be solved in polynomial time. A necessary condition for a graph
to be a visibility graph is the existence of at least one
Hamiltonian cycle, corresponding to the boundary of the
polygon. Tutte proved that every 4-connected planar graph has a
Hamiltonian cycle. However, in this thesis we shall prove that
no 4-connected planar graph could be a visibility graph. We
shall also give the necessary and sufficient conditions for a
polygon to have a planar visibility graph.

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