（n，k）--冒泡排序网络的结构连通度和子结构连通度

张国珍，杨伟丽

（山西大学 数学科学学院，山西 太原 030006）

0 引言和术语

在许多并行计算机系统中，处理器通过互连网络连接。例如：超立方体［1-2］，星图［3］，平衡超立方体［4］，冒泡排序图［5-9］，排列图［10-11］，k元 n立方体［12-13］。互连网络通常用简单无向图 G=(V，E)表示，V中每个顶点代表一个处理器，每条边对应一条通信路线。连通度是衡量互连网络可靠性和容错性最重要的参量。作为经典连通度的推广，Fàbrega和Fiol［14］引入g-超连通度，用κg(G)表示，是使得图G不连通所需删除的最少顶点的个数，并且删除顶点后G中每个分支的点数大于g。许多研究者主要研究单个节点故障对网络的可靠性和容错性的影响，然而，顶点之间是互相关联的，一个故障点的邻点可能更容易受到攻击并且有更高的概率发生故障。于是Lin等[1]提出了结构连通度和子结构连通度的概念。令H是G的一个连通子图，图G的H-结构连通度定义为κ(G；H)是指子图集合F={H1，H2，…，Ht}的最小基数，其中每一个Hi与H同构，且G-F是不连通的。图G的H子结构连通度定义为κs(G；H)，是指子图集合F={J1，J2，…，Jt}的最小基数，其中每一个Ji与H的子图同构，且G-F是不连通的。已有学者研究了超立方体［1］，折叠立方体［2］，纽立方体［15-16］，冒泡排序网络［17］和交换群网络［18］的结构连通度和子结构连通度。(n，k)-冒泡排序网络是n维冒泡排序网络的推广，它保留了n维冒泡排序网络的层次性和正则性，比n维冒泡排序网络更加灵活与实用。

（1）存在整数m∈[1，k-1]使得am=bm+1，am+1=bm且对于任意i∈[1，k]{m，m+1}有ai=bi；

（2）对于任意的 i∈[2，k]有 ai=bi并且 a1≠b1。

设 u 是 Bn，k中一个点，不妨设 u=1 2 3 4 5…(k-1)k。对应类型（1），u 在 Bn，k中有 k-1 个邻点，分 别 记 为 u1， u2， … ， uk-1， 其 中 u1=2 1 3 4 5…(k-1)k， u2=1 3 2 4 5…(k-1)k，uk-1=1 2 3 4 5…k(k-1)。 对 应 类 型（2），u 在 Bn，k中 有 n-k个 邻 点 ，分 别 记 为 uk+1=(k+1)2 3 4 5…(k-1)k，uk+2=(k+2)2 3 4 5…(k-1)k，un=n 2 3 4 5…(k-1)k。设p，q是正整数，满足1≤p＜q-1≤k-1，令 up，q=1 2 3…(p+1)p…(q+1)q…(k-1)k。设 s，t是正整数，满足 2≤s≤k-1 且 k+1≤t≤n，令 uts=t 2 3…(s+1)s…(k-1)k，utp，q=t 2 3…(p+1)p…(q+1)q…(k-1)k。图 1 画出了 (n，k)-冒泡排序网络 B4，1，B4，2和 B4，3。

图1 (n，k)-冒泡排序图B4，1（a），B4，2（b）和B4，3（c）Fig.1 (n，k)-bubble-sort graph B4，1（a），B4，2（b）and B4，3（c）

在图G中，如果存在两个非空集合X，Y，使得V(G)=X∪Y，X∩Y=∅且G中的任意一条边的两个端点不能同时属于X或Y，则称图G为二部图或者偶图。若X的每个顶点和Y的每个顶点相连，称G为完全偶图。若|X|=m，|Y|=n，对应的完全偶图记为Km，n。当m=1时，我们把K1，n称为n爪。若 V(Pk)={u1，u2，u3，…，uk}(ui≠uj，1≤i＜j≤k)且 E(Pk)={u1u2，u2u3，…，uk-1uk}，称 Pk为 一 条 k路。图2给出了P4和K1，3。假设V1是V的一个非空子集，以V1为顶点集，以两端点均在V1中的边的全体为边集所构成的子图，称为G的由V1导出的子图，记为G[V1]。若图G和图H同构，记为G≅H。设v是图G的一个顶点，G中所有与v相邻的点的集合记为N(v)。

图2 （a）路P4；（b）爪 K1，3Fig.2 （a）Path P4；（b）Claw K1，3

4 结论

在这篇文章中，我们研究了(n，k)-冒泡排序网络的H-结构连通度和H-子结构连通度，其中H∈{P3，P4，K1，3}。在此基础上，我们还可以探究(n，k)-冒泡排序网络中一般的路和爪的结构连通度和子结构连通度。通过类似方法也可以研究其他网络的结构容错性。