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

某些容错网络的嵌入研究

作　者: 经衿
导　师: 徐俊明
学　校: 中国科学技术大学
专　业: 应用数学
关键词: 中国科学技术大学超立方体网络导出子图博士学位论文边连通度故障点最长路网络拓扑结构泛圈性网络结构
分类号: O157.5
类　型: 博士论文
年　份: 2009年
下　载: 77次
引　用: 0次
阅　读: 论文下载

内容摘要

互连网络拓扑结构可以用无向图G来表示,顶点集和边集V(G)和E(G)分别表示处理器和处理器之间的通信线路.互连网络结构的设计和评价中,一个重要的课题是结构嵌入问题,归结为图论问题就是图的嵌入.线性阵列和环是并行和分布式计算中最基本结构,大量应用在如图像和信号处理的实际问题中.因此研究在网络结构中有效的嵌入路和圈具有很大重要性,前人在这方面做出了大量的工作.由于网络在使用中会发生故障,对出现故障的网络的研究就很有必要,衡量一个网络的容错能力就成为了互连网络结构研究的另一个重要课题.在所有的互连网络拓扑结构中,超立方体Q_n是最受关注的.近来Bubble-sort网络,是一种Cayley图,由于有着良好的拓扑结构特性,如高对称性和递归性,继超立方体后成为我们关注的对象.本文主要研究Bubble-sort网络和超立方体的(容错)路和圈嵌入问题,共分6章.其中第3章至第5章是主要部分.第1章绪论主要说明研究的背景,理论意义和使用价值.第2章介绍图和网络的基本概念,嵌入和容错的定义,Bubble-sort网络和超立方体的定义和基本性质,以及一些已有的结果.第3章研究Bubble-sort网络的2个基本性质.首先,我们得到Bubble-sort网络超连通度和超边连通度.1.κ’(B_n)=2n-4,当n≥3时.λ’(B_n)=2n-4,当n≥5时.然后我们得到Bubble-sort网络的二部分泛连通性.2.在B_n中,当n≥5时,任意2点x,y间存在长度为l的路,其中d(x,y)+2≤l≤n!-1,2|(l-d(x,y)).第4章研究点容错的Bubble-sort网络最长路的嵌入问题,得到以下结果.1.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,任何异色点x和y,在幸存图B_n-F_v中存在x和y之间长度为n!-2f_v-1的路.并由此得到了点容错Bubble-sort网络中最长圈的嵌入:2.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,在幸存图B_n-F_v中至少存在长为n!-2|F_v|的圈.3.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,任何2顶点x和y同色,则在幸存图B_n-F_v中有从x到y的长为n!-2|F_v|-2的路.在第5章中,我们主要讨论了边容错Bubble-sort网络和超立方体中的嵌入问题.1.B_n中的故障边集F_e满足|F_e|≤n-3,B_n-F_e的每条边都包含在一个长度从6到n!的偶圈上,当n≥5时.2.B_n中故障边集F_e满足|F_e|≤2n-7,且任意顶点都至少有2条边幸存时,当n≥4时,幸存图B_n-F_e中存在Hamilton圈.3.B_n中故障边集F_e满足|F_e|≤2n-7,且任意顶点都至少有2条边幸存时,当n≥4时,幸存图中有长为l的偶圈,其中6≤l≤n!.4.超立方体Q_n中的故障边集F_e满足|F_e|≤n-1,且当|F_e|=n-1时所有故障边不和一个顶点相连.当n≥4时,任意顶点uv,在幸存图中存在一条长为l的uv路,其中d(u,v)+4≤l≤2~n-1且2|(l-d(u,v)).第6章对本文的主要工作进行了总结,对有待进一步研究的问题提出了一些看法和猜想.附录中我们给出了证明中用到的数据.

全文目录

中文摘要  6-8
英文摘要  8-10
第一章绪论  10-15
  1.1 图论的历史  10-12
  1.2 计算机科学和互连网络拓扑结构  12-15
第二章预备知识  15-29
  2.1 图论术语的介绍  15-18
  2.2 圈和路的嵌入  18-21
  2.3 容错和超连通度  21-23
  2.4 Bubble-sort网络  23-25
  2.5 超立方体网络  25-27
  2.6 已有结果  27-29
第三章 Bubble-sort网络的基础性质  29-38
  3.1 Bubble-sort网络的超连通度  29-34
  3.2 Bubble-sort网络的二部泛连通性  34-38
第四章点容错Bubble-sort网络路嵌入  38-51
  4.1 点容错Bubble-sort网络的异色点间最长路嵌入  38-48
  4.2 点容错Bubble-sort网络的同色点间最长路嵌入  48-51
第五章边容错Bubble-sort网络和超立方体的嵌入  51-79
  5.1 边容错的Bubble-sort网络的边偶泛圈性  51-65
  5.2 条件边容错的Bubble-sort网络的Hamilton性  65-73
  5.3 条件边容错的Bubble-sort网络的二部泛圈性  73-75
  5.4 边容错的超立方体路嵌入  75-79
第六章结束语  79-83
  6.1 本文的主要结果  79-81
  6.2 有待研究的问题和猜想  81-83
参考文献  83-88
附录一 B_4中全部长度的路  88-89
附录二 B_5中2个导出子图中的路  89-109
附录三 B_4中一个故障点  109-115
附录四 B_4中边容错边泛圈  115-118
作者攻读博士学位期间完成论文目录  118-119
致谢  119

某些容错网络的嵌入研究

内容摘要

全文目录

相似论文