臺灣博碩士論文加值系統

超立方體(hypercube)架構從提出後就引起學者很大的研究興趣，相關的研究成果也不斷地被發表，而超立方體的變形架構也陸續地被提出來[1, 2, 4]，這是因為這些架構有著優良的拓樸(topology)特性[16]，例如短的直徑(diameter)、簡潔的繞徑(routing)與廣播(broadcasting)演算法、良好的嵌入(embedding)與容錯(fault-tolerance)特性…等。而在這些架構中建立多棵展開樹(spanning trees)也是個重要的議題，展開樹可分為邊互斥展開樹(edge-disjoint spanning tree)及獨立展開樹(independent spanning tree)。
近年，有許多學者進行互斥展開樹的研究，其中在1989年，Zehavi和Itai[21]兩位學者猜測在k-連結圖(k-connected graph)任意節點為根節點r的情況下，都存在k棵互斥展開樹，但目前仍只有k≦4的情況下被證實，至於k≧5的情況仍是未被解開的問題。
擴展立方體(augmented cubes)是超立方體的其中一種變型架構，比超立方體有更短的直徑和更高的分支度(degree)。由於分支度較高，在擴展立方體上建構多重展開樹的難度也相對提高。我們發現數個在擴展立方體上建構多重展開樹新的特性，並用來調整展開樹上某些父親節點使所有展開樹仍然互斥。本論文利用格雷碼轉二進制碼的特性與新的父親節點調整方法，提出在擴展立方體上建構最多棵的2n－1棵邊互斥展開樹的演算法。

The hypercube has received much attention since it was proposed and many related research results have been presented. Moreover, many variant structures of hypercube [1, 2, 4] have also been proposed. This is because hypercube-like interconnection networks have regular structures and good topological properties, such as smaller diameters, simple routing and broadcasting algorithms, good embedding and fault-tolerant properties, … etc. Furthermore, constructing multiple spanning trees is an importance issue on these structures, where spanning trees can be divided into edge-disjoint and vertex-disjoint (independent) spanning trees.
In fact, Zehavi and Itai [21] conjectured that for any k-connected graph G and each vertex r of G, there exist k disjoint spanning trees of G rooted at r. This conjecture has been confirmed only for k-connected graphs with k≦4, and it is still open for arbitrary k-connected graphs when k≧5.
The augmented cube is a variant of the hypercube, which has smaller diameter and larger degree than those of the hypercube. It is more difficult to construct spanning trees in the augmented cubes than that in the hypercube due to its large degree. We explore several properties in the construction of spanning trees in the augmented cubes, which is utilized to adjust parents of some nodes in the spanning trees in order to remain all spanning trees disjoint. In this thesis, using the conversion of gray codes to binary codes and new methods of parent adjustment, we present an algorithm for constructing (2n－1) edge-disjoint spanning trees on the n-dimensional augmented cubes.

第一章 緒論 1
1.1 研究動機與目的 1
1.2 研究方法與貢獻 1
1.3 論文架構 3
第二章 文獻探討 4
2.1 超立方體 4
2.2 漢明距離拉丁方陣 5
2.3 擴展立方體 8
2.4 邊互斥展開樹 10
第三章 研究方法 13
3.1 在超立方體上建構獨立展開樹 13
3.2 格雷碼轉二進制 17
3.3 調整演算法 25
第四章 結論與未來展望 42

[1]S. A. Choudum and V. Sunitha, “Augmented Cubes”, NETWORKS, Vol. 40, No. 2, pp. 71–84, 2002.
[2]P. Cull and S. M. Larson, “The Mobius cubes”, IEEE Trans. Compt., Vol. 44, pp. 647–659, 1995.
[3]S. Curran, O. Lee and X. Yu, “Finding four independent trees”, SIAM Journal on computing, Vol. 35, pp. 1023–1058, 1991.
[4]K. Efe, “A Variation on the hypercube with lower diameter”, IEEE Trans. Compt., Vol. 40 pp. 1312–1316, 1991.
[5]P. Fragopoulou and S. G. Akl, “Edge-disjoint spanning trees on the star network with applications to fault tolerance”, IEEE Trans. Compt., Vol. 45, No. 2, 1996.
[6]P. Fraigniaud and C. T. Ho, “Arc-disjoint spanning trees on the cube-connected-cycles network”, in: Proc. of the International Conference on Parallel Processing, Vol. 1, pp. 225–229, 1991.
[7]S. Y. H. Hsieh and C. J. Tu, “Constructing edge-disjoint spanning trees in locally twisted cubes”, Theoretical Computer Science, Vol. 410, pp. 926–932, 2009.
[8]A. Huck, “Independent trees in Planar Graphs”, Graphs and Combinatorics, Vol. 15, pp. 29–77, 1999.
[9]Y. Iwasaki, Y. Kajiwara, K. Obokata and Y. Igarashi, “Independent spanning trees of chordal rings”, Information Processing Letters, Vol. 69, pp. 155–160, 1999.
[10]S. L. Johnson and C. T. Ho, “Optimum broadcasting and personalized communication in hypercubes”, IEEE Trans. Compt., Vol. 38, pp. 1249–1268, 1989.
[11]C. T. Lin, “Embedding k(n－k) edge-disjoint spanning trees in arrangement graphs”, Journal of Parallel and Distributed Computing, Vol. 63, pp. 1277–1287, 2003.
[12]J. C. Lin, J. S. Yang, C. C. Hsu and J. M. Chang, “Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes”, Information Processing Letters, Vol. 110, Issue 10, pp. 414-419, 2010.
[13]Y. J. Liu, W. Y. Chou, J. K. Lan and C. Y. Chen, “Constructing independent spanning trees for hypercubes and locally twisted cubes”, Proceedings of 10th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2009), pp. 17–22, 2009.
[14]K. Obokata, Y. Iwasaki, F. Bao and Y. Igarashi, “Independent spanning trees of product graphs and their construction”, IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E79-A, pp. 1894–1903, 1996.
[15]P. Ramanathan and K. G. Shin, “Reliable broadcast in hypercube multicomputers”, IEEE Trans. Compt., Vol. 37, pp. 1654–1657, 1988.
[16]Y. Saad and M. H. Schultz, “Topological properties of hypercube”, IEEE Trans. Compt., Vol. 34, pp. 867–872, 1988.
[17]S. M. Tang, Y. L. Wang and Y. H. Leu, “Optimal independent spanning trees on hypercubes”, Journal of Information Science and Engineering., Vol. 20, pp. 143–155, 2004.
[18]M. C. Yang, “Constructing edge-disjoint spanning trees in twisted cubes”, Information Sciences, Vol. 180, pp. 4075–4083, 2010.
[19]J. S. Yang, J. M. Chang and H. C. Chan, “Independent spanning trees on folded hypercubes”, Proceedings of 10th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2009), pp. 73–83, 2009.
[20]J. S. Yang, S. M. Tang, J. M. Chang and Y. L. Wang, “Parallel construction of optimal independent spanning trees on hypercubes”, Parallel Computing, Vol. 33, pp. 73–79, 2007.
[21]A. Zehavi and A. Itai, “Three tree-paths”, Journal of Graph Theory, Vol. 13, pp. 175–188, 1989.