周 俊

(西安电子科技大学数学与统计学院，陕西西安 710071)

随着现代科学技术的发展，一个多处理器系统可由成千上万个处理器组成，系统在使用过程中会出现故障的处理器，将其找出是本文所要做的工作。所谓系统诊断就是找出一个处理器中故障点的过程，定义一个正整数t，只要一个系统的故障点不超过t，那么这个系统就是可诊断的。

目前，为诊断多处理器系统中的故障点，已有人提出了两种诊断模型:PMC模型和比较模型。本文将主要采用比较模型解决系统的诊断，所谓比较模型就是从系统中的一个点w去测试和w相邻的不同的两个点u，v，再比较两个测试结果是否一致。文中分别用(u，v)w和r((u，v)w)表示一个测试点和一个测试结果，若 r((u，v)w)=0，则表示测试一致;若 r((u，v)w)=1，则表示测试结果不同。在比较模型下，如果r((u，v)w)=0且w不是故障点，则u，v都是无故障点;如果r((u，v)w)=1，则 u，v，w 至少有一个点是故障点;如果w是故障点，则测试结果是不可靠的。

1 预备知识

设Γ是一个固定的群，S是Γ的一个子集且不含有 Γ 中的相同的元素，Cayley［1］图 Cay(Γ，S)是一个无向图，其中Γ是点集;集合{(g，gs )∈Γ，s∈S}是弧集。Sym(n)用一个置换{1，…，n}，ij位置置换表示为(p1…pi…pj…pn)(ij)=(p1…pj…pi…pn)。设 X 为一个置换集，则G(X)是一个置换树生成图［2］，其中点集为{1，2，…，n}边集 E=(ij)∈X}。

一个多处理器系统可以表示成一个无向图G=(V，E)，其中V和E分别是图G的点集和边集。如果两个点u，v是相邻的则uv是G中的一条边。一条路径可表示为 P［v0，vk］=〈v0，v1，…，vk〉，其中若 vi和vi+1在G中相邻，且P中的内部点互不相同。当v0=vk时，则P［v0，vk］为一个圈。设 u是图 G中的一个点，则uNG(u)表示u的邻点，设X为图G中的一个点集［3］，则 NG(X)={v∈V(G)－X∈X 且(u，v)∈E(G)}。用Gn表示n维置换树生成的 Cayley图［4－6］。

定义1 若一个有n个点的系统所有故障点不超过t，其所有的故障点可以被诊断出，该系统是t－可诊断的［7］。

定义2 假设一个图G=(V，E)，若G中的每一条边E至少有一个端点在H中，则H是G的一个点覆盖。假设u∈V，则点u关于图G的最小点覆盖数称为u的次序。

根据以上的定义可以得到以下结论:

引理1［8］Gn中任何点的次序都为 n－1。

引理2［8］Gn中任何两个点最多有两个相同的邻点。

引理3［9］Gn中没有奇圈。

引理4［9］设Gn是置换树生成的Caley图且Gn不是星图，则当n≥3时有:(1)Gn中最小圈是4。(2)Gn中没有K2，3作为子图，如图1所示。

图 1 K2，3

2 主要结果

引理5 设u，v是 Gn中两个点，则 NG(u，v)≥2n－4。

证明 Gn是(n－1)正则图，则。考虑两种情况:(1)u，v是Gn中相邻的两个点，则2n－4。(2)u，v不是 Gn中相邻的两个点，则

综上所述，Gn中任意两点中至少有2n－4个邻点。

引理 6 设 u，v，x，y是 Gn中 4 个点，则

证明 考虑到4个点中相邻点的数目，可以有以下几种情况:

(1)当4个点都相邻，则会有图2所示的3种情形。

图2 4个点相邻

1)4个点组成一个圈，则

2)4个点中最多有1个相同邻点，则

3)4个点中最多有两个相同邻点，则

(2)4个点中有3个点相邻，而另一个点与这3个点都不相邻。则会有如图3所示的两种情况。

图3 3个点相邻

1)这种情况下，4个点最多有4个相同邻点，则

2)这种情况下，4个点最多有3个相同的邻点，则

(3)4个点中两个点相邻与两个点相邻，如图4所示。则

图4 4个点两两相邻

(4)4个点中两个点相邻，另两个点不相邻，如图5所示。则

图5 4个点中两个点相邻另两个不相邻

(5)4个点都不相邻，如图6所示。则有

综上所述:Gn中任何4个点至少有4n－12个邻点。

定理1［8］一个有N个点的系统是t－可诊断的，

则满足3个条件:(1)N≥2t+1。(2)任意一个点的次序至少为t。(3)任何一个集合X⊂V，则有2t+p且

定理2［8］当n≥4时，n维星图在比较模型下是(n－1)可诊断的。

定理3 当n≥5时，n维置换树生成的 Cayley图在比较模型下是(n－1)可诊断的。

证明 由定理2可知，当n≥4时，n维星图在比较模型下是(n－1)可诊断的［5－6］。接下来，证明 Gn是(n－1)可诊断的。

已知Gn有n!个点且Gn中每个点的次序都是(n－1)。显然当n≥3时，n!≥2(n－1)+1。根据定理1，只要证明条件(3)。即满足是正确的。分两步证明，首先，证明当p=n－2时结论是正确的，再证明当0≤p≤n－3时结论正确。

图6 两个点不在T(X)中

1)NG(u)∩X=∅。2)若果存在u'∈NG(u)∩X，则NG(u')∩X=∅，如果两个点。

u，v∉T(X)则满足图7中3种情况的一种。

图7 两个点不在T(X)中的3种情形

情形1 不在T(X)中的两个点都是图6中情形a的点，由于则有

情形2 一个点是情形a中的点，另一个点是情形b中的点。假设u是情形b中的点，v是情形a中的点。由于v和X中任何点都不连通，所以u和v不相邻。故 有且

情形3 两个点都属于情形b中的点，由T(X)的定义可知，u'和v'是不相邻的，则且

图8 4个点不在T(X)中的5种情形

情形1 4 个点都属于情形 a，则 NG({u，v，x，y}) 以及 u，v，x，y 都不在 X 中且有 NG({u，v，x，y})≥4n －12，故有

情形2 4个点中有3个点属于情形a一个点属于情形b。假设u和u'是相连通的且u'∈X，则u'和v，x，y不相邻，则有以下3种情形:

情形2.1 v，x 和 y 相邻，则 NG({u'，v，x，y})以及v，x，y 都不在 X 中且有 NG({u'，v，x，y})≥4n － 12，故有

情形2.2 3个点中有两个点相邻一个点不相邻，则 NG({u'，v，x，y})以及 v，x，y 都不在 X 中且有NG({u'，v，x，y})≥4n －10，故有

情形 2.3 3 个点相互相邻，则 NG({u'，v，x，y})以及 v，x，y 都不在 X 中且有 NG({u'，v，x，y})≥4n －12，故有

情形3 4个点中有两个点属于情形a另外两个点属于情形b，假设u，v属于情形b x，y属于情形a，则u'和v'互不相邻，同时和x，y也不相邻。则有以下两种情形:

情形 3.1 x，y 是相邻的两个点，则 NG({u'，v'，x，y})以及 x，y 都不在 X 中且有 NG({u'，v，x，y})≥4n －10，故有

情形3.2 x，y是互不相邻的两个点，则NG({u'，v'，x，y})以及 x，y 都不在 X 中且有 NG({u'，v，x，y})≥4n－12，故有

情形4 4个点中有3个点属于情形b有一个点属于情形a，假设属于情形b且y属于情形a。则u'，v'，x'互不相邻且不和 y 相邻，则 NG({u'，v'，x'，y})以及 y都不在 X 中且有 NG({u'，v'，x'，y})≥4n －12，故有

情形 5 4 个点都属于情形 b，则 u'，v'，x'，y'互不相邻，则 NG({u'，v'，x'，y'})都不在 X 中且有 NG({u'，v'，x'，y'})≥4n －12，故有

3 结束语

证明了当n≥5时，置换树生成的Cayley图在比较模型下是n－1可诊断的。同时Gn的最小边界也已研究，这样就可以继续研究Gn的额外连通度。在此结果的基础上，当一个系统的故障处理器不超过n－1时，就可对该系统进行诊断。而该诊断只涉及一个测试阶段，以确定有故障的处理器和一个更换阶段。因此，使用与环境的组件是可靠的，并具有周期性和快速性，且经济实惠。

［1］Cheng E，Lipták L.Diagnosability of Cayley graphs generated by transposition trees with missing edges［J］.Information Sciences，2013，23(8):250 －252.

［2］Hsu G H，Chiang C F，Shih L M，et al.Conditional diagnosability of hypercubes under the comparison diagnosis model［J］.Journal of Systems Architecture，2009，55(2):140 －146.

［3］Zheng J，Latifi S，Regentova E，et al.Diagnosability of star graphs under the comparison diagnosis model［J］.Information Processing Letters，2005，93(1):29 －36.

［4］Bondy J A，Murty U S R.Graph theory with applications［M］.London:Macmillan，1976.

［5］Tanaka Y，Kikuchi Y，Araki T，et al.Bipancyclic properties of Cayley graphs generated by transpositions［J］.Discrete Mathematics，2010，310(4):748 －754.

［6］Caruso A，Chessa S，Maestrini P，et al.Diagnosability of regular systems ［J］.Journal of Algorithms，2002，45(2):126－143.

［7］Tanaka Y，Kikuchi Y，Araki T，et al.Bipancyclic properties of Cayley graphs generated by transpositions［J］.Discrete Mathematics，2010，310(4):748 －754.

［8］Yang W，Li H，Meng J.Conditional connectivity of Cayley graphs generated by transposition trees［J］.Information Processing Letters，2010，110(23):1027 －1030.

［9］Cheng E，Lipták L，Shawash N.Orienting Cayley graphs generated by transposition trees［J］.Computers and Mathematics with Applications，2008，55(11):2662 －2672.