簇度及其在互连网络可靠性和故障诊断中的应用

超级计算机的可靠性分析和故障诊断是容错计算的一个重要研究领域,是通过对其图论模型-互连网络的分析来进行的。其中可靠性分析包括确定其互连网络的超连通度、额外连通度并分析故障网络的结构；故障诊断能力的研究包括确定各种互连网络在PMC模型和比较模型下的可诊断数和条件可诊断数等。以往两方面的研究相对独立。本项目提出一个新的参数图的簇度并通过研究互连网络的最小k簇度来研究其可靠性和可诊断性能，从而展现这两方面的研究可以有机的结合起来。本项目将研究一些具体的互连网络、著名的图类、一般图的最小k簇度并应用其确定这些互连网络的可靠性和故障诊断参数。其中具体互连网络主要有折叠立方体网络、k元n立方体网络、星图网络等；著名的图类包括匹配合成网络、笛卡尔乘积图、凯莱图等。该项目不但可以建立最小k簇度研究的理论基础还可以将互连网络的可靠性分析和故障诊断研究有机的结合起来，从而建立容错计算研究的一套新的方法体系。

互连网络是多处理器系统的拓扑结构，是影响多处理器系统性能的一个关键因素。通过对互连网络的一些图论参数的研究，可以为多处理器系统的设计和维护提供重要的参考。连通度、限制连通度、超连通度、额外连通度是度量多处理器系统可靠性的重要参数。可诊断数、条件可诊断数是多处理器可诊断性能的重要度量参数。一些重要互连网络的这些参数在过去得到了大量的研究关注。几何学中的等周问题可以追溯到古希腊，图的等周问题也是近代组合学和图论的一个重要研究课题。最小簇度是图的等周问题的研究中的一项重要内容。以往的这几个方面的研究是相对独立的。本项目在自然科学基金（青年）的资助下，通过对这些问题的研究，取得了以下研究成果： .（1）为互连网络的可靠性和故障诊断参数的研究找到了一个新的研究方法. 显示可以利用互连网络的最小簇度的结果来确定其可靠性和可诊断性度量参数并分析故障互连网络的结果。从而在对互连网络的可靠性和故障诊断研究中，引入了图的等周问题的研究方法。.（2）研究了立方体网络、BC网络、折叠立方体网络等网络的可靠性和可诊断性能。.（3）研究了立方体、BC网络的最小簇度及其可靠性。.（4）提出了无桥3正则赋权图的完美匹配覆盖猜想并考察了它与其他几个完美匹配覆盖猜想之间的关系。