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

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

群作用图的卡氏积(英文)

群作用图是一种探讨并行结构及算法设计的重要研究模型,有向连通的群作图被证明等价于一个有向Cayley图的右陪集图。证明群作用图的卡氏积图仍然是群作用图,由于Cayley图是群作用图的特殊情形,借助于该结论,证明了Cayley图的卡氏积仍是Cayley图。

排列图的代数性质

构造了一种新的Cayley陪集图,并且证明了这种Cayley陪集图能够被表示成〈n〉上的k-置换集V(An,k)上的置换图An,k,进一步说明了得到广泛深入研究的(n,k)-排列图An,k是基于对称群的Cayley陪集图,从而是点传递的.