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

The Cartesian Product of Group Action Graphs and Its Hamiltonian Cycle

作　　者：叶和平[1,2] 肖文俊[1] 朱小平[2] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510640 [2]广东科学技术职业学院计算机工程系,广州510640

出　　处：《科技通报》2009年第5期629-634,共6页Bulletin of Science and Technology

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

摘　　要：群作用图是一种探讨并行结构及算法设计的重要研究模型,有向连通的群作图被证明等价于一个有向Cayley图的右陪集图。本文证明群作用图的卡氏积图仍然是群作用图,由于Cayley图是群作用图的特殊情形,借助于该结论,证明了Cayley图的卡氏积仍是Cayley图。哈密尔顿圈(Hamiltonian Cycle)对于并行结构上路由方案及并行算法设计具有有重要意义,文中探讨了有向群作用的卡氏积上具有哈密尔顿圈的一个充分条件,对文献所提出的新的互连结构MDSXN(n,m,k)上Hamiltonian圈的存在性进行了理论证明。Group Action Graph （GAG for short）has been developed for studying certain structural and algorithmic properties of the interconnection networks that underlie parallel architecture, and the connected counterpart is proven to be Cayley right coset graph. In this paper,we prove that the Cartesian product of two GAGs is still a GAG. Cayley graph is the special case of GAG,we also prove the Cartesian product of two Cayley graph is still a Cayley as a corollary of our main result. Hamiltonian cycle is very important to design routing and parallel algorithms for parallel structure. We discuss the sufficient condition for the existence of Hamiltonian cycle in the Cartesian product of GAGs if factor digraph has Hamiltonian cycle and explain that for the example MDSXN（n ,m, k）proposed in reference.

关 键 词：群作用图 Cayley右陪集图 卡氏积 CAYLEY图 哈密尔顿圈 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]