1. 引言
诊断度是多处理器系统故障分析的一个重要参数。它在衡量互联网络可靠性方面有着重要作用。在1997年，Preparata [1] 等首次提出了系统诊断度理论。它的优点在于能够自动地检测系统中的处理器。系统级故障理论的研究依赖于模型的建立，因此许多模型被提出。例如Preparat [1] 等提出了PMC模型；Maeng和Malek [2] 提出了MM*模型。在2005年，Lai [3] 等考虑到在一个系统中，某个处理器的所有与之相邻的处理器同时发生故障的概率很小，故而对传统诊断理论做了改进，提出了条件诊断度，它要求系统中每个处理器至少与一个非故障处理器相连。在2012年，Peng [4] 在条件诊断度的基础上，进一步提出了好邻条件诊断度。它要求每个非故障处理器至少与个非故障处理器相邻，并且证明了超立方
体在PMC模型下的好邻诊断度是。原军等在 [5] [6] 中分别证明了元立方体在PMC模型下的好邻诊断度是和3元立方体在PMC模型和MM*模型下的好邻诊断度是(是偶数)和(是奇数)。在 [7] [8] 中，王牟江山等研究了在PMC模型和MM*模型下的好邻诊断度，
此时。在 [9] 中，王世英和韩威萍研究了维超立方体在MM*模型下的好邻诊断度。近些年来，许多基于超立方体的变形网络图被提出，例如，交叉立方体，分层立方网络，元立方网络等，它们较之超立方体有着更好的拓扑性质，因此在某些领域更受青睐。在本文中，我们主要证明了在时，扩展3元立方网络图在PMC模型和MM*模型下的1好邻诊断度均为。
2. 预备知识
2.1. 符号
我们用一个无向简单图来表示多重处理器系统，其中是图的顶点集，一个顶点代表了一个处理器，是图的边集，它表示了处理器之间的连接关系。对于任意的非空顶点子集，以为顶点集，以两端点均在中的边的全体为边集所组成的子图，称为在中的导出子图，记作。是顶点在中关联的边的数目，表示在中的度。表示的顶点的最小度。对于任意顶点，在中与相邻的所有顶点组成的集合称为的邻集，记作。若
是的非空顶点子集，则的邻集为。对，令
。图被叫做-正则的，是指它的任意一点都有。对
于任意的，若且在中至少有个邻点，则称为的好邻故障集。如果不连通且的每个连通分支的最小度为，则称是一个好邻割。的所有好邻割中的最小顶点数称为的好邻连通度，记作。
在PMC模型中，相邻的处理器之间可以相互测试。图中，对于任意的表示用测试，其中是测试者，而是被测试者。若是非故障点而是故障点(或非故障点)，则测试结果是1 (或0)。若是故障点，则测试结果不可靠。
在MM*模型下，一个结点同时向与它相邻的两个结点，发出一个相同的测试任务，再把测试结果返回给结点，会对返回的结果进行比较。用来表示对,进行测试的比较结果。如果这两个结果是相同的，则；否则，。若是故障的，则测试结果无论是0或1都是不可靠的。
2.2. 扩展k元n立方体
令。在 [10] 中，作者给出了扩展元立方的两个定义。
定义 1 [10] 令和是整数，扩展元立方有点，每个点用一组维字符串表示，即，其中和。如果和相邻当且仅当满足下列条件中的一个：
1) (或)，对，而，对，那么这种边被称为一条边(或边)；
2) 存在某个，，，， (或，，，)，，对所有的成立，则这种边被叫做边(或边)。
扩展元立方也可以按照如下定义。
定义 2 [10] 令，扩展元1立方的顶点集为。与相邻当且仅当或者。令，扩展元立方是由个扩展元立方构成的，其中第个中的点的第位皆为一个固定的数。且对，点将增加四条边，即边，边，边，边。
引理 1 [10] 令为扩展元立方，且和是整数。
1) 对，由第位是的所有点构成的的导出子图，被定义为，它同构与；
2)是点传递的，是边传递的，而且；
3)与之间的边组成的集合被定义为，并且；
4) 令 (其中)，那么。
为了方便，我们采用下面的方法来表示一个点在中的邻点。令。 那么，的邻点分别是：当，，或； 当，，或。
引理2 [11] 如果是的一条边，是的一条边，那么下列条件成立：
1) 当且时，
；
。
2) 当，，
如果，；
3) 当，，
如果，那么；
如果，那么
如果，那么。
4) 当，，
引理3 [11] 令是扩展元立方, 其中且均为整数。令是中的两个不同的点，那么：
1)，当；
2)，当；
3)，当。
引理4 [11] 令是扩展3元立方，当时，的1好邻连通度。
3.在PMC模型下的1好邻诊断度
定理1 [12] 一个系统在PMC模型下是好邻-可诊断的当且仅当对于中任意两个不同的顶点数至多为的好邻故障集，，存在和，使得(如图1)。
Figure 1. A distinguishable pair under the PMC model
图1. 在PMC模型下可区分对
引理5 [11] 当时，对任意的，若和相邻，则有；若和不相邻，则有。
引理6 当时，设，，，和，那么有，，且，。
证明 因为，所以。又因为，，，，，所以。根据引理5知，在中的公共邻点数达到最大。又因为，，所以，。
下面我们证明。
任取，根据引理5，任意一对不相邻的顶点至多有6个公共邻点，即，。因此，。又因为，所以当时有。于是有当，。
有两个部分：和。因为和，所以。
引理7 当时，在PMC模型下的1好邻诊断度。
证明 令集合的定义与引理6相同，，。根据引理6，，，，。因此，和是的1好邻故障集。因为，，所以在中，不存在从到的边。根据定理1，不是1好邻-可诊断的。因此，。
引理8 当时，在PMC模型下的1好邻诊断度。
证明 由1好邻诊断度的定义，我们只需要证明是1好邻-可诊断的。根据定理1，等价于证明对于任意两个不同的好邻故障集，，其中和，存在和，使得。反证法。假设和是两个不同的1好邻故障集，并且，。但是这个点集对不满足定理1的任何条件。不失一般性，我们假设。如果，那么，这显然与时矛盾。因此，。然后由于从到没有边和是的一个1好邻故障集，所以和。同理，若，那么。由于从到没有边，所以是一个1好邻割。根据引理4，有。又因为，所以，这显然是矛盾的。因此是1好邻-可诊断的，即。
定理2在PMC模型下的1好邻诊断度。
4.在MM*模型下的1好邻诊断度
定理3 [12] 一个系统在MM*模型下是好邻-可诊断的当且仅当对中任意两个不同的顶点数至多为的好邻故障集，满足以下其中一个条件(如图2)。
Figure 2. A distinguishable pair under the MM* model
图2. 在MM*模型下可区分对
1) 存在和满足。
2) 存在和满足。
3) 存在和满足。
引理9 当时，在MM*模型下的1好邻诊断度。
证明 令集合的定义与引理6相同，，。根据引理6，，，，。因此，和是的好邻故障集。因为，，所以在中，不存在从到的边。根据定理1，不是1好邻-可诊断的。因此，。
引理10 当时，在MM*模型下的1好邻诊断度。
证明 根据1好邻诊断度的定义，需要证明是1好邻-可诊断的。反证法。根据定理3，假设和是两个不同的1好邻故障集，并且，。但是这个点集对不满足定理3的任何一个条件。不失一般性，我们假设。按照下面的情况进行讨论：
情形1。
因为，所以，这显然与时矛盾。因此，
情形2。
断言1没有孤立点。
反证法。假设至少有一个孤立点。因为是一个1 好邻故障集，所以至少存在一点使得。因为不满足定理3中的(3)，所以至多存在一点使得。因此仅有一点使得。如果时，那么。因为是一个1好邻故障集，所以和，这与是一个孤立点矛盾。因此，。类似地，我们可以断定仅有一点使得。设是中的孤立点集，。对任意的，在中有个邻点。因为，所以可得。假设，那么，这显然与时矛盾。所以，。因为不满足定理 3中的(1)且的任意一点在中不是孤立点，所以与之间不存在边相连。因此，是的一个点割且，即是的一个1好邻割。由引理4知，。因为，且和都非空，所以。再根据引理3，即任意一对不相邻的顶点至多有6个公共邻点，所以，。于是，我们来考虑下面三种情况：
情形2.1。
设。因为，所以我们来考虑在中的邻点个数。不失一般性，令和。由引理2和3知，和中任意两点在中的公共邻点个数分别为：，和。又因为和均有邻点在中，所以。因此，。而这与时矛盾。所以。
情形2.2。
令，和。因为，所以我们来考虑在中的邻点个数。由引理2和3知，，和中任意两点在中的公共邻点数分别为：，和。又因为和均有邻点在中。所以，。因此，。而这与时矛盾。所以
情形2.3。
令，和。由引理2和3知，，和中任意两点在中的公共邻点数分别为：，和。又因为有邻点在中，各有邻点在中，所以，。因此，。这与矛盾。所以，。断言1证明完毕。
对，根据断言1，在中至少有一个邻点。因为，不满足定理3，根据定理3的(3)，所以在中没有邻点。因为与中间没有边和是一个1好邻故障集，所以，。又因为与中间没有边，所以是的一个1好邻割。根据引理4，。由于，那么，，矛盾。因此，是1好邻-可诊断的。故。
结合引理9和引理10可得以下定理：
定理4在MM*模型下的1好邻诊断度。
5. 结束语
在这篇文章中，我们研究了扩展3元立方在PMC和MM*模型下的1好邻诊断度。我们证明了当时，扩展3元立方在PMC和MM*模型下的1好邻诊断度都是。这为今后进一步研究扩展3元立方网络的好邻连通度、诊断度和相关诊断算法提供了理论基础。
基金项目
国家自然科学基金资助项目(61370001)，教育部博士点基金(博导类)资助项目(20111401110005)。
*通讯作者。
参考文献