交叉立方体在两种策略下的可诊断性

DIAGNOSABILITY OF CROSSED CUBES UNDER TWO STRATEGIES

互连网络可诊断性度的高低是衡量这种网络性能优劣的重要标志二交叉立方体是近年提出的一类互连网络，它有一些比超立方体更好的性质．本文用PMC模型证明了n维交叉立方体Dn在精确策略和悲观策略下分别是n-可诊断的和（2n－2）／（2n－2）一可诊断的，从而证明民在这两种策略下的可诊断性度与n维超立体的相同．另外，本文在证明Dn是n-可诊断的同时，还得到了Dn中任何两顶点之间的n条互不相交的路径，它们可作为容错远路的依据．

The degree of diagnosability of an interconnection network is an impor-tant standard to measure the properties of the network- Crossed cubes which havebeen proposed recently are a kind of interconnection networks,possessing some bet-ter natures than hypercubes. This paper proves that n-dimensional crossed cube D.is n-diagnosable and (2n - 2)/(2n - 2)-diagnosable respectively under the precisestrategy and the pessimistic strategy by using the PMC model. Thus, it proves thatthe degrees of diagnosability of Dn are the same as those of n-dimensional hypercubeunder the two strategies- In the course of proving that D' is n-diagnosable in thispaper, n disjoint paths between any two nodes in D. are gained, which may be treat-ed as the basis of fault tolerant routing.