| 摘要: | 一個連接網路的結構通常可以用一個圖來表示。可是在連接網路的拓樸與設計上存在許多相互抵觸的要求。要設計一個完美的網路符合各方面的要求而且都是最佳化的狀況是幾乎不可能的事。超立方體(hypercube)網路是一個最受歡迎的拓樸結構之一。因為它有很多好的性質已經廣泛被使用，例如：規則的(regular)，對稱性的(symmetric)，強大的連接性和相關最小直徑[47,63]等等。在1976年，Hayes是第一篇文獻直接討論關於漢米爾頓的(Hamiltonian)和容錯的性質。從那時候開始對於漢米爾頓性質與容錯性質的文章就不斷越來越多。很多組合，代數學，和其他數學結構是與漢米爾頓性質與容錯性質有關係。因此，產生很多有意思的問題與重要的結果。例如：Hayes[37]，Simmons [65]，Lewinter和Widulski[45]等等都是在這方面很棒的文章。 容錯漢米爾頓存在著各式各樣的問題，例如: 圈(cycle)或路徑(path)嵌入在缺損連接網路問題。但是，在二分圖裡的路徑顏色是相互交錯的。所以，對於圖總點數大於3時，任何二分圖都不是漢米爾頓連通(hamiltonian connected)。因此，Simmon [65]定義漢米爾頓連結性的觀念。在給定一個二分圖中，去探討嵌入各式各樣的圈或路徑是一個重要的課題。圈或路徑嵌入問題就是漢米爾頓的問題的推廣。 在本篇論文裡有4章。我們將研究可否將路徑和圈嵌入有缺損的超立方體圖裡。在第1章，我們提及一些基本的定義和在漢米爾頓問題上古典結果。在第2章，我們在某一些缺損超立方體圖上討論漢米爾頓相關問題。在第3章，我們在某一些缺損超立方體圖上討論任意長度的圈和路徑嵌入問題。在第4章，我們提議並且討論︰在超立方體圖裡討論彼此相互獨立的漢米爾頓路徑和圈的問題。在最後，我們將對於這篇論文的結果與未來工作做一個總結並討論未來可能進行研究的方向。 The architecture of an interconnection network is usually represented by a graph. There exist mutually conflicting requirements in designing and topology of interco- nnection networks. It became almost impossible for us to design a network which is optimum in all aspects. The hypercube network is one of the most popular topologies among the interconnection networks. It has widely used due to many of its attractive properties, including regular, symmetric, strong connectivity and relative small diameter [48, 64] etc. The first paper dealing directly with hamiltonian property and fault- tolerant property appeared in 1976 Hayes [38]. Since that time the interest in hamiltonian property and fault-tolerant property has been on increase. Many combinatorial, algebraic, and other mathematical structures are linked to hamiltonian property and fault-tolerant property. There are lots of intriguing problems and significant results. Excellent surveys of them are provided by Hayes [38], Simmons [66], Lewinter and Widulski [46] etc. There are various fault-tolerant hamiltonian problems, such as cycle (path) embedding problems in hamiltonian faulty interconnection networks. However, any bipartite graph G is not hamiltonian connected for V(G). Any hamiltonian bipartite graph G = (V0; V1;E) satisfies |V0| = |V1|. Simmons [66] introduced the concept of hamiltonian laceability for hamiltonian bipartite graph. Hsieh et al. [41] introduced the concept of strongly hamiltonian laceability. Lewinter and Widulski [46] further introduced the concept of hyper-hamiltonian laceability. The Hamiltonian laceability, which deals with embedding a hamiltonian path in a given bipartite graph, is an important topic in interconnection networks. The cycle (path) embedding problem is a derivation of hamiltonian problems. In this thesis, there are four chapters in this thesis. We'll study the path and cycle embedding in faulty hypercubes. In Chapter 1, we mention some basic definitions and classical results on hamiltonian problem. In Chapter 2, we discuss hamiltonian problems on some faulty hypercubes. In Chapter 3, we discuss the cycle and path embeddingproblem, which deals with all the possible lengths of cycle and path in faulty hypercubes under some conditions. In Chapter 4, we propose and discuss related problems: Mutually independent hamiltonian paths and cycles problems in hypercubes. In the final section, we give our concluding remarks. |
