雙扭超方體,交錯超方體,和梅式超方體之容錯漢米爾頓性質

Abstract

一個 n 維雙扭超方體 (twisted cube)，TQn，是超方體 (hypercube) 的一種變形。在本論文中，我們首先提出建構偶數維度 (even-dimension-al) 雙扭超方體的建構法則。我們也探討在受傷 (faulty) 雙扭超方體中的漢米爾頓性質 (fault-tolerant amiltonicity)。令受傷集合 F 是 V(TQn) 連集 E(TQn) 的子集合。我們證明 TQn-F 仍然是漢米爾頓圖形(hamiltonian)，假如 |F| 大於等於 n-2。更進一步，我們證明在 V(TQn)-F 中給定任意兩節點 u 和 v，存在有一條漢米爾頓路徑(hamiltonian path) 於 XQn-F 中，假如 |F| 大於等於 n-3。TQn 的容錯漢米爾頓性質是 n-2 和容錯漢米爾頓連結性質 (fault-tolerant hamiltonian connectivity) 是 n-3，這兩者的結果都是最佳的。 類似的，一個 n 維交錯超方體 (crossed cube) 與梅氏超方體 (Möbiu cube) 兩者都是超方體的變形。在本論文中，我們證明最長漢米爾頓路徑能被建立在交錯超方體與梅氏超方體中。最特別的，在受傷交錯超方體與梅氏超方體中，我們證明在任意一對節點之間存在有一條漢米爾頓路徑。主要的，我們證明受傷交錯超方體與梅氏超方體包含 n-2 損壞 (faults)，仍然是漢米爾頓圖形。換句話說，長度是2n - fv 的環型 (ring) 可以被嵌入到受傷交錯超方體與梅氏超方體包含fv 損壞節點和 fe 損壞邊，此fv + fe 大於等於 n - 2 且 n 大於等於 3。最近的一個結果已經證明長度是 2n-2fv 的環型可以被嵌入到受傷超方體中，假設 fv+fe 大於等於 n-1 且 n 大於等於 4，具有一些限制。我們的結果和超方體中比較，證明較長的環型可以被嵌入到交錯超方體與梅氏超方體中且沒有限制。 環型結構 (cycle structure)，舉例號誌環 (token ring)，也常使用於地區網路 (local network) 的連接架構。而探討環型結構是否可嵌入某特定之網路拓撲架構，一直都是研究的重點問題。一個具有可嵌入環型結構的網路 (pancyclic network)，被定義為在這個網路內包含長度由4開始到節點總數之所有的環型。更進一步，應用這三種變形的容錯漢米爾頓連結度性質，我們證明它們都是環型結構的網路。

An n-dimensional twisted cube, TQ_n, is a variant of the hypercube. In this Dissertation, we first propose a construction method for even-dimensional twisted cubes. We also discuss the hamiltonian properties of faulty twisted cubes. Let the faulty set F be a subset of V(TQ_n) union E(TQ_n). We prove that TQ_n - F remains hamiltonian if |F| less than and equal to n-2. Moreover, we prove that given any two vertices u and v in V(TQ_n)-F there exists a hamiltonian path in TQ_n-F, if |F| less than and equal to n-3. Both of these two results are optimum in that the fault-tolerant hamiltonicity of TQ_n is at most n-2 and the hamiltonian connectivity of TQ_n is at most n-3. Similarly, both of an n-dimensional crossed cube, CQ_n, and an n-dimensional Mobius cube, MQ_n, are also variants of hyper-cubes according to specific rules. In this Dissertation, we showed that the longest fault-tolerant hamiltonian paths can be established in crossed cubes and Mobius cubes. In particular, we showed that there exists a hamiltonian path between any pair of vertices in a faulty CQ_n and a faulty MQ_n with n-3 faults. In addition, we prove that a faulty CQ_n and a faulty MQ_n remain hamiltonian with n-2 faults. That is, a ring of length 2^n-f_v can be embedded in a faulty CQ_n and a faulty MQ_n with f_v faulty nodes and f_e faulty edges, where f_v + f_e less than or equal to n-2 and n greater than or equal to 3. A recent result has shown that a ring of length 2^n-2f_v can be embedded in a faulty hypercube, if f_v+f_e less than or equal to n-1 and n greater than or equalto 4, with a few additional constraints. Our results, in comparison to hypercubes, show that longer rings can be embedded in CQ_n and MQ_n without additional constraints. Cycle structure, for example token ring, is often used as a connection structure for local area network. The problem of embedding a ring into different topologies of network is always an important topic research. A pancyclic network is defined to be a network that contains cycles from 4 to the total number of nodes in the network. Furthermore, using the hamiltonian connected property of these three variants, we show that they are all pancyclic networks.