论文部分内容阅读
容错性分析是当今研究互连网络的重要议题。限制连通度和限制容错直径是近几年人们提出的衡量互连网络容错性的两个主要参数。当考察这两个参数时，总是假设网络中和一个处理器相连接的所有处理器不会同时出现故障，从图论的角度上说，就是假设任何一个结点的邻点集不可能同时出现故障。对这两个参数的研究，弥补了单一的连通度和容错直径在反映互连网络的强可恢复性上的缺陷，为我们提供互连网络的容错性能的更准确的估计。本文研究了组合星图的限制连通度和限制容错直径。
首先，给出了限制连通度、限制容错直径、组合星图的定义。限制连通度是由图的极小限制分离集的元素个数决定的，所以我们先给出了分离集、限制集、限制分离集的定义。对组合星图定义描述的同时，也给出了组合星图的相关性质和定理。
其次，从n(n≥4)维2阶组合星图Sn，2入手，利用组合星图Sn，2可以被分解成n个完全图Kn-1的性质，给出并证明了组合星图Sn，2的极小分离集、极小限制分离集，同时证明了其取法的唯一性，得出组合星图Sn，2的限制连通度为n-1。然后，给出并证明了n≥5，k≥3，n-k≥2时，n维k阶组合星图Sn，k的极小分离集和极小限制分离集，同样也证明了其取法的唯一性，得出n维k阶组合星图Sn，k的限制连通度为n+k-3。
第三，根据求得的限制连通度，求当组合星图中故障结点数为限制连通度减1，并且故障结点集为组合星图的限制集时，剩余图的直径，即组合星图的限制容错直径。依次得出n(n≥4)维2阶组合星图Sn，2的限制容错直径为5；当n≥5，k≥3，n-k≥2时，n维k阶组合星图Sn，k的限制容错直径不超过d(Sn，k)+8，其中d(Sn，k)为组合星图Sn，k的直径；同时给出并证明了当n+k-4个故障点集全部为一条组合边的邻点集时剩余图的直径，即：再增加一个故障结点，故障结点集就成为了组合星图Sn，k的极小限制分离集的情况下的直径。
最后，给出组合星图S4，2，S5，2，S5，3的极小分离集、极小限制分离集、限制容错直径的图例，进一步验证了以上求得的组合星图的限制连通度和限制容错直径的正确性和有效性。