k元n立方体的类Hamilton性研究
|
摘要
互连网络是随着信息技术与计算科学的发展而产生的一个跨数学与信息科学的研究领域。互连网络的研究在图论、算法设计与分析、计算机体系结构、并行与分布计算、计算机网络与通信以及大规模集成电路的设计等诸多方面都起着非常重要的作用。
k元n立方体是互连网络中一个非常流行的拓扑结构,环、网格、超立方体等都是它的特例,并已被用于J-Machine、Mosaic、iWarp等许多并发操作计算机的设计。这是由于许多线性代数运算和偏微分方程都能在基于k元n立方体的拓扑结构的机器上有效执行。本文系统介绍了k元n立方体的网络参数和拓扑性质,并在此基础上讨论和研究了k元n立方体的类Hamilton性(Hamilton-likeproperties),主要研究成果有:
(1) 利用k元2立方体Q_2~k的规则性和对称性,具体给出Q_2~k中任意两点间(几乎)Hamilton路的构造方法,从而证明:
(ⅰ) Q_2~k是几乎Hamilton连通的;
(ⅱ) Q_2~k是偶泛连通的;
(ⅲ) Q_2~k是偶泛圈图;
(ⅳ) 当k为奇数时,Q_2~k中除包含从4到|V(Q_2~k)|-1的所有偶长圈外,还包括从k到|V(Q_2~k)|的所有奇长圈。
(2) 利用(1)中结论证明Q_2~k的连通性:
(ⅰ) 对任意n≥3,Q_n~k是几乎Hamilton连通的。
(ⅱ) 当k为奇数时,Q_n~k是Hamilton连通的。
Research of interconnection is an important aspect of mathematics and computer science. It is widely used in graph theory, algorithm design and analyse, computer architecture, parallel and discrete computation, computer network and communication, and design of large scale integration circuit. k-ary n-cube is a very popular topology of networks. Ring, mesh and hypercube are all its special cases. It has been used in the design of several concurrent computers, including the J-Machine, the Mosaic, the iWarp, and so on. Network parameters and topological properties of k-ary n-cubes are firstly systematically introduced and then its some Hamilton-like properties are investigated .The conclusions are as follows:(1) By regularity and symmetry of k-ary 2-cube, a method of constructing (almost) Hamilton path between any two different vertices is presented, thereby the following conclusions are proved:(i) Q~k_2 is (almost) Hamilton- connectivity; (ii) Q~k_2 is bipanconnected; (iii) Q~k_2 is bipancyclic;(iv) If k is odd, there are all odd cycles from k to |V(Q~k_2)| besides all even cycles from 4 to |V(Q~k_2)|-1 in Q~k_2 .(2) Using conclusion in (1), connectivity of Q~k_n is proved: (i) For any n ≥ 3 , Q~k_n is (almost) Hamilton- connectivity; (ii) If k is odd, Q~k_n is Hamilton-connectivity.
k元n立方体是互连网络中一个非常流行的拓扑结构,环、网格、超立方体等都是它的特例,并已被用于J-Machine、Mosaic、iWarp等许多并发操作计算机的设计。这是由于许多线性代数运算和偏微分方程都能在基于k元n立方体的拓扑结构的机器上有效执行。本文系统介绍了k元n立方体的网络参数和拓扑性质,并在此基础上讨论和研究了k元n立方体的类Hamilton性(Hamilton-likeproperties),主要研究成果有:
(1) 利用k元2立方体Q_2~k的规则性和对称性,具体给出Q_2~k中任意两点间(几乎)Hamilton路的构造方法,从而证明:
(ⅰ) Q_2~k是几乎Hamilton连通的;
(ⅱ) Q_2~k是偶泛连通的;
(ⅲ) Q_2~k是偶泛圈图;
(ⅳ) 当k为奇数时,Q_2~k中除包含从4到|V(Q_2~k)|-1的所有偶长圈外,还包括从k到|V(Q_2~k)|的所有奇长圈。
(2) 利用(1)中结论证明Q_2~k的连通性:
(ⅰ) 对任意n≥3,Q_n~k是几乎Hamilton连通的。
(ⅱ) 当k为奇数时,Q_n~k是Hamilton连通的。
Research of interconnection is an important aspect of mathematics and computer science. It is widely used in graph theory, algorithm design and analyse, computer architecture, parallel and discrete computation, computer network and communication, and design of large scale integration circuit. k-ary n-cube is a very popular topology of networks. Ring, mesh and hypercube are all its special cases. It has been used in the design of several concurrent computers, including the J-Machine, the Mosaic, the iWarp, and so on. Network parameters and topological properties of k-ary n-cubes are firstly systematically introduced and then its some Hamilton-like properties are investigated .The conclusions are as follows:(1) By regularity and symmetry of k-ary 2-cube, a method of constructing (almost) Hamilton path between any two different vertices is presented, thereby the following conclusions are proved:(i) Q~k_2 is (almost) Hamilton- connectivity; (ii) Q~k_2 is bipanconnected; (iii) Q~k_2 is bipancyclic;(iv) If k is odd, there are all odd cycles from k to |V(Q~k_2)| besides all even cycles from 4 to |V(Q~k_2)|-1 in Q~k_2 .(2) Using conclusion in (1), connectivity of Q~k_n is proved: (i) For any n ≥ 3 , Q~k_n is (almost) Hamilton- connectivity; (ii) If k is odd, Q~k_n is Hamilton-connectivity.
引文
[1] Ahmed E. A., Latifi S., Bridged hypercube networks, Journal of Parallel and Distributed Computing, 1990, 10, 90-95
[2] Al-Sadi J., Day K., Ould-Khaoua M., Unsafety vectors: a new fault-tolerant routing for k-ary n-cubes, Microprocessors and Microsystems, 2001, 25, 239-246
[3] Ashir Y. , Atewart S. I., On embedding cycles in k-ary n-cubes, Par. Processing Letters, 1997,7,49-55
[4] Ashir Y., Stewart I. A., Ahmed A., Communication algorithms in k-ary n-cube interconnection network, Inform. Process Lett, 1997, 61, 43-48
[5] Athas W. C, Seitz C. L., Multicomputers: message-passing concurrent computers, Computer, 1988,21,9-24
[6] Auletta V., Rescigno A. A., Sarano V., Embedding graphs onto the supercubes, IEEE Trans. On Computers, 1995, 44(4), 593-597
[7] Bettayeb S., On the k-ary hypercube, Theoret. Comput Sci., 1995,140, 333-339
[8] Bhuyan L. N. , Agrawal D. P., Generalized hypercube and hyperbus structures for a computer network, IEEE Trans. On Computers, 1984, c-33 (4), 323-333
[9] Bose B., Broeg B., Kwon Y., Ashir Y, Lee distance and topological properties of k-ary n-cubes, IEEE Trans.On Computers, 1995, 44(8), 1021-1030
[10] Bruck Y, Cypher R., C-T Ho, Efficient fault-tolerant mesh and hypercube architectures, Proc.22nd Int. Symp. On Fault-Tolerant Computing, IEEE Press, 1992, 162-169
[11] Chan M. Y, Lee S. J., Distributed fault-tolerant embeddings of rings in hypercubes, J Parallel Distr. Comput. 1991,11, 63-71
[12] Chan T. E, Saad Y, Multigrid algorithms on the hypercubes multiprocessor, IEEE Trans. Comput., 1986, 35(11), 969-977
[13] Chang J. M., Yang J. S., Wang Y. L., Yuwen Cheng, Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graghs, Networks, 2004,302-310
[14] Chedid F. B. , Chedid R. B., A new variation on hypercubes with smaller diameter. Information Processing Lett., 1993, 46, 275-280
[15] Cull P., Larson S. M., The Mobius cubes, IEEE Trans. On Computers, 1995, 44(5), 647-659
[16] Dally W., Performance analysis of k-ary n-cube interconnection networks, IEEE Trans. On Comput, 1990, 39 , 775-785
[17] Dally W. J., Chien A., Fiske S., Horwat W., Keen J., Larivee M., Lethin R., Nuth P., Wills S., Carrick P., Fyler G.., The J-machine:a fine-grain concurrent computer Information Processing 89,1989,Elsevier Science Publishers B.V. ,1147-1153
[18] Dally W. J., Stuart Fiske J. A., Keen J. S, Lethin R. A., Noakes M. D., Nuth P. R., Davison R. W. , Fyler G. A., The message-driven processor:A multicomputer processing node with efficient mechanisms, IEEE Micro, 1992, 12(2), 23-39
[19] Day K., The conditional node connectivity of the k-ary n-cubes, Journal of Interconnection Networks, 2004, 5, 13-26
[20] Day K., Abdel Elah Al-Ayyoub, Fault diameter of k-ary n-cube networks, IEEE Trans. On Parallel and Distributed system, 1997, 8(9), 903-907
[21] Day K., Tripathi A., Embedding of cycles in arrangement graphs, IEEE Trans. On Computers, 1993, 12, 1002-1006
[22] Duncan R., A survey of parallel computer architectures, Computer, 1990, 23, 5-16
[23] Duncan T. H., Performance of the Intel iPSC/860 and Ncube 6400 hypercubes, Parallel Comput., 1991, 17, 1285-1302
[24] Efe K., The crossed cube architecture for parallel computation, IEEE Trans on Parallel Distributed Systems, 1992, 3(5), 513-524
[25] Erdos P., Spencer J., Evolution of the n-cube, J. Comput. Math. Appl., 1997, 5, 3-39
[26] Esfahanian A. H., Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans. On Computers, 1989, 38,1586-1591
[27] Esfahanian A. H., Lionel M. Ni., Sagan B. E., The twisted n-cube with application to multiprocessing, IEEE On Computers, 1991, 40(1), 88-93
[28] Foldes S., A characterization of hypercubes, J Discrete Math., 1997, 17, 155-159
[29] Germa A., Heyedmann M. C., Sotteau D., Cycles in the cube-connected cycles graph, Discrete Appl. Math., 1998, 83,135-155
[30] Ghozati S. A., Wasserman, The k-ary n-cube network: modeling, topological properties and routing strategies, Computers and Electrical Engineering, 1999, 25, 155-168
[31] Greenberg D. S., Heath L. S., Rosenberg A. L., Optimal embeddings of butterfly-like graphs in the hypercube, Math System Theory, 1990, 23, 61-77
[32] Harary F., Hayes J. P., Node fault tolerance in graphs, Networks, 1996, 27, 19-23
[33] Hwang S. C, Chen G. H., Cycles in butterfly graph, Networks, 2000, 35(2), 161-171
[34] Jianxi Fan, Hamilton-connectivity and cycle-embedding of the Mobius cubes, Inform. Process Lett, 2002, 82, 113-117
[35] Jwo J., Lakshmivarahan S., Dhall S. K., A new class of interconnection networks based on the alternating group, Networks, 1993,23, 315-326
[36] Latifi S., Combinatorial analysis of the fault-diameter of the n-cube, IEEE Trans. On Computers, 1993, 42, 27-33
[37] Linder D., Harden J., An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes, IEEE Trans. On Computers, 1991, 40, 2-12
[38] Myurg M. Bae, IEEE Computer Society, B. Bose, Edge disjoint hamiltonian cycles in k-ary n-cubes and hypercubes, IEEE Trans.Computers, 2003, 52, 1271-1284
[39] Myung M. Bae, Venkatesan R., Bose B., Data rearrangement between radix-k and Lee distance Gray codes in k-ary n-cubes, Journal of Parallel and Distributed Computing, 2002, 62, 19-37
[40] Ni L., McKinley P., A survey of wormhole routing techniques in direct networks, Computer, 1993, 26,62-76
[41] Rosenberg A. L., Product-shuffle networks:toward reconciling shuffles and butterflies, Discrete Appl Math, 1992, 465-488
[42] Saad Y., Schultz M., Data communications in hypercubes, J. Parallel Distributed
Comput., 1989, 6, 115-135
[43] Saad Y., Schultz M., Topological Properties of Hypercubes, IEEE Trans. On Comput., 1988, 37(7), 867-871
[44] Sarbazi-Azad H., Oould-Khaoua M., Mackenzie L. M., Akl S. G., On some properties of k-ary n-cubes, Proceedings of the Eighth International Conference on Parallel and Distributed Systems, 2001, 517-523
[45] Somani A. K., Thatte S., The helical cube network, Networks, 1995, 26, 87-100
[46] Song Z. M. , Qin Y. S., A new sufficient condition for panconnected graphs, Ars Combin, 1992, 34, 161-166
[47] Tseng-Kuei Li, Chang-Hsiung Tsai, Jimmy J. M. Tan, Lih-Hsing Hsu, Biapanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes, Inform. Process Lett., 2003, 87, 107-110
[48] Tseng Y. C., Embedding a ring in a hypercube with both faulty links and faulty nodes, Inform. Process Lett, 1996, 59, 217-222
[49] Weizhen Mao, David M. Nicol, On k-ary n-cubes: theory and applications, Discrete Applied Mathematics, 2003, 129, 171-193
[50] Yang C. S., Tsai Y. M., Chi S. L., Shepherd S. B. Shi, Adaptive wormhole routing in k-ary n-Cubes, Parallel Computing, 1995, 21, 1925-1943
[51] Zhang C. Q., Panconnectivity of locally connected k(1,3)-free graphs, Math and statistics:Theoretical Mathematics, 1989
[52] 李文兵,裴伟东,马燕,大规模并行处理机的互连网络初探,天津师大学报(自然科学版),2000,20(3),51-54
[53] 孙云,朱海燕,王德强,常见立方形递归网络及其互连函数,大连海事大学学报,2003,29(1)
[54] 孙云,立方形递归网络若干性质的研究,大连海事大学,硕士,2003
[55] 王鼎兴,陈国良,《互连网络结构分析》,第一版,1990,科学出版社,1-82
[56] 王德强,《立方形递归网络》,第一版,2002,大连海事大学出版社,17-177
[57] 王朝瑞,《图论》,第一版,1978,高等教育出版社,4-58
[2] Al-Sadi J., Day K., Ould-Khaoua M., Unsafety vectors: a new fault-tolerant routing for k-ary n-cubes, Microprocessors and Microsystems, 2001, 25, 239-246
[3] Ashir Y. , Atewart S. I., On embedding cycles in k-ary n-cubes, Par. Processing Letters, 1997,7,49-55
[4] Ashir Y., Stewart I. A., Ahmed A., Communication algorithms in k-ary n-cube interconnection network, Inform. Process Lett, 1997, 61, 43-48
[5] Athas W. C, Seitz C. L., Multicomputers: message-passing concurrent computers, Computer, 1988,21,9-24
[6] Auletta V., Rescigno A. A., Sarano V., Embedding graphs onto the supercubes, IEEE Trans. On Computers, 1995, 44(4), 593-597
[7] Bettayeb S., On the k-ary hypercube, Theoret. Comput Sci., 1995,140, 333-339
[8] Bhuyan L. N. , Agrawal D. P., Generalized hypercube and hyperbus structures for a computer network, IEEE Trans. On Computers, 1984, c-33 (4), 323-333
[9] Bose B., Broeg B., Kwon Y., Ashir Y, Lee distance and topological properties of k-ary n-cubes, IEEE Trans.On Computers, 1995, 44(8), 1021-1030
[10] Bruck Y, Cypher R., C-T Ho, Efficient fault-tolerant mesh and hypercube architectures, Proc.22nd Int. Symp. On Fault-Tolerant Computing, IEEE Press, 1992, 162-169
[11] Chan M. Y, Lee S. J., Distributed fault-tolerant embeddings of rings in hypercubes, J Parallel Distr. Comput. 1991,11, 63-71
[12] Chan T. E, Saad Y, Multigrid algorithms on the hypercubes multiprocessor, IEEE Trans. Comput., 1986, 35(11), 969-977
[13] Chang J. M., Yang J. S., Wang Y. L., Yuwen Cheng, Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graghs, Networks, 2004,302-310
[14] Chedid F. B. , Chedid R. B., A new variation on hypercubes with smaller diameter. Information Processing Lett., 1993, 46, 275-280
[15] Cull P., Larson S. M., The Mobius cubes, IEEE Trans. On Computers, 1995, 44(5), 647-659
[16] Dally W., Performance analysis of k-ary n-cube interconnection networks, IEEE Trans. On Comput, 1990, 39 , 775-785
[17] Dally W. J., Chien A., Fiske S., Horwat W., Keen J., Larivee M., Lethin R., Nuth P., Wills S., Carrick P., Fyler G.., The J-machine:a fine-grain concurrent computer Information Processing 89,1989,Elsevier Science Publishers B.V. ,1147-1153
[18] Dally W. J., Stuart Fiske J. A., Keen J. S, Lethin R. A., Noakes M. D., Nuth P. R., Davison R. W. , Fyler G. A., The message-driven processor:A multicomputer processing node with efficient mechanisms, IEEE Micro, 1992, 12(2), 23-39
[19] Day K., The conditional node connectivity of the k-ary n-cubes, Journal of Interconnection Networks, 2004, 5, 13-26
[20] Day K., Abdel Elah Al-Ayyoub, Fault diameter of k-ary n-cube networks, IEEE Trans. On Parallel and Distributed system, 1997, 8(9), 903-907
[21] Day K., Tripathi A., Embedding of cycles in arrangement graphs, IEEE Trans. On Computers, 1993, 12, 1002-1006
[22] Duncan R., A survey of parallel computer architectures, Computer, 1990, 23, 5-16
[23] Duncan T. H., Performance of the Intel iPSC/860 and Ncube 6400 hypercubes, Parallel Comput., 1991, 17, 1285-1302
[24] Efe K., The crossed cube architecture for parallel computation, IEEE Trans on Parallel Distributed Systems, 1992, 3(5), 513-524
[25] Erdos P., Spencer J., Evolution of the n-cube, J. Comput. Math. Appl., 1997, 5, 3-39
[26] Esfahanian A. H., Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans. On Computers, 1989, 38,1586-1591
[27] Esfahanian A. H., Lionel M. Ni., Sagan B. E., The twisted n-cube with application to multiprocessing, IEEE On Computers, 1991, 40(1), 88-93
[28] Foldes S., A characterization of hypercubes, J Discrete Math., 1997, 17, 155-159
[29] Germa A., Heyedmann M. C., Sotteau D., Cycles in the cube-connected cycles graph, Discrete Appl. Math., 1998, 83,135-155
[30] Ghozati S. A., Wasserman, The k-ary n-cube network: modeling, topological properties and routing strategies, Computers and Electrical Engineering, 1999, 25, 155-168
[31] Greenberg D. S., Heath L. S., Rosenberg A. L., Optimal embeddings of butterfly-like graphs in the hypercube, Math System Theory, 1990, 23, 61-77
[32] Harary F., Hayes J. P., Node fault tolerance in graphs, Networks, 1996, 27, 19-23
[33] Hwang S. C, Chen G. H., Cycles in butterfly graph, Networks, 2000, 35(2), 161-171
[34] Jianxi Fan, Hamilton-connectivity and cycle-embedding of the Mobius cubes, Inform. Process Lett, 2002, 82, 113-117
[35] Jwo J., Lakshmivarahan S., Dhall S. K., A new class of interconnection networks based on the alternating group, Networks, 1993,23, 315-326
[36] Latifi S., Combinatorial analysis of the fault-diameter of the n-cube, IEEE Trans. On Computers, 1993, 42, 27-33
[37] Linder D., Harden J., An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes, IEEE Trans. On Computers, 1991, 40, 2-12
[38] Myurg M. Bae, IEEE Computer Society, B. Bose, Edge disjoint hamiltonian cycles in k-ary n-cubes and hypercubes, IEEE Trans.Computers, 2003, 52, 1271-1284
[39] Myung M. Bae, Venkatesan R., Bose B., Data rearrangement between radix-k and Lee distance Gray codes in k-ary n-cubes, Journal of Parallel and Distributed Computing, 2002, 62, 19-37
[40] Ni L., McKinley P., A survey of wormhole routing techniques in direct networks, Computer, 1993, 26,62-76
[41] Rosenberg A. L., Product-shuffle networks:toward reconciling shuffles and butterflies, Discrete Appl Math, 1992, 465-488
[42] Saad Y., Schultz M., Data communications in hypercubes, J. Parallel Distributed
Comput., 1989, 6, 115-135
[43] Saad Y., Schultz M., Topological Properties of Hypercubes, IEEE Trans. On Comput., 1988, 37(7), 867-871
[44] Sarbazi-Azad H., Oould-Khaoua M., Mackenzie L. M., Akl S. G., On some properties of k-ary n-cubes, Proceedings of the Eighth International Conference on Parallel and Distributed Systems, 2001, 517-523
[45] Somani A. K., Thatte S., The helical cube network, Networks, 1995, 26, 87-100
[46] Song Z. M. , Qin Y. S., A new sufficient condition for panconnected graphs, Ars Combin, 1992, 34, 161-166
[47] Tseng-Kuei Li, Chang-Hsiung Tsai, Jimmy J. M. Tan, Lih-Hsing Hsu, Biapanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes, Inform. Process Lett., 2003, 87, 107-110
[48] Tseng Y. C., Embedding a ring in a hypercube with both faulty links and faulty nodes, Inform. Process Lett, 1996, 59, 217-222
[49] Weizhen Mao, David M. Nicol, On k-ary n-cubes: theory and applications, Discrete Applied Mathematics, 2003, 129, 171-193
[50] Yang C. S., Tsai Y. M., Chi S. L., Shepherd S. B. Shi, Adaptive wormhole routing in k-ary n-Cubes, Parallel Computing, 1995, 21, 1925-1943
[51] Zhang C. Q., Panconnectivity of locally connected k(1,3)-free graphs, Math and statistics:Theoretical Mathematics, 1989
[52] 李文兵,裴伟东,马燕,大规模并行处理机的互连网络初探,天津师大学报(自然科学版),2000,20(3),51-54
[53] 孙云,朱海燕,王德强,常见立方形递归网络及其互连函数,大连海事大学学报,2003,29(1)
[54] 孙云,立方形递归网络若干性质的研究,大连海事大学,硕士,2003
[55] 王鼎兴,陈国良,《互连网络结构分析》,第一版,1990,科学出版社,1-82
[56] 王德强,《立方形递归网络》,第一版,2002,大连海事大学出版社,17-177
[57] 王朝瑞,《图论》,第一版,1978,高等教育出版社,4-58