最近幾年來，嵌置問題已受到廣泛地討論。在此篇論文中，我們研究嵌置
各種不同的客人圖形到主人圖形，例如把完全二元樹、不完全二元樹、樹
形機器和四元樹嵌置到超立方體與不完全超立方體中。此外，我們也研究
在一個有缺失的超立方體中，動態地重建完全二元樹。首先，我們使用最
小的不完全超立方體來嵌置完全二元樹，並且保持完全二元樹的相鄰性，
然後在超立方體中嵌置不完全二元樹。第二，我們在有限大小的超立方體
中，最佳地嵌置大型完全二元樹。第三，我們在膨脹值 =1 的條件下，嵌
置樹形機器到不完全超立方體中，然後在負載平衡的條件下，嵌置大型樹
形機器到有限大小的超立方體中。第四，我們嵌置完全四元樹到超立方體
中，並且保持完全四元樹的相鄰性，然後在膨脹值 =1 的條件下，嵌置完
全四元樹到不完全超立方體中。最後，我們在有缺失的超立方體中，使用
動態的重建方法來嵌置完全二元樹，並且重建之後會被影響到的結點數目
，要儘可能的少。

The embedding problem has been widely discussed in recent
years. In this dissertation, we study embedding of various
guest graphs such as complete binary trees, incomplete binary
trees, tree machines and quadtrees into host graphs such as
hypercubes and incomplete hypercubes. We also study dynamic
reconfiguration of complete binary trees in faulty hypercubes.
First, we embed a complete binary tree into an incomplete
hypercube of the smallest size so that the adjacency of the
complete binary tree is preserved, and look for an incomplete
binary tree in a hypercube. Second, we optimally embed a large
complete binary tree into a hypercube of limited size. Third,
we embed a tree machine into an incomplete hypercube with
expansion 1, and embed a large tree machine into a hypercube of
limited size with load-balance. Fourth, we embed a quadtree
into a hypercube so that the adjacency of the quadtree is
preserved, and embed a quadtree into an incomplete hypercube
with expansion 1. Fifth, we dynamically reconfigure to embed a
complete binary tree into a faulty hypercube, and the number of
the affected nodes of the complete binary tree are as few as
possible after reconfiguring.

Cover
Chinese Abstract
English Abstract
Acknowledgement
Contents
List of Figures
1 Introduction
1.1 Overview of Embedding graphs into Hypercubes
1.2 Outline of the Dissertation
2 Preliminaries
3 Embedding of Binary Trees into Hypercubes
3.1 Embedding of Complete Binary Trees into Smallest Incomplete Hypercubes
3.2 Embedding of Largest Incomplete Binary Trees into Hypercubes
4 Embedding of Large Complete Binary Trees into Hypercubes
4.1 Optimal Embedding of Th into Hh
4.2 Optimal Embedding of Large Complete Binary Trees into Hypercubes
5 Embedding of Trees Machines into Hypercubes
5.1 Embedding of Tree Machine into Inconplete Hypercubes with Expansion
5.2 Embedding of Large Trees Machines into Hypercubes
6 Embedding of Quadtrees into Hypercubes
6.1 Embedding of Quadtrees into Hypercubes with Dilation 1
6.2 Embedding of Quadtrees into Incomplete Hypercubes with Expansion 1
7 Dynamic Reconfiguration of Complete Binary Trees in Faulty Hypercubes
7.1 Reconfiguring of Th in a Faulty Hh+1
7.2 Reconfiguring of Th in Hh+2 with Faults
8 Conclusions
Bibliography
Vita