Hypermesh网络的超边连通度朱强，李刚平，王新科，程广兰（西安电子科技大学 理学院，陕西 西安 710071）摘要：超边连通度是对传统边连通度的推广,而且是度量互连网络容错性的一个重要参数. Hypermesh网络由于具有良好的性能，而受到广泛的研究和关注. 本文通过对Hypermesh网络容错性质的考察，证明了当，时，它的超边连通度是.关键词：Hypermesh网络；超边连通度；点割；边割Super edge-connectivity of Hypermesh NetworkZHU Qiang，LI Gang-ping，WANG Xin-ke，CHENG Guang-lan(Department of Mathematics，Xidian University，Xian，710071，China)Abstract: As a generalization of classical edge-connectivity, the super edge-connectivity can provide more accurate measure of fault-tolerance for interconnection networks. The Hypermesh network, due to its good performance, has been widely studied. In this paper, we investigate the fault-tolerant properties of Hypermesh network, and prove that the super edge-connectivity of k-ary n-dimensional Hypermesh network is 2n(k-1)-2 for n2 and k3. Key words：Hypermesh network；super edge-connectivity；vertex-cut；edge-cut1 引言 随着科学技术、VLSI技术的飞速发展使得实现大规模的、高度复杂的互连网络成为可能，这些互连网络已被广泛应用于广播网、局域网、电信网以及其他分布式计算机系统的设计中，且成为现代并行处理系统的核心组成部分，在很大程度上决定着整个系统的性能.显然，互连网络可以用图来表示. 图的顶点表示系统中的元件，图的边表示元件之间的物理连线，其中有向边表示单向通信连线，无向边表示双向通信连线，而关联函数指定了元件之间的连接方式. 这样的图称为互连网络拓扑结构，或者简称网络拓扑. 反之，图也可以看成是某个互连网络的拓扑结构. 从拓扑上讲，图和互连网络是一回事. 将网络、元件和连线说成是图、顶点和边，反之亦然. 图是有向的还是无向的，根据通信连线是单向的还是双向的决定1. 因此，我们用一个连通的无向图作为互连网络的拓扑结构，它是决定网络性能的一个重要因素，而网络的可靠性和容错性是网络设计者所追求的目标之一. 通常人们用连通度和边连通度来衡量网络系统的可靠程度3. 然而随着对计算机网络拓扑结构的深入研究，人们发现用连通度和边连通度来度量网络的容错性有三个缺陷. 首先，两个图的连通度（或边连通度）即使相同，它们的可靠性也不一定一样，因为它们的最小点割数（或最小边割数）可能不同. 其次，这两个参数不能区别按不同方式移去个点（或条边）后产生的不同连通分支的情况. 这说明连通度和边连通度不能反映由于处理器或通讯信道损坏造成的系统损坏程度. 因而这两个参数在某些应用上不够精确. 第三，在分析和应用这两个参数时我们都不言而喻的假定了系统的任何部分都可能同时出现故障，也就是说对这些参数没有加任何限制. 然而，在带有某种类型故障诊断算法的计算机互连网络中，人们可以安全的假定网络组件的某些子集不会同时出现故障，或者对这些参数加上某些限制. 对于这样的网络，经典的连通度和边连通度就不能精确的度量其可靠性了. 事实上，我们在确定图的连通度和边连通度时，只考虑使得（或）不连通的点割（或边割）的最小数，忽略的相应的集合（或）同时发生故障的可能性. 换句话说，在连通度和边连通度的定义中，对（或）的分支和点割（或边割）没有加任何条件或限制. 所以为了弥补以上缺陷，人们自然会想到对（或）的分支和点割（或边割）加上一些条件或限制，从而推广了经典连通度和边连通度的概念. 在1983年，Harary16首先提出了条件连通度的概念. 1988年，Esfahanian和Hakimi5把条件具体化，提出了限制连通度的概念.一个网络的限制（边）连通度是限制其任何一个节点的所有邻点（边）不会同时出故障的情况下，网络中最少需要多少个节点（边）发生故障才能使其变得不再连通。因为在以立方体等互连网络为拓扑结构的多处理器系统中一个节点的所有邻点或者邻边发生故障的可能性非常小，因此限制（边）连通度能更精确的分析这些互连网络的可靠性. 近几年来，它们引起了理论计算机科学工作者和数学工作者很大的研究兴趣. 许多著名网络的限制连通性和限制边连通性已被研究，参见3，6-15.在1986年，Boesch等从另一方面，将条件连通度的条件具体化，然后提出了超连通度和超边连通度的概念，参见17，18。超连通度和超边连通度是限制当一个系统中去掉故障节点（边）后没有平凡连通分支的情况下最少需要发生故障使得系统变得不再连通的节点（边）数。相比于限制（边）连通度，超（边）连通度仅仅限制非故障节点的所有邻点（边）不会同时发生故障。由于图的超连通度和超边连通度可以比连通度更准确的反映了网络的可靠性，因而获得了广泛的关注和研究. 正是图的超连通度和超边连通度的研究，上世纪八十年代将图的连通性引向新的高潮，许多著名网络的超连通度和超边连通度已被研究，参见19-27.-元-维Hypermesh图是由T. Szymanski4提出的一种新的网络拓扑结构，它是正则图. 由于其具有良好的性能如点和边对称、较小的直径、高连通性、简单的路由算法等4，30-32，因而受到广泛的研究关注，许多关于Hypermesh网络的性能已被研究如文献30-33. 最近Liu et al.29求出了Hypermesh网络的在PMC模型下的精确可诊断数及一步精确诊断的算法，其复杂度为. Yang et al.28求出了在比较模型下Hypermesh网络的条件可诊断数.在这篇文章中，我们通过对Hypermesh网络拓扑性质的研究，求出它的超边连通度. 第二部分给出了本文用到的一些概念及符号，主要结论将在第三部分给出.2 概念及符号说明图是指一个顶点集为，边集为的无环无平行边的简单连通图. 表示的最小度，表示的最小边度，和分别表示的连通度和边连通度. 边，用或表示图中与相邻接的所有的边的集合，称为在中的邻边集. 顶点，用表示在中的邻点集. 顶点集，则在中的邻点集记作. 对于中两个不同的顶点和，用表示和在中的公共邻点集，和在中的共邻数记作. 设和是中两个不同的顶点，我们用表示和之间最短路的长度. 若，我们用或表示由顶点集在中的诱导子图，进而用表示. 若，则用表示从去掉这些边之后的一个支撑子图6. 其它未给出定义的符号及定义与参考文献2一致.定义134,35 设是连通的，是的一个子集. 不连通且不含孤立点，则称是的超点割. 如果图中含有超点割，则图的超连通度定义为的所有超点割的最小点数，记作. 如果中不存在超点割，则定义. 这时称图的超连通度不存在. 设是边集的一个子集. 若不连通且不含孤立点，则称是的一个超边割，则图的超边连通度定义为的所有超边割的最小边数，记为. 否则定义，这时称图超边连通度是不存在的. 从定义可知，超边割和限制边割是一样的，没什么本质区别. 因此，对任何连通图均有，只要它们存在. 然而，超点割和限制点割概念之间却是有区别的. 超点割与限制点割的区别在于超点割仅仅限制非故障节点的所有邻点不同时发生故障，而一个故障节点的所有邻点可以同时发生故障。例如，考虑如图1中所示的图. 它有唯一的超点割，因此，. 但它没有限制点割，因为唯一可能的限制点割也是，然而它包含作为它的子集. 因此，不存在. 因此，对于一个连通图，如果存在，那么必存在，而且. 这是因为，任何限制点割一定是超点割. 反之，如果不存在，那么也一定不存在.图1在一个实际的多处理器系统中，如果一个节点的所有邻点（边）同时发生故障，那么这个节点无论是否发生故障，已经变得不再可用了，因此可以假设这种情况下该节点也为故障节点。因此超（边）连通度比限制（边）连通度可以更好的衡量网络的可靠性。-元-维Hypermesh图是由T. Szymanski4提出的一种新的网络拓扑结构定义24 一个-元-维Hypermesh网络，记作，顶点集. 顶点，若，当且仅当，且，即和两个序列中只有第位两个数字不同，其余均相同，显然. 图2为一个4-元3-维的Hypermesh网络：图2 -元-维Hypermesh 根据网络的定义，我们可得到下面两个引理：引理1 一个-元-维的Hyermesh网络，其中，对于任一给定的，令，则（1）与-元-维的Hyermesh同构，记作，并且是的一个分割；（2）对于，和之间存在一个完备匹配，记作；（3）是的一个分割.即，且对任意，与之间存在一个完备匹配.引理2 设和为中任意两个不同的顶点，其中，.(1) 若，则；(2) 若，则；(3) 若，则. 定理14 一个-元-维Hypermesh网络，有.3 主要结论下面我们分两步证明本文的主要结论，第一步我们将证明当，时，第二步证明当时，如果没有孤立点，则是连通的，分别由引理3和引理4给出.引理3 对任一，有，其中，.证明：设，显然，是不连通的. 对于任一，根据的定义，及引理2，有. 因此，不含有孤立点，且是的超边割. 所以，.引理4 对任一，且，. 若没有孤立点，则是连通的.证明：根据引理1，一个能被分解为个维的. 设，令，. 显然有，记，则. 不失一般性，假设，根据定理1，因为，而，所以一定有. 因此只可能有和是不连通的. 下面我们分三种情形进行讨论：情形1：假设对所有的，是连通的. 根据引理1，对任意，与之间存在一个完备匹配，又因. 所以，连通子图与在中是连通的，即是连通的.情形2：假设只有一个是不连通的，不失一般性，我们设是不连通的. 令，由情形1可知是连通的.设任一，显然有，又因为是超边割集，所以在中既没有孤立点，也没有孤立边，即中每个分支至少有个顶点. 任取一点，假设在中所在的连通分支为. 若，则在中与连通子图是连通的. 因此，假设. 又因，我们设,为中的另外两个顶点，而，且与之间存在一个完备匹配. 设任一，不失一般性，假设，且为中与相匹配的点，如图3所示. 若和均不属于，则结论得证.图3然而，所以一定存在这样的. 因此，在中与是连通的，即是连通的.情形3：假设和均是不连通的，令，类似于情形1可知是连通的. 下面证明中任一顶点在中与是连通的. 设为中任意一点，且在中所在的连通分支为，则. 若，则结论得证. 因此，我们假设，则，令为在中的诱导子图，则是正则的. 一般的，设,为中的另外两个顶点，则. 再设，不失一般性，假设，且. 若和均不属于，则结论成立.又因，所以至少存在一个这样的，使得和均不属于.因此，结论得证. 同理，可证中任一顶点在中与也是连通的. 综上所述，当时，是连通的. 从而，结合引理3与引理4我们可得到下面的定理.定理2 一个-元-维Hypermesh网络的超边连通度，其中，. 4 结束语在这篇论文中，我们主要证明了，H