在PMC模式下對星狀圖局部診斷能力之研究

Abstract

在PMC模式下面，我們介紹了一個新的診斷模式較做局部診斷能力，並且利用了一個結構來決定一個點的t-局部診斷能力。以星狀圖為例子來說，我們證明出在PMC模式下它的每個點的局部診斷能力和它的分支相同。於是我們提出了新的系統診斷觀念，叫做強局部診斷性質。一個系統若是其每點的局部診斷能力和它的分支相同則稱之具有強局部診斷性質。我們證明出星狀圖Sn在n □ 3的時候有此性質，甚至在n-3個邊壞掉的情況下此性質仍然存在。此外，若是我們保持每個點都有兩個好邊的話，則無論壞多少邊性質還是會存在。最後我們提出了一個局部診斷演算法其時間複雜度是O(NlogN)，而N是代表一個系統內點的數目。

Under the PMC model, we introduce a new measure of diagnosability, called local diagnosability, and derive a structure for determining whether a node of a system is locally t-diagnosable. For star graph, we prove that the local diagnosability of each node is equal to its degree under the PMC model. Then, we propose a concept for system diagnosis, called strong local diagnosability property. A system G = (V,E) is said to have a strong local diagnosability property, if the local diagnosability of each node is equal to its degree. We show that an n-dimensional star graph Sn has this strong property, n □ 3. Next, we study the local diagnosability of a faulty star graph. We prove that Sn keeps this strong property even if it has up to n-3 faulty edges. Furthermore, we prove that Sn keeps this strong property no matter how many edges are faulty, provided that each node of a faulty star graph Sn is incident with at least two fault-free edges. Besides, we propose a new diagnosasis algorithm whose time complexity is O(NlogN) where N is the number of nodes in a system.