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

论文摘要

在高性能并行与分布系统中,k元n方体是应用最为广泛的一种互联网络之一.k元n方体Qnk（k≥2,n≥1）的顶点集V（Qnk）={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（Qn4）,若u和v相邻,则存在长为l的无故障（u,v）路,其中l是奇数且2n-1≤l≤4n-2f-1.（2）设u,v∈V（Qn4）,若存在一个整数j∈{0,1,…,n-1},满足uj=vj±2（mod 4）且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（Qn4）,若u和v相邻,则存在长为l的无故障（u,v）路,其中l是奇数且1≤l≤4n-2|Fv|-1.（2）设u,v∈V（Qn4）,若存在一个整数j∈{0,1,…,n-1},满足uj=vj±2（mod 4）且ui=vi,i∈{0,1,…,n-1}＼{j},则存在长为l的无故障（u,v）路,其中l是偶数且2≤l≤4n-2|Fv|-2.（3）设u,v∈V（Qn4）,若存在两个不相同的整数i,j∈{0,1,…,n-1},满足ui=vi±1（mod 4）,uj=vj±1（mod 4）且um=vm,m∈{0,1,…,n-1}＼{i,j},则存在长为l的无故障（u,v）路,其中l是偶数且4≤l≤4n-2|Fv|-2.

论文目录

• 中文摘要
• Abstract
• 引言
• 第一章 预备知识
• 第二章 含有故障点的4元n方体中的路嵌入
• 第三章 含有故障点或故障边的4元n方体中的路嵌入
• 结论
• 参考文献
• 攻读学位期间取得的研究成果
• 致谢
• 个人简况及联系方式