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

局部扭立方体LTQ_n容错性研究

作　者: 翟文华
导　师: 徐喜荣
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 拓扑结构图局部扭立方体边泛圈哈密顿连通容错性
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 13次
引　用: 0次
阅　读: 论文下载

内容摘要

设计一个网络时总会考虑很多因素,其中连通性是最基本的一个,但仅仅满足连通性是不够的,因此相关学者提出了更严格的要求,如泛圈性(网络中存在长为g≤l≤N的所有圈,其中g表示网络中最小的圈长,N表示网络中节点的个数)；泛连通性(网络中任何两个节点之间存在长为d≤l≤N-1的路径,其中d表示这两个节点之间的距离,N表示网络中节点的个数)等。并且一个大型网络在实际运行时不可避免的会出现各种错误,因此除了考虑正常情况下网络的泛圈性和泛连通性外,考虑网络的容错泛圈性和容错泛连通性对于一个大型网络也很重要。本文研究的是网络拓扑结构图---局部扭立方体的容错性。局部扭立方体LTQn网络作为超立方体Qn网络的一种变形,它不仅保留了超立方体网络的一些优良性质,如：正则性,对称性LTQn=L(?)R、泛圈性等,同时在顶点维数相同的情况下它的半径仅为超立方体网络的一半左右,因此有关局部扭立方体网络性质的研究引起了相关领域的科研工作者的重视。在本文中,我们利用计算机程序搜索的结果结合数学归纳法的证明思想来研究局部扭立方体网络的容错性,并取得了以下成果：(1)对于L中的任意一点UL,它在L中有n-2个强邻接点SL1,SL3,...,SLn-1(?)一个弱邻接点WL。并且对于弱邻接点WL和任意一个强邻接点WL’,在R中d(WR,uR)=2,但不存在一个长为2的路径连接SR’和UR,其中uR WR SRi分别是uL WL SLi在R中唯一邻接点。(2)当|F|≤n-3,n≥3时,对于LTQn中的任意一条正确边e,在LTQn-F中存在长为6≤l≤2”-|Fv|的正确圈包含边e。(3)3≤n≤4时,局部扭立方体是(n-3)容错哈密顿连通；n≥5时,局部扭立方体是(2n-8)边容错哈密顿连通,如果每个顶点至少连接三条正确的边。

全文目录

摘要  4-5
Abstract  5-8
引言  8-9
1 基本概念及预备知识  9-21
  1.1 互连网络拓扑结构图  9-14
    1.1.1 图的基本概念  9-13
    1.1.2 图的同构  13-14
    1.1.3 图的嵌入  14
  1.2 类哈密顿性  14-15
  1.3 容错性质介绍  15-16
  1.4 数学归纳法证明思想介绍  16
  1.5 几种重要的组合网络  16-19
    1.5.1 超立方体网络  17
    1.5.2 交叉立方体网络  17-18
    1.5.3 星图网络  18-19
  1.6 本论文主要工作  19-21
2 图的遍历算法及其应用  21-28
  2.1 图在计算机中的储存  21-22
  2.2 图的遍历算法  22-24
    2.2.1 深度优先遍历  22-23
    2.2.2 广度优先遍历  23-24
  2.3 图的遍历在圈嵌入算法中的应用  24-28
    2.3.1 回溯法  25
    2.3.2 圈嵌入算法  25-28
3 局部扭立方体邻接点分类研究  28-32
  3.1 局部扭立方体定义  28-29
  3.2 局部扭立方体邻接点关系研究  29-32
4 局部扭立方体容错边泛圈性证明  32-46
  4.1 局部扭立方体容错研究的相关结果  32-34
  4.2 局部扭立方体容错边泛圈性证明  34-43
  4.3 有关局部扭立方体容错边泛圈进一步讨论  43-46
5 局部扭立方体边容错哈密顿连通性研究  46-52
  5.1 哈密顿连通性证明相关的准备知识  46
  5.2 局部扭立方体边容错哈密顿连通性证明  46-52
结论  52-53
参考文献  53-56
攻读硕士学位期间发表学术论文情况  56-57
致谢  57-58

局部扭立方体LTQ_n容错性研究

内容摘要

全文目录

相似论文