雙扭立方體及交錯立方體網路之拓樸性質

Abstract

交錯立方體是超立方體的一種變形,在本論文中對交錯立方體我們先發展 出一個新的最短路徑演算法,它可在O(n)的時間內產生多條最短路徑,因此 改進原作者O(n^2)時間內產一條最短路徑之演算法. 依據我們的最短路徑 演算法,提出一個評估連結網路的新參數,稱之為邊壅塞度,然後求雙割寬 度,由雙割寬度我們可得到連結網路之邊壅塞度,然而邊壅塞度和雙割寬度 間存在有一關係式,這關係式使得原本分別難求的問題變得單純易找. 同 時對交錯立方體及雙扭立方體,我們亦證明它們的寬度直徑和容錯直徑是 超立方體之一半, 並且兩者都存在有長度大於4 的任意圓環. An n-dimensional crossed cube is a variation of hypercube. In this thesis,we give a new shortest path routing algorithm. In comparison with Efe'salgorithm which generates one shortest path in O(n^2) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortestpath routing algorithm, we define a new performance measure of interconnection networks called edge congestion. Using our shortest pathrouting algorithm and assnming that message exchange between all pairs ofvertices are equally probable, we first show that the edge congestion ofcrossed cube is no larger than the edge congestion of hypercubes, then we prove that the bisection width and edge congestion of the crossed cube are2^(n-1) and 2^n, respectively. We also find a relationship between edge edge congestion and bisection width. Such relation provides some bounds of thesetwo parameters for some graphs. We also prove that wide diameter and fault diameter of crossed cubes are (n/2)+2. Furthermore, we study embedding ofcycles in crossed cubes and construct more types of cycles of an arbitrarylength at least four.Similarly, twisted cube is derived by changing some connections of hypercubeaccording to specific rules. We prove that wide diameter and fault diameterof twisted cubes are (n/2)+2. We also show that twisted cube is a pancyclicnetwork that is cycles of an arbitrary length at least four.