论文部分内容阅读
一个多处理器系统常被看成是互联网络图,它可能会含有成千上万个处理器.互联网络图的拓扑结构是一个简单无向连通图,处理器可以用图的点表示,处理器之间的通信情况可以用边来表示.随着互联网络图的点数增多,点的错误情况是不可避免的,因此互联网络图的容错性和错误诊断性越发重要.条件错误集是一种特殊的错误集,它不能包含任意一个点的全部邻居.条件诊断度就是我们能准确判断出的一个互联网络图中最大的条件错误集合的顶点个数.图G的连通度是一个数,记为κ（G）,即为了使图G不连通至少需要去掉κ（G）个点.由于图的连通度不超过其最小度,因此F`abrega等人提出了g-外连通度的概念并引起了广泛关注.出于系统自行检测错误的目的,人们提出了很多不同的诊断模型,其中PMC模型和MM模型有相当广泛的应用.本文主要研究了一些互联网络图的性质并得到了以下结果:（1）冒泡星图（bubble-sort star graphs）BSn的1,2,3-外连通度分别是4n-8（n≥4）,6n-15（n≥5）以及8n-23（n≥5）.冒泡星图在PMC模型和MM模型下的条件诊断度分别是8n-21（n≥5）和6n-15（n≥6）.（2）圆匹配构成图（round matching composition networks）G=（G1,G2,···,Gr;M′）在PMC和MM模型下的条件诊断度分别是4k+1和3k+1（k≥4）.通过这些结果,我们还得到了k-阶n-维立方体（k-ary n-cubes）和循环递归图（recursive circulant graphs）在PMC和MM模型下的条件诊断度.（3）（n,k）-冒泡图（（n,k）-bubble-sort graphs）Bn,k的1,2-外连通度分别是n+k-3和n+2k-5,其中n≥5,3≤k≤n-2.（n,k）-冒泡图在MM模型下的条件诊断度是n+2k-5,其中n≥5,3≤k≤n-2.（4）S Pn图的1,2,3-外连通度分别是2n-4（n≥3）,3n-7（n≥5）以及4n-10（n≥6）.S Pn图在MM模型下的条件诊断度是3n-7（n≥5）.通过这些结果,我们还得到了星图（star graphs）和煎饼图（pancake graphs）的1,2,3-外连通度和它们在MM模型下的条件诊断度.