1. 前言
近些年来，随着多处理器规模的扩大，处理器的稳定性对系统的正常运行起着至关重要的作用。为了保证系统的稳定性，一个处理器无论何时发生故障，它都应该及时地被非故障处理器所识别，我们把识别故障处理器的过程叫做系统的诊断。在一个系统中，如果所有的故障处理器能够被自我诊断出来，并且所诊断出的故障处理器的数量不超过，那么我们说这个系统是可诊断的。一个系统的诊断度指的是是可诊断的的最大值。
为了识别系统中的故障处理器，一些诊断模型被提出，如PMC模型和MM*模型。PMC模型 [1] 是由Preparata等首次提出，它是通过两个相邻的处理器之间相互测试来实现的。Maeng和Malek提出了另一种比较诊断模型(MM*模型) [2] 。在MM*模型下，一个顶点分别给它的两个邻点发出相同的任务，然后比较它们反馈的结果。2005年，Lai等提出了多处理器系统的一种限制诊断度，命名为条件诊断度 [3] 。2012年，Peng等通过限制每个非故障顶点至少有个非故障邻点，提出了好邻诊断度 [4] ，并且他们证明了超立方体在PMC模型下的好邻诊断度是。王世英，韩威萍在文 [5] 中证明了维超立方体在MM*模型下的好邻诊断度。原军等在文 [6] 中证明出了元立方体在PMC模型和MM*模型下的好邻诊断度是。他们在文 [7] 中还证明了3元立方体的好邻诊断度。对于条件诊断度来说，其假设故障和非故障点的邻域中均至少有一个是非故障的。而对于1好邻诊断度来说，其仅假设非故障点的邻域中至少有一个是非故障的。在实际中，为节约资源和提高运算效率，大规模多处理器系统中多采用模块化设计方式。局部处理器多共享如电源、存储空间等软硬件资源且相对地数据交换频率较高。这就意味着非故障点的邻域中至少存在一个非故障点的概率远大于故障点邻域中至少存在一个非故障点的概率。鉴于此种情况，1好邻诊断度较条件诊断度更为贴合实际。马晓蕾等在文 [8] 中证明了交叉立方体的1好邻连通度和诊断度。在文 [9] 中，王牟江山等证明了网络的1好邻诊断度不超过条件诊断度。我们在这篇文章中研究Möbius立方体的1好邻连通度和诊断度。本文第二部分是预备知识，第三部分证明了Möbius立方体的1好邻连通度是，第四部分又证明了Möbius立方体在PMC模型下和在MM*模型下的1好邻诊断度是，第五部分是结论。
2. 预备知识
在这部分，我们将给出文中需要的一些基本符号和概念，Möbius立方体、PMC模型、MM*模型在这部分将给出介绍。
互联网络的拓扑结构我们用图来表示，其中顶点表示处理器，边表示两处理器之间的通信链路。对于一个顶点，是在中的度，表示在中与相关联的边数。对于任意一点，与相邻的所有顶点的集合称作的邻集，记作。假设，那么的邻集表示为。设和是中两个不同的子集。我们将对称差记作。一条路是一个所有顶点互不相同的相邻的顶点序列。如果是图的边子集，且中的任意两条边没有公共顶点，则称是的一个匹配。如果是图中包含边数最多的匹配，称是的一个最大匹配。特别地，若最大匹配饱和了的所有顶点，称它是的一个完美匹配。任意一个故障集，对于任意一点，如果，那么称作的好邻故障集。如果好邻故障集使得不连通，那么是一个好邻割。的所有好邻割中的最小顶点数称为的好邻连通度，记作。文中其它未定义而直接使用的基本符号和概念参见文献 [10] 。
在PMC模型中，为了诊断系统，在中相邻的两点之间可以相互测试。在中，两个相邻的顶点和，表示从到的测试，其中是测试者，是被测试者，我们用表示测试结果。在PMC模型下，所有的测试结果如表1所示。在MM*模型下，结点给它相邻的两个结点，分配同一个的任务，再把测试结果反馈给结点，对这两个结点反馈的结果进行比较。全部的测试结果叫做这个系统的比较症候，记作。我们用来表示测试结果。在MM*模型下，所有可能出现的比较结果如表2所示。
维超立方体是一种很受欢迎的拓扑结构，Möbius立方体作为超立方体的一种重要变形，它有着比超立方体更好的性质。在文献 [11] 中已经给出了维Möbius立方体的概念，维Möbius立方体是一个有个顶点和条边的正则图。的直径大约是维超立方体的一半。在中，点之间的平均通信步大约是超立方体的2/3，比超立方体有着更强的动态性能。因此也是一种很好的网络拓扑结构，值得我们研究。
维Möbius立方体作为超立方体的变形，其有两种形式，0型维Möbius立方体和1型维Möbius立方体，分别记作和。
定义1维Möbius立方体，表示为和，它的顶点集是。在中，两个顶点，相邻当且仅当(a)存在()满足：
(1) 如果，那么。
(2) 如果，那么。
(b)满足。
在中，两个结点，相邻当且仅当(a)存在()满足：
图1给出了4维的0型Möbius立方体，图2给出了4维的1型Möbius立方体。
Table 1. The test results in the PMC model
表1. 在PMC模型下测试结果
Table 2. The test results in the MM* model
表2. 在MM*模型下测试结果
Figure 1. 4 dimensional 0 type Möbius cube
图1. 4维0型Möbius立方体
Figure 2. 4 dimensional 1 type Möbius cube
图2. 4维1型Möbius立方体
和都是维Möbius立方体，本文只讨论，并把它记为。
3. n维Möbius立方体的1好邻连通度
引理 3.1 [12] 当时，不包含三圈。
根据定义1，两个顶点，相邻当且仅当条件(b)成立，即，当时满足，此时我们称顶点和之间的连边是的第维边。我们将沿着最高维分解，是通过删除中所有第维的边，将其分解成两个维子图和，显然他们都同构于。我们称和之间的连边为交叉边，这些交叉边的集合是的一个完美匹配。
引理 3.2维Möbius立方体中任意两个顶点之间至多有两个公共邻点。
证明根据引理3.1，任意两个相邻的顶点没有公共邻点。设，是中任意两个不相邻的顶点。用归纳法证明。当时,是一个四圈，此时结论成立。我们假设时结论都成立，即，中任意两个顶点之间至多有两个公共邻点当。将沿最高维分解成两个维子图和，它们同构于，和之间存在完美匹配。若和在同一个维的子图中，不失一般性，假设。由归纳假设和在中至多有两个公共邻点。因为和之间交叉边是一个完美匹配，所以和在中没有公共邻点。若和分别在两个维的子图中，不失一般性，假设和。因为和之间交叉边是一个完美匹配，所以与在和中均至多有一个公共邻点。因此，和在中至多有两个公共邻点。由和的任意性，中任意两个不相邻的顶点至多有两个公共邻点。
引理 3.3 [12] 维Möbius立方体的连通度。
引理3.4 当时，对任意的，设且，则。
证明要证，我们只需证明不含孤立点。当或4时，结论显然成立。当时，用反证法证明。假设是中的孤立点，则。因为和，所以和。根据引理3.2，可得和。于是，。因为是正则图，所以。因此，至少存在一个邻点不在中，这与矛盾。所以不含孤立点。故。
引理 3.5维Möbius立方体的1好邻连通度。
证明 令和的定义与引理3.4相同，则是的一个割。因为没有三圈，可以得到。根据引理3.4，可以推出，又因为。因此，是一个1好邻割。故可以推出。
引理 3.6令是的一个点割。当时，恰有两个分支，一个是平凡分支，另一个是非平凡分支。
证明将沿最高维分解成两个()维的子图和，它们同构于。设，，则且。不失一般性，我们假设。
情形1或者。
不失一般性，我们假设。此时。因为和之间的交叉边是的一个完美匹配，所以是连通的。这与是的一个点割矛盾。
情形2 且。
情形2.1。
根据引理3.3，，所以是连通的。
情形2.1.1。
根据引理3.3，，所以是连通的。因为以及和之间的交叉边是的一个完美匹配，所以是连通的，即，是连通的。这与是的一个点割矛盾。
情形2.1.2。
此时。假设是连通的，证明同情形2.1.1。因此是不连通。注意到，又因为和之间的交叉边是的一个完美匹配，所以中除孤立点外的分支一定与连通。因此，恰有两个分支，一个是平凡分支，另一个是非平凡分支。
情形2.2。
此时。此情形证明同情形2.1.2。
综上所述，结论成立。
引理 3.7令是的一个点割。当时，恰有两个分支，一个是平凡的，另一个是非平凡的。
证明 将沿最高维分解成两个()维的子图和。显然，它们同构于。设，，则且。我们采用归纳法证明。当时，。根据引理3.6，恰有两个分支，一个是平凡的，另一个是非平凡的。假设时结论也成立，即，是的一个点割且当时，恰有两个分支，一个是平凡的，另一个是非平凡的。下面证明时结论也成立。不失一般性，假设，因为，所以。
情形1。
根据引理3.3，，则和都连通。因为且和之间的交叉边是的一个完美匹配，所以是连通的，即，是连通的。这与是的一个点割矛盾。
情形2。
根据引理3.3，。则连通。
若连通，证明同情形1。故不连通。由归纳假设，恰有两个分支，一个是平凡分支，另一个是非平凡分支。因此，。注意到，。又因为和之间的交叉边是的一个完美匹配，所以。因此，中至少有一点与中的点相连。则连通。若与中的任意一点相连，那么连通，这与是的一个点割矛盾。故恰有两个分支，一个是平凡分支，另一个是非平凡分支。
情形2.2.1。
在这种情况下，。根据引理3.3，连通。若连通，证明同情形1。故不连通。注意到，又因为和之间的交叉边是的一个完美匹配，所以中除孤立点外的分支一定与连通。因此，恰有两个分支，一个是平凡分支，另一个是非平凡分支。
情形2.2.2。
在这种情况下，。因为和之间的交叉边是的一个完美匹配，所以连通。这与是的一个点割矛盾。
引理 3.8维Möbius立方体的1好邻连通度。
证明我们用反证法证明，假设是一个1好邻割且。则没有孤立点且不连通。根据引理3.7，当，恰有两个分支，一个是平凡的，另一个是非平凡的。这与没有孤立点矛盾。因此，结论成立。
结合引理3.5和引理3.8可得以下定理：
定理 3.9 维Möbius立方体的1好邻连通度。
4.在PMC模型下和MM*模型下的1好邻诊断度
定理4.1 [6] 在一个系统中，对于任意两个不同的且顶点个数不超过的好邻故障集，，若，是可区分的，则是好邻条件-可诊断的，使得是好邻条件-可诊断的最大值叫做的好邻诊断度，记作。
定理4.2 [6] 一个系统在PMC模型下是好邻-可诊断的当且仅当对于中任意两个不同的顶点数至多为的好邻故障集，，存在和，使得(如图3)。
定理4.3 [6] 一个系统在MM*模型下是好邻-可诊断的当且仅当对中任意两个不同的顶点数不超过的好邻故障集，满足以下其中一个条件(如图4)：
(1) 存在和满足。
(2) 存在和满足。
(3) 存在和满足。
Figure 3. A distinguishable pair under the PMC model
图3. 在PMC模型下可区分对
Figure 4. A distinguishable pair under the MM* model
图4. 在MM*模型下可区分对
引理4.4 维Möbius立方体在PMC模型下和MM*模型下的1好邻诊断度。
证明 对任意的，设，和。因为没有三圈，所以和。根据引理3.4，和。因此，，是的两个1好邻故障集。因为和，所以在和之间没有边。由定理4.2定理4.3，我们可以推出在PMC模型下和MM*模型下不是1好邻-可诊断的。因此，由1好邻诊断度的定义可知的1好邻诊断度小于，即。
引理4.5 维Möbius立方体在PMC模型下的1好邻诊断度。
证明由1好邻诊断度的定义，需要证明是1好邻-可诊断的。根据定理4.2，证明是1好邻-可诊断的等价于证明任意两个不同的且顶点个数不超过的1好邻故障集，，存在和，使得。
采用反证法证明。假设在中有两个不同的且顶点个数不超过的1好邻故障集，，根据定理4.2，对任意的和使得。不失一般性，假设。可以分以下两种情况进行讨论：
因为和，我们可以推出。当时，上述不等式矛盾。
情形 2 。
根据假设与之间没有边和是好邻故障集，可得。同理，若，则。因为，都是1好邻故障集，所以也是一个好邻故障集。又因为在和之间没有边，所以不连通。故是的1好邻割。根据引理3.8，可得。因此，。这与相矛盾。因为以上两种情况都产生矛盾，所以是1好邻-可诊断的。由的定义可得，。
结合引理4.4和引理4.5，可得以下定理：
定理 4.6维Möbius立方体在PMC模型下的1好邻诊断度。
引理 4.7 维Möbius立方体在MM*模型下的1好邻诊断度。
证明根据1好邻诊断度的定义，等价于证明是1好邻-可诊断的。采用反证法证明。根据定理4.3，假设中存在两个不同的且顶点个数不超过的1好邻故障集，，和不满足定理4.3中的(1)-(3)。不失一般性，假设。分以下两种情况进行讨论：
情形 1。
证明同引理4.5的情形1。
断言 1 没有孤立点。
为了证明结论成立我们采用反证法。设至少有一个孤立点。因为是一个1好邻故障集，所以至少存在一点使得与相邻。另一方面，因为不满足定理4.3中的(1)~(3)中的任意一种条件，所以至多存在一点使得。因此仅有一点使得。因为是一个1好邻故障集，所以在至少有一个邻点，即。同理，仅有一点使得。设是中的孤立点集，令是由点集导出的子图。因此，对任意的，存在个邻点在中。由于，故。因为，所以。假设，有。当时，上式矛盾，故。因为不满足定理4.3中的(1)且的任意一点是不孤立的，所以可以推出与之间不存在边相连。因此，是的点割且，即是的一个1好邻割。根据定理3.8，。 因为,并且和都是非空的，所以。于是，设和。所以对于任意的满足。根据引理3.2，与在中至多有两个公共邻点。因此， 至多有两个孤立点。
假设中恰有一个孤立点，则，在中与相邻。显然，，，和。根据引理3.2，与在至多有两个公共邻点，所以。因此，。于是，。这与矛盾。
假设在中还有另外一个孤立点,则，和。根据引理3.1，可以得到和。又因为在中任意两点至多有两个公共邻点，所以，，和中任意两个集合在中都没有公共点。因此。于是，，这与矛盾。断言1证明完毕。
设。根据断言1，在中至少有一个邻点。因为，不满足定理4.3中的(1)~(3)中的任意一种条件，根据定理4.3(1)，所以对于任意一对相邻的点，不存在使得和。因此，我们可以得到在中没有邻点。由的任意性，与之间没有边。因为是一个1好邻故障集且，所以,则。因为和都是1好邻故障集并且与之间没有边，所以是的一个1好邻割。根据引理3.6，有。因此，。这与矛盾。于是，是1好邻-可诊断的。故。
结合引理4.4和引理4.7可得以下定理：
定理 4.8 维Möbius立方体在MM*模型下的1好邻诊断度。
5. 结论
在这篇文章中，我们研究了维Möbius立方体在两种模型下的1好邻诊断度问题。本文证明了Möbius立方体的1好邻连通度是，又证明了Möbius立方体在PMC模型下的1好邻诊断度是和在MM*模型下的1 好邻诊断度是。1好邻诊断度是假设每个非故障点至少有1个好的邻点，好邻诊断度是假设每个非故障点至少有个好的邻点。这项工作将对后面研究Möbius立方体网络的好邻连通度、诊断度和相关诊断算法提供很好的帮助。
基金项目
国家自然科学基金资助项目(61370001)，教育部博士点基金(博导类)资助项目(20111401110005)。
*通讯作者。
参考文献