在一任意圖形上尋找漢米頓迴路（或環）是--NP - complete的問題，但是在一有高度對稱性、平行性之拓撲結構--完整超立方體上，尋找漢米頓迴路這一問題能夠在複雜度O（N）之時間解決。N是超立方體節點的數目。假如在一有錯誤節點產生之完整超立方體系統上，則上述O（N）的演算法無法在其上面找一環路徑。因此，我們研究的目的是在一有錯誤節點產生的完整超立方體上，尋找一個能容下大多數健康節點的環。我們推出一新的不完整超立方體模型--subcube - graph。這個模型是由損壞的完整超立方體所得出。藉由這個模型，我們發展出一演算法。演算法應用深度優先搜尋法則於subcube - graph，以求出這個模型的擴展樹。藉由擴展樹分別求出每一樹節點之環路徑，再藉著我們的破邊法連結每一樹節點之環路徑。如此，在原來損壞的超立方體上，可容納大多數健康節點的環便可求出。我們的方法不受限於錯誤節點數目的多寡，這個限制常困擾許多現有的環嵌入演算方法。

It is well known that the general problem of finding a Hamilton cycle (ring) in an arbitary graph is NP - complete. However, in an - dimensional hypercube, an advocated symmetric topological structure, the searching of a Hamilton cycle (ring) can be easily carried out in O (N), where N is the number of nodes in a complete hypercube. In an injured hypercube which has faulty nodes, the above O (N) algorithrn can't be applied for finding a ring in it. Hence, the purpose of our research is to develop a heuristic algorithm to find rings in the injured hypercubes. In this thesis, we develop a new incomplete hypercube model, which uses a subcbe - graph to present the topology of an injured hypercube, to provide a better representation for it. This incomplete hypercube model server as the foundation for our ring embeding algorithm. Our ring embedding algorthm employs depth - first search on subcube - graph associated with a heuristic break edge method to derive a ring passing through the maximal possible number of the available processor elements in the injured hypercube. Our method can provide a ring embedding on an injured hypercube with high processor utilization. Also, our method has no limitation on the number of faulty nodes that bothers many existing fault - tolerant ring embedding schemes. The time complexity of our method is O (mn), where m is the number of cube - nodes in a subcube - graph and n is the dimension of the injured hypercube.