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

de Bruijn图的限制边连通度

作　者: 李春芳
导　师: 李胜家
学　校: 山西大学
专　业: 运筹学与控制论
关键词: 网络限制边连通度超级限制边连通性有向de Bruijn图无向de Bruijn图
分类号: O157.5
类　型: 硕士论文
年　份: 2006年
下　载: 80次
引　用: 0次
阅　读: 论文下载

内容摘要

多处理机系统的互连网络拓扑通常以(无向或有向)图为数学模型,这时图的顶点代表处理机,而一对处理机之间的直接通信联系则用连接这对顶点的边来表示,因此网络拓扑的性能可以通过图的性质和参数来度量。对互连网络性能的一个关键要求是希望网络的可靠(容错)性好,这对应于图论的术语来说,就是希望图的连通度和边连通度大。不过用连通度和边连通度这两个参数考究系统的可靠性有缺陷,因而作为传统边连通概念的推广,Esfahanian和Hakimi提出了限制边连通的概念:设G是无向简单连通图,F是G的一个边割,如果G-F不含孤立点,则称F是G的一个限制边割。最小限制边割所含的边数称为G的限制边连通度(有向图的限制边连通度可类似给出)。限制边连通度是计算机互连网络可靠性的一个重要度量。超级限制边连通性是比限制边连通度更精确的一个网络可靠性指标。一个图是超级限制边连通的,如果它的任一最小限制边割都孤立一条有最小边度的边。本文主要研究了有向de Bruijn图的限制边连通度和无向de Bruijn图的超级限制边连通性。在第一章我们给出本文将用到的图论方面的主要的术语、记号。并介绍了de Bruijn图和限制边连通度方面的基本概念和基本结论。 de Bruijn图是重要的de Bruijn网络的拓扑结构,曾受到广泛的研究。不过对有向de Bruijn图的限制边连通度的研究还不多。在本文第二章我们计算了有向de Bruijn图的限制边连通度,给出:当d≥3,n≥2或d=2,n≥3时,有向de Bruijn图B(d,n)的限制边连通度为(2d-2)。根据这个结果我们可直接得到有向de Bruijn图是超级边连通的。在第三章我们将在已有结论的基础上继续对无向de Bruijn图的超级限制边连通性作更深入的研究,得到了一个有关无向de Bruijn图超级限制边连通性方面更好的结果:若无向de Bruijn图UB(d,n 的阶至少为4,则它是超级限制边连通的,除非d=2且n≥3。从而全面解决了无向de Bruijn图的超级限制边连通性。

全文目录

引言  7-8
第一章预备知识  8-12
  1.1 图论的一些基本术语和记号  8-9
  1.2 de Bruijn图的基本概念和基本结论  9-10
  1.3 有关连通性的基本概念和基本结论  10-12
第二章有向de Bruijn图的限制边连通度  12-18
  2.1 准备工作  12-15
  2.2 主要结论  15-18
第三章无向de Bruijn图的超级限制边连通性  18-26
  3.1 相关结论  18
  3.2 准备工作  18-22
  3.3 主要结论  22-26
结论  26-27
参考文献  27-29
致谢  29-30
附录  30-31
个人情况  31-32

de Bruijn图的限制边连通度

内容摘要

全文目录

相似论文