臺灣博碩士論文加值系統

在一個圖形(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)所組成，因此這篇論文在此兩種圖形上研究了最短路徑路由演算法和最佳廣播演算法。

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.

誌謝I
論文摘要II
Abstract IV
Contents VI
List of Figures VIII
List of Tables X
1 Introduction 1
2 Preliminary 5
2.1 The WK-recursive Network and the Basic WK-recursive Pyramid 5
2.2 Triangular Meshes and Triangular Pyramids 10
3 WK-recursive Networks and WK-recursive Pyramids 12
3.1 Hamiltonicity 12
3.2 Pancyclic and (2l+1

[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.
[6] Y.-C. Chen, Pancycles and Hamiltonian Connectedness of the Pyramid Network with One Node or One Edge Fault. Master Thesis, Department of Computer Science and Information Engineering, National Chi Nan University, Puli, Nantou Hsien, Taiwan, Republice of China, 2003.
[7] Y.-C. Chen, The Enhanced Pyramid Network: An Attractive to the Pyramid Network. Master Thesis, Department of Computer Science and Information Engineering, National Chi Nan University, Puli, Nantou Hsien, Taiwan, Republice of China, 2005.
[8] Y.-C. Chen and D.-R. Duh, “An optimal broadcasting algorithm for enhanced pyramid networks,” Proc. of the 22nd Workshop on Combinatorial Mathematics and Computational Theory, National Cheng Kung University, Tainan, Taiwan, pp. 206-211, 2005.
[9] Y.-C. Chen and D.-R. Duh, “Proof that enhanced pyramid networks are 2-edge-hamitonicity,” Proc. of the 23nd Workshop on Combinatorial Mathematics and Computational Theory, Dayeh University, Changhua, Taiwan, pp. 76-84, 2006.
[10] Y.-C. Chen and D.-R. Duh, “Two-node-hamiltonicity of enhanced pyramid networks,” Information Sciences, Vol. 180, No. 13, pp. 2588-2595, 2010.
[11] Y.-C. Chen, D.-R. Duh, and H.-J. Hsieh, “On the enhanced pyramid network,” Proc. of International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, USA, pp. 1483-1489, 2004.
[12] Y.-C. Chen, D.-R. Duh, and R.-Y. Wu, “Hamiltonian-connectedness of the pyramid networks with one fault node,” Proc. of International Conference on Parallel and Distributed Computing and Networks, pp. 147-152, 2005.
[13] Y.-Y. Chen, D.-R. Duh, T.-L. Ye, and J.-S. Fu, “Weak-vertex-pancyclicity of (n, k)-star graphs,” Theoretical Computer Science, Vol. 396, pp. 191-199, 2008.
[14] L. Cinque and G. Bongiovanni, “Parallel prefix computation on a pyramid computer,” Pattern Recognition Letter, Vol. 16, No. 1, pp. 19-22, 1995.
[15] R. Cipher and H. L. G. Sanz, “SIMD architectures and algorithms for image processing and computer vision,” IEEE Transactions on Acoustic, Speech, and Signal Processing, Vol. 37, No. 12, pp. 2158-2174, 1989.
[16] G. Della Vecchia and C. Sanges, “Recursively scalable networks for message passing architectures,” Parallel Processing and Applications, pp. 33-40, 1987.
[17] G. Della Vecchia and C. Sanges, “An optimized broadcasting technique for WK-recursive topologies,” Future Generation Computer Systems, Vol. 5, pp. 353-357, 1990.
[18] D.-R. Duh and G.-H. Chen, “Topological properties of WK-recursive network,” Journal of Parallel and Distributed Computing, Vol. 23, pp. 468-474, 1994.
[19] D.-R. Duh, Y.-C. Chen, and R.-Y. Wu, “Proof that pyramid networks are 1-hamiltonian-connected with high probability,” Information Sciences, Vol. 177, No. 19, pp. 4188-4199, 2007.
[20] C. R. Dyer and A. Rosenfeld, “Triangle cellular automata,” Information and Control, Vol. 48, No. 1, pp. 54-69, 1981.
[21] J.-F. Fang, Y.-R. Wang, and H.-L. Huang, “The m-pancycle-connectivity of a WK-recursive network,” Information Sciences, Vol. 177, pp. 5611-5619, 2007.
[22] M. H. Farahabady, N. Imani, and H. Sarbazi-Azad, “Some topological and combinatorial properties of WK-recursive mesh and WK-pyramid interconnection networks,” Journal of Systems Architecture, Vol. 54, No. 10, pp. 967-976, 2008.
[23] R. Fernandes, “Recursive interconnection networks for multicomputer networks,” Proc. of the 1992 International Conference on Parallel Processing, Vol. I, pp. 76-79, 1992.
[24] R. Fernandes, D. Friesen, and A. Kanevsky, “Embedding rings in recursive networks,” Proc. of Sixth Symposium on Parallel and Distributed Processing, pp. 273-280, 1994.
[25] R. Fernandes and A. Kanevsky, “Hierarchical WK-recursive topologies for multicomputer systems,” Proc. of the 1993 International Conference on Parallel Processing, Vol. I, pp. 315-318, 1993.
[26] J. S. Fu, “Hamiltonicity of the WK-recursive network with and without faulty nodes,” IEEE Transactions on Parallel and Distribured Systems, Vol. 16, No. 9, pp. 853-865, 2005.
[27] F. Harary and J. Hayes, “Edge fault tolerance in graphs,” Networks, Vol. 23, pp. 135-142, 1993.
[28] H.-J. Hsieh, omega-wide Diameters of Enhanced Pyramid Networks. Ph.D Thesis, Department of Computer Science and Information Engineering National Chi Nan University, Puli, Nantou Hsien, Taiwan, Republice of China, 2011.
[29] H.-J. Hsieh and D.-R. Duh, “Average distances of pyramid networks,” Proc. of International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, USA, pp. 171-176, 2006.
[30] H.-J. Hsieh and D.-R. Duh, “omega-wide diameters of enhanced pyramid networks,” Theoretical Computer Science, Vol. 412, No. 29, pp. 3658-3675, 2011.
[31] H.-J. Hsieh, D.-R. Duh, and J.-S. Shiau, “A constant time shortest path routing algorithm for pyramid network,” Proc. of International Conference on Parallel and Distributed Computing and Systems, MIT Cambridge, MA, USA, pp. 71-75, 2004.
[32] S.-Y. Hsieh and N.-W. Chang, “Pancyclicity on the Mobius cube with both faulty nodes and faulty edges,” IEEE Transactions on Computers, Vol. 55, No. 7, pp. 854-863, 2006.
[33] S.-Y. Hsieh and N.-W. Chang, “Extended fault-tolerant cycle embedding in faulty hypercubes,” IEEE Transactions on Reliability, Vol. 58, No. 4, pp. 702-710, 2009.
[34] J. F. Jenq and S. Sahni, “Image shrinking and expanding on a pyramid,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 11, pp. 1291-1296, 1993.
[35] J. S.-T. Juan and C.-M. Huang, “On the strong distance problems of pyramid networks,” Applied Mathematics and Computation, Vol. 195, No. 1, pp. 154-161, 2008.
[36] M. Ma and P. Wang, “Some new topological properties of the triangular pyramid networks,” Information Sciences, Vol. 248, pp. 239-245, 2013.
[37] S. Razavi and H. Sarbazi-Azad, “The triangular pyramid: Routing and topological properties,” Information Sciences, Vol. 180, pp. 2328-2339, 2010.
[38] H. Sarbazi-Azad, M. Ould-Khaoua, and L. M. Mackenzie, “Algorithmic construction of hamiltonians in pyramids,” Information Processing Letters, Vol. 80, No. 2, pp. 75-79, 2001.
[39] Z. Shen, “An routing algorithm for the pyramid structures,” Proc. of the 2001 ACM Symposium on Applied Computing, Las Vegas, USA, pp. 484-488, 2001.
[40] Z. Shen, “An alternative routing algorithm for the pyramid structures,” Proc. of the 2003 ACM Symposium on Applied Computing, Melbourne, Australia, pp. 1009-1013, 2003.
[41] Y.-C. Wang and J. S.-T. Juan, “The m-pancycle-connectivity of basic WK-recursive pyramids,” Proc. of the 30nd Workshop on Combinatorial Mathematics and Computational Theory, Hualien, Taiwan, pp. 103_108, 2013.
[42] Y.-C. Wang and J. S.-T. Juan, “Hamiltonicity of the basic WK-recursive pyramid with and without faulty nodes,” Theoretical Computer Science, Vol. 562, No. 11, pp. 542-556, 2015.
[43] Y.-C.Wang, J. S.-T. Juan, and D.-R. Duh, “Shortest path routing algorithms for triangular meshes and triangular pyramids,” Proc. of International Conference on Engineering and Applied Science 2014 (ICEAS 2014), Sapporo, Japan, pp. 480-490, 2014.
[44] Y.-C. Wang, J. S.-T. Juan, and D.-R. Duh, “Broadcasting algorithms for triangular meshes and triangular pyramids,” Proc. of International Congress on Engineering and Information 2015, Kyoto, Japan, pp. 845-854, 2015.
[45] R.-Y. Wu, Hamiltonicity of pyramid networks. Master Thesis, Department of Computer Science and Information Engineering National Chi Nan University, Puli, Nantou Hsien, Taiwan, Republice of China, 2001.
[46] R.-Y. Wu and D.-R. Duh, “Hamiltonicity of the pyramid network with or without fault,” Journal of Information Science and Engineering, Vol. 25, No. 2, pp. 531_542, 2009.
[47] J. Xu, Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, 2002.
[48] J. Xu, Theory and Application of Graphs. Kluwer Academic Publishers, 2003.
[49] D. Zivkovic, “Hamiltonianicity of the tower of hanoi problem,” University of Beograd. Publikacije Elektrotehnickog fakulteta - serija: matematika, Vol. 17, pp. 31_37, 2006.