关于修正冒泡排序网络的一簇猜想  

One Variety Conjectures of Modified Bubble Sort Network

作　　者：师海忠[1] 马继勇[1] 牛攀峰[1] 侯菲菲[1] 

机构地区：[1]西北师范大学数学与信息科学学院,兰州730070

出　　处：《计算机科学》2011年第B10期265-267,275,共4页Computer Science

基　　金：甘肃省自然科学基金(ZS991-A25-017-G)资助

摘　　要：修正冒泡排序网络是互连网络设计中的一个重要的Cayley图模型,关于修正冒泡排序网络的一簇猜想如下:对于任意的自然数n≥3,修正冒泡排序网络Yn是i个边不交的哈密尔顿圈以及n-2i个完美对集的并,其中1≤i≤︱n/2︱。证明了当i=1,2时,这个猜想是正确的。Modified bubble sort networks are important cayley graphs model in networks design.One variety conjectures of modified bubble sort networks were proposed as follows：for any integer n≥3,modified bubble sort networks Yn are a union of i edge-disjoint hamiltonian cycles and n-2i perfect matchings of Yn,and 1≤i≤︱n/2︱.We proved the conjectures are true for i=1,2.

关 键 词：CAYLEY图 修正冒泡排序网络 哈密尔顿圈 

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