臺灣博碩士論文加值系統

在本文中，我們提出蜂巢環形曲面圖形的一個變形，叫做矩形式蜂巢環形曲面網路。矩形式蜂巢環形曲面具有漢彌爾頓環路和把一對節點從圖形中移走，仍然具有漢彌爾頓環路。矩形式蜂巢環形曲面網路具有同類性質圖形。這種性質很有益, 因為我們能夠降低矩形式蜂巢環形曲面網路的複雜性。 矩形式蜂巢環形曲面 HReT(m,n)在由 Stojmenovic 發表的論文中被定義了。矩形式蜂巢環形曲面 HReT(m,n)有許多好的性質，包括同類圖形，3-度的正規圖形，雙向圖形，漢彌爾頓環路，1-P的漢彌爾頓環路，漢彌爾頓環路連通性等等的許多好性質。因為矩形式蜂巢環形曲面的節點的度為 3 是固定的，這能夠在最壞(最差)的情況中至多有兩個節點錯誤仍然具有漢彌爾頓路。在本文中，我們將證明所有矩形式蜂巢環形曲面當任何一對節點錯誤時，都具有漢彌爾頓環路性質。

In this thesis, we propose a variation of Honeycomb Torus, called Honeycomb Rectangular Torus Networks.The Honeycomb Rectangular Torus is Hamlitonian and to remove a pair of nodes from each partite sets of graph, still has Hamlitonian cycle. Honeycomb
Rectangular Torus Network is homogeneous graph. This property is
very helpful, because we can reduce the complexity of the
Honeycomb Rectangular Torus. The Honeycomb Rectangular Torus
HReT(m,n) is defined in the paper written by Stojmenovic
Honeycomb Rectangular Torus has many good properties including homogeneous graph, 3-regular graph, Bipartite
graph , hamiltonian cycle, 1-p hamiltonian cycle, hamiltonian
connectivity etc. Since $HReT(m,n)$ is regular of degree 3, it can tolerate at most two node faults in the worst case in order to construct a hamiltonian cycle. In this paper, we will prove that
all the honeycomb rectangular torus have hamiltonian cycle, when
any one pair nodes fault.

1. Introduction
2. Properties in Honeycomb Rectangular Torus
2.1 Notations and Definition
2.2 basic properties of HRet(m,n)
3.Fault tolerant ring embedding in HReT(m,n)
3.1 Basic case : two fault nodes in HReT(6,2)
3.2 Two faulty nodes in HReT(6,n)
3.3 Two faulty nodes in HReT(m,2)
3.4 Two faulty nodes (i.j) and (i,j+1) which this two nodes
are adjacent in HReT(m,n)
4. conclusion

1.Ivan Stojmenovic, it Honeycomb Networks:Topological Properties and Communiction Algorithms
,1999
2.J.A.Bondy and U.S.R.Murty, Graph Theory
with Applications, North-Holland, New York, (1980).
3.J.Myoupo, and D.Seme,All-to-All Broadcasting Algorithms on Honeycomb Networks and
Applications", it Parallel Processing Letters,vol.9, pp.539-550, 1999.
4. G.M.Megson, X.Yang, and X.Liu,
Honeycomb Tori are Hamiltonian.Information Processing
Letters. ol.39, pp.10-18, 1990.
5.M.S.Chen, K.G.Shin, and D.D.Kandlur,
Addressing, Routing, and Broadcasting in Hexgonal Mesh
Multiprocessors", IEEE Trans.Computers, vol.39, pp.
10-18, 1990.
6. F.T. Leighton, Introduction to Parallel
Algorithms and Architectures: Arrays Trees
Hypercubes, Morgan Kaufmann Publishers, San Mateo, CA, 1992.
8.G.M.Megson, X.Yang, and X. Liu,
Honeycomb Tori are Hamiltonian", Information Processing
Letters, vol.72, pp.99-103, 1999.
9.G.M.Megson, X.Liu, and X.Yang,
Fault-Tolerant Ring Embedding in a Honeycomb Torus with Nodes
Failures", Parallel Processing Letters, vol.9, pp.551--561, 1999.
10.B.Parhami and D.M.Kwai, ``A Unified Formulation of
Honeycomb and Diamond Networks", IEEE Trans. Parallel and
Distributed Systemsvol.12, pp.74--80, 2001.
11.I.Stojmenovic, ``Honeycomb Networks: Topological
Properties and Communication Algorithms", IEEE Trans.
Parallel and Distributed Systems, vol.8, pp.1036--1042, 1997.
12.H.Y.Youn and J.Y.Lee, ``An Efficient Dictionary
Machine Using Hexgonal Processor Arrays", IEEE Trans.Parallel and Distributed Systems, vol.7, pp.166--273, 1996.