弦環式網路的邊刪除直徑不變性質

Abstract

環狀網路是最簡單的網路架構，然而，環狀網路的可靠度低、傳輸延遲高，因此，以環狀網路為基礎的混合式環狀網路相繼被提出，以提高其可靠度與降低傳輸延遲。Arden和Lee[1]在1981 年提出了以環狀網路延伸而成的弦環式網路。弦環式網路是在環狀網路的結構中增加弦，使得其可靠度提高、直徑降低。更具體的來說，一個弦環式網路CR(N,w)具有N 個點(N為偶數，點的編號為0至N−1) 與3N/2 條邊，邊的連線方式為： i 連至(i+1) mod N ， □i=0,1,…,N−1，及 i 連至(i+w) mod N ，□i=1,3,…,N−1， 其中w為不大於N/2的奇數。弦環式網路為3-正則圖，它與環狀網路一樣具有漢彌爾頓圈，而且比環狀網路擁有更好的直徑。在1987 年，Lee和Tanoto[14,15]提出了邊刪除直徑不變圖的概念。令D(G) 為圖G的直徑。一個圖G為diameter-edge-invariant 若它滿足D(G−e)=D(G)，□e□E(G)。本篇論文之目的在於研究弦環式網路CR(N,w)的邊刪除直徑不變性質，特別是在w□{3,5,7,9}時，我們判斷出所有的CR(N,w)是否為邊刪除直徑不變圖。

One of the simplest topologies for interconnection networks is the ring network. However, the ring network has poor reliability (any failure in a node or link destroys the function of the network) and it has high transmission delay (large diameter). As a result, hybrid topologies utilizing the ring network as a basis for synthesizing richer interconnection schemes have been proposed to improve the reliability and reduce the transmission delay. The chordal ring network, proposed by Arden and Lee [1] in 1981, is a commonly used extension for the ring network. The chordal ring network is considered to be obtained by adding chords to a cycle (a ring network) so that the diameter can be reduced and the reliability can be increased. More specifically, a chordal ring network CR(N,w), where N is a positive even integer and w is a positive odd integer such that w≤N/2, is a graph with N nodes 0, 1, . . . ,N−1 and 3N/2 links of the form: (i, (i+1) mod N), i = 0, 1, 2, . . . ,N−1, (i, (i+w) mod N), i = 1, 3, 5, . . . ,N−1. The chordal ring network is 3-regular, preserves the Hamiltonian cycle from the ring network, and has a better diameter than the ring network. In 1987, Lee and Tanoto [14,15] proposed diameter-edge-invariant graphs. Let D(G) denote the diameter of a graph G. G is diameter-edge-invariant (dei) if D(G−e) = D(G) for all e □ E(G). The purpose of this thesis is to study the dei property of chordal ring networks. In particular, we determine if CR(N,w) is dei for all w □ {3, 5, 7, 9}.