基礎WK遞迴金字塔與三角金字塔之研究

A Study on Basic WK-Recursive Pyramids and Triangular Pyramids

王怡君(Yi-Chun Wang)

指導教授 ： 阮夙姿

國立暨南國際大學/科技學院/資訊工程學系/博士(2015年)

https://doi.org/10.6837/NCNU.2015.00155

摘要

在一個圖形(graph)G中，一個迴圈(cycle)若包含了圖形G中所有的點各一次，則稱此迴圈為漢彌爾頓迴圈(Hamiltonian cycle)。若圖形G中存在漢彌爾頓迴圈則稱此圖為漢彌爾頓圖(Hamiltonian graph)。在G中，若一條路徑(path)包含了G中所有的點各一次，則稱此路徑為漢彌爾頓路徑(Hamiltonian path)。一個圖形中，若任兩點間皆存在漢彌爾頓路徑，則此圖型被稱為漢彌爾頓連通(Hamiltonian-connected)。以上的問題一般被統稱為漢彌爾頓性質(Hamiltonicity)。圖形G中若存在長度從三至圖G點數的各種大小的迴圈，稱G擁有泛迴圈性質(pancyclic)。若圖形G中，任意兩點均被包含於長度從m至圖G點數的各種大小的迴圈中，則稱G擁有m泛圈連通度性質(m-pancycle-connectivity)。路由(route)的意思是，一個起點將傳輸訊息給一個目的點。而路由演算法(routing algorithm)將在給定起點和終點後，決定出一條訊息傳輸的路徑。執行路由演算法後，若這條路徑剛好為起點與終點的最短路徑，這個演算法即被稱為最短路徑路由演算法(shortest path routing algorithm)。廣播(broadcast)的定義為，一個帶有訊息的起點將會把訊息傳給圖上其他所有點。而廣播演算法(broadcasting algorithm)則將決定每一個點在收到訊息後，該將訊息傳給哪些點。一個廣播演算法將在圖型中被每個點分別執行並完成資訊傳遞。考慮起點到圖中任意點的訊息傳輸路徑，若每條路徑皆為該兩點的最短路徑，則稱此演算法為最佳廣播演算法(optimal broadcasting algorithm)。

本論文將討論兩個變形的金字塔網路圖形。第一個圖形是我們所定義的基礎WK遞迴金字塔(basic WK-recursive pyramid)，由於這個圖形由WK遞迴網路(WK-recursive networks)所組成，因此本論文主要解決了在有壞點與無壞點的狀況下之WK遞迴金字塔的漢彌爾頓性質、泛圈圖性質與m-泛圈連通度性質，此時的m為(2^{l+1}-2)，其中，l為圖形的高度。第二個圖型則是由Razavi與Sarbazi-Azad於2010年所定義的三角金字塔(triangular pyramid)。由於三角金字塔是由三角格狀圖(triangular meshes)所組成，因此這篇論文在此兩種圖形上研究了最短路徑路由演算法和最佳廣播演算法。

關鍵字

漢彌爾頓 ； 路由演算法 ； 廣播演算法 ； 三角金字塔 ； 基礎WK遞迴金字塔

並列摘要

A Hamiltonian cycle is a cycle that contains every vertex of G exactly once. A graph G is Hamiltonian if there exists a Hamiltonian cycles in G. A Hamiltonian path is a path that contains every vertex of G exactly once. A graph G is Hamiltonian-connected if every two distinct vertices of G are connected by a Hamiltonian path. Above problems are called Hamiltonicity of G. A graph is pancyclic if it embeds cycles of every length ranging from 3 to |V(G)|. A graph G is m-pancycle-connected if and only if any two vertices of G are in a common cycle of all lengths ranging from m to |V(G)|.

In routing, a source vertex sends a message to a target vertex and the routing algorithm decides a path from the source vertex to the target vertex. If the routing path is a shortest path between any vertices pair, the algorithm is a shortest path routing algorithm. In broadcasting, one source has a message which must be sent to all other vertices. The broadcasting algorithm can decide successors of the source vertex or each intermediate vertex. Note that, this thesis uses all ports routers, that is, a message from one vertex can be sent to all its neighbors at the same time. A broadcasting algorithm is executed in parallel on each vertex and considering the path of message transmission between source and any the other vertex in G. If all paths are the shortest paths between a source vertex and every destination vertex, the broadcasting algorithm is optimal.

This thesis studies above problems on two variants of pyramid networks. One is the basic WK-recursive pyramid, which is a special case of the WK-recursive pyramid. The WK-recursive pyramid is proposed by Fernandes and Kanevsky in 1993. Because each basic WK-recursive pyramid consists of the WK-recursive networks, we discuss the the WK-recursive networks at the same time. This thesis shows the Hamiltonicity of the Basic WK-recursive pyramid with/without fault vertices, proves that the basic WK-recursive pyramid is pancyclic, m-pancycle-connected, where m = (2^{l+1}-2) and l is the number of layer of the basic WK-recursive pyramids. The other is the triangular pyramid, defined by Razavi and Sarbazi-Azad in 2010. Each triangular pyramid consists of the triangular meshes, so we also need to study the triangular meshes. This thesis designs shortest path routing algorithms and broadcasting algorithms for the triangular meshes and the triangular pyramids, and proves that the proposed algorithms are optimal. Additionally, every intermediate vertex in the triangular meshes and the triangular pyramids determines its successors without knowing the position of the source vertex.

並列關鍵字

Hamiltonicity ； Routing algorithms ； Broadcasting algorithms ； Triangular pyramids ； basic WK-recursive pyramids

參考文獻

[1] F. Buckley and F. Harary, Distance in Graphs. Addisson-Wesley, Longman, 1990.

[2] F. Cao, D.-Z. Du, D. Hsu, and S.-H. Teng, “Fault tolerance properties of pyramid networks,” IEEE Transactions on Computers, Vol. 48, No. 1, pp. 88-93, 1981.

[3] J.-M. Chang, J.-S. Yang, Y.-L. Wang, and Y. Cheng, “Pan-connectivity, fault-tolerant hamiltonicity and hamiltonian connectivity in alternating group graphs in alternating group graphs,” Networks, Vol. 44, No. 4, pp. 302-310, 2004.

[4] J.-M. Chang, J.-S. Yang, Y.-L. Wang, and Y. Cheng, Panconnectivity, fault-tolerant hamiltonicity, hamiltonian-connectivity in alternating group graphs,- Networks, Vol. 14, pp. 302-310, 2004.

[5] G.-H. Chen and D.-R. Duh, “Topological properties, communication, and computation on WK-recursive network,” Networks, Vol. 24, No. 6, pp. 303-317, 1994.