ㄧ個只花O(log N)時間找出具有N點之雙環式網路的steps的演算法以及Hyper-L1三環式網路的存在性的探討

Abstract

雙環式網路及三環式網路是許多學者專家廣泛探討的區域網路架構。給定一個正整數N，找出具有N點、直徑最小的雙環式網路DL(N;s1,s2)的s1和s2（又稱為steps）是學者專家們ㄧ直以來所想達成的目標。已知雙環式網路的minimum distance diagram是L-型；對於雙環式網路而言，直徑可以很容易的由它的L-型計算出。因此「找出具有N點、直徑最小的雙環式網路」的一個常見的方法是：將此問題轉換為「先找出一個直徑相當不錯的L-型，再找出與這個L-型對應的雙環式網路DL(N; s1, s2)的s1和s2」。給定一個雙環式網路DL(N; s1, s2)，在論文[8]中，Cheng和黃光明老師提出了一個漂亮而且只花O(log N)時間、找出對應的L-型的演算法。但是，「給定一個L-型，是否能夠只花O(log N)時間，找出與這個L-型相對應的雙環式網路DL(N; s1, s2)的steps」，卻一直是一個open problem [5]。在這篇論文裡，我們提出一個只花O(log N)時間、找出與一個給定的L-型相對應的雙環式網路DL(N; s1, s2)的steps的演算法。 令N(D)表示一個直徑為D的三環式網路所能包含的最多點數。Hyper-L型已被多位學者發現為推導出N(D)的下界的一個有效的工具。然而，並非每一個Hyper-L 型都會有一個三環式網路來得到它。截至目前為止，共有三種hyper-L型被學者們提出來，為了方便起見，我們分別稱它們為hyper-L0、hyper-L1、hyper-L2。在論文[7]中，陳秋媛老師、黃光明老師、李珠矽老師、以及石舜仁學長提出了hyper-L0三環式網路存在的充份必要條件。在這篇論文裡，我們提出hyper-L1三環式網路存在的充份必要條件。

Double-loop networks and triple-loop networks have been widely studied as architecture for local area networks. Given an N, it is desirable to find a double-loop network DL(N; s1, s2) with its diameter being the minimum among all double-loop networks with N nodes. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Since the diameter can be easily computed from an L-shape, one method is to start with a desirable L-shape and then asks whether there exist s1 and s2 (also called the steps of the double-loop network) to realize it. While Cheng and Hwang [8] have given an elegant O(log N)-time algorithm to find the L-shape of a double-loop network DL(N; s1, s2), it is an open problem whether the steps of a double-loop network with N nodes can be found in O(log N) time [5]. In this thesis, we propose an O(log N)-time algorithm to find the steps of a double-loop network with N nodes. Hyper-L tiles were proven to be an effective tool to obtain lower bounds for N(D), the maximum number of nodes in a triple-loop network with diameter D. Unfortunately, not every hyper-L tile has a triple-loop network realizing it. Up to now, three types of hyper-L tiles have been proposed; for convenience, call them hyper-L0, hyper-L1, and hyper-L2. In [7], Chen et al. derived the necessary and sufficient conditions for the existence of hyper-L0 triple-loop networks. In this thesis, we shall derive the necessary and sufficient conditions for the existence of hyper-L1 triple-loop networks.