论文部分内容阅读
一个互连网络通常被抽象为一个图,记作G =(V,E,)V中的顶点对应互连网络中的处理器,E中的边对应互连网络中连接处理器之间的连线.在大规模计算机互连网络中,随着处理器的不断增加,互连网络结点发生故障是不可避免的,因此互连网络的容错成为一个焦点问题_对于多重处理器系统,(n,k)-泡型网络,(n,k)-星网络都是备受关注的互连网络.增广泡型网络Rn弥补了泡型网络边连通度和限制边连通度小,容错能力弱的弊端,是并行计算机系统的候选拓扑结构之一.设Gn,k是由两个变量确定的层次互连网络.其中,n≥2,1 ≤ k ≤ n—1.令F(?)V(Gn,k)∪E(Gn,k).若Gn,k-F不包含与Gn-m,k-m同构的子网,则称F是Gn,k的一个Gn-m,k-m排除集.更进一步地,若F∩E(Gn,k)=(?),则称F是Gn,k的一个Gn-m,k-m点排除集;若F ∩ V(Gn,k)=(?),则称F是Gn,k的一个Gn-m,k-m边排除集.Gn,k的元素个数最少的Gn-m,k-m点排除集的势叫Gn,k的一个Gn-m,k-m点排除数,记作Fm(Gn,k,);Gn,k的元素个数最少的Gn-m,k-m边排除集的势叫Gn,k的一个Cn-m,k-m边排除数,记作fm(Gn,k).在网络理论研究中关于匹配的问题同样是深受专家学者的关注.图G的匹配排除数mp(G)是指被删除之后使得“结果图”中既没有完美匹配也没有几乎完美匹配的最小边集的势.若G本身既没有完美匹配,也没有几乎完美匹配,则定义mp(G)= 0.在本文中,我们主要研究了(n,k)-泡型图,(n,k)—星图的子网排除问题和增广泡型图Rn的边连通度和限制边连通度及增广泡型图Rn的匹配排除问题,主要结果如下:(1)在(n,k)-星图中,FO(Sn,k)= f0(Sn,k)= 1,F1(Sn,k)= f1(Sn,k)= n,Fn-2(Sn,k)=n!/2,fn-2(Sn,k)=(n-1)n!/2 及对于一个素数n,f2(Sn,k)= n(n-1).(2)在(n,k)-泡型图中,对于1 ≤ m ≤ k-1,fm(Bn,k)=Fm(Bn,k)=(mn)m!.(3)在增广泡型图Rn中,λ(Rn)= n,λ’(Rn)=2n-2和mp(Rn)= n。