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. 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. 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. 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. 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. 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. 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. Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.
- 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