旋轉圖(bi-rotator graph)最早是由Corbett在1994年所提出的，近幾年來被廣泛的研究。旋轉圖(rotator graph) 經由修改後，將原有的邊由單向改為雙向，因此就成了雙向旋轉圖。誠如星狀圖(star graph)一樣，雙向旋轉圖擁有許多良好的特性，像是點對稱(node symmetry)、較低的直徑(low diameter)，以及遞回建構(recursive construction)。
本篇論文主要是在探討如何在任意規模(scale)的雙向旋轉圖下，建構獨立展開樹(independent spanning trees)。在規模為n的雙向旋轉圖中是由n!的點所構成，而且它每個點的分支度(degree)為2n-3。展開樹(spanning trees)它包涵了原圖所有的頂點，且由它所構成的邊是不會有循環的。在一個展開樹中，假如它的任一有向邊均不會與其它展開樹中的邊相同時，我們就可稱這個樹為獨立展開樹。獨立展開樹通常被用來做容錯廣播(fault tolerance broadcasting)。當欲由根節點廣播到其它節點時，每一個獨立展開樹均可充份被利用到，因此，在雙向旋轉圖的容錯廣播，藉由建構這些獨立展開樹即可很容易的實現。
本篇論文，藉著點對稱和遞回建構的特性提供了一個有效率的演算法來建構雙向旋轉圖的獨立展開樹。我們所提出的演算法可建構出2n-3個獨立展開樹座落在n-BR上的一個點，且這個數量已被證明是最大值。

Rotator graphs, first proposed by Corbett in 1994, have been studied in recent years. Later, traditional rotator graphs were modified by adding generation functions to make all edges bi-directional called bi-rotator graphs. Like star graphs, Bi-Rotator graphs also possess rich structure properties, such as symmetry, low diameter and recursive construction.
This thesis focuses on the problems of constructing independent spanning trees for a given scale of the bi-rotator graphs. A bi-rotator graph of scale n contains n! nodes and degree of each node is 2n-3. A spanning tree of a graph is composed of all nodes of the original graph and parts of edges which connect all nodes and form no cycles. Spanning trees are said to be independent if a directed edge can only be consisted in one tree; that is, there exist no common edges in two or more trees. Independent spanning trees are usually utilized in fault-tolerant broadcasting. Each of the independent spanning trees can be applied in a broadcasting process which sends messages from the root to all other nodes through the edges of the tree. Hence, fault tolerance broadcasting in the bi-rotator graph can be achieved by providing multiple independent spanning trees of the graph.
Applying the properties of symmetry and recursive construction, the thesis presents an efficient algorithm of constructing independent spanning trees for a bi-rotator graph. Our algorithm constructs 2n-3 independent spanning trees rooted at a designated node for an n-BR. Hence, the number of the spanning tree is proved to be maximum.

Abstract II
List of figures VI
List of tables VIII
Chapter 1 Introduction 1
1-1. Background and motivation 1
1-2. Outline of the thesis 5
Chapter 2 Preliminaries 7
2-1. Topological properties of the bi-rotator graph 7
2-2. Independent spanning trees 9
2-3. Idea of independent spanning trees construction 11
Chapter 3 Construction of independent spanning trees 13
3-1. Notation and definition 14
3-2. Construction of independent spanning trees algorithm 27
3-3. The upper bound of independent spanning trees’ height 30
3-4. An example of construction of independent spanning
trees 32
3-5. The correctness of our algorithm 52
Chapter 4 Conclusion 54
References 55

[1] 林宏仁，旋轉圖的分散式廣播演算法，國立台灣科技大學資訊管理研究所，民國86年。
[2] 洪明豪，星狀圖連通網路上尋找點互異的路徑和邊互異的延展樹之演算法，私立逢甲大學資訊工程研究所，民國82年。
[3] S. B. Akers and B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks”, IEEE Trans. on Computers, vol.38, no.4, pp.555-565, April 1989.
[4] M. Benmaiza and A. Touzene, “One-to-all broadcast algorithm for constant 4 degree cayley graphs”, Parallel Computing, vol.25, pp249-269, 1999.
[5] Ge-Ming Chiu, and Kai-Shung Chen, “Efficient fault-tolerance multicast scheme for hypercube multicomputers”, IEEE Trans. on Parallel and Distributed Systems, vol.9, no.10, pp.952-962, Oct. 1998.
[6] P. F. Corbett, “Rotator graphs: An efficient topology for point-to-point multiprocessor networks”, IEEE Trans. on Parallel and Distributed Systems, vol.3, no.5, pp.622-626, Sept. 1992.
[7] P. Fragopoulou and S. G. Akl, “Edge-disjoint spanning trees on the star network with applications to fault tolerance”, IEEE Trans. on Computers, vol.45, no.2, pp.174-185, Feb. 1996.
[8] H. P. Katseff, “Incomplete hypercubes”, IEEE Trans. on Computers, vol.37, no.5,pp604-607, May 1988.
[9] S. Khuller and B. Schieber, “On independent spanning trees”, Information Processing Letters, vol.42, pp.321-323, 1992.
[10] Y. Lan, “An adaptive fault-tolerance routing algorithm for hypercube multicomputers”, IEEE Trans. on Parallel and Distributed Systems, vol.6, no.11, pp.1147-1152, Nov. 1995.
[11] Hon-Ren Lin and Chiun-Chieh Hsu, “Distributed broadcasting algorithms in rotator graphs”, Communication of IICM, pp.53-66, Dec. 2001.
[12] Hon-Ren Lin and Chiun-Chieh Hsu, “Topological properties of bi-rotator graphs”, IEICE Trans. Inf. & Syst., pp.2172-2178, Vol.E86-D, no10, Oct. 2003.
[13] V. E. Mendia and D. Sarkar, “Optimal broadcasting on the star graph interconnection network”, IEEE Trans. on Parallel and Distributed Systems, vol.3, no.4, pp.389-396, July 1992.
[14] Shin-Hsien Sheu and Chang-Biau Yang, “Multicast algorithms for hypercube multiprocessors”, Journal of Parallel and Distributed Computing, vol. 61, pp.137-149, 2001.
[15] Yu-Chee Tseng and Jang-Ping Sheu, “Toward optimal broadcast in a star graph using multiple spanning trees”, IEEE Trans. on Computers, vol.46, no.5, pp.593-599, 1997.
[16] Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi, “Independent spanning trees of chordal rings”, Information Processing Letters, vol.69, pp.155-160, 1994.
[17] Z. Jovanovic and J. Misic, “Fault tolerance of the star graph interconnection network”, Information Processing Letters, vol.49, no.3, pp.145-150, Feb. 1994.
[18] K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi, “Independent spanning trees of product graphs and their construction”, IEICE Trans. Fundamentals, vol.E97-A, no.11, pp.1894-1903, Nov. 1996.
[19] P. Ramanathan and K. G. Shin, “Reliable broadcast in hypercube multicomputers”, IEEE Trans on Computers, vol.46, no.5, pp1654-1657, Dec. 1988.
[20] J. Wu, “Reliable unicasting in faulty hypercubes using safety levels”, IEEE Trans. on Computers, vol.46, no.2, pp.241-247, Feb. 1997.