k元n立方体的类Hamilton性研究

论文摘要

互连网络是随着信息技术与计算科学的发展而产生的一个跨数学与信息科学的研究领域。互连网络的研究在图论、算法设计与分析、计算机体系结构、并行与分布计算、计算机网络与通信以及大规模集成电路的设计等诸多方面都起着非常重要的作用。 k元n立方体是互连网络中一个非常流行的拓扑结构,环、网格、超立方体等都是它的特例,并已被用于J-Machine、Mosaic、iWarp等许多并发操作计算机的设计。这是由于许多线性代数运算和偏微分方程都能在基于k元n立方体的拓扑结构的机器上有效执行。本文系统介绍了k元n立方体的网络参数和拓扑性质,并在此基础上讨论和研究了k元n立方体的类Hamilton性（Hamilton-likeproperties）,主要研究成果有: （1） 利用k元2立方体Q2k的规则性和对称性,具体给出Q2k中任意两点间（几乎）Hamilton路的构造方法,从而证明: （ⅰ） Q2k是几乎Hamilton连通的; （ⅱ） Q2k是偶泛连通的; （ⅲ） Q2k是偶泛圈图; （ⅳ） 当k为奇数时,Q2k中除包含从4到|V（Q2k）|-1的所有偶长圈外,还包括从k到|V（Q2k）|的所有奇长圈。 （2） 利用（1）中结论证明Q2k的连通性: （ⅰ） 对任意n≥3,Qnk是几乎Hamilton连通的。 （ⅱ） 当k为奇数时,Qnk是Hamilton连通的。

论文目录

• 第1章 绪论
• 1.1 互连网络的发展与现状
• 1.2 互连网络的类 Hamilton性
• 1.3 本文主要研究内容
• 第2章 互连网络模型
• 2.1 互连网络概念
• 2.2 网络设计
• 2.3 几个常用的网络拓扑结构
• 2.3.1 线性阵列
• 2.3.2 环形网
• 2.3.3 全连接网
• 2.4.4 星形网
• 2.3.5 网格形网
• 2.3.6 立方体形网
• 第3章 k元n立方体的网络参数与拓扑性质
• 3.1 基本概念与记号
• 3.1.1 图论术语与记号
• 3.1.2 n位k进制串及其运算
• 3.2 Lee距离与k元n立方体
• 3.3 k元n立方体的网络参数与拓扑结构
• 3.3.1 正则性
• 3.3.2 直径
• 3.3.3 链路
• 3.3.4 结构递归性
• 3.3.5 可嵌入性
• 第4章 k元n立方体的类Hamilton性
• 4.1 预备知识
• 4.2 以的类Hamihon性
• k₂的（几乎）Hamilton连通性'>4.2.1 O^k₂的（几乎）Hamilton连通性
• k₂步的偶泛连通性和偶泛圈性'>4.2.2 O^k₂步的偶泛连通性和偶泛圈性
• k_n的（几乎）Hamilton连通性'>4.3 Q^k_n的（几乎）Hamilton连通性
• 4.4 实例
• 第5章 结语
• 攻读学位期间发表的论文
• 致谢
• 参考文献
• 研究生履历