Advances in Applied Mathematics
Vol.05 No.02(2016), Article ID:17671,9 pages
10.12677/AAM.2016.52036

The 1-Good-Neighbor Connectivity and Diagnosability of Crossed Cubes

Xiaolei Ma1, Shiying Wang1,2*, Zhenhua Wang1

1School of Mathematics and Information Science, Henan Normal University, Xinxiang Henan

2Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang Henan

Received: May 4th, 2016; accepted: May 23rd, 2016; published: May 26th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

Connectivity and diagnosability are important parameters in measuring the fault diagnosis of multiprocessor systems. In 2012, Peng et al. proposed a new measure for fault diagnosis of the system, which is called g-good-neighbor diagnosability that restrains every fault-free node containing at least g fault-free neighbors. The n-dimensional crossed cube is an important variant of the hypercube. In this paper, we prove that the 1-good-neighbor connectivity of crossed cube is 2n − 2 for n ≥ 4, and the 1-good-neighbor diagnosability of crossed cube is 2n − 1 under the PMC model for n ≥ 4 and the MM* model for n ≥ 5.

Keywords:Interconnection Network, Graph, Diagnosability, Crossed Cube

交叉立方体的1好邻连通度和诊断度

马晓蕾1,王世英1,2*,王贞化1

1河南师范大学,数学与信息科学学院,河南 新乡

2河南师范大学,河南省大数据统计分析与优化控制工程实验室,河南 新乡

收稿日期:2016年5月4日;录用日期:2016年5月23日;发布日期:2016年5月26日

摘 要

连通度和诊断度是度量多处理器系统故障诊断能力的重要参数。2012年,Peng等提出了一个新的系统故障诊断方法,称为g好邻诊断度,它限制每个非故障顶点至少有g个非故障邻点。n维交叉立方体是超立方体的一个重要变形。本文证明了交叉立方体的1好邻连通度是2n – 2 (n ≥ 4),又证明了交叉立方体在PMC模型下的1好邻诊断度是2n – 1 (n ≥ 4)和在MM*模型下的1好邻诊断度是2n – 1 (n ≥ 5)。

关键词 :互连网络,图,诊断度,交叉立方体

1. 引言

连通度和诊断度是度量多处理器系统故障诊断能力的重要参数。它们是互联网络中热门的研究课题之一。通常我们把互联网络用图来表示,其中顶点表示处理器,边表示两处理器之间的链路。为了保证计算机系统的可靠性,系统中的故障处理器应该被诊断出来并被非故障处理器替换。Preparata等首次提出了系统级故障诊断模型,称为PMC模型 [1] 。它是通过两个相邻的处理器之间相互测试来完成系统的诊断。Maeng和Malek提出了MM*模型 [2] 。在这种模型下,一个顶点分别给它相邻的两个顶点发出相同的任务,然后比较它们反馈的结果。传统的诊断度允许点的邻点全为故障点,但是在大型多处理器系统中这种故障出现的概率极小。因此Lai等提出了网络的条件诊断度 [3] ,它限制系统中任意一个处理器至少与一个非故障处理器相邻。2012年,Peng等通过在系统中限制每个非故障顶点都至少有g个非故障邻点,提出了网络的g好邻诊断度 [4] ,并且证明了超立方体在PMC模型下的g好邻诊断度是

。原军等在文 [5] 中证明了k元n立方体在PMC模型和MM*模型下的g好邻诊断度是。在文 [6] 中,王牟江山等证明了网络的1好邻诊断度不超过条件诊断度。因此,研究网络的1好邻诊断度也是很有意义的。本文首先证明了交叉立方体的1好邻连通度是。然后,我们又证明了交叉立方体在PMC模型下的1好邻诊断度是和在MM*模型下的1好邻诊断度是

2. 预备知识

是一个无向简单图,其中分别表示图G的顶点集和边集。对于任意的非空顶点子集,以为顶点集,以两端点均在中的边的全体为边集所组成的子图,称为在G中的导出子图,记作是顶点v在G中关联的边的数目,表示v在G中的度。表示G的顶点的最小度。对于任意顶点,在G中与v相邻的所有顶点组成的集合称为v的邻集,记作。若S是G的非空顶点子集,则S的邻集为。图G的每一个顶点都恰好与边集M中的一条边关联,称M是G的一个完美匹配。对于任意的,若中至少有g个邻点,则称F为G的g好邻故障集。如果不连通且的每个连通分支的最小度为g,则称F是一个g好邻割。G的所有g好邻割中的最小顶点数称为G的g好邻连通度,记作。文中其它未定义而直接使用的符号和术语参见文献 [7] 。

在PMC模型中,相邻的处理器之间可以相互测试。图G中,对于任意的表示从u到v的测试,其中u是测试者而v是被测试者。若u是非故障点而v是故障点(或非故障点),则测试结果是1(或0)。若u是故障点,则测试结果不可靠。一个系统G的一个测试任务是每对相邻顶点测试结果的集合。它可以用一个有向图表示,其中表示。所有测试结果的集合称为系统G的症候,记作。一个症候是一个函数。对两个不同的顶点子集,若,则称F1和F2是可区分的,记(F1, F2)为可区分的点对;否则,称F1和F2是不可区分的,记(F1, F2)为不可区分的点对。

在MM*模型下,与一个结点w相邻的两个结点u,v被分配一个相同的任务,再把测试结果返回给结点w,w再对这两个结点返回的结果进行比较。用来表示w比较u,v输出的比较结果,如果这两个结果是相同的,则;否则,。全部的测试结果叫做这个系统的比较症候,记作。假定三个结点都是非故障的,则测试结果为0;若w是非故障的,但u,v至少有一个是故障的,则比较结果为1;若w是故障的,则测试结果无论是0或1都是不可靠的。

定义2.1 [5] :在一个系统中,对于任意两个不同的g好邻故障集F1,F2,其中,若F1,F2是可区分的,则G是g好邻条件t-可诊断的。

定义2.2 [5] :使得G是g好邻条件t-可诊断的最大值t称为G的g好邻诊断度,记作

n维交叉立方体CQn [8] 有超立方体的正则性和相同的连通度。它是一个有2n个顶点和条边的n正则图。它包含长度为的圈,直径为大约是超立方体的一半。n维交叉立方体CQn的顶点u用长为n的二进制字符串表示,如,其中表示最高位,u0表示最低位。

定义2.3:两个二元序列称为相关对,记为,当且仅当

n维交叉立方体CQn可以用递归定义表示:

定义2.4:1维交叉立方体CQ1是顶点标号分别为0和1的完全图(如图1)。n维交叉立方体包含两个维子交叉立方体,其中各顶点的最高位分别是0和1。设,则u和v在CQn中相邻当且仅当

(1) 如果n是偶数,

(2) 当时,

我们称之间的边为交叉边。显然,这些交叉边的集合是CQn的一个完美匹配。

定义2.5:交叉立方体CQn的顶点集为,两个顶点相邻当且仅当满足以下条件之一。

条件1:存在一个整数d,使得

(1)

(2)

(3) 如果d是偶数,

(4) 当时,

条件2:

(1)

Figure 1. The 4-dimensional crossed cube CQ4

图1. 4维交叉立方体CQ4

(2) 如果n是偶数,

(3) 当时,

3. CQn 的1好邻连通度

引理3.1:交叉立方体CQn中任意两个顶点至多有两个公共邻点。

证明:因为CQn没有三圈,所以任意两个相邻的顶点没有公共邻点。设u,v是CQn中任意两个不相邻的顶点。用归纳法证明u和v至多有两个公共邻点。当时,CQ2是一个四圈,结论成立。假设时结论都成立,现证时结论也成立。将CQn沿最高位分解成两个维的子图,则之间存在完美匹配(如图1)。若u和v在同一个维的子图中,不失一般性,假设。由归纳假设u和v在中至多有两个公共邻点。因为之间存在完美匹配,所以u和v在中没有公共邻点。若u和v分别在两个维的子图中,不失一般性,假设。因为之间存在完美匹配,所以u与v在中至多有一个公共邻点。因此,u和v在CQn中至多有两个公共邻点。由u和v的任意性,CQn中任意两个不相邻的顶点至多有两个公共邻点。

引理3.2 [8] :交叉立方体CQn的连通度

引理3.3:当时,对任意的,设,则

证明:要证,只需证明不含孤立点。当时结论显然成立。用反证法证明时结论也成立。假设w是中的孤立点,则。因为,所以。根据引理3.1,可得。于是,。因为CQn是n正则图,所以。因此,w至少存在一个邻点不在F中。这与矛盾。所以不含孤立点。故

引理3.4:交叉立方体CQn的1好邻连通度

证明:设A和F的定义与引理3.3相同,则F是一个割。因为CQn不包含三圈,所以。根据引理3.3,可得。又因为。因此,F是一个1好邻割。故

引理3.5:交叉立方体CQn的1好邻连通度

证明:设F是CQn的任意的一个1好邻割。根据1好邻连通度的定义,要证,只需证明。用反证法证明。假设。因为F是1好邻割,所以没有孤立点且不连通。将CQn沿最高位分解成两个维的子图。则同构于。设,则。因为,所以。根据引理3.2,可得。因此,连通。设是连通的。由于和在间的交叉边是CQn的一个完美匹配,是连通的,即是连通的。这个矛盾到是不连通的。因此,设是不连通的。由引理3.2,。设的分支。设和设。由于F是1好邻割,所以在中存在一点v使得。即,是连通的。设和设。设在中存在一点,它相邻到a和b中至少一个。则是连通的。设在中不存在一点,它相邻到a和b两个。由于在间的交叉边是CQn的一个完美匹配,所以。由于,所以。由于,所以。注意到。由于,所以在中存在一点,它相邻到a,b邻集中一点,即是连通的。因此,是连通的,即,是连通的。这个矛盾到是不连通的。

结合引理3.4和引理3.5可得以下定理:

定理3.6:交叉立方体CQn的1好邻连通度

4. CQn在PMC模型下的1好邻诊断度

定理4.1 [4] :一个系统在PMC模型下是g好邻t-可诊断的当且对于V中任意两个不同的顶点数至多为t的g好邻故障集F1,F2,存在,使得(如图2)。

引理4.2:最小度为1的图至少有两个顶点。

引理4.3:交叉立方体CQn在PMC模型下的1好邻诊断度

证明:对任意的,设。因为CQn不包含三圈,所以。根据引理3.3,可得。又因为,所以F1,F2是CQn的两个1好邻故障集。因为,所以在之间没有边。由定理4.1,CQn不是1好邻2n-可诊断的。因此,

引理4.4:交叉立方体CQn在PMC模型下的1好邻诊断度

证明:根据1好邻诊断度的定义,需要证明CQn是1好邻-可诊断的。根据定理4.1,等价于证明任意两个不同的1好邻故障集F1,F2,其中,存在,使得。反证法。假设存在两个不同的1好邻故障集F1,F2,其中,对任意的都有。不失一般性,假设。分以下两种情况进行讨论:

情形1:

。当时,上述不等式矛盾。

情形2:

Figure 2. A distinguishable pair (F1, F2) under the PMC model

图2. 在PMC模型下可区分对(F1, F2)

根据假设之间没有边和F1是1好邻条件故障集,可得。同理,若。因此,也是1好邻条件故障集。又因为之间没有边,所以不连通。故是CQn的1好邻割。根据定理3.6,可得。根据引理4.2,可得。因此,。这与相矛盾。

由于以上两种情况都产生矛盾,故CQn是1好邻-可诊断的。于是,

结合引理4.3和引理4.4,可得以下定理:

定理4.5:交叉立方体在PMC模型下的1好邻诊断度

5. CQn在MM*模型下的1好邻诊断度

定理5.1 [4] :一个系统在MM*模型下是g好邻t-可诊断的当且仅当对V中任意两个不同的顶点数至多为t的g好邻故障集F1,F2,满足以下其中一个条件(如图3):

(1) 存在满足

(2) 存在满足

(3) 存在满足

引理5.2:交叉立方体CQn在MM*模型下的1好邻诊断度

证明:对任意的,设。因为CQn不包含三圈,所以。由引理3.3,可得。因此,F1,F2是CQn的两个1好邻故障集且。因为且A与之间没有边,所以F1,F2不满足定理5.1中的(1)~(3)。因此,CQn不是1好邻条件2n可诊断的。故

引理5.3:交叉立方体CQn在MM*模型下的1好邻诊断度

证明:根据1好邻诊断度的定义,需要证明CQn是1好邻-可诊断的。反证法。根据定理5.1,假设中存在两个不同的顶点数至多为的故障集不满足定理5.1中的(1)~(3)。不失一般性,假设。分以下两种情况进行讨论:

情形1:

证明同引理4.4的情形1。

情形2:

断言1:没有孤立点。

反证法。假设至少有一个孤立点w。因为F1是一个1好邻故障集,所以至少存在一点使得。因为F1,F2不满足定理5.1中的(3),所以至多存在一点使得。因此仅有一点使得。同理,当时,仅有一点使

Figure 3. A distinguishable pair (F1, F2) under the MM* model

图3. 在MM*模型下可区分对(F1, F2)

。设W是中的孤立点集,。因此,当时,对任意的,存在个邻点在中。由于,故。因为,所以。假设,有。当时,上式矛盾。所以,。因为F1,F2不满足定理5.1中的(1)且的任意一点在H中不是孤立点,所以之间不存在边相连。因此,是CQn的点割且,即是CQn的一个1好邻割。根据定理3.6,。 因为都非空,所以。于是,设。故对于任意的满足。根据引理3.1,v1与v2至多有两个公共邻点。因此,至多有两个孤立点。

假设中恰有一个孤立点v,则。因为不包含三圈,所以。根据引理3.1,v1与v2至多有两个公共邻点,所以。因此,。于是,。这与矛盾。

假设中恰有两个孤立点v和。因为CQn不包含三圈,所以。又因为任意两点至多有两个公共邻点,所以

中任意两个集合在中都没有公共点。因此于是,,这与矛盾。

,则。因为F2是一个1好邻故障集,所以没有孤立点。断言1证明完毕。

。根据断言1,u在中至少有一个邻点。因为F1,F2不满足定理5.1,根据定理5.1(1),所以对于任意一对相邻的点,不存在使得

Figure 4. CQ4 is not 1-good-neighbor 7-diagnosable

图4. CQ4不是1好邻7-可诊断的

。因此,u在中没有邻点。由u的任意性,中间没有边。因为F1是一个1好邻故障集且,所以。根据引理4.5,。因为F1和F2都是1好邻故障集且之间没有边,所以是CQn的一个1好邻割。根据定理3.6,。因此,。这与矛盾。于是,CQn是一个1好邻-可诊断的。故

结合引理5.2和引理5.3可得以下定理:

定理5.4:交叉立方体CQn在MM*模型下的1好邻诊断度

下面的例子说明当时,CQ4在MM*模型下不是1好邻7-可诊断的。设。容易验证F1和F2不满足定理5.1中的(1)~(3) (如图4),所以CQ4在MM*模型下不是1好邻7-可诊断的。

6. 结束语

连通度和诊断度是互联网络容错的重要指标,本文研究了交叉立方体的1好邻连通度和1好邻诊断度。它是交叉立方体传统诊断度的两倍,意味着系统能够诊断出更多的故障结点。此外,本文还证明了在MM*模型下CQ4不是1好邻7-可诊断的。这为今后进一步研究交叉立方体网络的g好邻连通度、诊断度和相关诊断算法提供了理论基础。

基金项目

国家自然科学基金资助项目(61370001),教育部博士点基金(博导类)资助项目(20111401110005)。

文章引用

马晓蕾,王世英,王贞化. 交叉立方体的1好邻连通度和诊断度
The 1-Good-Neighbor Connectivity and Diagnosability of Crossed Cubes[J]. 应用数学进展, 2016, 05(02): 282-290. http://dx.doi.org/10.12677/AAM.2016.52036

参考文献 (References)

  1. 1. Preparata, F., Metze, G. and Chien, R.T. (1968) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, 12, 848-854.

  2. 2. Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, 173-175.

  3. 3. Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Di-agnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. http://dx.doi.org/10.1109/TC.2005.19

  4. 4. Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under the PMC Model. Applied Mathematics Computation, 218, 10406-10412. http://dx.doi.org/10.1016/j.amc.2012.03.092

  5. 5. Yuan, J., Liu, A.X., Ma, X., Liu, X.L., Qin, X. and Zhang, J.F. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177. http://dx.doi.org/10.1109/TPDS.2014.2318305

  6. 6. Wang, M.J.S., Guo, Y.B. and Wang, S.Y. (2015) The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics.

  7. 7. Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.

  8. 8. Efe, K. (1992) The Crossed Cube Architecture for Parallel Computation. IEEE Transactions on Parallel and Distributed Systems, 3, 513-524. http://dx.doi.org/10.1109/71.159036

期刊菜单