k元n方体的条件强匹配排除

摘要

To measure the ability of k-ary n-cube to remain the property of having a perfect matching or an almost perfect matching in the presence of failures,by analysis of constructions of the fault sets that make the k-ary n-cube having neither a perfect matching nor an almost perfect matching under the conditional fault model,the minimum number of failures that make the k-ary n-cube unmatchable under the conditional fault model was studied.When k≥4 is even and n≥ 2,the exact value of the fault-tolerant parameter for k-ary n-cube was obtained and all the corresponding minimum fault sets were characterized.When k≥3 is an odd number and n≥2,a sharp lower hound and a sharp upper bound on the fault tolerance parameter for k-ary n-cube were given.The results indicate that the parallel computer system,which takes the k-ary n-cube with odd k as underlying interconnection topology,has good ability to remain the property of having a perfect matching or an almost perfect matching under the conditional fault model.Moreover,this system is still matchable if the number of failures does not exceed 2n and at most 4n-3 failures could make this system unmatchable.%为了度量发生故障时k元n方体对其可匹配性的保持能力,通过剖析条件故障下使得k元n方体中不存在完美匹配或几乎完美匹配所需故障集的构造,研究了条件故障下使得k元n方体不可匹配所需的最小故障数.当k≥4为偶数且n≥2时,得出了k元n方体这一容错性参数的精确值并对其所有相应的最小故障集进行了刻画;当k≥3为奇数且n≥2时,给出了该k元n方体容错性参数的一个可达下界和一个可达上界.结果表明,选取k为奇数的k元n方体作为底层互连网络拓扑设计的并行计算机系统在条件故障下对其可匹配性有良好的保持能力;进一步地,该系统在故障数不超过2n时仍是可匹配的,要使该系统不可匹配至多需要4n-3个故障元.