立方體家族之環路嵌入

Abstract

在這篇論文中，我們探討k-陣列n立方體(k-ary n-cube)在漢米爾頓(Hamiltonian)與漢米爾頓連結(Hamiltonian connected)特性上面的容錯能力，k-陣列n立方體是一個二分圖(bipartite graphs)若且唯若k是偶數，令F為點和╱或邊的錯集合，且令k □ 3為奇數，當|F| □ 2n-2，我們證明在一個有錯的k-陣列n-立方體之中，存在一個漢米爾頓迴圈，另外，當|F| □ 2n-3，我們證明在有錯的k-陣列n-立方體之中，對於任意兩個點，都存在一條漢米爾頓路徑連結這兩個點，因為k-陣列n-立方體是一個2n-正則圖，在最壞的情況下，2n-3和2n-2的容錯程度都是最佳的了。 雙扭立方體(twisted cubes)、交叉立方體(crossed cubes)、梅氏立方體(möbius cubes)都是超立方體(hypercube)之外可供選擇的連結網路，而且，這三個連結網路的直徑都只有超立方體的一半而已，最近，有人證明了梅氏立方體擁有泛迴圈的特性，也就是說，各種長度至少為四的迴圈都可以嵌入它，由於容錯能力在平行處理領域的重要性，在這篇論文中，我們研究雙扭立方體、交叉立方體、梅氏立方體可同時容錯點和邊的特性，我們證明了他們都是(n-2)-容錯泛迴圈圖，亦即，當錯不超過n-2時，有錯的他們都是泛迴圈圖，再者，我們的結果已經是最佳的，因為如果有n-1個錯的話，就不能保證存在某種長度的迴圈。 另外，我們也證明了超立方體Qn是(2n-5)-條件式容錯二分泛迴圈圖，令F □ E(Qn)為超立方體之中錯的邊，然後，我們證明了，在條件不成立並且|F| □ 2n-3的時候，有錯的超立方體含有除了漢米爾頓迴圈的各種偶數長度的迴圈，所以，當錯邊最多為2n-5並且錯邊可以任意分布的時候，我們在有錯的超立方體之中找到各種可能長度的迴圈。

In this dissertation, we investigate fault-tolerant capabilities of the $k$-ary $n$-cubes with respect to the hamiltonian and hamiltonian connected properties. The $k$-ary $n$-cube is a bipartite graph if and only if $k$ is an even integer. Let $F$ be a faulty set with nodes and/or links, and let $k\geq 3$ be an odd integer. When $|F|\leq 2n-2$, we show that there exists a hamiltonian cycle in a wounded $k$-ary $n$-cube. In addition, when $|F|\leq 2n-3$, we prove that, for two arbitrary nodes, there exists a hamiltonian path connecting these two nodes in a wounded $k$-ary $n$-cube. Since the $k$-ary $n$-cube is regular of degree $2n$, the degrees of fault-tolerance $2n-3$ and $2n-2$ respectively, are optimal in the worst case.

The M\"{o}bius cube $MQ_n$, crossed cube $CQ_n$, and twisted cube $TQ_n$ are alternatives to the popular hypercube network. However, the diameters of these three interconnection networks are about one half of that of the hypercube. Recently, $MQ_n$ was shown to be pancyclic, i.e., cycles of any length at least four can be embedded into it. Due to the importance of the fault tolerance in the parallel processing area, in this dissertation, we study injured $MQ_n$, $CQ_n$, and $TQ_n$ with mixed node and link faults. We show that they are $(n-2)$-fault-tolerant pancyclic for $n\geq 3$, that is, injured $n$-dimensional $MQ_n$, $CQ_n$, and $TQ_n$ are still pancyclic with up to $(n-2)$ faults. Furthermore, our results are optimal in the sense that if there are $n-1$ faults, there is no guarantee of having a cycle of a certain length in them.

The hypercube $Q_n$ is one of the most popular networks. In this dissertation , we first prove that the $n$-dimensional hypercube is $2n-5$ conditional fault-bipancyclic. That is, an injured hypercube with up to $2n-5$ faulty links has a cycle of length $l$ for every even $4\leq l\leq 2^n$ when each node of the hypercube is incident with at least two healthy links. In addition, if a certain node is incident with less than two healthy links, we show that an injured hypercube contains cycles of all even lengths except hamiltonian cycles with up to $2n-3$ faulty links. Furthermore, the above two results are optimal. In conclusion, we find cycles of all possible lengths in injured hypercubes with up to $2n-5$ faulty links under all possible fault distributions.