臺灣博碩士論文加值系統

　　在計算機科學中，連接網路拓樸結構是相當重要且被許多學者廣泛討論的，因它擁有相當重要的特性¬－平行以及分散式運算，而此特性是一個影響系統效能相當重要的因素。在眾多種類的網路拓樸結構中，超立方體是常被討論的網路拓樸結構，因其擁有相當良好的特性，如規律對稱特性、直徑短、強連通特性、遞迴結構、靈活的分區、且擁有相對較低複雜度的連結。超立方體不僅適合於特殊目的與一般性目的的工作，還能有效率地模擬其他網路特性。在另一方面，交叉立方體擁有類似於超立方體的性質，如遞迴結構、與超立方體相同的節點數目、與超立方體相同連結的數目，更重要的是交叉立方體的直徑約只有超立方體直徑的一半，而直徑的大小在平行運算中是相當重要的，因其會直接影響平行運算的速度。
　　本篇論文主要在改善過去Meijie Ma曾提出在n維交叉立方體CQn擁有至多n－3個錯誤中，具有可容錯之路徑，其路徑長度滿足2n-1－1 至圖形所有頂點扣除掉錯誤頂點後減1之長度，以及改善另一篇Jung-Heum Park提出在HL-graph扣除掉至多n－3個錯誤後，擁有2n－3以上之長度的路徑。本篇論文主要的研究目的是在證明擁有至多n－3個錯誤頂點的交叉立方體中，存在相較於路徑長度2n－3更短之不同長度的路徑。
　　本篇論文的研究結果顯示，當提出n ≥ 5 的n維交叉立方體CQn，在擁有至多n－3個錯誤頂點時，存在一條任意長度為2n－5至2n－f－1的路徑，其中f為錯誤頂點數目。

　In computer science, network topology is important and widely discussed by researchers since it is essential for parallel and distributed computation. Recently, many network topologies have been proposed. Among these topologies, the hypercube is one of the most popular topologies since it has good properties such as regularity, symmetry, small diameter, strong connectivity, recursive structure, flexible partition, and relatively low link complexity. Not only is it ideally suited to both special-purpose and general-purpose tasks, but it can efficiently simulate many other networks. The crossed cube has a structure similar to the hypercube, including recursive structure, the same number of vertices, and the same number of edges. However, the diameter of the crossed cube is only about one half of that of the hypercube. The diameter is an important factor for parallel computing speed.

　　In this study, we improve the previous result of Meijie Ma et al. that an n-dimensional crossed cube with up to n – 3 faults has a fault-free path of various length satisfying 2n-1－1 to the number of all vertices minus the faulty vertices and minus one. We also improve the result of Jung-Heum Park et al. that an n-dimensional HL-graph with up to n – 3 that has a fault-free path of various lengths with minimum 2n－3. In our main result, we prove that an n-dimensional crossed cube with up to n – 3 faulty vertices has a fault-free path of various length short than 2n－3.

　　The result of this study indicates that for an n-dimensional crossed cube with up to n – 3 faulty vertices, where n ≥ 5, there exists a fault-free path of various length satisfying 2n – 5 to 2n – f – 1, where f denotes the number of faulty vertices.

第壹章 緒論 1
1.1 研究背景 1
1.2 研究目的 3
1.3 論文架構 4
第貳章 文獻探討 5
2.1 圖形理論的基本定義與特性 5
2.2 圖形的泛連通性與泛圈性 9
2.3 漢米爾頓路徑與迴圈 11
2.4 連接網路 12
2.5 可容錯性質 14
2.6 交叉立方體 16
第參章 主要研究 22
3.1 交叉立方體的漢米爾頓 22
3.2 定義說明 25
3.3 主要定理 27
第肆章 結論 43
參考文獻 44

[1] Y. Alavi, James E. Williamson, Panconnected graphs, Studia Scientiarum Mathematicarum Hungarica, 10 (1-2), pp. 19-22, 1975.
[2] John Adrian Bondy, Pancyclic graphs I, Journal of Combinatorial Theory, 11(1), pp. 80-84, 1971.
[3] John Adrian Bondy, U.S.R. Murty, Graph Theory, Springer, London, 2008.
[4] Chien-Ping Chang, Ting-Yi Sung, Lih-Hsing Hsu, Edge congestion and topological properties of crossed cubes , IEEE Transactions on Parallel and Distributed Systems, 11(1), pp. 64-80, 2000.
[5] Chien-Ping Chang, Chia-Ching Wu, Conditional fault diameter of crossed cubes, Journal of Parallel and Distributed Computing, 69(1), pp. 91-99, 2009.
[6] Hon-Chan Chen, Tzu-Liang Kung, Lih-Hsing Hsu, Embedding a Hamiltonian cycle in the crossed cube with two required vertices in the fixed positions, Applied Mathematics and Computation, 217(24), pp. 10058-10065, 2011.
[7] Xie-Bin Chen, Edge-fault-tolerant panconnectivity and edge-pancyclicity of the complete graph, Information Sciences, 235(20), pp. 341-346, 2013.
[8] Y-Chuang Chen, Chang-Hsiung Tsai, Lih-Hsing Hsu, Jimmy J.M. Tan, On some super fault-tolerant Hamiltonian graphs, Applied Mathematics and Computation, 148(3), pp. 729-741, 2004.
[9] Dongqin Cheng, Dachang Guo, Fault-tolerant cycle embedding in the faulty hypercubes, Information Sciences, 253(20), pp. 157-162, 2013.
[10] William J. Dally and Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann, 2004.
[11] Reinhard Diestel, Graph Theory, Springer, New York, 1991.
[12] Qiang Dong, Xiaofan Yang, Embedding a long fault-free cycle in a crossed cube with more faulty nodes, Information Processing Letters, 110(11), pp. 464-468, 2010.
[13] Kemal. Efe. A variation on the hypercube with lower diameter, IEEE Transactions on Computers, 40(11), pp. 1312-1316, 1991.
[14] Kemal Efe, The crossed cube Architecture for parallel computation, IEEE Transactions on Parallel and Distributed Systems, 3(5), pp. 513-524, 1992.
[15] Jianxi Fan, Xiaola Lin, Xiaohua Jia, Node-pancyclicity and edge-pancyclicity of crossed cubes, Information Processing Letters, 93(3), pp. 133-138, 2005.
[16] Jianxi Fan, Xiaola Lin, Xiaohua Jia, Optimal path embedding in crossed cubes, IEEE Transactions on Parallel and Distributed Systems, 16(12), pp. 1190-1200, 2005.
[17] Jianxi Fan, Xiaohua Jia, Xiaola Lin, Complete path embeddings in crossed cubes, Information Sciences, 176(22), pp. 3332-3346, 2006.
[18] Jung-Sheng Fu, Conditional fault Hamiltonicity of the complete graph, Information Processing Letters, 107(3-4), pp. 110-113, 2008.
[19] Miltos D. Grammatikakis, D. Frank Hsu, and M. Hraetzl, Parallel System Interconnections and Communciations, CRC Press, 2001.
[20] Jonathan Gross, Handbook of graph theory, CRC PRESS, 2004.
[21] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. Snepscheut. The twisted cube. In Volume I:Parallel architectures on PARLE: Parallel Architectures and Languages Europe, 1, pp. 152-159, London, UK, 1987.
[22] Hao-Shun Hung, Jung-Sheng Fu, Gen-Huey Chen, Fault-free Hamiltonian cycles in crossed cubes with conditional link faults, Information Sciences, 177(24), pp. 5664-5674, 2007.
[23] Wen-Tzeng Huang, Yen-Chu Chuang, Jimmy Jiann-Mean Tan, On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E85-A(6), pp. 1359-1371, 2002.
[24] Priyalal Kulasinghe, Connectivity of the crossed cube, Information Processing Letters, 61(4), pp. 221-226, 1997.
[25] M. S. Krishnamoorthy, b. Krishnamurthy, Fault diameter of interconnection networks, Computers &; Mathematics with Applications, 13(5-6), pp. 577-582, 1987.
[26] Priyalal Kulasinghe, Sald Bettayeb, Embedding Binary Trees into Crossed Cubes, IEEE Transactions on Computers, 44(7), pp. 923-929. 1995.
[27] Pao-Lien Lai, Hong-Chun Hsu, Constructing the nearly shortest path in crossed cubes, Information Sciences, 179(14), pp. 2487-2493, 2009.
[28] S. M. Larson, P. Cull. The Möbius cubes, IEEE Transactions on Computers, 44(5), pp. 647-659, 1995.
[29] Meijie Ma, Guizhen Liu, Jun-Ming Xu, Fault-tolerant embedding of paths in crossed cubes, Theoretical Computer Science, pp. 407(1-3), pp. 110-116, 2008.
[30] Jung-Heum Park, Hyeong-Seok Lim, Hee-Chul Kim, Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Theoretical Computer Science, 377(1-3), pp. 170-180, 2007.
[31] Y. Saad, M. H. Schultz. Topological properties of hypercubes, IEEE Transactions on Computers, 37(7), pp. 867-872, 1988.
[32] Dajin Wang, Hamiltonian Embedding in Crossed Cubes with failed links, IEEE Transactions on Parallel and Distributed Systems, 23(11), pp. 2117-2124, 2012.
[33] Douglas B. West, Introduction to graph theory, Prentice-Hall, United States of America, 2001.
[34] Jun-Ming Xu, Meijie Ma, Min Lü, Paths in Möbius cubes and crossed cubes, Information Processing Letters, 97(3), pp. 94-97, 2006.
[35] Ming-Chien Yang, Tseng-Kuei Li, Fault-tolerant cycle-embedding of crossed cubes, Information Processing Letters, 88(4), pp. 149-154, 2003.
[36] X. F. Yang , D.J. Evans, G. M. Megson, The locally twisted cubes, International Journal of Computer Mathematics, 82(4), pp. 401-413, 2005