交錯立方體網路之容錯可嵌入環型結構性質

Abstract

在網路的架構之中，超方體是一個經常被使用的結構。但超方體中有一些特性如直徑的長度並不是非常理想，所以許多人提出其超方體的各式變形超方體。而其中又以交錯超方體的性質最為完美，在本篇論文中我們將以此交錯超方體為討論的主題。而在網路當中最重要的就是網路的容錯性質，當有任何的錯誤發生，我們必須保證網路仍能正常無誤。為了使網路可以有更加的容錯性質，我們便將最常使用的環狀結構可否完整的嵌入至特定的網路拓撲架構；作為判斷的一個指標。所以若能在有錯誤之下，我們仍可以將環狀架構嵌入；將代表此網路架構擁有極佳的容錯特性，有極高的可靠度。因此我們將在此篇論文中，證明交錯立方體在有錯誤之下，仍然可以把環型結構嵌入。

In the network architecture, hypercube Qn is a popular one. Hypercube has many good properties including regularity, symmetry, hamiltonicity, etc. However, there are several variations of the hypercube which have some properties superior to the classical hypercubes. In 1992, Efe [11] proposed a new structure, Crossed Cube. The Crossed Cube CQn is one of the hypercube variant. It is shown in literature that CQn has several properties better than those of the hypercube. For example, the diameter of CQn is approximately one half of that of the hypercube Qn. An important characteristics of networks is the fault tolerant property and cycle embedding cabability. In the thesis, we study the Crossed Cube and we show that CQn is pancyclic, i.e. we can embed cycles of all lengths from 4 to |V(CQn)| into the crossed cube. Moreover, we prove that CQn is still pancyclic with up to n-2 edge/vertex faults.