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

来源：计算机应用杂志2017年第9期北京时间：

作者：冯凯

单位：山西大学 计算机与信息技术学院, 太原 030006

摘要：为了度量发生故障时k元n方体对其可匹配性的保持能力，通过剖析条件故障下使得k元n方体中不存在完美匹配或几乎完美匹配所需故障集的构造，研究了条件故障下使得k元n方体不可匹配所需的最小故障数。当k ≥ 4为偶数且n ≥ 2时，得出了k元n方体这一容错性参数的精确值并对其所有相应的最小故障集进行了刻画；当k ≥ 3为奇数且n ≥ 2时，给出了该k元n方体容错性参数的一个可达下界和一个可达上界。结果表明，选取k为奇数的k元n方体作为底层互连网络拓扑设计的并行计算机系统在条件故障下对其可匹配性有良好的保持能力；进一步地，该系统在故障数不超过2n时仍是可匹配的，要使该系统不可匹配至多需要4n-3个故障元。

关键词：并行计算机系统,互连网络,k元n方体,完美匹配,条件故障

基金资助：国家自然科学基金资助项目（61502286）。