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

摘要

互连网络(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-FFe的每条无错误边都在长度从6到2n的无错误偶圈上。
　　上面两个结论在容错边的数目上改进了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,v]使得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的偶圈上。
　　第七章提出一些待解决的问题。

目录

声明

致谢

摘要

1 引言

1．1 研究背景

1．2 主要结果

2 基本概念

2．1 图的基本概念

2．2 超立方体和折叠超立方体

2．3 增广立方体

2．4 平衡超立方体

3 超立方体的边容错圈嵌入

3．1 引言

3．2 有错误边的超立方体的偶泛圈性

4 折叠超立方体的容错圈嵌入

4．1 引言

4．2 折叠超立方体的点容错圈嵌入

4．2．1 折叠超立方体的点容错偶圈嵌入

4．2．2 折叠超立方体的点容错奇圈嵌入

4．3 折叠超立方体的条件边容错奇圈嵌入

4．4 折叠超立方体的条件边容错偶圈嵌入

5 增广立方体的条件边容错泛圈性

5．1 引言

5．2 增广立方体的条件边容错泛圈性

6 平衡超立方体中的路嵌入和容错圈嵌入

6．1 引言

6．2 平衡超立方体中的两条点不相交的路嵌入

6．3 平衡超立方体的点容错圈嵌入

6．4 平衡超立方体的边容错圈嵌入

7 结论

参考文献

作者简历及攻读博士学位期间取得的研究成果

学位论文数据集