一个系统级故障诊断问题

A System Level Fault Diagnosis Problem

寻找症候的最小相容集，这是系统级故障诊断的一个重要问题，在ＣｈｗａＨａｋｉｍｉ模型下，我们证明了两个结果：１）对于二分图系统，该问题是ＮＰ难的；２）对于森林系统，该问题是多项式时间可解的。

In system level fault diagnosis,it is an important problem to find a minimum compatible set of the syndrome. Under the model of Chwa  Hakimi,we prove two results:1)this problem is NP hard for bipartite graph systems;2)this problem is polynomial time solvable for forest systems.