在分散式的網路架構下，獨立展開樹(independent spanning trees)的建構能讓根節點便於從中找到數條互斥的路徑。這些互斥路徑，可使訊息廣播(broadcasting)具有容錯性，容許多個節點失效時仍可完成廣播程序；並且可對同一節點進行平行傳輸，達到分散負載及縮短完成時間的目的；此外，互斥路徑的平行傳輸方式，也可被應用於訊息安全分送。
近年，有許多學者進行互斥展開樹的研究，其中在1989年Zehavi和Itai兩位學者猜測在k-連結圖(k-connected graph)任意節點為根節點r的情況下，都存在k棵互斥展開樹，但目前仍只有k≤4的情況下被證實，至於k≥5的情況仍是未被解開的問題。
本文將探討一般性弦環圖(general chordal rings)互斥展開樹的建構問題。在環形圖(circulant graph)家族裡，分支度為四的弦環圖(chordal ring)及遞迴環形圖(recursive circulant graph)已經找到點互斥展開樹之建構方法；由於一般性弦環圖需要比前兩者建構更多的互斥展開樹，因此建構的難度也隨之提高。本文將更進一步分析一般性弦環圖基本路徑和延伸路徑的組成，以及以弦將節點切割的情況，提出在一般性弦環圖建構與分支度(δ_m)相同數量的邊互斥展開樹，並證明其演算法之正確性。

In a distributed network, independent spanning trees can be constructed by joining several disjoint paths rooted on the same node. These disjoint paths can be used for fault-tolerant message broadcasting, which can guarantee successful transmission of data even if some nodes and links fail. Another application of independent spanning trees is concurrent transmission of data from one node along disjoint paths to another, which can distribute the transmission load and reduce transmission time. In addition, we can utilize the disjoin paths to accomplish security message distribution.
In 1989, Zehavi and Itai conjectured that, for any node r in the k-connected graph G, there exist k disjoint spanning trees of G rooted at r. This conjecture has been proved only for k-connected graph with k ≤ 4, and it is still open for arbitrary k-connected graph when k ≥ 5.
In this thesis, we will propose a method of constructing multiple disjoint spanning trees on general chordal rings. Four-degree chordal rings and recursive circulant graphs are two kinds of circulant graphs, for which node-disjoint spanning trees have been confirmed. Since the number of disjoint spanning trees needed to construct on the general chordal ring is larger than those on the two graphs, it is more difficult to construct the disjoint spanning trees on the general chordal ring. First we explore topological properties of the general chordal ring. Then we use the proposed topological properties to find disjoint elementary paths and extend paths on the general chordal ring. Based on these paths, an algorithm is presented for constructing edge-disjoint spanning trees and the correctness of its algorithm is proved, where the number of edge-disjoint spanning trees is just the same as the connectivity of the general chordal ring.

[1]T. Araki, “Edge-pancyclicity of recursive circulants”, Information Processing Letters, Vol. 88, pp. 287–292, 2003.
[2]T. Araki and Y. Shibata, “Pancyclicity of recursive circulant graphs”, Information Processing Letters, Vol. 81, pp. 187–190, 2002.
[3]B.-W. Arden and H. Lee, “Analysis of chordal ring network”, IEEE Trans. Computers, Vol. 30, pp. 291-295, 1981.
[4]F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi, “Reliable broadcasting and secure distributing in channel networks”, Proc. of 3rd International Symposium on Parallel Architectures, Algorithms and Networks, pp. 472-478, 1997.
[5]J.-C. Bermond, F. Comellas, and D.-F. Hsu, “Distributed loop computer networks: A survey”, Journal of Parallel and Distributed Computing, Vol. 24, pp. 2-10, 1995.
[6]N. Chalamaiah and B. Ramamurthy, “Finding shortest paths in distributed loop networks”, Information Processing Letters, Vol. 67, pp. 157-161, 1998.
[7]J. Cheriyan and S.-N. Maheshwari, “Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs”, Journal of Algorithms, Vol. 9, pp. 507-537, 1998.
[8]I. Chung, Construction of a paralled and shortest routing algorithm o recursive circulant networks, Proc. 4th International Conference on High Performance Computing in the Asia-Pacific Region, pp. 580-585, 2000.
[9]S. Curran, O. Lee, and X. Yu, “Finding four independent trees”, SIAM Journal on Computing, Vol. 35, pp. 1023-1058, 2006.
[10]D.-Z. Du, D.-F. Hsu, Q. Li, and J. Xu, “A combinational problem related to distributed loop networks”, Networks, Vol. 20, pp. 173-180, 1990.
[11]P. Erdős and F.-D. Hsu, “Distributed loop network with minimum transmission Delay”, Theoretical Computer Science, Vol. 100, pp. 223-241, 1992.
[12]S.-Y. Hsieh and C.-J. Tu, “Constructing edge-disjoint spanning trees in locally twisted cubes”, Theoretical Computer Science, Vol. 410, pp. 926-932, 2009.
[13]A. Huck, “Independent trees in graphs”, Graphs and Combinatorics, Vol. 10, pp. 29-45, 1994.
[14]A. Huck, “Independent trees in planar graphs”, Graphs and Combinatorics, Vol. 15, pp. 29-77, 1999.
[15]A. Itai and M. Rodeh, “The multi-tree approach to reliability in distributed networks”, Information and Computation, Vol. 79, pp. 43-59, 1988.
[16]Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi, “Independent spanning trees of chordal rings”, Information Processing Letters, Vol. 69, pp. 155-160, 1999.
[17]C. Kim, J. Choi and H.-S. Lim, “Embedding full ternary trees into recursive circulants”, Proc. First EurAsian Conference on Information and Communication Technology, pp. 874–882, 2002.
[18]S. Kim and I. Chung, “Application of the special Latin square to parallel routing algorithm on a recursive circulant network”, Information Processing Letters, Vol. 66, pp. 141-147, 1998.
[19]H.-S. Lim, J.-H. Park and K.-Y. Chwa, “Embedding trees in recursive circulants”, Discrete Applied Mathematics, Vol. 69, pp. 83–99, 1996.
[20]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, pp. 414-419, 2010.
[21]Y.-J. Liu, W.-Y. Chou, J.-K. Lan, and C.-Y. Chen, “Constructing Independent Spanning Trees for Hypercubes and Locally Twisted Cubes”, Proc. of 10th International Symposium on Pervasive Systems, Algorithms, and Networks, pp. 17-22, 2009.
[22]K. Miura, D. Takahashi, S. Nakano and T. Nishizeki, “A linear-time algorithm to find four independent spanning trees in four-connected planar graphs”, International Journal of Foundations of Computer Science, Vol. 10, pp. 195-210, 1999.
[23]K. Mukhopadhyaya and B.-P. Sinha, “Fault-tolerant routing in distributed loop networks”, IEEE Trans. Computers, Vol. 44, pp. 1452-1456, 1995.
[24]S. Nagai and S. Nakano, “A linear-time algorithm to find independent spanning trees in maximal planar graphs”, Proc. 26th Workshop on Graph-Theoretic Concepts in Computer Science, Vol. E84-A, pp. 1102-1109, 2001.
[25]L. Narayanan and J. Opatrny, “Compact routing on chordal rings of degree four”, Algorithmica, Vol. 23, pp. 72-96, 1999.
[26]K. Obokata, Y. Iwasaki and F. Bao, Y. Igarashi, “Independent spanning trees of product graphs and their construction”, Lecture Notes in Computer Science, Vol. 1197, pp. 338-351, 1996.
[27]B. Parhami and D.-M. Kwai, “Periodically regular chordal rings”, IEEE Trans. Parallel and Distributed Systems, Vol. 10, pp. 658-672, 1999.
[28]J.-H. Park, “Strong hamiltonicity of recursive circulants”, Journal of Korean Information Science Society, Vol. 28, pp.742–744, 2001.
[29]J.-H. Park and K.-Y. Chwa, “Recursive circulant: A new topology for multicomputer networks, Proc. of International Symposium on Parallel Architectures, Algorithms and Networks, pp. 73-80, 1994.
[30]J.-H. Park and K.-Y. Chwa, “Recursive circulants and their embeddings among hypercubes”, Theoretical Computer Science, Vol. 244, pp. 35–62, 2000.
[31]S.-M. Tang and Y.-L. Wang, “Generalized recursive circulant graphs”, Proc. of National Computer Symposium, pp. 127-132, 2009.
[32]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.
[33]C.-H. Tsai, Jimmy J.-M. Tan, Y.-C. Chuang and L.-H. Hsu, “Hamiltonian propertiesof faulty recursive circulant graphs”, Journal of Interconnection Networks, Vol. 3, pp. 273–289, 2002.
[34]I. Stojmenovic, Multiplicative circulant networks: Topological properties and communication algorithms, Discrete Applied Mathematics, Vol. 77, pp. 281-305, 1997.
[35]J.-S. Yang, J.-M. Chang, S.-M. Tang and Y.-L. Wang, “Reducing the height of independent spanning trees in chordal rings”, IEEE Trans. Parallel and Distributed Systems, Vol. 18, pp. 644-657, 2007.
[36]J.-S. Yang, J.-M. Chang, S.-M. Tang and Y.-L. Wang, “On the independent spanning trees of recursive circulant graphs G(cdm,d) with d > 2”, Theoretical Computer Science, Vol. 410, pp. 2001-2010, 2009.
[37]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.
[38]J.-S. Yang, S.-M. Tang and Y.-L. Wang, “Constructing multiple independent spanning trees on recursive circulant graphs G(2^m, 2)”, International Journal of Foundations of Computer Science, Vol. 21, pp. 73-90, 2010.
[39]A. Zehavi and A. Itai, “Three tree-paths”, Journal of Graph Theory, Vol. 13, pp. 175-188, 1989.
[40]G.-W. Zimmerman and A.-H. Esfahanian, “Chordal rings as fault-tolerant loops”, Discrete Applied Math., Vol. 37/38, pp. 563-573, 1992.