在弦環網路上建構完全獨立擴展樹

Completely independent spanning trees on chordal rings

姚星辰(Sing-Chen Yao)

指導教授 ： 楊進雄

國立臺北商業大學/管理學群/資訊與決策科學研究所/碩士(2013年)

https://doi.org/10.6818/NTUB.2013.00006

摘要

令 T1,T2,...,Tk 為圖 G 上的 k 棵擴展樹。在圖 G 上的任何兩點 u,v ，連接 u 和 v 這兩個點的路徑在 k 棵樹上互為點不相交，那麼 T1,T2,...,Tk 就被稱之為是在圖 G 上的一組完全獨立擴展樹。完全獨立擴展樹的建構可以被應用在互連網路上廣播的容錯和安全的訊息傳布。 Hasunuma 是第一位提出完全獨立擴展樹這個概念的學者，而且他還進一步的猜測在任何一個 2k-連通的圖形上，可以建構出 k 棵的完全獨立擴展樹。但是很不幸地這個猜測在最近被 Péterfalvi 推翻掉了。在本篇論文的內容當中，我們提出了在邊為 4 的弦環網路 CR(N,d) 上，滿足 N=k(d-1)+j 在 k≥4 是偶數且 0≤j≤4 的條件下，建構出兩棵完全獨立擴展樹的方法。此外，我們還推導出了每一棵建構出來的完全獨立擴展樹的直徑。

關鍵字

圖形理論 ； 連結網路 ； 環狀網路 ； 弦環網路 ； 獨立擴展樹 ； 完全獨立擴展樹

並列摘要

Let T1,T2,...,Tk be spanning trees in a graph G. If, for any two vertices u,v of G, the paths joining u and v on the k trees are mutually vertex-disjoint, then T1,T2,...,Tk are called completely independent spanning trees in G. The construction of completely independent spanning trees can be applied in fault-tolerant broadcasting and secure message distribution on interconnection networks. Hasunuma first introduced the concept of completely independent spanning trees and conjectured that there are k completely independent spanning trees in any 2k-connected graph. Although this conjecture was, unfortunately, disproved by Péterfalvi recently. In this thesis, we show that there are two completely independent spanning trees in 4-regular chordal rings CR(N,d) with N=k(d-1)+j under the conditions that k≥4 is even and 0≤j≤4. Moreover, the diameter of each constructed completely independent spanning tree is derived.

並列關鍵字

Graph theory ； Interconnection networks ； Rings ； Chordal rings ； Independent spanning trees ； Completely independent spanning trees

參考文獻

[1] B.W. Arden and H. Lee, Analysis of chordal ring network, IEEE Trans. Comput., 30 (1981) 291-295.

[2] F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi, Reliable broadcasting and secure distributing in channel networks, in: Proc. 3rd Int. Symp. Parallel Architectures, Algorithms and Networks (ISPAN '97), Taipei, Dec. 1997, 472-478.

[3] F. Bao, Y. Igarashi, and S.R. Öhring, Reliable broadcasting in product networks, Discrete Appl. Math., 83 (1998) 3-20.

[4] J.C. Bermond, F. Comellas, and D.F. Hsu, Distributed loop computer networks: a survey, J. Parallel Distrib. Comput., 24 (1995) 2-10.

[5] N. Chalamaiah and B. Ramamurthy, Finding shortest paths in distributed loop networks, Inform. Process. Lett., 67 (1998) 157-161.