蝴蝶圖, 遞迴式循環圖及立方體上漢米爾頓容錯性質的研究

Abstract

一個分散式系統網路連接的拓樸是提昇分散式系統效能的重要決定因素之一，設計一連結網路必須考量很多因素，其中漢米爾頓性質是建構一連接網路拓樸主要考量的因素之一。此外容錯性質也是備受需要考量的，因為當處理器增加時，網路失誤率也會提高。一個圖形G去掉k個以下錯誤後仍然還可以存在一漢米爾頓迴路則G稱為k-漢米爾頓圖形，如果G是所有與G有相同點數的k-漢米爾頓圖形中擁有最少個邊的圖形則G 是最佳化的k-漢米爾頓圖形。研究最佳化的k-漢米爾頓圖形動機是來自於設計一擁有最佳容錯性質的環狀網路。 本論文研究主要討論三種著名的連結網路族群的漢米爾頓容錯性質；分別是蝴蝶圖、遞迴式循環網路圖和立方體圖。在論文中圖形錯誤的元素集合以F表示，同時fv表示F中錯誤的點數。 一般討論一個圖形G的漢米爾頓化性質是指G是否是漢米爾頓圖形或者G是否是漢米爾頓連接圖形。由於二分圖形不是漢米爾頓連接圖形，所以Simmon[35] 介紹了在二分圖形中漢米爾頓雷絲化的性質。例如n維度的超立方體Qn是一有名的二分圖形，假設F是Qn中邊的集合且元素個數小於或等於n-2，我們證明了Qn-F中對任意在不同分區的二點一定存在一條漢米爾頓路徑連接他們，同時在相同分區的任何二點一定存在一條長2n-2的路徑連接他們。另一方面當F中的元素個數小於或等於n-3時，對任何一點v我們也證明了在Qn-{v}-F中，任何與v不同分區的二點一定存在一條漢米爾頓路徑連接他們。另外，我們也證明了即使Qn發生了n-2個邊錯誤，仍然存在長度為任意偶數的迴圈經過給定的一條邊。 對於n×2n個點的n維度蝴蝶圖網路BFn，當F中元素的個數小於或等於2時，我們證明了BFn-F擁有一長度為n´2n-2fv的迴路，而且當n為奇數時BFn是最佳化的2-漢米爾頓圖形。 遞迴式循環圖G(cdk,d) 是一種正規點對稱圖形，而且可以用遞迴的方式建構。在本篇論文中我們證明了當F中的元素個數小於或等於此圖形的維度減2時，在c和d都是偶數或者c是奇數時，G(cdk,d)-F仍具有漢米爾頓迴路，同時若當F中的元素個數小於或等於此圖形的維度減3時，此種遞迴式循環圖G(cdk,d)-F中之任何兩點都可找到一條漢米爾頓路徑連接他們。

The performance of a distributed system is significantly determined by its network topology. Designing the topology of interconnection network involves mutually conflicting requirements. One of the major requirements in designing the topology of networks is the hamiltonicity. On the other hand, fault tolerance is highly desirable for massive parallel systems which have relative high probability of failure. For a positive integer k, a graph G = (V,E) is k-hamiltonian if G-F is hamiltonian for any F Í VÈE with |F| £ k. A k-hamiltonian graph G is optimal if it contains the least number of edges among all k-hamiltonian graphs with the same number of vertices as G. The study of optimal k-hamiltonian graphs is motivated from the design of optimal fault-tolerant token rings in computer networks. This research studied fault-tolerant hamiltonicities of three famous family interconnection networks, namely wrapped butterfly graphs, recursive circulant graphs, and hypercubes. In this thesis, F denotes the fault set of the graph and fv denotes the number of faulty node in F. When the hamiltonicity of a graph G is concerned, it is usual to investigate whether G is hamiltonian or hamiltonian-connected. Since a bipartite graph is not hamiltonian-connected, Simmons[35] introduced the concept of hamiltonian laceability for class of bipartite graphs. It is known that every hypercube Qn is a bipartite graph. Assume that n ³ 2 and F is a subset of edges with |F| £ n-2. We prove that there exists a hamiltonian path in Qn -F between any two vertices of different partite sets. Moreover, there exists a path of length 2n-2 between any two vertices of the same partite set. Assume that n ³ 3 and |F| £ n-3. We prove that there exists a hamiltonian path in Qn-{v}-F between any two vertices in the partite set without node v. In addition, it is shown that Qn contains every even cycle even if it has n-2 edge faults. Let BFn denote the n-dimensional wrapped butterfly graph with n2n vertices. When |F| £ 2, we prove that BFn-F contains a cycle of length n2n-2fv. Moreover, BFn-F contains a cycle of length n2n-fv if n is an odd integer. In other words, BFn is optimal 2-hamiltonian regular graph if n is an odd integer. A recursive circulant graph G(cdk,d) is a circulant graph with cdk vertices and jumps of powers of d where d ³ 2 and 2£c£d. We also prove that G(cdk,d)-F remains hamiltonian when it is not a bipartite graph and |F| £ deg(G(cdk,d))-2, where deg(G(cdk,d)) denotes a degree of G(cdk,d). Moreover, we prove that for any two vertices u and v in V(G(cdk,d))-F, there exists a hamiltonian path of G(cdk,d)-F joining u and v, when it is not a bipartite graph and |F| £ deg(G(cdk,d))-3. Furthermore, all bounds are tight.