缺边分裂星图在比较模型下的诊断性

作者：王世英; 赵丽娜

来源：山西师范大学学报(自然科学版), 2022, 36(01): 1-9.

DOI：10.16207/j.cnki.1009-4490.2022.01.013

• 互连网络
• 局部诊断性
• 比较模型
• 分裂星图

多处理器系统的诊断性是一个重要的研究课题，系统的可诊断性是衡量互连网络容错性的重要指标． 互连网络在多处理器系统中发挥着重要作用，且互连网络通常由一个图来表示，其节点(顶点)表示处理器，链路(边)表示处理器之间的通信链路． 分裂星图Sn2有许多良好的性质，本文研究了比较模型下 Sn2的诊断性． 根据局部诊断性的概念，强局部诊断性质被讨论，该性质描述了节点的局部可诊断性及其度的等价性． 我们证明了 Sn2(n≥ 5) 具有这种性质，并且在比较模型下，即使存在(2n -6) 个缺失边，它仍然保持这一强性质． 因此，只要缺失边集的基数不超过(2n -6)，每个处理器剩余度中最小值可以得到具有任意缺失边的 n? 维分裂星图的诊断性．

• 单位
  山西师范大学