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

交叉立方体的容错泛圈性研究

作　者: 邓爱华
导　师: 徐喜荣
学　校: 大连理工大学
专　业: 计算机系统结构
关键词: 互连网络交叉立方体网络边容错点泛圈容错点泛圈
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 12次
引　用: 0次
阅　读: 论文下载

内容摘要

对简单图G=(V,E), F是图G中边或者点的子集。F为图中出现的错误数,确定一个网络结构中出现错误的最大值为多少时剩余子网络(即由V\F与E\F构成的子网络)任意一个顶点或边之间还能进行有效通信,就是对这个网络容错泛圈性的研究,即如果此时图中任意顶点或边还能找到围长至顶点个数的圈,那么这个图抽象出的网络结构就具有容错泛圈性,记fv为错误的顶点数,fe为错误的边数。研究图的容错泛圈性在很多领域具有广泛的应用,例如不影响通信的情况下去掉某些设备以节省资源；分布式系统中多任务消息传输的有效性问题等等都可以转化为图的容错泛圈性问题。一个大型网络在投入使用的过程中,它的某些组件和连线难免会发生故障。鉴于其理论和实际意义,本文通过计算机构造和数学推理证明相结合的方法,研究了交叉立方体CQn的边容错点泛圈性和容错点泛圈性质,给出了交叉立方体网络结构可以保证正确设备正常通讯时出现错误的上界。设fe是CQn中错误边的个数,fv,是CQn中错误点的个数,我们得到了以下结论：(1)当fe≤n-3时,对交叉立方体CQn任意顶点u都可以找到长度为6到2n的圈,且顶点u落在这些圈上。(2)当fe+fv≤n-3时,对交叉立方体CQn任意顶点u都可以找到长度为8到2n-fv的圈,且顶点u落在这些圈上。

全文目录

摘要  4-5
英文摘要  5-8
引言  8-9
1 基本概念和预备知识  9-17
  1.1 图论的基本概念  9-11
  1.2 图的嵌入  11-12
  1.3 联网络及其背景  12-16
    1.3.1 互联网络拓扑结构  12-14
    1.3.2 互联网络与图  14-15
    1.3.3 容错问题和研究现状  15-16
  1.4 本章小结  16-17
2 几种常用的网络  17-24
  2.1 超立方体网络  17-18
  2.2 折叠立方体网络  18-20
  2.3 M(?)bius立方体网络  20-21
  2.4 增广立方体网络  21-22
  2.5 局部扭立方体  22-23
  2.6 本章小结  23-24
3 交叉立方体的容错泛圈性  24-50
  3.1 数学归纳法及搜索算法  24-30
    3.1.1 数学归纳法  24
    3.1.2 搜索算法  24-28
    3.1.3 图的存储  28-30
  3.2 交叉立方体定义及其性质  30-32
  3.3 交叉立方体两点之间距离的一个重要公式  32-40
  3.4 定理证明  40-49
    3.4.1 交叉立方体边容错点泛圈性的证明  40-44
    3.4.2 交叉立方体容错点泛圈性的证明  44-49
  3.5 本章小结  49-50
结论  50-51
参考文献  51-53
攻读硕士学位期间发表学术论文情况  53-54
致谢  54-55

交叉立方体的容错泛圈性研究

内容摘要

全文目录

相似论文