超立方體與二元樹都是被熱門研究的網路架構，因為它們擁有良好的性質。如超立方體有高連通值(strong connectivity)、低直徑(low diameter)、有規律性(regularity)與對稱性(symmetry) ，可以被許多其它網路架構嵌入。二元樹是一個許多演算法所使用的資料結構，如分而治之(divide and conquer)等。尤其在資料庫上的一些演算法更可以在以樹為主的資料結構上得到相當好的執行效率。在平行計算(parallel computation)理論中，圖形的嵌入是一個相當重要的議題。二元樹可以嵌入至超立方體意指一些專門設計給二元樹的演算法能夠轉移至超立方體網路結構上順利地實行。
如果我們能夠藉由點數就能判斷是否能嵌入，則我們可以省去嘗試將點數過多的情況卻總是無法嵌入的時間。本篇論文主要研究的問題就是判斷特定點數的二元樹是否能嵌入它的最似超立方體，我們的研究證明了在點數小於12的二元樹時，均可以嵌入。某些特定點數的二元樹不能嵌入。並更進一步提出一個推測，我們證明了，若此推測為真，則Bhatt等人的推測也為真。

Both hypercubes and binary trees are well studied interconnection networks, because both of them have good properties. For example, hypercubes have properties of strong connectivity, low diameter, regularity and symmetry and they can also be embedded by many other interconnection networks. Binary trees are used as data structures for many algorithms. Especially, they are used on data base algorithms in order to of data base get efficiency. In parallel computation, it is an important issue to embed binary trees to hypercubes, because the existence of such an embedding demonstrates the ability of a hypercube-formed interconnection network to simulate an algorithm which is designed for a binary tree. If we can determine whether there exists such an embedding though the number of verities of the given binary tree, then we can avoid wasting time on trying to embed the given binary tree. In this paper, we study the problem that whether we can embed a binary tree with a specific order to its optimal hypercubes. We prove that any binary tree with order small than 12 can be embedded to its optimal hypercubes. Furthermore, for the conjecture of Bhatt et al. at 1985, we proposed another conjecture. We also proved that if the conjecture is true, the Bhatt's conjecture is true as well.

目次 I
圖目錄 II
表目錄 IV
第一章 緒論 1
第一節 研究背景 1
第二節 本文的貢獻 9
第三節 論文架構 10
第二章 相關的文獻探討 11
第三章 主要的研究結果 15
第四章 結論 31
參考文獻 32

[1]R.Balakrishnan and K. Ranganatha, A Textbook of Graph Theory, Springer , 2000
[2]J. L. Bentley, and H. T. Kung, "A tree machine for searching problems," Proceedings of International Conference on Parallel Processing, pp. 257-266, 1979.
[3]Saïd Bettayeb, Priyalal Kulasinghe, "Embedding Binary Trees into Crossed Cubes," IEEE Transactions on Computers, Volume 44, Issue 7, pp. 923 - 929, 1995
[4]S. Bezrukov, B. Monien,W. Unger, G.Wechsung, "Embedding caterpillars into the hypercube," Technical Report, University of Paderborn, 1995.
[5]S. N. Bhatt, and I. C. F. Ipsen, "How to embed trees in hypercubes," Yale University Res. Rep., RR-443, Dec. 1985.
[6]Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg, "Efficient ebmedding of trees in hypercubes," SIAM J. Comput., vol. 21, pp. 151-162, Feb. 1992.
[7]S. N. Bhatt, F. Chung, T. Leighton, and Rosenberg A, "Optimal simulation of tree machines," Proceedings of the 1986 27th Annual Symposium of Foundations of Computer Science, pp. 274-282.
[8]L. Bhuyan, and D. P. Agrawal, "Generalized hypercubes and hyperbus structures for a computer network," IEEE Transactions on Computers, C-33, pp. 323-333, 1984.
[9]R. Caha, V. Koubek, Optimal embeddings of odd ladders into a hypercube, Discrete Appl. Math. 116 (2002) 73–102.
[10]A. M. Despain, and D. A. Patterson, "X-tree: A tree structured multiprocessor computer architecture," Proceedings of the 5th Annual Symposium on Computer Architecture, pp. 144-151, 1978.
[11]S. R. Desphance, and R. Jenevein, "Scalability of binary trees on a hypercube," Proceedings of International Conference on Parallel Processing, pp. 661-668, 1986.
[12]Tomás Dvorák: "Dense sets and embedding binary trees into hypercubes", Discrete Applied Mathematics 155(4): pp. 506-514 (2007)
[13]T. Tomás Dvorák, I. Havel, J.-M. Laborde, P. Liebl, Generalized hypercubes and graph embedding with dilation, Rostock. Math. Kolloq. 39 (1990) 13–20.
[14]Kemal Efe, "Embedding large complete binary trees in hypercubes with load balancing," Journal of Parallel and Distributed Computing, Volume 35, Issue 1, pp. 104 - 109, 1996
[15]K. Efe, "Embedding mesh of trees in the hypercube," Journal of Parallel and Distributed Computing, vol. 11, pp. 222-230, 1991.
[16]Jianxi Fan, Xiaohua Jia "Embedding meshes into crossed cubes," an International Journal, Volume 177 , Issue 15, pp. 3151-3160, August 2007
[17]T. Feder and E. W. Mayr, "An efficient algorithm for embedding complete binary trees in the hypercube", Stanford University, manuscript, 1987.
[18]Jung-Sheng Fu, "Cycle Embedding in a Faulty Hypercube," ICPADS 2002: pp.5-10
[19]V. Heun and E. W. Mayr "A new efficient algorithm for embedding an arbitrary binary tree into its optimal hypercube," Journal of Algorithms, Vol. 20, pp. 375-399, 1996
[20]C. T. Ho, and S. L. Johnsson, "Spanning balanced trees in Boolean cubes," SIAM J. Sci, Statist. Comput., vol.10-4, pp. 607-630, July 1989.
[21]E. Horowitz, and A. Zorat, "The binary tree as an interconnection network：Applications to multiprocessor systems and VLSI," IEEE Transactions on Computers, vol. 30, pp. 247-253, 1981.
[22]Feng-Shr Jiang, Shi-Jinn Horng, Tzong-Wann Kao, "Embedding of Generalized Fibonacci Cubes in Hypercubes with Faulty Nodes," IEEE Transactions on Parallel and Distributed Systems, Volume 8 , Issue 7, pp.727 - 737, July 1997
[23]S. Latifi and S. Q. Zheng, “Determination of Hamiltonian cycles in cube-based networks using generalized Gray codes,” Journal of Electrical and Computer Engineering, vol. 21, no. 3, pp. 189-199, 1992.
[24]F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees and Hypercubes, Morgan Kaufmann, San Mateo CA, 1992.
[25]F. T. Leighton, "Parallel computing using mesh of trees," Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science, pp. 200-218, 1983.
[26]Ernst L. Leiss, Hari N. Reddy: Embedding Complete Binary Trees Into Hypercubes. Information Processing Letters archive Volume 38(4): 197-199 (1991)
[27]Jen-Chih Lin, Tzong-Heng Chi, Huan-Chao Keh, Ay-Hwa Andy Liou, "Embedding of complete binary tree with 2-expansion in a faulty Flexible Hypercube," Journal of System Architecture 47 (2001) 543-548.
[28]B. Monien and I.H. Sudborough, "Simulating Binary Trees on Hypercubes," Proceedings Third Aegan Workshop on Computing, Lecture Notes Computer Science 319, pp170-180, 1988
[29]S. Ravindran, A. M. Gibbons, M. S. Paterson, "Dense Edge-Disjoint Embedding of Complete Binary Trees in Interconnection Networks," Theoretical Computer Science, 249 (2000), pp. 325-342
[30]Youcef Saad and Martin Schultz, "Topological properties of hypercube," IEEE Transaction Computers, vol.37, no. 7, pp.867-871, July 1988.
[31]Adhijit Sengupta, "On ring embedding in hypercubes with faulty nodes and links," Information Processing Letters, Volume 68 , Issue 4, pp. 207 - 214, 1998
[32]Yu-Chee Tseng, Shu-Hui Chang, Jang-Ping Sheu, "Fault-Tolerant Ring Embedding in a Star Graph with Both Link and Node Failures," IEEE Transactions on Parallel and Distributed Systems, Volume 8, Issue 12, pp. 1185 - 1195, 1997
[33]W.T.T Tutte, Graph Theory, Cambridge University Press, (2001)
[34]A. Wagner, "Embedding arbitrary binary trees in a hypercube," Journal of Parallel and Distributed Computing, vol. 7, pp. 503-520, 1989.
[35]A. Wagner and D.G. Corneil, "Embedding trees in a hypercube is NP-complete," SIAM J. Comput. 7 (1990), pp. 570-590.
[36]Douglas B. West, Introduction to Graph Theory, Prentice Hall, 1996
[37]Angela Y. Wu, "Embedding of tree networks into hypercubes," Interconnection networks for high-performance parallel computers book, pp. 532 - 543, 1994
[38]J. Wu, E. B. Fernandez, and Y. Luo, "Embedding of Binomial Trees in Hypercubes with Link Faults," Journal of Parallel and Distributed Computing, vol. 54, pp. 59-74, 1998.
[39]Junming Xu, Theory and Application of Graphs, Network Theory and Applications, 2003