標題: 有錯單一方向性之超立方體中環形圖之嵌入Fault-Free Ring Embedding in Faulty Uni-directional Hypercube 作者: 曾偉富徐力行Lih-Hsing Hsu資訊科學與工程研究所 關鍵字: 漢彌爾頓環路;容錯;超立方體;單一方向性超立方體;hypercube;uni-directional hypercube;fault-tolerant;hamiltonian 公開日期: 2000 摘要: 在這篇論文裡,我們針對單一方向性的超立方體 (UQn) 結構, 做進一步的研究， 首先， 在UQn中， 在n 是偶數且 n 大於或等於 4 的情況下， 當 UQn 最多發生 (n-2)/2 條連接線錯誤時， 我們證明它可以內含一個漢彌爾頓環路， 而這是最佳的結果。 進而， 我們證明出當 UQn 中發生的連接線和節點的錯誤總和小於或等於 (n-2)/2 時， UQn 裡依然可以內含一個長度為 2n - 4fv 的漢彌爾頓環路 (fv為錯誤節點之數量)。A uni-directional hypercube, denoted UQn, is an n-dimensional hypercube, denoted Qn, with simplex uni-directional links. While accommodating large number of nodes, UQn requires less complicated communication than the hypercubes. In addition, they alleviate the pin-limitation problem encountered in fabricating VLSI hypercubes and allow hypercube implementation of the Metropolitan Area Networks using optical fiber links. In this paper, we prove that UQn is (n-2)/2 - edge hamiltonian. That is, in UQn, up to (n-2)/2 links can fail without destroying all available hamiltonian cycles. This result is optimal. Moreover, we prove that a ring of length 2n - 4fv can be embedded in a faulty UQn with |fe| + |fv| (n-2)/2 faulty edges and vertices where fe are faulty edges and fv are faulty nodes. URI: http://140.113.39.130/cdrfb3/record/nctu/#NT890394044http://hdl.handle.net/11536/66947 Appears in Collections: Thesis