超級立方體網路之拓樸性質

Abstract

超級立方體(Supercubes)是超立方體(hypercubes)的一種變形, 在本論文中, 我們討論在超級立方體上任兩節點之間精確距離, 並且提出一個新的最短路徑演算法。 假設N與s均為正整數且2^s< N <= 2^{s+1}, 根據Auletta等學者的研究指出, 具有N個節點的超級立方體的容錯直徑(fault diameter) 在N不為2^{s+1}–1, 2^{s+1}+2以及 2^s+2^{s-1}+1時為s+1, 其餘狀況則為s+2。本論文中, 我們將指出以上的結果並不正確, 並且證明具有N個節點的超級立方體的容錯直徑(fault diameter) 在N為2^{s+1}-2^i +1, 0<= i <= s-1, 時為s+2。 同時我們將討論如何在超級立方體上的任意兩個節點之間建立若干條完全不重疊的路徑(數目與連結度, connectivity, 相等), 然後, 我們將證明N個節點的超級立方體的寬廣直徑(wide diameter)與容錯直徑(fault diameter) 在N為2^{s+1}–2^i+1, 0<=i<=s-1, 時為s+2, 其餘狀況則為s+1。

A supercube is a variation of hypercube. Usually each vertex of the (s+1)-dimensional hypercube is labeled with a unique integer k with 0<= k <= 2^{s+1}-1. The supercube S_N of N nodes with 2^s<N <= 2^{s+1} is constructed by merging nodes u and u-2^s, with N<= u <= 2^{s+1}-1, in the (s+1)-dimensional hypercube into a single node labeled as u-2^s and leaving other nodes in the (s+1)-dimensional hypercube unchanged. In this dissertation, we give the exact distance between any two nodes of supercube and present a new shortest path routing algorithm on S_N. Assume that $N$ and $s$ are positive integers with 2^s < N<= 2^{s+1}. It is claimed by Auletta, Rescigno, and Scarano that the fault diameter of the supercube with N nodes, is exactly s+1 if N \notin {2^{s+1}-1, 2^{s+1}-2, 2^s+2^{s-1}+1}, and s+2 otherwise. In this dissertation, we will argue that the above claim is not correct. Instead, we will show that the fault diameter of the supercube with N nodes is s+2 if N in {2^{s+1}-2^i+1|0<=i<=s-1}. Then we show how to construct k(S_N)disjoint paths between any two nodes of the supercube where k(S_N) is the connectivity of S_N. Finally, we compute the wide diameter and the fault diameter of S_N. We show that both the wide diameter and the fault diameter are equal to s+2 if N in {2^{s+1}- 2^i+1|0<=i<=s-1} and s+1 otherwise.