k-元n-立方体的路和圈

1、k- 元 n- 立方体的路和圈当前 VLSI 技术的进步 , 使得建造具有数千甚至数万个处理器的超大型并行分布式系统已经可以实现了. 而在这些并行分布式系统中, 最重要的一个步骤就是决定各个处理器之间连接的拓扑结构, 即互连网络 ( 简称网络 ). 这是因为网络的拓扑性质直接影响到并行分布式系统的硬件和软件两个层面的各种设计. k-元 n- 立方体是一类重要的互连网络 . 一方面 , 它包含圈网络 , 环形网络 , 超立方网络等常见互连网络作为其子类 . 另一方面 , 目前已有多个大型并行分布式系统如Cray T3D , J-machine和 iWarp 等都采用了 k- 元 n- 立方体网络

2、的连接方式 . 对于互连网络来说 , 有一类重要的问题 , 是在某一个网络上模拟另外一个网络, 这个问题被称为网络嵌入问题. 在这当中 , 线性数组和环是对于并行分布式计算而言,两种最基本的网络 . 它们具有结构简单 , 度较小等特点 , 适合发展简单而有效的算法 , 同时只需花费相当低的通讯代价. 线性数组和环在实际层面上的广泛运用给了我们在图上研究路嵌入和圈嵌入问题的动机. 本文主要研究 k- 元 n- 立方体网络上的各种路嵌入和圈嵌入问题. 本文共分五章 . 第一章首先给出本文将用到的图论方面的术语、记号 , 然后综述 k- 元 n- 立方体上的路和圈嵌入问题的应用背景以及相应的基本概念

3、 , 最后概述本文的研究内容、研究进展和获得的主要结果.在路嵌入问题中 , 在互联网络的顶点之间寻找并行路( 不交路 ) 是保障数据有效传递最主要的事件之一 . 第二章主要研究 2- 元 n- 立方体 ( 超立方体 ) 上的多对多不交路覆盖问题 . 令 G是一个图 . 对一个具有 k 个源点的集合 S=s1,s2, ,sk 和一个具有 k 个汇点的集合 T=t1,t2,tk,多对多 k- 不交路问题就是判定是否存在 k 条不相交的 (S,T)- 路使得每一条路连接一个源点Si 和一个汇点 t (i),其中 是基于集合 1,2, ,k 上的某个映射 . 若这 k 条路包含了 G的所有顶点 , 则

4、称这些不交路的集合是图G的一个 k- 不交路覆盖 . 本章通过对超立方体的结构性质讨论 , 提出超立方体对集合s 或 T限制这一新概念 , 推广了陈协彬等给出的一个结果 , 证明了超立方体 Qn包含多对多不成对的 n- 不交 (S,T)- 路覆盖当且仅当超立方体 Qn中不存在一个点 v 使得 NQn(v)=S且 v(?)T 或 NQn(v)=T且 v(?)S. 在一个系统中 , 处理器和它们彼此之间的链接都有可能发生故障 , 因此考虑一个互连网络的容错能力是非常重要的 . 也就是说 , 互连网络在发生某些处理器故障或者链接故障时 , 这个网络仍能保持原有的性质 . 一般来说 , 有两种考察互连

5、网络容错能力的模型：随机故障与条件故障 . 若假设故障会毫无限制的随机发生 , 就称之为随机故障 . 反之 , 若假设故障的发生会满足某些条件 , 则称之为条件故障 . 通常解决条件故障下的问题比解决随机故障下的问题要难得多 . 记一个简单图 G的顶点集和边集分别为 V(G)和 E(G). 若图 G包含一个长从围长 g(G) 到|V(G)| 的圈 , 则称图G是泛圈的 . 若它包含一个长从4 到|V(G)| 的偶圈 , 则被称为是二元泛圈的 . 进一步 , 二元泛圈图 G被称为是边二元泛圈的若 G的每条边都在长从 4 到|V(G)| 的偶圈上 . 泛圈性和二元泛圈性都是判断一个网络拓扑是否适合

6、将不同长度的圈映射到其上的重要测量值 . 如何将不同长度的圈嵌到互连网络中是近年来圈嵌入问题研究的一个热点 . 第三章和第四章分别研究了随机故障假设下 k- 元 n- 立方体的边二元泛圈性和条件故障假设下 k- 元 n- 立方体的泛圈性 . 在第三章中 , 我们证明了具有至多 2n-3 个故障元的 k- 元 n- 立方体在 k 3 为奇数时仍具有边二元泛圈性 , 在 k4 为偶数时是几乎边二元泛圈的. 这一结果回答了 Iain A. Stewart等人在文献 5 中提出的问题 . 第四章证明了在条件故障假设下3- 元 n- 立方体是(4n-5)-条件故障泛圈的 , 其中 n 3. 此外 , 在

7、第三章和第四章的最后分别说明我们的结果在某种意义下都是不可改进的.2006 年,Caha 和 Koubek研究了超立方体上经过指定边哈密顿圈的存在性, 这一问题在某些程度上是具有故障边的超立方体上哈密顿圈嵌入问题的补问题. 自从那以后 , 关于超立方体上经过指定边的哈密顿路和圈的研究得到了关注. 第五章扩展以上结果 , 对 k- 元 n- 立方体的经过指定边的哈密顿连通性进行研究. 设 P 是 3- 元 n- 立方体的一个边集合 , 满足由 P 导出的子图由两两点不交路组成( 则称 P是一个线性集 ) 且 |p| 2n-2. 设 u 和 v 是任意两个顶点满足由P 导出的路没有一条以它们作为中间顶点或同时以它们