在比較模式下強診斷性質之研究

Abstract

在多處理器系統中，診斷能力是一個重要的性質，以增加系統的可靠度。在比較模式下，n維度的超立方體家族診斷能力皆是n，但是我們發現除了當某一點的所有鄰居同時皆是壞點的情形下，其它情況時其實這些超立方體家族診斷能力根本是n+1以上。在本篇中，我們提出強診斷性質的觀念，並且證明如下：令G1和G2擁有相同點數且兩者皆是t-正則圖形，在G1和G2之間做一完全配對，形成一配對構成網路G=G1♁G2，則G在比較模式下不僅是(t+1)-診斷系統並且也是強(t+1)-診斷系統。根據以上結果，我們知道任何一個n維度的超立方體家族在比較模式下皆是強n-診斷系統，當n≧4。

The diagnosability is an important property on the high-performance signal processing systems. We need to find faulty processors quickly and correctly to make sure the reliability of system. There are many achievements related to diagnosability in recent researchs. Under the comparison model, the diagnosability of n-dimensional cube family is n. But we find that these cubes are almost (n + 1)-diagnosable except that all the neighbors of some vertex are faulty simultaneously. In this thesis, we introduce a new concept, called a strongly t-diagnosable system under the comparison model. The goal of this thesis is the following. G1, G2 are two t-regular graph with the same number of vertices N, N ≧ t+1, for t ≧ 3. orderGi(v) ≧ t for every node v in Gi and the connectivity κ(Gi)≧t for i = 1, 2. We prove that the MCN constructed from G1 and G2 is strongly (t + 1)-diagnosable system. Applying this result, the Hypercube Qn, the Crossed cube CQn, the Twisted cube TQn, and the Mobius cube MQn are all strongly n-diagnosable for n ≧4.