跳到主要內容

臺灣博碩士論文加值系統

(44.211.31.134) 您好!臺灣時間:2024/07/22 19:19
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:蔡燿陽
研究生(外文):Yau-Yang Tasi
論文名稱:網格圖上漢米爾頓路徑之決定
論文名稱(外文):The decision of Hamiltonian path in Mesh
指導教授:黃俊平黃俊平引用關係
學位類別:碩士
校院名稱:國立虎尾科技大學
系所名稱:工業工程與管理研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:66
中文關鍵詞:漢米爾頓路徑漢米爾頓迴路格子圖網格圖
外文關鍵詞:Hamiltonian pathHamiltonian cycleGrid graphMeshes
相關次數:
  • 被引用被引用:0
  • 點閱點閱:1380
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在實際空間中,直接求解路徑問題的困難度相當高,因而衍生出將路徑投射在網格的圖形上,以網格圖(Mesh)的圖形表示法來探討路徑最佳化的問題。網格圖為最原始的圖形表示法,造成許多研究論文以網格圖為出發點,將實際空間的結構加以簡化,以求取路徑問題的最佳解。

在三度空間中找出一條最佳路徑的問題是近代許多研究學者致力專精研究的主題,如:郵差問題(CPP)與旅行推銷員問題(TSP)等等,皆屬NP-complete的路徑問題,隨著節點數(vertices)越多,求解的困難度也越高。許多學者將實際的路徑問題簡化為2D的網格圖,試以所提之演算法求解,但求解前須判斷路徑是否有解,這方面一直是學者忽略的重點。

本論文研究可分為兩大部分,分別為:(1)矩形網格圖是否有漢米爾頓路徑;以及(2)劃分矩形網格圖成為2×2、2×3、3×2與3×3之基本單元的基本網格圖中是否有漢米爾頓路徑。上述兩個問題皆未有文獻探究。有鑑於此,本研究先後針對該兩項議題提出證明,爾後對其未來延展性詳加敘述,以利於對路徑問題有更深入的探討。
The essence of this thesis is to study the Hamiltonian path over a given mesh graph. The problem of solving Hamiltonian path is known as an NP-complete problem, and it is hard to handle in mathematics. The mesh is a special type of graph. All the edge of a mesh have the same length that locate along either the horizontal or the vertical directions. The rectangular mesh graphs are divided into the basic graphs in this thesis that include 2×2、2×3、3×2 and 3×3 subgraphs. The point of this research is to prove that a Hamiltonian path exists over the rectangular mesh graph that is a combination of the basic mesh graphs.
中文摘要 --------------------------------------------------------------------------- i
英文摘要 --------------------------------------------------------------------------- ii
誌謝 --------------------------------------------------------------------------- iii
目錄 --------------------------------------------------------------------------- iv
表目錄 --------------------------------------------------------------------------- vi
圖目錄 --------------------------------------------------------------------------- vii
第一章 緒論--------------------------------------------------------------------- 1
1.1. 研究背景--------------------------------------------------------------- 1
1.2. 研究目的--------------------------------------------------------------- 2
1.3. 研究限制--------------------------------------------------------------- 2
1.4. 研究流程--------------------------------------------------------------- 3
第二章 文獻探討--------------------------------------------------------------- 4
2.1. 圖論--------------------------------------------------------------------- 4
2.1.1. 圖論的由來------------------------------------------------------------ 5
2.1.2. 圖論的定義------------------------------------------------------------ 6
2.1.3. 圖論的應用範圍------------------------------------------------------ 7
2.2. 漢米爾頓路徑與漢米爾頓迴路------------------------------------ 8
2.2.1. 漢米爾頓--------------------------------------------------------------- 8
2.2.2. 漢米爾頓數學模式--------------------------------------------------- 8
2.3. 網格圖------------------------------------------------------------------ 9
2.3.1. 網格的基本定義------------------------------------------------------ 10
第三章 網格圖包含漢米爾頓路徑之證明--------------------------------- 13
3.1. 網格圖之漢米爾頓路徑之證明------------------------------------ 13
3.1.1. m×n網格圖------------------------------------------------------------ 13
3.1.2. 往復式漢米爾頓路徑------------------------------------------------ 15
3.1.3. 證明m×n網格圖含有漢米爾頓路徑------------------------------ 16
3.2. 網格圖劃分成基本網格圖之漢米爾頓路徑證明--------------- 22
3.2.1. 網格圖必定由基本網格圖所拼湊--------------------------------- 22
3.2.2. 規則性拼湊網格圖的漢米爾頓路徑走法------------------------ 23
3.2.3. 不規則性拼湊網格圖的漢米爾頓路徑--------------------------- 26
3.2.4. 區塊之結合------------------------------------------------------------ 31
第四章 討論--------------------------------------------------------------------- 34
4.1. 矩形禁止區塊之網格圖--------------------------------------------- 34
4.2. 不規則禁止區塊之網格圖------------------------------------------ 36
4.3. 特殊禁止區塊之網格圖--------------------------------------------- 37
第五章 結論與未來研究方向------------------------------------------------ 40
5.1. 結論--------------------------------------------------------------------- 40
5.2. 未來方向--------------------------------------------------------------- 40
參考文獻 --------------------------------------------------------------------------- 41
附錄一 --------------------------------------------------------------------------- 42
附錄二 --------------------------------------------------------------------------- 43
1.吳瑞瑜(2001),金字塔網路之漢彌爾頓性質,國立暨南國際大學,碩士論文。
2.柯為仁(2004),雙向旋轉圖上網格圖嵌入之研究,國立臺灣科技大學,碩士論文。
3.賴盈志、洪春男(2004),Generalized pancake graphs 的漢米爾頓容錯性質,大葉大學,碩士論文。
4.Afrati, F. (1994). “The hamilton circuit problem on grids”, Theoretical Informatics and Applications,Vol.28, pp. 567–582.
5.Arkin, E. M.、Mitchell, J. S. B.、Polishchuk, V. (2007). “Two New Classes of Hamiltonian Graphs”, Electronic Notes in Discrete Mathematics, Vol.29, pp.565-569.
6.Balakrishnan, R.、Ranganathan, K. (2000). “A textbook of graph theory” Springer-Verlag, pp. 107-108.
7.Chen, S. D.、Shen, H. & Topor, R.W. (1995). ” Efficient parallel permutation-based range-join algorithms on meshconnected computers”, in: Proceedings of the 1995 Asian Computing Science Conference, Pathumthani, Thailand, Springer-Verlag, pp. 225–238.
8.Chen, S. D.、Shen, H. & Topor, R.W. (2002).” Permutation-based range-join algorithms on N-dimensional meshes”, IEEE Transactions on Parallel and Distributed Systems, Vol.13, pp.413–431.
9.Chen, S. D.、Shen, H. & Topor, R.W. (2002). “An efficient algorithm for constructing hamiltonian paths in meshes”, Parallel Computing, Vol.28 , pp.1293-1305.
10.Garey, M. R.、Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York.
11.Itai, A.、Papadimitriou, C.、Szwarcfiter, J. (1982).” Hamilton paths in grid graphs”, SIAM Journal on Computing, Vol.11, pp.676–686.
12.Lee, C. Y. (1961). “An Algorithm for Path Connections and Its Applications” IRE Trans. On Electron. Computer, Vol. EC-10, pp.346-365
13.Sohel Rahman, M.、Kaykobad, M. (2005). ” On Hamiltonian cycles and Hamiltonian paths”, Information Processing Letters, Vol.94, pp.37–41.
14.Silvester, J.、Kleinrock, L. (1983). “On the capacity of multihop slottee ALOHA networks with regular structure”, IEEE Transactions on Communications COM-31, pp.947–982.
15.Umans, C.、Lenhart, W. (1997). “Hamiltonian Cycles in Solid Grid Graphs”, IEEE Foundations of Computer Science. Proceedings., 38th Annual Symposium on, pp.496–505.
16.West, D. B. (2001). Introduction to graph theory. Prentice-Hall.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊