最大區域連通度與邊泛迴圈之條件式容錯度之研究

Abstract

容錯度的問題己經是個相當廣泛討論的主題。在這篇論文當中，我們在幾個連結網路上研究了一些條件式容錯度的特性。首先，我們討論在n維度的超立方體網路中，當每個節點都必需要兩個好的節點與其相連時，任何2n-5個的邊壞掉的情形下，對任意一個邊都可以找到長度從6到2n的迴圈通過這個邊。並且証明出此結果為最佳結果。 接著我們在類超立方體網路中對Menger定理做了研究。我們証明在n維度的類超立方體網路中，在壞掉n-2個節點之後，對任意一對點u跟v皆可以找到min{deg(u), deg(v)}條vertex-disjoint的路徑連結這兩個點。若給予每個節點都必需要兩個好的節點與其相連的條件下，則容錯度可以上升到2n-5。 最後我們定義了一對一及一對多兩種最大區域連通度的特性。我們証明了在k+1正規MCNs網路中，在壞掉容錯於小於k-1的情形下，都具有一對一及一對多的最大區域連通度的特性。進一步的我們也討論在k+1正規MCNs網路中，任意拔除f個點，對於任意獨立兩個大小為t的點集合中，可以找到t條vertex-disjoint的路徑連結這兩個點集合，其中f和t存在著f+t≦2k的情形。我們也針對由transposition tree生成的Cayley graph做相關的研究。在n-1正規式transposition tree生成的Cayley網路中，容錯度在n-3的情形下皆有一對一及一對多的區域性連通度的特性。

The problem of fault-tolerance has been discussed widely. In this thesis, we study several properties with conditional fault on some interconnection networks. First of all, we show that for any set of faulty edges F of an n-dimensional hypercube Qn with F ≦2n-5, each edge of the faulty hypercube Qn -F lies on a cycle of every even length from 6 to 2n with each vertex having at least two healthy edges adjacent to it, for n≧3. Moreover, this result is optimal in the sense that there is a set F of 2n-4 conditional faulty edges in Qn such that Qn -F contains no Hamiltonian cycle. Second, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercube-like networks with n-2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u),deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n-5 vertex faults. The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. Finally, we define two vertices to be maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. We prove that a (k+1)-regular Matching Composition Network is maximally local-connected, even if there are at most (k-1) faulty vertices in it. Moreover, we introduce the one-to-many and many-to-many versions of connectivity, and prove that a (k+1)-regular Matching Composition Network is not only (k-1)-fault-tolerant one-to-many maximally local-connected but also f-fault-tolerant many-to-many t-connected (which will be defined subsequently) if f+t=2k. In the same issue, we show that an (n-1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n-3) faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.