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

论文摘要

在互联网络中,一个结构能被另一个结构模拟是很重要的.网络模拟问题能归结为图的嵌入问题.因此,设计和衡量一个互联网络的中心问题之一就是研究图的嵌入能力.路或圈网络具有结构简单、度数小、通信成本低的优点,因而它们是并行处理和分布计算中的两个最受欢迎的互联网络.若一个网络含有不同长度的路或圈,则它就能够有效地模拟许多设计在线性阵列或环上的算法.因此研究互联网络的泛圈性或泛连通性具有实际的意义.当一个网络在运行时,故障是可能会发生的,因此研究有故障的网络也是重要又有现实意义的.超立方体、折叠超立方体和完全图是三类常见的互联网络拓扑结构.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的路.

论文目录

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