计算机科学与应用  >> Vol. 6 No. 9 (September 2016)

推广立方连通圈网络的Hamilton分解的算法
The Algorithms for the Hamiltonian Decomposition of the General Cube-Connected Cycles Network

DOI: 10.12677/CSA.2016.69071, PDF, HTML, XML, 下载: 1,096  浏览: 3,809 

作者: 师海忠, 常立婷:西北师范大学数学与统计学院,甘肃 兰州

关键词: 互连网络推广立方连通圈Hamilton圈完美对集带弦环网络Interconnection Network General Cube-Connected Cycles Hamiltonian Cycle Perfect Matching Chordal Ring Network

摘要: 立方连通圈网络是超立方体的有界度变形,它具有超立方体几乎所有的优良性质,而且克服了超立方体顶点度随网络规模增大而增大的缺点,是代替超立方体的一个具有强大竞争力的网络结构。但立方连通圈网络的结构是简单还是复杂呢?这是一个悬而未决的问题。带弦环网络是一类经典的互连网络,该网络具有结构简单等优点。在这篇文章中利用师海忠提出的正则图连通圈网络模型设计出了包含立方连通圈网络的一类网络——推广立方连通圈网络GCCC(n) (n > 2),证明了GCCC(n) (n > 2)可分解为边不交的一个Hamilton圈和一个完美对集的并,即GCCC(n) (n > 2)是带弦环网络。并给出推广立方连通圈网络分解为边不交的一个Hamilton圈和一个完美对集的并的算法。
Abstract: The cube-connected cycles network is a hypercube of bounded-degree derivative. It has almost all of the excellent properties of hypercube. It also overcomes the shortcoming of hypercube vertices of degrees which will increase with the augment of the network size. But the cube-connected cycles network is simple or complex? This is an open question. Chordal ring network is a kind of classical interconnection network, which has the advantages of simple structure and so on. In this article, a model of the regular graph connected cycle network which is proposed by Haizhong Shi is used to design a kind of network which contains the cube-connected cycles network—the generalized cube-connected network GCCC(n) (n > 2). The authors prove that GCCC(n) (n > 2) can be decomposed into union of edge-disjoint a Hamiltonian cycle and a perfect matching, namely, GCCC(n) (n > 2) is a chordal ring network. They also make a algorithm for GCCC(n) (n > 2) can be decomposed into union of edge-disjoint a Hamiltonian cycle and a perfect matching.

文章引用: 师海忠, 常立婷. 推广立方连通圈网络的Hamilton分解的算法[J]. 计算机科学与应用, 2016, 6(9): 573-582. http://dx.doi.org/10.12677/CSA.2016.69071

参考文献

[1] Akers, S.B., Harel, D. and Krishnamurthy, B. (1987) The Star Graph: An Attractive Alternative to the n-Cube. Proceeding of the 1987 International conference on Parallel Processing, The Pennsylvania University Press, Philadelphia, 393-400.
[2] Akers. S.B. and Krishnamurthy, B. (1989) A Group-Theoretic Model for Symmetric Interconnection Networks. IEEE Transactions on Computers, 38, 555-565. http://dx.doi.org/10.1109/12.21148
[3] Ohring, S.R., Sarkar, F. and Hohndel, D.H. (1995) Cayley Graph Connected Cycles: A New Class of Fixed-Degree Interconnection Networks. Proceeding of the 28th annual Hawaii International Conference on System Science, 3-6 January 1995, 479-488. http://dx.doi.org/10.1109/hicss.1995.375509
[4] 师海忠. 互连网络的代数环模型[D]: [博士学位论文]. 北京: 中国科学院应用数学研究所, 1998.
[5] 徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2007.
[6] Efe, K. (1991) A Variation on the Hypercube with Lower Diameter. IEEE Transactions on Computer, 40, 1312-1316. http://dx.doi.org/10.1109/12.102840
[7] Ei-Amawy, A. and Latifi, S. (1991) Properties and Performance of Folded Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 2, 31-42. http://dx.doi.org/10.1109/71.80187
[8] Cull, P. and Larson, S.M. (1995) The Mǒbius Cube. IEEE Transactions on Computer, 44, 647-659. http://dx.doi.org/10.1109/12.381950
[9] Efe, K. (1998) The Crossed Cube Architecture for Parallel Computation. IEEE Transactions on Parallel and Distributed Systems, 3, 513-523. http://dx.doi.org/10.1109/71.159036
[10] Hsu, L.-H. and Lin, C.-K. (2009) Graph Theory and Interconnection Networks. CRC Press, New York.
[11] 师海忠. 正则图连通圈: 多种互连网络的统一模型[C]//中国运筹学会. 中国运筹学会第十届学术交流会论文集. Hong Kong: Global-link Informatics Limited, 2010: 202-208.
[12] 师海忠, 牛攀峰, 马继勇, 侯菲菲. 互连网络的向量图模型[J]. 运筹学学报, 2011, 15(3): 115-123.
[13] 师海忠, 路建波. 关于互连网络的几个猜想[J]. 计算机工程与应用, 2008, 44(31): 112-115.
[14] 师海忠. 互连网络的新模型: 多部群论模型[J]. 计算机科学, 2013, 40(9): 21-24.
[15] 师海忠. 几类新的笛卡尔乘积互连网络[J]. 计算机科学, 2013, 40(6A): 265-270.
[16] Shi, H. and Shi, Y. (2015) A New Model for Interconnection Network: K-Hierarchical Ring and R-Layer Graph Network. http://vdisk.weibo.com/s/dlizJyferZ-Zl
[17] Shi, H. and Shi, Y. (2010) A Hierarchical Ring Group-Theoretic Model for Intercon-nection Networks. http://vdisk.weibo.com/s/dlizJyfeBX-2J
[18] Shi, H. and Shi, Y. (2015) Cell-Breading Graph Model for Interconnection Networks. http://vdisk.weibo.com/s/dlizJyfesb05y
[19] Preparata, F.P. and Vuillemin, J. (1981) The Cube-Connected Cycles: A Versatile Network for Parallel Computation. Communications of the Association for Computing Machinery, 24, 300-309. http://dx.doi.org/10.1145/358645.358660
[20] Annexstein, F., Baumslag, M. and Rosenberg, A.L. (1990) Group Action Graphs and Parallel Architectures, SIAM Journal on Computing, 19, 544-569. http://dx.doi.org/10.1137/0219037
[21] Bruck, J., Cypher, R. and Ho, C.-T. (1995) On the Construction of Fault-Tolerant Cube-Connected Cycles Networks. Journal Parallel and Distributed Compu-ting, 25, 98-106. http://dx.doi.org/10.1006/jpdc.1995.1032
[22] Friš, I., Havel, I. and Liebl, P. (1997) The Diameter of the Cube-Connected Cycles. Information Processing Letters, 61, 157-160. http://dx.doi.org/10.1016/S0020-0190(97)00013-6
[23] Stong, R. (1987) On Hamiltonian Cycles in Cayley Graphs of Wreath Products. Discrete Mathematics, 65, 75-80. http://dx.doi.org/10.1016/0012-365X(87)90212-3
[24] Miller, F.P. (2010) Cube-Connected Cycles. VDM Verlag Dr. Müller, Saarbrücken.
[25] Li, H., Hsu, T.-H., Ho, Y.-H. and Tsay, C.-W. (2014) Cycles in Cube-Connected Graph. Discrete Applied Ma-thematics, 167, 163-171. http://dx.doi.org/10.1016/j.dam.2013.11.021
[26] Biggs, N. (1993) Algebraic Graph Theory. 2nd Edition, Cambridge University Press, Cambridge.
[27] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan Press Ltd., London.
[28] 师海忠, 常立婷, 赵媛, 张欣, 王海峰. 2r-正则图连通圈网络的Hamilton分解[J]. 计算机科学, 2016, 43(11A) (已录用).