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