论文部分内容阅读
互连网络是数学和计算机科学的一个研究热点,它在图论、算法设计与分析、计算机体系结构、并行与分布计算、计算机网络与通信以及大规模集成电路的设计等诸多方面起着非常重要的作用.超立方体及其变体是一类具有良好的拓扑性质和网络参数的互连网络模型,关于它们的研究与应用在互连网络的研究中备受青睐.
本文主要研究超立方体的一种变体——扭n立方体中边不交Hamilton圈问题.边不交Hamilton圈问题指的是在图G中寻找尽可能多的Hamilton圈,且各Hamilton圈的边互不相交.
首先,在充分考虑4元n立方体中边不交Hamilton圈的算法的基础上,本文结合Lee距离Gray码理论,利用其结构的递推性,证明了它的一个重要性质,即:当n为偶数时,由Bae和Bose提出的Gray码生成函数h0生成的Hamilton圈H0一定含有路<0n-200,0n-201,0n-202,0n-203>;当n为奇数时,由h0生成的Hamilton圈H0经“边变换”后得到的Hamilton圈H0也一定含有此路.然后,利用这个性质,构造了2m维超立方体与4元m立方体的同构映射f,并将两者联系起来研究,得出了n维超立方体中的Hamilton圈H0一定含有路<0n-200,0n-201,0n-211,0n-210>的结论.最后,依据扭n立方体与n维超立方体的关系,通过作相应的顶点对应变换,给出了扭n立方体中存在[n/2]个边不交Hamilton圈的结论,同时对这[n/2]个边不交Hamilton圈的生成算法进行了具体的描述,从而在一定意义上较好地解决了扭n立方体中边不交Hamilton圈问题.