蔡学鹏,徐刚刚,冯苗苗,严玉茹

(新疆农业大学数理学院,新疆 乌鲁木齐 830052)

1 引言

众所周知,互连网络在并行计算及通信系统中发挥着重要作用.一个网络的拓扑结构在数学上通常被抽象的模型化为一个图G=(V(G),E(G)),其中V(G)是图G的顶点集来表示网络处理器的集合,E(G)是图G的边集来表示网络的通信链路集.在本文中,术语图和网络可以互换使用.本文中所有的图都认为是无向的,简单的和连通的,对于未说明的图论符号和术语,可参考文献[1-2].

G=(V(G),E(G))是一个图.对图G中任意顶点u,设集合

分别表示顶点u的邻点集和邻边集,记为NG(u)和NEG(u).dG(u)=|NG(u)|称为图G中顶点u的度.对图G的子图K,设

分别表示子图K在G中邻点集和子图K在G中的邻边集.设u,v∈V(G),dG(u,v)表示G中连接u与v的一条最短路.对图G的点集X和Y,

图G中一条具有n个顶点n−1条边的路用Pn=〈u1,u2,···,un〉表示.设x是一个实数,[x]表示不超过x的最大整数.

图G的经典连通度κ(G)和边连通度λ(G)是衡量网络可靠性和容错性的两个重要参数[3].连通度κ(G)和边连通度λ(G)越大,网络的可靠性就越高.但是,这两个参数有明显的不足之处,比如,在一个图中删除相同阶数的点集(边集)后得到的图的分支情况可能会有很大的区别,并且在互连网络的实际应用当中,与一个处理器相连接的所有处理器(链路)同时发生故障是不可能的,所以这两个参数衡量网络可靠性和容错性是不精确的.为克服这些不足之处,自然要去推广图G的经典连通度(边连通度),通过对G-S的每一个分支强加一些限制条件,这里……