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

三类网络的容错圈或路的嵌入

作　者: 方来金
导　师: 陈协彬
学　校: 漳州师范学院
专　业: 基础数学
关键词: 超立方体折叠超立方体完全图泛圈性泛连通性容错边容错互连网络
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 12次
引　用: 0次
阅　读: 论文下载

内容摘要

在互联网络中,一个结构能被另一个结构模拟是很重要的.网络模拟问题能归结为图的嵌入问题.因此,设计和衡量一个互联网络的中心问题之一就是研究图的嵌入能力.路或圈网络具有结构简单、度数小、通信成本低的优点,因而它们是并行处理和分布计算中的两个最受欢迎的互联网络.若一个网络含有不同长度的路或圈,则它就能够有效地模拟许多设计在线性阵列或环上的算法.因此研究互联网络的泛圈性或泛连通性具有实际的意义.当一个网络在运行时,故障是可能会发生的,因此研究有故障的网络也是重要又有现实意义的.超立方体、折叠超立方体和完全图是三类常见的互联网络拓扑结构.n维超立方体(记为Qn)是具有2n个顶点n-正则n-连通的二部图；作为n维超立方体Qn的一种变形—n维折叠超立方体(记为FQn)是具有2n个顶点(n+1)-正则(n+1)-连通图；n个顶点的完全图(记为Kn)是每一对不同的顶点都有一条边相连的简单图,它是具有n个顶点(n-1)-正则(n-1)-连通图.这三类互连网络被广泛地应用于并行处理和分布计算系统中.本文研究了以下三个问题：(1)故障超方体中有关路和圈的嵌入问题；(2)折叠超方体中的边容错泛连通性问题；(3)完全图的容错泛连通性问题.并得到了以下五个结果：1、设3≤h≤n,Fv(?)V(Qn)和Fe(?)E(Qn)且|Fv|+|Fe|≤n-h,则在Qn-Fv-Fe中,每个长为h的路P都包含在每个偶长从2h+2到2n-2|Fv|的圈中.并且当|Fv|+|Fe|<h-1时,路P还包含在长为2h的圈中.2、设n≥4,F(?)E(Qn),f=|F|≤n-1,δ(Qn-F)≥2,x和y是Qn-F中任意的两个顶点,h=H(x,y)≥2是x和y的Hamming距离.则在Qn-F中有每个长为l的(x,y)路,这里h+2≤l≤2n-1且l-h是偶数.3、设n≥4,Fe为FQn(n≥4)中的故障边集且|Fe|≤n-1.设x和y是FQn-Fe中的任意两个顶点,d(x,y)表示x与y在FQn中的距离.则对每个整数l适合d(x,y)+2≤l≤2n-1且l-d(x,y)是偶数,在FQn-Fe中存在长为l的(x,y)路.4、若n(n≥4)是偶数,Fe为FQn的故障边集且|Fe|≤n-1,设x和y是FQn-Fe中的任意两个顶点,d(x,y)表示x与y在FQn中的距离.(1)若d(x,y)≥3,则对于每个l适合n-1≤l≤2n-1,在FQn-Fe中有长为l的(x,y)路.(2)若1≤d(x,y)≤2,且当|Fe|=n-1时,Fe的n-1条边不关联于同一个顶点,则对于每个l适合n≤l≤2n-1,在FQn-Fe中有长为l的(x,y)路.5、用Kn表示n个顶点的完全图,F表示Kn中任意至多n-3个故障元素(点和／或边)组成的集合,使得G=Kn-F中的每个顶点至少关联三条边且G不同构于K6去掉三条两两相邻的边所得的图.则G具有泛连通性,即：G中的任意两个顶点x和y都有长从2到|V(G)|-1的路.

全文目录

摘要  5-7
Abstract  7-10
第1章引言  10-18
  1.1 图与互连网络  10
  1.2 图的嵌入与容错性  10-11
  1.3 相关概念  11-12
  1.4 超立方体  12-15
  1.5 折叠超方体  15-16
  1.6 完全图  16
  1.7 本文的主要工作  16-18
第2章引理  18-20
第3章故障超立方体中有关圈和路的两个结果  20-26
第4章折叠超立方体的边容错泛连通性  26-29
第5章完全图的容错泛连通性  29-34
参考文献  34-39
致谢  39-40
攻读硕士学位期间完成的学术论文  40

三类网络的容错圈或路的嵌入

内容摘要

全文目录

相似论文