| 低维修正冒泡排序网络一个猜想的证明 |
| |
| 引用本文： | 马继勇,师海忠,牛攀峰.低维修正冒泡排序网络一个猜想的证明[J].甘肃科学学报,2011,23(1):57-60. |
| |
| 作者姓名： | 马继勇 师海忠 牛攀峰 |
| |
| 作者单位： | 西北师范大学,数学与信息科学学院,甘肃,兰州,730070 |
| |
| 摘 要： | 修正冒泡排序网络是互连网络设计中的一个重要的Cayley图模型,关于修正冒泡排序网络的一个猜想如下:对于任意的自然数n≥3,如果n为奇数,则修正冒泡排序网络Yn是n-1/2个边不交的哈密尔顿圈以及一个完美对集的并;如果n为偶数,则修正冒泡排序网络Yn是n/2个边不交的哈密尔顿圈的并.证明了当n=3,4,5时,这个猜想是...
|
| 关 键 词： | Cayley图 修正冒泡排序网络 哈密尔顿圈 |
Proving of a Conjecture of Low Dimension Modified Bubble Sort Network |
| |
| MA Ji-yong,SHI Hai-zhong,NIU Pan-feng.Proving of a Conjecture of Low Dimension Modified Bubble Sort Network[J].Journal of Gansu Sciences,2011,23(1):57-60. |
| |
| Authors: | MA Ji-yong SHI Hai-zhong NIU Pan-feng |
| |
| Institution: | (College of Mathematics and Information Science,Northwest Normal University,Lanzhou 730070,China) |
| |
| Abstract: | Modified bubble sort networks are important networks designed from Cayley graph model.One conjecture is proposed as follows:For any integer n≥3,if n is odd,the modified bubble sort network Yn is a union of n-1/2 edge-disjoint Hamiltonian cycles and a perfect matching of Yn;if n is even,the modified bubble sort network Yn is a union of n/2 edge-disjoint Hamiltonian cycles.It is proved that the conjecture is true for n=3,4,5. |
| |
| Keywords: | Cayley graph modified bubble sort network Hamiltonian cycle |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
