故障4元n方体中的路嵌入

来源 :山西大学 | 被引量 : 0次 | 上传用户:abcd432110000
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在高性能并行与分布系统中, k元n方体是应用最为广泛的一种互联网络之一.k元n方体Qkn(k≥2,n≥1)的顶点集V(Qkn)={u0u1…un-1:0≤ui≤k-1,0≤i≤n-1},两个不同的顶点u=u0u1…un-1和v=v0v1…vn-1相邻当且仅当存在一个整数j∈{0,1,…,n-1},满足uj=vj±1(mod k)且ui=vi,i∈{0,1,…,n-1}{j}.  在多处理器系统中,网络故障是不可避免的.当网络中出现故障时,该网络仍然具有原有的一些好的性质,这种情况被称为容错性.客图能否被嵌入主图的问题成为图嵌入问题.在并行处理系统中,由于路和圈的结构均可被用于模拟线性数组,所以在图嵌入问题中经常会选择路和圈来作为客图.在本文中,我们主要研究故障4元n方体中的路嵌入问题.本文分为三章:  在第一章,我们介绍了一些本文将要用到的有关图论方面的基本概念.  在第二章,我们研究了含有故障点的4元n方体中的路嵌入问题.设故障点数f≤n-1.主要结果如下:  (1)设u,v∈V(Q4n),若u和v相邻,则存在长为l的无故障(u,v)路,其中l是奇数且2n-1≤l≤4n-2f-1.  (2)设u,v∈V(Q4n),若存在一个整数j∈{0,1,…,n-1},满足uj=vj±2(mod4)且ui=vi,i∈{0,1,…,n-1}{j},则存在长为l的无故障(u,v)路,其中l是偶数且2n≤l≤4n-2f-2.  在第三章,我们研究了含有故障点或边的4元n方体中的路嵌入问题.设故障集F是故障点集Fv和故障边集Fe的并集,满足|F|≤2n-3.主要结果如下:  (1)设u,v∈V(Q4n),若u和v相邻,则存在长为l的无故障(u,v)路,其中l是奇数且1≤ l≤4n-2|Fv|-1.  (2)设u,v∈V(Q4n),若存在一个整数j∈{0,1,…,n-1},满足uj=vj±2(mod4)且ui=vi,i∈{0,1,…,n-1}{j},则存在长为l的无故障(u,v)路,其中l是偶数且2≤l≤4n-2|Fv|-2.  (3)设u,v∈V(Q4n),若存在两个不相同的整数i,j∈{0,1,…,n-1},满足ui=vi±1(mod4),uj=vj±1(mod4)且um=vm,m∈{0,1,…,n-1}{i,j},则存在长为l的无故障(u,v)路,其中l是偶数且4≤ l≤4n-2|Fv|-2.
其他文献
变分不等式理论是应用数学中一个十分重要的研究领域,它在非线性最优化理论、微分方程、控制论、对策论、社会经济平衡理论等领域有着广泛的应用。变分不等式系统作为变分不等
排序问题是指在一定约束限制条件下,对工件、机器按时间进行分配和安排他们的加工次序,要求使得一个或者多个目标函数值达到最优,而单机重新排序问题是既复杂又重要的排序问题之
两网格方法与外推方法是求解偏微分方程的有效数值方法。本文将两网格方法与外推方法相结合,构造了一类复合式外推两网格方法用于求解椭圆方程中的各类问题,可得到更高精度数