（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)。……