若干互连网络的圈嵌入和路嵌入

发布时间:2017-06-02 11:15

  本文关键词:若干互连网络的圈嵌入和路嵌入,由笔耕文化传播整理发布。


【摘要】:互连网络(interconnection networks)通常用一个简单图来表示,其中点表示处理器,边表示处理器之间的通信连线。反之,图也可以看成是某个互连网络的拓扑结构。从拓扑结构上来讲,图和互连网络是一样的。在本文我们将不区分“图”和“互连网络”。当评估一个互连网络的时候,一个主要的指标是图嵌入能力。所谓图嵌入,是指在一个图(称为主图)中找到另一个图(称为客图)作为它的子图。本文所研究的嵌入指的是在一个给定的互连网络中找到一个子图。路和圈是并行和分布式计算的两个最基础的结构。圈嵌入(或路嵌入)处理的是在一个给定的图中找到给定长度的圈(或路)。随着互连网络规模的增大,处理器和通信连线可能会出现错误,因此考虑有错误元素的网络是非常重要的。在有错误的互连网络中嵌入路和圈是并行处理的一个重要方面。容错圈嵌入(或路嵌入)指的是在有错误元素的互连网络中找到给定长度的无错误圈(或路)。 本论文的结构如下: 第一章,介绍互连网络的圈嵌入和路嵌入的研究背景。 第二章,介绍若干与本文有关的互连网络的概念。 第三章,研究有错误边的超立方体的容错圈嵌入问题。考虑至多有3n-8条错误边的n-维超立方体Qn(n≥5)满足以下两个条件:(1)每个点都至少与两条无错误边相关联;(2)不包含满足下列条件的4-圈:它的不相邻的顶点的度数在把所有的错误边去掉后都是2,证明了在Qn中存在长度从4到2n的无错误偶圈。这个结论在嵌入圈的长度方面改进了Liu和Wang的如下结论:Qn在有同样错误边数和满足条件(1)和(2)下,存在一条无错误的哈密尔顿圈。 第四章,研究折叠超立方体的圈嵌入问题。 首先研究折叠超立方体的点容错圈嵌入问题。假设FFv表示n-维折叠超立方体FQn中的错误点集,考虑有|FFv|≤n-2个错误点的FQn,证明了:当n≥3时, FQn中的每条无错误边都在长度从4到2n-2|FFv|的无错误偶圈上;当n≥2且n是偶数时, FQn中的每条无错误边都在长度从n+1到2n-2|FFv|-1的无错误奇圈上。这个结论在容错点的数目和嵌入圈的性质上改进了Hsieh等人的结论。他们考虑了有错误点数|FFv|=1的FQn,证明了:(1)当n≥3时,那么FQn中包含长度从4到2n-2的无错误偶圈;(2)当n≥2且为偶数时,那么FQn中包含长度从n+1到2n-1的无错误奇圈。 其次研究在条件错误下的折叠超立方体的边容错奇圈的嵌入。设FQn是有|FFe|≤2n-5条错误边的n-维折叠超立方体且每个点都至少与两条无错误边相关联,其中n≥4且是偶数,证明了FQn-FFe中的每条边都在长度从n+1到2n-1的无错误奇圈上。 再次研究在条件错误下的折叠超立方体的边容错偶圈的嵌入。设FQn是有|FFe|≤2n-4条错误边的n-维折叠超立方体且每个点都至少与两条无错误边相关联,其中n≥5。证明了FQn-Fe的每条无错误边都在长度从6到2”的无错误偶圈上。 上面两个结论在容错边的数目上改进了Xu等人的如下结论:他们考虑了有|FFe|≤n-1个错误边的FQn,证明了FQn-FFe中的每条边都在长度从4到2n的无错误偶圈上;当n是偶数时,FQn-FFe中的每条边都在长度从n+1到2n-1的无错误奇圈上。 第五章,研究增广立方体的条件边容错泛连通性。研究了在有至多4n-12条错误边的n-维增广立方体AQn(n≥3)且每个点都至少与两条无错误边相关联,证明了AQn包含所有长度从3到2n的无错误圈。这个结论在容错边的数目上改进了Ma等人的如下结论:他们考虑了错误边数不超过2n-3的AQn(n≥2),证明了AQn中包含所有长度从3到2n的无错误圈。 第六章,研究了平衡超立方体的路嵌入和圈嵌入性质。 首先证明了平衡超立方体中的两条点不相交的路嵌入问题。令X和Y表示n-维平衡超立方体BHn的二部划分的点集,其中n≥1。令u和x表示x中的两个点,v和y表示y的两个点。我们证明了在Bhn中存在两条点不相交的路P[x,y]和R[u,y]使得V(P[x,y])∪V(R[u,V])=V(BHn)。作为这个结论的推论可得到Xu等人证明的BHn(n≥1)具有哈密尔顿交织性的结论。 其次研究了平衡超立方体的点容错圈嵌入。令Fv表示n-维平衡超立方体BHn的错误点集,且|Fv|≤n-1,其中n≥1。证明了Bhn中的每条无错误边都在长度从4到22n-2|Fv|的无错误偶圈上。 再次研究了平衡超立方体的边容错圈嵌入。我们考虑有|Fe|≤2n-3条错误边的n-维平衡超立方体BHn,其中n≥2。证明了BHn的每条无错误边都在长度从6到22n的无错误偶圈上。 上面两个结论分别从容错点数和容错边数上改进了Xu等人的如下结论:他们证明了在无错误情况下,BHn(n≥1)中的每条边都在长度从4到22n的偶圈上。 第七章提出一些待解决的问题。
【关键词】:互连网络 容错 圈嵌入 路嵌入
【学位授予单位】:北京交通大学
【学位级别】:博士
【学位授予年份】:2015
【分类号】:O157.5
【目录】:
  • 致谢5-6
  • 中文摘要6-9
  • ABSTRACT9-14
  • 1 引言14-24
  • 1.1 研究背景14-21
  • 1.2 主要结果21-24
  • 2 基本概念24-32
  • 2.1 图的基本概念24-26
  • 2.2 超立方体和折叠超立方体26
  • 2.3 增广立方体26-28
  • 2.4 平衡超立方体28-32
  • 3 超立方体的边容错圈嵌入32-54
  • 3.1 引言32-35
  • 3.2 有错误边的超立方体的偶泛圈性35-54
  • 4 折叠超立方体的容错圈嵌入54-88
  • 4.1 引言54-55
  • 4.2 折叠超立方体的点容错圈嵌入55-64
  • 4.2.1 折叠超立方体的点容错偶圈嵌入55
  • 4.2.2 折叠超立方体的点容错奇圈嵌入55-64
  • 4.3 折叠超立方体的条件边容错奇圈嵌入64-80
  • 4.4 折叠超立方体的条件边容错偶圈嵌入80-88
  • 5 增广立方体的条件边容错泛圈性88-104
  • 5.1 引言88
  • 5.2 增广立方体的条件边容错泛圈性88-104
  • 6 平衡超立方体中的路嵌入和容错圈嵌入104-178
  • 6.1 引言104
  • 6.2 平衡超立方体中的两条点不相交的路嵌入104-134
  • 6.3 平衡超立方体的点容错圈嵌入134-155
  • 6.4 平衡超立方体的边容错圈嵌入155-178
  • 7 结论178-179
  • 参考文献179-185
  • 作者简历及攻读博士学位期间取得的研究成果185-188
  • 学位论文数据集18

【参考文献】

中国期刊全文数据库 前2条

1 马美杰;徐俊明;杜正中;;折叠超立方体网络的边容错哈密顿性(英文)[J];中国科学技术大学学报;2006年03期

2 杜正中;经};马美杰;徐俊明;;容错超立方体网络的圈嵌入(英文)[J];中国科学技术大学学报;2008年09期


  本文关键词:若干互连网络的圈嵌入和路嵌入,由笔耕文化传播整理发布。



本文编号:415109

资料下载
论文发表

本文链接:https://www.wllwen.com/shoufeilunwen/jckxbs/415109.html


Copyright(c)文论论文网All Rights Reserved | 网站地图 |

版权申明:资料由用户983bd***提供,本站仅收录摘要或目录,作者需要删除请E-mail邮箱bigeng88@qq.com