標題: 弦環式網路的邊刪除直徑不變性質
The Diamete-edge-invariant Property of Chordal Ring Networks
作者: 黃信菖
Huang, Hsin-Chang
陳秋媛
Chen, Chiu-yuan
應用數學系所
關鍵字: 環狀網路;弦環式網路;連接網路;直徑;邊刪除;正則圖;ring network;chordal ring network;interconnection network;diameter;edge deletion;regular graph
公開日期: 2008
摘要: 環狀網路是最簡單的網路架構,然而,環狀網路的可靠度低、傳輸延遲高,因此,以環狀網路為基礎的混合式環狀網路相繼被提出,以提高其可靠度與降低傳輸延遲。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}.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079522533
http://hdl.handle.net/11536/41204
Appears in Collections:Thesis


Files in This Item:

  1. 253301.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.