兩種Hyper-L 型三環式網路存在性的探討

Abstract

令N(D)表示一個直徑為D的三環式網路所能包含的最多點數。Hyper-L型已被多位學者發現為推導出N(D)的下界的一個有效的工具，不幸的是，並非每一個Hyper-L 型都會有一個三環式網路來得到它，所以「如何判斷一個Hyper-L 型是否存在三環式網路來得到它」就變成是一個相當重要的問題。截至目前為止，共有三種hyper-L型被學者們提出來，為了方便起見，我們分別稱它們為hyper-L H0、hyper-L H1、hyper-L H2。Aguiló 等人提出hyper-L H0三環式網路存在的兩個必要條件，陳秋媛老師與黃光明老師、李珠矽老師、以及去年畢業的石舜仁同學提出了hyper-L H0三環式網路存在的充份必要條件。在這篇論文裡，我們將提出hyper-L H1和hyper-L H2三環式網路存在的充份必要條件。

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. Thus it becomes important to determine when will a hyper-L tile have a triple-loop network realizing it. Up to now, three types of hyper-L tiles have been proposed; for convenience, call them hyper-L H0, hyper-L H1, and hyper-L H2. Aguiló et al. derived two necessary conditions for the existence of hyper-L H0 triple-loop networks. Also, Chen et al. derived the necessary and sufficient conditions for the existence of hyper-L H0 triple-loop networks. In this thesis, we shall derive the necessary and sufficient conditions for the existence of hyper-L H1 and hyper-L H2 triple-loop networks.