学位论文 > 优秀研究生学位论文题录展示

k-元n-立方体的路嵌入与容错性

作　者: 张淑蓉
导　师: 王世英
学　校: 山西大学
专　业: 基础数学
关键词: 图互连网络容错性不交路泛圈性 k-元n-立方体哈密顿路
分类号: O157.5
类　型: 博士论文
年　份: 2013年
下　载: 30次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机应用的不断深入,迫切需要速度更快,性能更高的计算机系统,进而开辟了并行和分布式系统的研究领域.系统中元件之间的连接模式称为该系统的互连网络,或者简称为网络.毫无疑问,并行和分布式系统功能的实现,在很大程度上依赖于该系统的互连网络结构.k-元n-立方体(Qkn)是最重要的互连网络之一.它具有许多优良性质,如易运行,低延迟和高带宽.正是这些优良的性质使得k-元n-立方体受到了广泛关注,并且大量的并行和分布式系统都是基于k-元n-立方体来形成其连接模式,如iWarp[1], Cray T3D[2]和Blue Gene/L torus [3]互连网络可以看成一个图.此时,图的顶点表示系统中的元器件,图的边表示元件之间的物理连线.这样的图称为互连网络拓扑结构,简称网络拓扑.路以其简单的结构成为最为基础也最为重要的网络拓扑之一.在网络设计中,路的可嵌入性是一项重要的基本原则.因此,互连网络中路的嵌入问题受到了广泛关注.随着网络中元件数目的不断增加,特别是对于超大规模计算机互连网络,网络故障是不可避免的,可能是元件本身也可能是它们内部连接出现故障.当网络中出现故障时,该网络仍然具有原有一些好的性质的程度被称为容错性.在通常情况下,人们希望即使有故障出现,网络的性质也能够得到最大程度的保留.因此,网络的容错性成为了一个重要的研究课题.本文将主要研究k-元n-立方体的路嵌入问题和容错性.本文共分五章.第一章介绍了研究背景和意义,将要用到的有关图的一些基本概念和术语,以及本文的研究内容,研究进展和获得的主要结果.在网络中寻找顶点之间的不相交路被大量应用在高性能互连网络中,所以这-问题得到了广泛研究并且成为了一类重要的路嵌入问题.在不相交路问题中,多对多不交路覆盖问题是其中最重要的一个.第二章主要对k为偶数时k-元n-立方体的多对多不交路覆盖问题进行了研究.已知k是偶数当且仅当k-元n-立方体是二部图.设(X,Y)是该k-元n-立方体的一个二分划.给定两个顶点集合S(?)X和T(?)y满足|S|=|T|=m,其中1≤m≤2n-1.本章证明了该k-元n-立方体中存在m条不相交的(S,T)-路使得每一条路连接一个S中的点和一个T中的点,而且这m条路包含了该k-元n-立方体的所有顶点.这一结论推广了Chen在文献[4]中的部分结果.一般来说,有两种考察互连网络容错能力的模型：随机故障与条件故障.若假设故障会毫无限制的随机发生,就称之为随机故障.若假设故障的发生会满足某些条件,则称之为条件故障.本文第三章到第五章对含有故障和条件故障的k-元n-立方体的容错性进行了研究.令G是一个简单二部图,(V0,V1)是G的一个二分划.若在G中,任意两点s∈V0和t∈V1之间存在一条哈密顿st-路,则称G为哈密顿交织图.随后Lewinter和Widulski[5]提出了若G为哈密顿交织图,且任取三个顶点v∈Vi和s,t∈V1-i吨其中i∈{0,1},G-υ中存在一条哈密顿st-路,则称G为超级哈密顿交织图.因为二部图不是哈密顿连通的,所以考察一个二部图是否为哈密顿交织图或超级哈密顿交织图成为了一个研究热点.在第三章,主要证明了当k≥4是偶数时,至多包含2n-3条故障边的k-元n-立方体为超级哈密顿交织图.在本文第四章,证明了当k≥4是偶数时,至多包含4n-5条条件故障边的k-元n-立方体为哈密顿交织图.此外,在第三章和第四章的最后分别举例说明了所得的结果在某种意义下都是最优的.泛圈性是判断一个网络是否适合将不同长度的圈映射到其上的重要指标.记一个简单图G的顶点集为V(G),若G包含长从4到|V(G)|的偶圈,则称G为偶泛圈的.而边偶泛圈性是比偶泛圈性更强的网络性质. G被称为是边偶泛圈的若G的每条边都在长从4到|V(G)|的偶圈上.在圈嵌入问题中,研究一个图的边偶泛圈性成为一个重要的课题.在第五章,证明了当k≥4是偶数,并且k-元n-立方体Qnk的条件故障边数不大于4n-5时,每条非故障边都在长从6到|V(Qnk)|的非故障偶圈上.

全文目录

中文摘要  8-10
Abstract  10-14
第一章绪论  14-23
  1.1 k-元n-立方体的路嵌入和容错性的应用背景  14-15
  1.2 基本概念和记号  15-20
  1.3 本文的研究内容,研究进展和主要结果  20-23
第二章 k元n立方体的多对多不交路覆盖  23-49
  2.1 相关概念和结果  23-24
  2.2 准备工作  24-32
  2.3 k-元n-立方体的多对多不交路覆盖  32-48
  2.4 本章小结  48-49
第三章容错k-元n立方体的超级哈密顿交织性  49-56
  3.1 相关概念和结果  49
  3.2 容错k-元n-立方体的超级哈密顿交织性  49-55
  3.3 本章小结  55-56
第四章条件容错k-元n-立方体的哈密顿交织性  56-104
  4.1 相关概念和结果  56-57
  4.2 准备工作  57-58
  4.3 条件容错k-元2-立方体的哈密顿交织性  58-81
  4.4 条件容错k-元n-立方体的哈密顿交织性  81-103
  4.5 本章小结  103-104
第五章条件容错k-元n-立方体的边偶泛圈性  104-155
  5.1 相关概念和结果  104-105
  5.2 准备工作  105-107
  5.3 条件容错k-元2-立方体的边偶泛圈性  107-129
  5.4 条件容错k-元n-立方体的边偶泛圈性  129-153
  5.5 本章小结  153-155
总结  155-157
参考文献  157-162
攻读博士学位期间的主要成果  162-164
致谢  164-165
个人简况及联系方式  165-167

k-元n-立方体的路嵌入与容错性

内容摘要

全文目录

相似论文