互连网络的连通性和诊断度

(山西师范大学 数学与计算机学院, 山西 临汾 041004)

在科学与工程计算领域，海量数据的处理和复杂问题的解决对计算机的计算能力的要求日益提高，并且这些需求的增长速度已经远远超出了微处理机的发展速度.在此背景下, 并行计算机系统应运而生并得到快速发展.并行计算机系统常以某个具有优良性质的互连网络为底层拓扑结构进行构建.互连网络的性能对整个系统的硬件消耗、通信性能、路由算法的可行性都起着重要的甚至是决定性的作用，以至于并行计算机系统的设计理念已经由以CPU为主逐步让位于以互连网络为主.并行计算机系统中元器件之间的连接模式称为该系统的互连网络，简称网络.从拓扑上讲，一个系统的互连网络逻辑上指定了该系统中所有元器件之间的连接方式.互连网络可以看成一个图，图的顶点表示系统中的元器件或处理器， 图的边表示元件之间的物理连线.因此，网络拓扑的性能可以通过图的性质和参数来度量.网络出现故障是不可避免的.由此，互连网络的连通性和故障诊断是一个重要的研究课题.

1 概念和记号

设G=(V,E)是无向简单图. 对于图论术语和符号未在此定义的，遵循文献[1].为方便起见，子集F⊆V称为G的故障集.

定义1设G=(V,E)是一个连通图. 对于一个故障集F⊆V， 如果|N(v)∩(VF)|≥g对于VF的每一个点v，则故障集F称为一个g好邻故障集. 对于G的一个g好邻故障集F，如果G-F是不连通的，则称F为G的一个g好邻割. 如果G有一个g好邻割，则称G为g好邻连通的.对于一个g好邻连通图G，G的g好邻连通度是G的最小g好邻割的基数，用κ(g)(G)表示.

由文献[2]，笔者得出定理1.

对于多重处理器系统，一些处理器可能在系统中失效和处理器故障的识别在可靠计算中起重要作用.识别的过程称为系统诊断.几种诊断模型被提出来识别故障处理器.一种方法是Preparata等[3]提出的Preparata、Metze和Chien(PMC)诊断模型.系统的诊断是通过两个相互连接的处理器来实现的.诊断那个系统G，G中的两个相邻节点能够执行相互测试.对于V(G)中两个相邻的节点u和v，执行u测试v由有序对(u,v)表示.如果u测试v评估为故障(分别为无故障)，则测试(u,v)的结果为1(分别为0).在PMC模型中，通常假设测试结果是可靠的(分别是不可靠的)如果节点u无故障(分别是故障的).系统G的测试作业T是一个集合对每对相邻顶点的测试.建模为有向测试图T=(V(G),L)，其中(u,v)∈L中暗示u和v在G中相邻.测试作业的所有测试结果的集合T被称为诊断子. 形式上，诊断子是一个函数σ:L{0,1}.那个系统中的所有故障处理器的集合称为故障集.这可以是V(G)的任何子集.对于给定的诊断子σ，顶点子集F⊆V(G)被说与σ一致，如果诊断子σ可根据下面的情况产生，对于(u,v)∈L使得u∈VF，σ(u,v)=1当且仅当v∈F.这意味着F是一个可能的故障处理器集合.由于故障处理器产生的测试结果是不可靠的，给定的一组F的故障顶点可能会产生很多不同的诊断子.另一方面，不同故障集可能会产生相同的诊断子.让σ(F)表示与F相一致的的所有诊断子的集合.在PMC模型中，V(G)中的两个不同的集合F1和F2被说是可区分的如果σ(F1)∩σ(F2)=∅.否则，F1和F2被说是不可区分的.另外，我们说 (F1,F2)是可区分对如果σ(F1)∩σ(F2)=∅； 否则，(F1,F2)是不可区分对.

另一个主要方法，即比较诊断模型(MM模型)，由Maeng等[4]提出.在MM模型中，处理器将相同的任务发送给一对不同的邻居，然后比较它们的响应以诊断系统G=(V(G),E(G)).G的比较方案被建模为多重图，由M=(V(G),L)表示，其中L是标记边集.一条标号边(u,v)w∈L中表示比较，其中，两个顶点u和v由顶点w比较，这意味着uw,vw∈E(G).M=(V(G),L)中所有比较结果的集合称为诊断子，用σ表示.如果比较(u,v)w不同意，那么σ(u,v)w=1.否则，σ(u,v)w=0.因此，诊断子是从L到0,1的函数. Anton等[5]提出MM*模型.它是MM模型的一个特殊情况.在MM*中，每个节点必须测试其相邻节点的所有对，如果uw,vw∈E(G)，则(u,v)w∈L.对于给定的诊断子σ，一个顶点的子集F⊆V(G)被认为与σ一致如果诊断子σ可以从那种情况中产生， 对于任意 (u,v)w∈L使得w∈VF,σ(u,v)w=1当且仅当u和v至少有一个是在F中.让σ(F)表示与F一致的所有诊断子的集合.设F1和F2是V(G)中的两个不同的集合.如果σ(F1)∩σ(F2)=∅，那么，(F1,F2)是可区分对；否则，(F1,F2)是不可区分对.

文献[6]笔者得出定理2.

定义4一个系统G=(V,E)在顶点x处是局部t可诊断的, 如果诊断子σF是由包含顶点x的故障集F产生的且|F|≤t, 每一个与σF一致的故障集F′都必须包含顶点x且|F′|≤t.

定义5在一个系统G=(V,E)中顶点x局部诊断度tl(x)是G在x处局部t可诊断的最大t值.

定义6x表示图G=(V,E)中的一个顶点. 如果x的局部诊断度等于它的度， 即tl(x)=dG(x), 那么称x具有强局部诊断性质.

定义7设G=(V,E)是一个图. 如果G中每个顶点的局部诊断度等于该顶点在图G中的度， 即tl(x)=dG(x)， 那么称G具有强局部诊断性质.

2 连通性和诊断度

作为一个著名的互连网络的拓扑结构，n维超立方体Qn有很多好性质，如连通性、对称性、网络的高容错性等.

一个n维超立方体Qn(n≥1)是一个图.其顶点集是0和1的所有n元组的集合；如果两个顶点准确地不同在一个坐标，那么它们是相邻的.

2012年, Peng等[7]提出了一种多处理器系统故障诊断方法，即g好邻诊断度，它要求每个无故障节点至少有g个无故障邻点.由文献[7]得出定理3.

定理3[7]设Qn是一个超立方体和0≤g≤n-3，则tg(Qn)=(n-g+1)2g-1在PMC模型下.

2016年笔者得出定理4.

定理4[8]设Qn是一个超立方体，n≥5和0≤g≤n-3，则tg(Qn)=(n-g+1)2g-1在MM*模型下.

2015年，笔者得出定理5.

2016年，笔者得出定理6.

定理6[13]

定理3～6完全解决了k元n立方的g好邻诊断度的问题.

对于一个整数n≥1，长度为n的二进制字符串表示为u1u2…un，其中,ui∈{0,1}对于任意一个整数i∈{1,2,…,n}.n维局部扭立方，表示为LTQn，是2n个顶点和n2n-1边的n正则图.它能递归地定义如下：

对于n≥2，一个n维局部扭立方LTQn按递归方式定义如下：

①LTQ2是由分别标记为00、01、10和11的四个节点组成的图，连接由四条边 {00,01}、{01,11}、{11,10}和{10,00}.

②对于n≥3，LTQn是由两个不相交的LTQn-1拷贝构成，按照以下步骤：0LTQn-1表示给LTQn-1的一个拷贝的每个节点的标号前加0获得的图.1LTQn-1表示给LTQn-1的一个拷贝的每个节点的标号前加1获得的图.连接0LTQn-1的每个节点 0u2u3…un到1LTQn-1的节点1(u2+un)u3…un，其中“+”表示模2加法.

2017年，笔者得出定理7.

定理7[14]设n≥3和0≤g≤n-3，则n维局部扭立方LTQn的g好邻诊断度tg(LTQn)=2g(n-g+1)-1在PMC模型和MM*模型下.

由文献[15]得出定理8.

2017年，笔者得出定理9.

定理9[16]

2019年，笔者得出定理10.

定理10[17]

图G1和G2的Cartesian积是一个图G1⊗G2.它的顶点集是{(x,y):x∈V(G1),y∈V(G2)}.在G1⊗G2中， 顶点(x1,y1)和(x2,y2)是相邻的当且仅当x1=x2和y1y2∈E(G2) 或者x1x2∈E(G1)和y1=y2.

三维超Petersen图HP3是一个Petersen图.对于n≥4，n维超Petersen图HPn是HPn=HPn-1⊗K2.

2019年，笔者得出定理11.

定理11[18]

设R={(00,00)、(10,10)、(01,11)、(11,01)}. 两位二进制字符串u=u1u0和v=v1v0是对相关的，表示为u～v，当且仅当 (u,v)∈R.

一个n维交叉立方体立方CQn， 它的顶点集是{vn-1vn-2…v0:0≤i≤n-1,vi∈{0,1}}.顶点u=un-1un-2…u0和v=vn-1vn-2…v0是相邻的当且仅当满足以下条件之一.

①存在一个整数l(1≤l≤n-1)使得

1)un-1un-2…ul=vn-1vn-2…vl；

2)ul-1≠vl-1；

3) 如果l是偶数，则ul-2=vl-2；

②

1)un-1=vn-1；

2) 如果l是偶数，则un-2=vn-2；

2018年，笔者得出定理12.

定理12[19]

2019年，笔者得出定理13.

定理13[20]设n≥7，则n维交叉立方CQn是(4n-9)两超3限制连通的.

设G是一个有限群，S是G不含单位元的生成集.Cayley有向图Cay(S,G) 定义如下: 它的顶点集是G，孤集是{(g,gs):g∈G,s∈S}.若对任意的s∈S，有s-1∈S，则称这个Cayley图为无向Cayley图.本文所说的Cayley图均为无向Cayley图，且假定S的元是对换，则S生成的置换群是对称群Sn的子群，它的单位元记为(1).它是顶点传递的.由于对换可用图直观的表示出来，所以引入下面的概念.

考虑一个n≥3 阶连通简单图H，它的顶点集为{1,2,…,n}，它的每条边可视为Sn中的一个对换，这样H的边集E(H)，就对应了Sn中的一个对换集S.在这个意义下，把H称为对换简单图.Cayley图Cay(S,)称为H对应的Cayley图. 当对换简单图是树时,称为对换树. 当对换简单图是路时, 它对应的Cayley图称为泡型图 (Bubble sort graph).当对换简单图是星时, 它对应的Cayley图称为星图 (Star graph).由于n阶对换树对应的Cayley图都是Sn上的Cayley图，故任意一个n阶对换简单图对应的Cayley图也是Sn上的Cayley图.

对换树对应Cayley图，表示为CΓn.

2017年，笔者得出定理14.

定理14[21]

(1)设n≥3，则CΓn的自然连通度是κ(1)(CΓn)=2n-4.

(2)设n≥4，则CΓn的自然诊断度是t1(CΓn)=2n-3在PMC模型下.

(3)设n≥4，则，除去泡型图B4，t1(CΓn)=2n-3在MM*模型下.

(4)B4的自然诊断度是t1(B4)=4在MM*模型下.

2016年，笔者得出定理15.

定理15[22]设n≥4，则CΓn的2好邻诊断度是t2(CΓn)=g(n-2)-1在PMC模型和MM*下.其中g是CΓn的围长.

完全简单图Kn对应的Cayley图，称为一个巢图，用CKn表示.

2018年，笔者得出定理16.

定理16[23]

(1)设n≥4，则巢图CKn的自然连通度是κ(1)(CKn)=n2-n-2.

(2)设n≥4，则CKn的自然诊断度是t1(CKn)=n2-n-1在PMC模型下.

(3)设n≥5，则CKn的自然诊断度是t1(CKn)=n2-n-1在MM*模型下.

2017年，笔者得出定理17.

定理17[24]

2017年，笔者得出定理18.

定理18[25]

(1)设n≥4，则n维泡型星图BSn的自然诊断度是t1(BSn)=4n-7在PMC模型下.

(2)设n≥5，则BSn的自然诊断度是t1(BSn)=4n-7在MM*模型下.

2017年，笔者得出定理19.

定理19[26]

(1)设n≥5，则n维泡型星图BSn的2好邻连通度是κ(2)(BSn)=8n-22.

(2)κ(2)(BS4)=8.

(3)设n≥5，则t2(BSn)=8n-19在PMC模型和MM*模型下.

2016年，笔者得出定理20.

定理20[27]

2019年，笔者得出定理21.

定理21[28]

(1)设n≥4，则n维泡型图Bn的自然诊断度是t1(Bn)=2n-3在PMC模型下.

(2)设n≥5，则Bn的自然诊断度是t1(Bn)=2n-3在MM*模型下.

(3)设n≥4，则Bn的2好邻诊断度是t2(Bn)=4n-9在PMC模型和MM*模型下.

(4)设n≥7，则Bn的3好邻诊断度是t3(Bn)=8n-25在PMC模型和MM*模型下.

2017年，笔者得出定理22.

定理22[29]设n≥4和0≤g≤n-2，则星图Sn的g好邻诊断度是tg(Sn)=(g+1)!(n-g)-1在PMC模型和MM*模型下.

交错群An是对称群Sn的一个子群.它由整个的偶置换组成.我们知道{(12i),(1i2):i=3,4,…,n}是An的一个生成集.n维交错群图AGn， 它的点集V(AGn)=An； 它的两点u,v相邻当且仅当u=v(12i)或者u=v(1i2)，3≤i≤n.

2018年，笔者得出定理23.

定理23[30]

(1)设n≥5，则n维交错群图AGn的然诊断度是t1(AGn)=4n-10 在PMC模型和MM*模型下.

(2)t1(AG4)=5在PMC模型下.

(3)t1(AG4)=4在MM*模型下.

2018年，笔者得出定理24.

2018年，笔者得出定理25.

定理25[32]设n≥5，则n维交错群图AGn的2好邻诊断度是t2(AGn)=6n-16在PMC模型和MM*模型下.

2019年，笔者得出定理26.

由于篇幅的限制没有列出来的，参见文献[34-50].

2018年，笔者得出定理27.

定理27[51]n维交错群图AGn有强局部诊断性和保持这个强局部诊断性即使存在(2n-7)遗失边在它在MM*模型下.

2019年，笔者得出定理28～32.

定理28[52]n维泡型星图BSn(n≥5)有强局部诊断性和保持这个强局部诊断性即使存在(2n-5)遗失边在它在MM*模型下.这个结果是最优的.

定理29[53]排列图An,k有强局部诊断性和保持这个强局部诊断性即使存在((k-1)(n-k)-1)遗失边在它在MM*模型下.这个结果是最优的.

定理30[54]交换超立方体EH(s,t)) (2≤s≤t和s=1,t=2)有强局部诊断性在MM*模型下.