簡易檢索 / 詳目顯示
| 研究生： |
陳俊吉 Chen, Jiun-Ji |
|---|---|
| 論文名稱： |
卡氏積圖之容錯超漢彌頓性質 Fault-Tolerant Super-Hamiltonicity ot the Cartesian Product Graph |
| 指導教授： |
謝孫源
Hsieh, Sun-Yuan |
| 學位類別： |
碩士 Master |
| 系所名稱： |
電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年： | 2006 |
| 畢業學年度： | 94 |
| 語文別： | 英文 |
| 論文頁數： | 31 |
| 中文關鍵詞： | 容錯漢彌頓性 、卡氏積圖型 、卡氏積 、超漢彌頓性 、容錯 、k 維度 、容錯漢彌頓連接性 |
| 外文關鍵詞： | k-regular, Hamiltonian, Hamiltonian connected, Fault-tolerant, Super fault-tolerant Hamiltonian, Cartesian product, Cartesian product graphs |
| 相關次數： | 點閱：130 下載：2 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
一個k維度並具有漢彌頓環路且有漢彌頓連接性的圖型稱為超漢彌頓圖型。它會在移除k - 2個點、邊後仍然具有漢彌頓環路，並在移除k - 3個點、邊後仍然有漢彌頓連接性。因此，超漢彌頓圖型可說是具有最佳的容錯能力的漢彌頓圖型。在本論文中，我們的目的是進一步證明，以兩個超漢彌頓圖型經過卡氏積圖型運算後，所形成的圖型依然是個超漢彌頓圖型。
A k-regular Hamiltonian and Hamiltonian connected graph is called super fault-tolerant Hamiltonian if and only if it remains Hamiltonian after removing at most k - 2 nodes and/or edges and remains Hamiltonian connected after removing at most k - 3 nodes and/or edges. A super fault-tolerant Hamiltonian graph has a certain optimal favor with respect to the fault-tolerant Hamiltonicity and Hamiltonian connectivity. In this thesis, we investigate a method to find Hamiltonian cycles and Hamiltonian connectivity in graphs constructed by Cartesian product from any two super fault-tolerant Hamiltonian graph. Therefore, the Cartesian product of two super fault-tolerant Hamiltonian graph is also a super fault-tolerant Hamiltonian graph.
[1]W.T. Huang, Y.C. Chuang, J.M Tan, L.H Hsu, "Fault-free Hamiltonain cycle in faulty Mobius cubes," J.Comput. Syst. 4(2000) 106-114.
[2]W.T. Huang, M.Y. Lin, J.M.Tan, L.H.Hsu, "Fault-tolerant ring embedding in faulty crossed cubes," in Proceeding of world Multiconf.Syst., Cybernetic and Inform. SCI'2000 IV, pp.97-102,2000.
[3]W.T.Huang, J.M.Tan, C.N.Hung, L.H.Hsu, "Fault-tolerant Hamiltonicity of twisted cubes," J.Paralled Distrib. Comput. 62(2002) 591-604.
[4]Y. C. Chen, C. H. Tsai, L. H. Hsu, J. J. M. Tan, "On some super fault-tolerant Hamiltonian graphs," Applied Mathmatics and Computation, vol. 148, pp. 729--741, 2004.
校內：2009-09-14公開校外：2009-09-14公開