在当代社会,多处理器系统的应用越来越广泛。其功能实现主要依赖于节点之间的连接,也就是互连网络。互连网络的可靠性估计和故障诊断对系统的设计和维护有着重要的作用。而h-额外连通度和h-额外条件可诊断数分别是可靠性估计和故障诊断的重要措施。冒泡排序星图由于同时具有冒泡排序图和星图的性质比如小直径,对称,高容错性等而被广泛研究。首先,本文通过构造法和反证法得到了冒泡排序星图的最小h-簇度,h-额外连通度,以及在PMC模型下的h-额外条件可诊断数。当n?4和n?6时,冒泡排序星图的最小2,3-簇度分别等于它的1,2-额外连通度,为4n-8和6n-15;冒泡排序星图在PMC模型下的1,2-额外条件可诊断数分别等于它的1,2-额外连通度加上h,为4n-7和6n-13。其次,本文确定了一般简单图的h-额外连通度。给出一个最小连通分支确定算法MCDA,通过确定每个连通分支的顶点数目来找到其中最小的连通分支包含的顶点个数;在MCDA算法的基础上,进一步给出一般简单图中的h—额外连通度确定算法ECDA。并将该算法应用于具体网络中,结果表明,算法结果和理论证明的结果一致。最后,本文通过构造法和反证法研究了一般简单图的h-额外条件可诊断数。证明了当最小h(10)1-簇度和h-额外连通度相等时,PMC模型下一般简单图的h-额外条件可诊断数就等于h-额外连通度加上h。