扭n立方体边不交Hamilton圈的研究

论文摘要

互连网络是数学和计算机科学的一个研究热点,它在图论、算法设计与分析、计算机体系结构、并行与分布计算、计算机网络与通信以及大规模集成电路的设计等诸多方面起着非常重要的作用。超立方体及其变体是一类具有良好的拓扑性质和网络参数的互连网络模型,关于它们的研究与应用在互连网络的研究中备受青睐。 本文主要研究超立方体的一种变体——扭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圈H′0经“边变换”后得到的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圈问题。

论文目录

• 第1章 绪论
• 1.1 并行计算
• 1.1.1 并行计算模型
• 1.1.2 并行处理机及其特点
• 1.1.3 并行计算机的发展现状
• 1.2 互连网络的特性及其上算法
• 1.2.1 互连网络研究内容
• 1.2.2 互连网络特性
• 1.2.3 互连网络上的算法
• 1.3 本文的主要研究成果
• 第2章 基础知识与互连网络模型
• 2.1 图论概念与记号
• 2.2 Lee距离Gray码与Hamilton圈
• 2.3 常见的互连网络
• 2.3.1 一维线性阵列
• 2.3.2 网格形网
• 2.3.3 树形网
• 2.3.4 立方体形网
• 第3章 超立方体与扭n立方体的性质
• 3.1 k元n立方体、超立方体及扭n立方体网络
• 3.1.1 k元n立方体
• 3.1.2 超立方体
• 3.1.3 扭立方体
• 3.2 超立方体与扭n立方体的性质
• 3.2.1 正则性、连通度与直径
• 3.2.2 顶点容错度和边容错度
• 3.2.3 结构递归性
• 第4章 扭n立方体的边不交Hamilton圈
• 4.1 扭4立方体中边不Hamilton圈
• 4.2 2维环绕中的2个独立Gray码
• 4.3 扭6立方体中边不交Hamilton圈
• 4.3.1 4元3立方体中边不交Hamilton圈
• 4.3.2 扭6立方体中边不交Hamilton圈
• 4.4 扭n立方体中边不交Hamilton圈
• 4.4.1 4元n立方体中边不交Hamilton圈
• 4.4.2 扭n立方体中边不交Hamilton圈
• 第5章 结束语
• 攻读学位期间公开发表的论文
• 致谢
• 参考文献
• 研究生履历