漢彌爾頓環路之點容錯坎入在矩形式蜂巢環形曲面網路

Abstract

在本文中，我們提出蜂巢環形曲面圖形的一個變形，叫做矩形式蜂巢環形曲面網路。矩形式蜂巢環形曲面具有漢彌爾頓環路和把一對節點從圖形中移走，仍然具有漢彌爾頓環路。矩形式蜂巢環形曲面網路具有同類性質圖形。這種性質很有益, 因為我們能夠降低矩形式蜂巢環形曲面網路的複雜性。 矩形式蜂巢環形曲面 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.