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

Bubble-sort图的k-限制边连通度

作　者: 陈玉娟
导　师: 王世英
学　校: 山西大学
专　业: 应用数学
关键词: 互连网 k-限制边割 k-限制边连通度 Bubble-sort图
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 11次
引　用: 0次
阅　读: 论文下载

内容摘要

我们经常用图G=(V,E)代表互连网络,从互连网络的大规模多元信息处理机系统中可得到一些基础拓扑性质.在一个大规模多元信息处理系统中,元件故障是不可避免的.因此,互连网络的容错能力成为一个被广泛研究的关键因素.边连通度是测量互连网络容错性的一个重要参数.然而,在一个大规模多元信息处理系统中,与一些点相关联的所有边同时出现故障的可能性是很小的.因此,用k-限制边连通度去度量网络的可靠性就显得尤为重要.一个连通图G的k-限制边连通度是使得G-F不连通且G-F的每个分支至少有k个顶点的最小边子集F的基数.特别地,图G的2-限制边连通度也叫做限制边连通度,简记为λ’(G).在高性能并行与分布系统中,Bubble-sort图(简记为Bn)是一个具有一些诸如对称性和递归结构等好的拓扑性质的互连网络.Bn(n≥1)是含有n!个顶点的图,每个顶点χ可表示为x=x1x2…xn，1≤xi≤n且xi≠xj,1≤i,j≤n.两个顶点x=x1x2…xn和y=y1y2…yn相邻当且仅当存在整数1≤i≤n-1使得xi=yi+1,xi+1=yi且xj=yi,j∈{1,2,…,n}\{i,i+1}.在本文中,我们主要研究Bubble-sort图的k-限制边连通度,其中k∈{2,3,4}.本文分为四章：在第一章,我们介绍了一些本文将要用到的有关图论方面的基本概念和记号.在第二章,我们研究了Bubble-sort图的限制边连通度.主要结果如下：设Bn(n≥3)是Bubble-sort图,λ’(Bn)是Bn的限制边连通度.则λ’(Bn)=2n-4.在第三章,我们研究了Bubble-sort图的3-限制边连通度.主要结果如下：设Bn(n≥3)是Bubble-sort图,A3(Bn)是Bn的3-限制边连通度.则A3(Bn)=3n-7.在第四章,我们研究了Bubble-sort图的4-限制边连通度.主要结果如下:设Bn(n≥4)(Bn)是Bubble-sort图,λ4(Bn)是Bn的4限制边连通度.则λ4(Bn)= 4n-12.

Bubble-sort图的k-限制边连通度

内容摘要

全文目录

相似论文