群作用图的卡氏积及其哈密尔顿圈

作     者：叶和平 肖文俊 朱小平 

作者机构：华南理工大学计算机科学与工程学院广州510640 广东科学技术职业学院计算机工程系广州510640 

基　　金：广东省自然科学基金(05006349) 

出 版 物：《科技通报》 (Bulletin of Science and Technology)

年 卷 期：2009年第25卷第5期

页      码：629-634页

摘      要：群作用图是一种探讨并行结构及算法设计的重要研究模型,有向连通的群作图被证明等价于一个有向Cayley图的右陪集图。本文证明群作用图的卡氏积图仍然是群作用图,由于Cayley图是群作用图的特殊情形,借助于该结论,证明了Cayley图的卡氏积仍是Cayley图。哈密尔顿圈(Hamiltonian Cycle)对于并行结构上路由方案及并行算法设计具有有重要意义,文中探讨了有向群作用的卡氏积上具有哈密尔顿圈的一个充分条件,对文献所提出的新的互连结构MDSXN(n,m,k)上Hamiltonian圈的存在性进行了理论证明。

主 题 词：群作用图 Cayley右陪集图 卡氏积 Cayley图 哈密尔顿圈 

学科分类：08[工学] 081201[081201] 0812[工学-测绘类] 

D　O　I：10.13774/j.cnki.kjtb.2009.05.001

馆 藏 号：203387449...