加强超立方体中条件容错圈

加强超立方体中条件容错圈 Cycles in Conditional Faulty Enhanced Hypercube Networks first-author 张艳娟，女，讲师，主要从事图论方面的研究. E-mail:pyyj134@163.com 张艳娟，女，讲师，主要从事图论方面的研究. E-mail: pyyj134@163.com pyyj134@163.com 三峡大学 理学院，湖北 宜昌 443002 三峡大学 理学院，湖北 宜昌 443002 College of Science, China Three Gorges University, Yichang 443002, Hubei, China College of Science, China Three Gorges University, Yichang 443002, Hubei, China 研究了条件容错模型下 n 维加强超立方体 Q n, k 的结构性质，设 F v 表示故障点的集合， F e 表示错误边的集合，且| F v |= f v ，| F e |= f e .若 Q n, k ( n ≥4, 1≤ k ≤ n -1)满足约束条件：1) f v + f e ≤2 n -4和2) Q n, k 中每个点至少关联两条无故障边时， Q n, k - F e - F v 中含一个长度至少为2 n -2 f v 的圈.同时证明了当 Q n, k ( n ≥5, 1≤ k ≤ n -1)满足约束条件:1) f e + f v ≤2 n -3， f e ≥ k 和2)每个节点至少关联两条无故障边时， Q n, k 中能嵌入一条长为2 n -2 f v 的容错圈. In this article, we investigate the conditional fault-tolerant properties of the enhanced hypercube. Let F v and F e be the set of faulty vertices and faulty edges respectively in the n -dimensional enhanced hypercube Q n, k , and | F v |= f v , | F e |= f e . When f e + f v ≤2 n -4, and each vertex is incident with at least two fault-free edges, we showed that there exists a fault-free cycle, which is of length at least 2 n -2 f v in Q n, k ( n ≥4, 1≤ k ≤ n -1). Furthermore, when f e + f v ≤2 n -3, f e ≥ k , and each vertex is incident with at least two fault-free edges, we showed there exists a fault-free cycle, which is of length at least 2 n -2 f v in Q n, k ( n ≥5). 超立方体 加强超立方体 容错性 圈嵌入 hypercube enhanced hypercube fault-tolerance cycles embedding 引言 1 超立方体是现今最著名、最通用, 也是最有效的互连网络的拓扑结构.在高性能计算中尤其在大型工业计算中有着非常重要的作用.因其结构正则、对称以及相对小的传输延迟，许多好的算法易于嵌入等优良性质而受到广泛关注 [ 1 1 ] .但是超立方体也有它固有的缺点，比如较大的直径，因此设计和维护高维的超立方体网络的复杂度比较高.为了获得比超立方体更优良的性质, 人们提出了超立方体的一系列变型结构, 如广义超立方体, 折叠超立方体, 纽立方体, 增广超立方体以及加强超立方体等等. 在现实网络中，处理器或者处理器连线发生故障是不可避免的，这就要求网络具有一定的容错性.也就是说当网络中一定数目的节点或者连线坏掉时，网络仍然可以有效的工作.在标准容错情况下，故障边的分布不受点的限制.超立方体网络及其变形网络在标准容错条件下已经有许多结论，关于超立方体及其变形结构性质以及点边容错性质，最近文献[ 2 2 ]得到了许多好的结果.例如，文献[ 2 2 ]证明了在超立方体 Q n ( n ≥5)中，当| F v |+| F e |≤2 n -4, | F e |≤ n -2时，则 Q n - F v - F e 包含一条长度至少为2 n -2| F v |的无故障圈. Du等 [ 3 3 ] 证明了当| F v |=2 n -3时，则 Q n ( n ≥5)中能嵌入一条长度至少为2 n -2| F v |的无故障圈.由于加强超立方体 Q n, k 1≤ k ≤ n -1是在 n -维超立方体 Q n 中添加2 n -1 条的边得到的新结构 [ 4 4 ] ，因此超立方体是加强超立方体的一个支撑子图，那么上述研究结论在加强超立方体 Q n, k 中均成立.Liu在文献[ 5 5 ]中研究加强超立方体存在大量故障点和故障边时圈的一些性质，即当| F e |≤ n -1且| F v |+| F e |≤2 n -4时，则 Q n, k ( n ≥4)中能找到一条长为2 n -2| F v |的容错圈. Liu在文献[ 6 6 ]中研究了加强超立方体 Q n, k ( n ≥3, 1≤ k ≤ n -1)的泛圈性问题，证明了当 n 和 k 奇偶性不同时， Q n, k 中每一条边均在长为 n - k +2到2 n -1的奇圈上.Zhang [ 7 7 ] 证明了当 n 和 k 奇偶性相同时，若| F v |=2， Q n, k 中含有长度从4到2 n -4的偶圈，而且含有长度从 n - k +2到2 n -3的所有奇圈.同时文献[ 7 7 ]还证明了当| F v |≤ n -2时，若 n 和 k 奇偶性相同， Q n, k 中存在长度为2 n -2| F v |的偶圈；若 n 和 k 奇偶性不同， Q n, k 中存在长度为2 n -2| F v |的偶圈同时有长度为2 n -2| F v |+1的奇圈. Fan [ 8 8 ] 证明了在折叠超立方体 F Q n ( n ≥4)中，当| F v |=2 n -3，则 F Q n - F v 中存在一个长度至少为2 n -2 f v 的圈. 然而，由于网络的不同部分可能有不同的可靠性，我们就可以假设在一些部分的某些子集中，这些部分并不是同时坏掉的.Fu [ 9 9 ] 提出了条件容错模型，即在网络模型中，所有的点都至少与两条非故障边相连.在这种模型下，也得到了一些结论.例如, Liu [ 10 10 ] 证明了在约束条件：1)| F e |≤2 n -3和2)每个节点至少关联两条无故障边时， Q n, k 中能找到一条长为2 n 的容错圈. Liu [ 11 11 ] 进一步研究了条件容错模型下若加强超立方体 Q n, k 满足约束条件：1)| F e |≤2 n -3和2)每个节点至少关联两条无故障边时，当 n 和 k 有相同的奇偶性，那么在 Q n, k 中存在偶长为4到2 n 的的容错圈；当 n 和 k 有不同的奇偶性，那么在 Q n, k 中存在奇长为 n - k +2到2 n -1的容错圈.Cao [ 12 12 ] 证明了在折叠超立方体 F Q n ( n ≥3)中，若| F e |+| F v |≤2 n -3，| F e |≥1且每个点至少关联两条非故障边，则在 F Q n - F v - F e 中存在一个长度至少为2 n -2 f v 的圈. 本文讨论了加强超立方体网络中存在大量故障点和故障边时圈的一些性质. 相关定义及引理 1 G =( V , E )表示一个图， V 为点集， E 为边集.图中的一条路定义为一个点和边交替出现的序列 P = v 0 e 1 v 1 e 2 v 2 … e i v i … e k v k (1≤ i ≤ k )，其中点 v 1 , v 2 , …, v k 互不相同.边 e i 的端点是 v i -1 和 v i ，称 P 是从 v 0 到 v k 的一条路或一条( v 0 , v k )路. k 称为路 P 的长度.在简单图中， P 可以由其顶点序列来表示 P [ v 0 , v k ]=〈 v 0 , v 1 , v 2 , …, v k 〉.若 v 0 = v k ，则称 P 为圈.圈上所包含的边的数目称为圈长，长为 k 的圈称为 k 圈，若 k 为偶数，则称为偶圈；若 k 为奇数，则称为奇圈.图 G 中连接点 u 和 v 之间的最短路的长度称为两点间的距离，记为 d G ( u , v ). 超立方体网络 Q n =( V ( Q n ), E ( Q n ))是 n 维立方体, 它的图论模型是一个简单的无向图， V ( Q n )={ x 1 x 2 … x n : x i ∈{0, 1}, i =1, 2, …, n }，超立方体中每个点 x 都可以用一个长为 n 的二元位串表示，即 x = x 1 x 2 … x n ， x i =0, 1.设 x = x 1 x 2 … x i -1 x i x i +1 … x n 和 y 为 V ( Q n )中两个点， x 和 y 之间有边相连当且仅当 y 满足： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458408&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458408&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458408&type=middle Q n 中两个顶点 x = x 1 x 2 … x n 和 y = y 1 y 2 … y n 之间的Hamming距离定义为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458442&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458442&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458442&type=middle ，表示两顶点的二元字符串中对应的不同分量的个数(或表示为 d H ( x , y )).用 d Q n ( x , y )表示 Q n 中两点 x 和 y 之间的距离，即连接 x 和 y 两点之间的最短路的长度.由上述定义可知，在 Q n 中有 d Q n ( x , y )= d H ( x , y ).称连接 u , u i 之间的边( u , u i )为 Q n 中的 i -维边，记 E i ={( u , u i )| h ( u , u i )=1}， i ∈{1, 2, …, n }，即 Q n 中所有 i -维边的集合.由此可知 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458445&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458445&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458445&type=middle . 超立方体 Q n 可以沿着第 i (1≤ i ≤ n )-维划分，得到两个子图.分别用 Q n -1 i 0 和 Q n -1 i 1 表示这两个子图.从划分的定义来看，可知这样得到的两个子图 Q n -1 i 0 和 Q n -1 i 1 是两个( n -1)-维超立方体子图.一个点 x = x 1 x 2 … x n 是 Q n -1 i 0 中的一个点当且仅当此点的第 i 位为 x i =0；类似的，点 x 是 Q n -1 i 1 中的一个点当且仅当此点的第 i 位为 x i =1. 下面给出加强超立方体 Q n, k 的定义. 定义1    n 维加强超立方体记为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458410&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458410&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458410&type=middle 其定义如下 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458415&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458415&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458415&type=middle 设 x = x 1 x 2 … x i -1 x i x i +1 … x n 和 y 为 V ( Q n, k )中两个点， x = x 1 x 2 … x i -1 x i x i +1 … x n 和 y 之间有边相连当且仅当 y 满足下列条件之一： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458419&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458419&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458419&type=middle 或者 2) http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458447&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458447&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458447&type=middle , 1≤ k ≤ n -1. 由定义1可知加强超立方体 Q n, k 是在超立方体 Q n 中添加2 n -1 条补边(the complementary edge)后得到的，即 V ( Q n, k )= V ( Q n )， E ( Q n, k )= E c ∪ E ( Q n )，其中补边集记为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458423&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458423&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458423&type=middle 边( u , u i )代表 Q n, k 中的超立方体的 i 维边，其定义为： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458427&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458427&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458427&type=middle 在本文中，记 F v 为故障点的集合， F e 为故障边的集合， F e c 为 Q n, k 中故障补边的集合， F e i 为 Q n, k 中超立方体的故障 i 维边的集合，且| F e |= f e ，| F v |= f v ， F e c = F e ∩ E c ， F e i = F e ∩ E i ，| F e c |= f e c ，| F e i |= f e i . 引理1 [ 5 5 ]   在加强超立方体 Q n, k 中，对任意的 j ∈{ k , k +1, …, n }∪{ c }，则有 Q n, k - E j 同构于 Q n . 引理2 [ 5 5 ]   在加强超立方体 Q n, k ( n ≥3, 1≤ k ≤ n -1)中，若 f e + f v ≤2 n -4， f e ≤ n -1，则 Q n, k - F e - F v 中存在一个长度至少为2 n -2 f v 的圈. 引理3 [ 13 13 ]   在超立方体 Q n ( n ≥3)中，若 f e + f v ≤2 n -4， f e ≤2 n -5且 Q n 中每个点至少关联两条无故障边，则在 Q n - F e - F v 中存在一个长度至少为2 n -2 f v 的圈. 引理4 [ 10 10 ]   在加强超立方体 Q n, k ( n ≥3, 1≤ k ≤ n -1)中，若 f e ≤2 n -3且 Q n, k 中每个点至少关联两条无故障边，则在 Q n, k - F e 中存在一个长度为2 n 的圈. 引理5 [ 6 6 ]   在加强超立方体 Q n, k ( n ≥3, 1≤ k ≤ n -1)中，若 n 和 k 奇偶性不同，则 Q n, k 中每一条边均在长为 n - k +2到2 n -1的奇圈上. 引理6 [ 8 8 ]   在折叠超立方体 F Q n ( n ≥4)中，若 f v =2 n -3，则在 F Q n - F v 中存在一个长度至少为2 n -2 f v 的圈. 引理7 [ 12 12 ]   在折叠超立方体 F Q n ( n ≥3)中，若 f e + f v ≤2 n -3， f e ≥1且 F Q n 中每个点至少关联两条无故障边，则在 F Q n - F v - F e 中存在一个长度至少为2 n -2 f v 的圈. 引理8 [ 14 14 ]   将加强超立方体 Q n, k 沿着第 i (1≤ i ≤ n )-维划分，可以得到两个子图.我们分别用 Q n -1, k i 0 ( Q n -1 i 0 )和 Q n -1, k i 1 ( Q n -1 i 1 )来表示这两个子图.当 i < k 时，得到的两个子图 Q n -1, k i 0 和 Q n -1, k i 1 是两个( n -1)-维的加强超立方体子图；当 i ≥ k 时，得到的两个子图 Q n -1 i 0 和 Q n -1 i 1 是两个( n -1)-维的超立方体子图.一个点 x = x 1 x 2 … x n 是 Q n -1, k i 0 ( Q n -1 i 0 )中的一个点当且仅当此点的第 i 位为 x i =0；类似的，此点 x 是 Q n -1, k i 1 ( Q n -1 i 1 )中的一个点当且仅当此点的第 i 位为 x i =1. 引理9 [ 5 5 ]   在加强超立方体 Q n, k ( n ≥3, 1≤ k ≤ n -1)中，设 u 和 v 为 Q n, k 中任意两点，若 f e + f v ≤ n -1，则当 d ( u , v )为奇数时， u 和 v 之间存在一条长为2 n -2 f v -1的( u , v )路；当 d ( u , v )为偶数时， u 和 v 之间存在一条长为2 n -2 f v -2的( u , v )路. 引理10 [ 15 15 ]   在超立方体 Q n ( n ≥2)中，设 u 和 v 为 Q n 中任意两点，则 u 和 v 之间存在一条长为 l 的( u , v )路，其中 d ( x , y )≤ l ≤2 n -1且 l 与 d ( x , y )奇偶性相同. 条件(2 n -4)-点边容错下加强超立方体中容错圈的嵌入 1 若一个点恰好关联了l条无故障边，则称这个点为l-无故障点. 引理11   若f e +f v ≤2n-4，则Q n, k 中至多存在一个2-无故障点. 证   用反证法证明.假设Q n, k 含两个2-无故障点u和v，接下来只需要考虑一种特殊情况即Q n, k 中故障元素达到最小值时，即当点u和v有公共邻点，可知Q n, k 中故障元素至少为(n-1)+(n-1)-1=2n-3，这与条件f e +f v ≤2n-4相矛盾，因此假设不成立，即Q n, k 中至多存在一个2-无故障点. 定理1   若Q n, k (n≥4, 1≤k≤n-1)满足约束条件：1) f e +f v ≤2n-4和2) Q n, k 中每个点至少关联两条无故障边，则Q n, k -F e -F v 中含一个长度至少为2 n -2f v 的圈. 证   记F v 为Q n, k 中故障点的集合，F e 为Q n, k 中故障边的集合，F e c 为Q n, k 中故障补边的集合，F e i 为Q n, k 中超立方体故障i-维边的集合，且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458431&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458431&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458431&type=middle 由引理2，当f e +f v ≤2n-4，f e ≤n-1时，Q n, k -F e -F v 含一个长度至少为2 n -2f v 的圈.因此，只需要考虑如下情况：f e +f v ≤2n-4，f e ≥n.由引理11可知Q n, k 中至多存在一个2-无故障点，故可以从Q n, k 中是否含2-无故障点来分两种情况讨论： 情形1   当加强超立方体Q n, k 中恰好存在一个2-无故障点.设u为Q n, k 中的2-无故障点，即点u关联恰好两条无故障边，Q n, k -{u}中每个点均为l-无故障点，其中l≥3(若l < 3，这与引理11相矛盾)，即Q n, k -{u}中每个点均关联至少3条无故障边.在此情况下，Q n, k 中与点u关联的故障边的总数是n-1，故一定存在一个j∈{k, k+1, …, n}∪{c}使得(u, u j )是一条故障边(假设这样的j不存在，则可设(u, u i )为与点u关联的故障边且i∈{1, 2, …, k-1}，那么此时可知与点u关联的故障边总数至多为k-1，而k-1≤n-2 < n-1，这与点u关联的故障边的总数是n-1相矛盾，故一定存在这样的j)，即f e j ≥1，j∈{k, k+1, …, n}∪{c}.由引理1知，Q n, k -E j 同构于Q n (j∈{k, k+1, …, n}∪{c}).因为f e +f v ≤2n-4且f e j ≥1，则有 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458435&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458435&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458435&type=middle 又因为Q n, k -{u}中每个点均为l-无故障点，其中l≥3，并且与点u关联的j维边为故障边，所以可知Q n, k -E j 中每个点至少关联两条无故障边，故Q n, k -E j 满足引理3的约束条件，于是由引理3知，在 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458449&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458449&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458449&type=middle 中存在一个长度至少为2 n -2f v 的圈，又因为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458451&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458451&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458451&type=middle ，即在Q n, k -F e -F v 中能找到一个长度至少为2 n -2f v 的圈. 情形2   当加强超立方体Q n, k 中不存在2-无故障点.也就是说，Q n, k 中每个点均为l-无故障点，其中l≥3，即Q n, k 中每个点均关联至少3条无故障边.分以下几种情况讨论： 情形2.1   F e k ∪F e k+1 ∪…∪F e n ∪F e c ≠∅，在这种情况下，选择一个j-维边(j∈{k, k+1, …, n}∪{c})使得f e j ≥1.由引理1知，Q n, k -E j 同构于Q n ，同情况1中的讨论方法一样，可知此时Q n, k -E j 满足引理3的约束条件，于是可知在Q n, k -F e -F v 中存在一个长度至少为2 n -2f v 的圈. 情形2.2   F e k ∪F e k+1 ∪…∪F e n ∪F e c =∅，即Q n, k 中的故障边全部在集合E 1 ∪E 2 ∪…∪E k-1 中，也就是说Q n, k 中的故障边全部分布在Q n, k -E c (≅Q n )中，即 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458454&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458454&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458454&type=middle .因为f e +f v ≤2n-4且f e ≥n，故f v ≤n-4.下面通过故障点数f v 来分情况讨论. 情形2.2.1   f v =0，f e ≤2n-4.由于Q n, k 中每个点均关联至少两条无故障边且f e ≤2n-4≤2n-3，由引理4，Q n, k -F e 中可嵌入一个长度至少为2 n 的圈. 情形2.2.2   f v ≥1，f e ≤2n-5.由引理1，Q n, k -E c 同构与Q n ，因为Q n, k 中每个点均关联至少三条无故障边，故在Q n, k -E c 中每个点关联至少两条无故障边且f e +f v ≤2n-4，f e ≤2n-5，即Q n, k -E c 满足引理3的约束条件，故由引理3，在Q n -F v -F e 中存在一个长度至少为2 n -2f v 的圈，又由于Q n -F v -F e ⊂Q n, k -F e -F v ，即在Q n, k -F e -F v 中能找到一个长度至少为2 n -2f v 的圈.定理1得证. 条件(2 n -3)-点边容错下加强超立方体中容错圈的嵌入 1 下面将在定理1的基础上增加故障元素至2n-3来讨论此时加强超立方体中容错圈的嵌入问题，主要证明当Q n, k 满足约束条件：1)|F v |+|F e |≤2n-3, |F e |≥k和2)每个节点至少关联两条无故障边时，Q n, k (n≥5)中能嵌入一条长为2 n -2|F v |的容错圈. 引理12   若f e +f v ≤2n-3，则Q n, k (n≥4, 1≤k≤n-1)中至多存在两个2-无故障点. 证   用反证法证明.假设Q n, k 含三个2-无故障点u，v和w.由引理5可知，当k=n-1时，Q n, k 含长度为3的圈.接下来只需要考虑一种特殊情况即Q n, k 中故障元素达到最小值时，即三条边(u, v)，(v, w)和(w, u)依次连接组成长为3的圈，且三条边(u, v)，(v, w)和(w, u)均为故障边，此时，得到故障元素总数至少为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458436&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458436&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458436&type=middle 这与条件f e +f v ≤2n-3相矛盾，因此假设不成立，即Q n, k 中至多存在两个2-无故障点. 引理13   若f e +f v ≤2n-3，且Q n, k 恰好含两个2-无故障点u和v，那么就有d (u, v)=1且uv∈F e . 证   若d (u, v) > 1，那么故障边的总数至少为(n-1)+(n-1)=2n-2 > 2n-3，与引理条件f e +f v ≤2n-3产生矛盾，故d (u, v)=1；若uv∉F e ，那么故障边的总数至少为(n-1)+(n-1)=2n-2 > 2n-3，与引理条件f e +f v ≤2n-3产生矛盾，故uv∈F e . 定理2  若Q n, k (n≥5)满足约束条件：1) f e +f v ≤2n-3，f e ≥k和2)每个节点至少关联两条无故障边，则Q n, k -F e -F v 中能嵌入一条长为2 n -2f v 的容错圈. 证   记F v 为Q n, k 中故障点的集合，F e 为Q n, k 中故障边的集合，F e c 为Q n, k 中故障补边的集合，F e i 为Q n, k 中故障超立方体的i维边的集合，其中i∈1, 2, …, n，且|F e |=f e ，|F v |=f v ，F e c =F e ∩E c ，|F e c |=f e c ，|F e i |=f e i .由定理1可知，当f e +f v ≤2n-4时，Q n, k -F e -F v 含一个长度至少为2 n -2f v 的圈.由引理6和引理7可知，当f e +f v =2n-3且k=1时，Q n, 1 (=FQ n )中含一个长度至少为2 n -2f v 的圈.由引理4可知，当f v =0, f e =2n-3时，Q n, k 中能找到一条长为2 n 的容错圈.因此，只需要考虑如下情况：当1) f e +f v =2n-3，f v ≥1，2≤k≤f e ≤2n-4和2)每个节点至少关联两条无故障边时，Q n, k -F e -F v (n≥5, k≥2)中能嵌入一条长为2 n -2f v 的容错圈.由引理11，通过2-无故障点的数量来分三种情况讨论. 情形1   Q n, k 不含2-无故障点，也就是说Q n, k 中每个点均是l-无故障点，其中l≥3，下面我们分情况讨论： 情形1.1   F e k ∪F e k+1 ∪…∪F e n ∪F e c ≠∅，在这种情况下，可以找到存在至少一条故障边的一维边j维边，其中j∈{k, k+1, …, n}∪{c}，也就是说f e j ≥1.由引理1可知Q n, k -E j 同构于Q n (即Q n, k -E j ≅Q n ).由于f e +f v =2n-3且f v ≥1，那么就有f e ≤2n-4，f e -f e j ≤2n-5，f v +f e -f e j ≤2n-4，又由于Q n, k -E j 个点至少关联两条无故障边，即Q n, k -E j 满足引理3的限制条件，则可知在 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458457&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458457&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458457&type=middle 中含有一个长度至少为2 n -2f v 的圈.又由于Q n -F v - http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458460&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458460&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458460&type=middle ，于是可知在Q n, k -F e -F v 中存在一个长度至少为2 n -2f v 的圈. 情形1.2   F e k ∪F e k+1 ∪…∪F e n ∪F e c ≠∅，即所有的故障边均分布在F e 1 ∪F e 2 ∪…∪F e k-1 中，也就是说所有的故障边均分布在Q n, k -E c ≅Q n 中.由于Q n, k 中每个点均是l-无故障点，其中l≥3，由引理8可知，对于任意的i∈{1, 2, …, k-1}，都有(n-1)-维加强超立方体Q n-1, k i0 和Q n-1, k i1 中每个点至少关联两条无故障边.设F v i0 F v i1 表示Q n-1, k i0 Q n-1, k i1 中的故障点集合，F e i0 F e i1 表示Q n-1, k i0 Q n-1, k i1 中的故障边集合，令|F v i0 |=f v i0 ，|F v i1 |=f v i1 ，|F e i0 |=f e i0 ，|F e i1 |=f e i1 .设F h i 为横跨Q n-1, k i0 和Q n-1, k i1 之间的超立方体的i-维故障边，|F h i |=f h i .由于f e ≥k≥2且所有的故障边均分布在F e 1 ∪F e 2 ∪…∪F e k-1 中，那么就有 max {|F e 1 |, |F e 2 |, …, |F e k-1 |}≥2. 情形1.2.1    max {|F e 1 |, |F e 2 |, …, |F e k-1 |}≥3. 令f h i = max {|F e 1 |, |F e 2 |, …, |F e k-1 |}≥3(i∈1, 2, …, k-1)，这样的i-维边确定后，将Q n, k 按照i-维边划分得到两个子加强超立方体Q n-1, k i0 和Q n-1, k i1 .不妨假设f e i0 +f v i0 ≤f e i1 +f v i1 ，那么则有2(f e i0 +f v i0 )≤f e i0 +f v i0 +f e i1 +f v i1 ≤2n-6，故f e i0 +f v i0 ≤n-3且f e i1 +f v i1 ≤2n-6.由于Q n-1, k i1 中每个点至少关联两条无故障边，故由定理1可知，在Q n-1, k i1 中存在一个长度至少为2 n-1 -2f v i1 的圈C h .由于C h 长度为2 n-1 -2f v i1 ，即在C h 上至少存在2 n-2 -f v i1 条相互不相交且不同的边.由于n≥5，故2 n-2 > 2n-3，又f v +f e =2n-3，故2 n-2 -f v i1 > f v +f e -f v i1 =f e i0 +f v i0 +f e i1 +f h i > f e i0 +f v i0 +f h i ，因此在C h 上至少存在一条边(a, b)使得边(a, a i )，(b, b i )和(a i , b i )均为无故障边.令P[a, b]是C h -{(a, b)}上连接点a和点b的一条路，其长度为2 n-1 -2f v i1 -1.由引理9可知，Q n-1, k i0 中点a i 和点b i 之间存在一条长度至少为2 n-1 -2f v i0 -1的无故障路P[a i , b i ]，故可以在Q n, k 中构造出一个圈为C=P[a, b]⊕(b, b i )⊕P[b i , a i ]⊕(a i , a)(用“⊕”来表示路的连接符号，它也可以用来连接边)，其长度为2 n-1 -2f v i0 -1+2+2 n-1 -2f v i1 -1=2 n -2f v . 情形1.2.2    max {|F e 1 |, |F e 2 |, …, |F e k-1 |}=2，即max{2, k}≤f e ≤2(k-1).不失一般性，假设|F e 1 |≥|F e 2 |≥…≥|F e k-1 |，即|F e 1 |=2.将Q n, k 按照1-维边划分得到两个子加强超立方体Q n-1, k 10 和Q n-1, k 11 .不妨假设f e 10 +f v 10 ≤f e 11 +f v 11 ，于是就有f e 10 +f v 10 ≤n-3且f e 11 +f v 11 ≤2n-5，我们可以分以下几种情况讨论： 情形1.2.2.1   1≤f e 10 +f v 10 ≤n-3且f e 11 +f v 11 ≤2n-6，参照情形1.2.1，可以在Q n, k 中构造出长度至少为2 n -2f v 的圈. 情形1.2.2.2   f e 10 +f v 10 =0且f e 11 +f v 11 =2n-5.由于f v 11 =f v ≥1，设u为Q n-1, k 11 中的一个故障点，由定理1(假设u为无故障点)，则在Q n-1, k 11 中存在一个不含任何除了u以外的其他故障元素的h-圈C h ，其长度为h=2 n-1 -2(f v 11 -1). 情形1.2.2.2.1   若圈C h 含点u，设x和y是点u在圈C h 上的两个邻点，设w (≠u)和z (≠u)分别为点x和y在C h 上的邻点. 情形1.2.2.2.1.1   若(x, x 1 )和(y, y 1 )是Q n, k 中两条无故障边.由于x和y是点u在圈C h 上的两个邻点，则d (x, y)=2，因此d (x 1 , y 1 )=2.由于f e 10 +f v 10 =0，即Q n-1, k 10 是一个无故障加强超立方体，又因为Q n-1 10 ⊂Q n-1, k 10 ，由引理10可知，当d (x 1 , y 1 )=2时，点x 1 和y 1 之间存在一条长度为2 n-1 -2的路P 1 =P[x 1 , y 1 ].由于C h =P[y, x]⊕(x, y)，则C=P[y, x] ⊕(x, x 1 )⊕P[x 1 , y 1 ]⊕(y 1 , y)为所求，其长度为2 n -2f v . 情形1.2.2.2.1.2   若(x, x 1 )和(z, z 1 )是Q n, k 中两条无故障边(关于(y, y 1 )和(w, w 1 )是Q n, k 中两条无故障边的讨论是类似的).由于w (≠u)和z (≠u)分别为点x和y在C h 上的邻点，则d (x, z)=3，因此d (x 1 , z 1 )=3.因为Q n-1, k 10 是无故障加强超立方体，Q n-1 10 ⊂Q n-1, k 10 ，故由引理10可知，当d (x 1 , z 1 )=3时，点x 1 和点z 1 之间存在一条长度为2 n-1 -1的路P 2 =P[x 1 , z 1 ].由于C h =P[z, x]⊕(x, u)⊕(u, y)⊕(y, z)，因此我们需要的圈可以构造为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458439&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458439&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458439&type=middle 其长度为2 n -2f v . 情形1.2.2.2.1.3   若(x, x 1 )和(y, y 1 )是Q n, k 中两条故障边.由于Q n, k 中每个点均是l-无故障点，其中l≥3, 故除了点u和边(x, x 1 )以外，点x在Q n-1, k 11 中关联至多n-4个故障元素，除了点u和边(y, y 1 )以外，点y在Q n-1, k 11 中关联至多n-4个故障元素，因此，在Q n-1, k 11 中与点x关联的故障元素总数加上与点y关联的故障元素总数之和至多为n-4+n-4+1=2n-7 < 2n-5，故在Q n-1, k 11 中一定可以找到一个端点不属于{x, y}的故障边(或者一个不与点x关联也不与点y关联的故障点)，不妨假设在Q n-1, k 11 中存在这样的故障边(a, b)(至于存在这样的故障点的情形讨论是一样的)，故由定理1(假设(a, b)为无故障边)可知，在Q n-1, k 11 中存在一个圈C 1 不含除了(a, b)以外的其他故障元素，其长度为2 n-1 -2f v 11 .圈C 1 不含(a, b)的情况较容易讨论，不妨讨论圈C 1 含(a, b)的情况.由于故障边(a, b)的端点不属于{x, y}，故边(a, a 1 )和(b, b 1 )是非故障边.由于d (a, b)=1，d (a, a 1 )=1，d (b, b 1 )=1，因此d (a 1 , b 1 )=1.由引理10，在超立方体Q n-1 10 中，当d (a 1 , b 1 )=1时，点a 1 和点b 1 之间存在一条长为2 n-1 -1的路P[a 1 , b 1 ].由于圈C 1 =P[b, a]⊕(a, b), 因此有圈C=P[b, a] ⊕(a, a 1 )⊕P[a 1 , b 1 ]⊕(b 1 , b)，其长度为2 n-1 -1+2+2 n-1 -2f v 11 -1=2 n -2f v . 情形1.2.2.2.1.4   若(x, x 1 )和(w, w 1 )是Q n, k 中两条故障边(关于(y, y 1 )和(z, z 1 )是Q n, k 中两条故障边的讨论是类似的).由于Q n, k 中每个点均是l-无故障点，其中l≥3, 故除了点u和边(x, x 1 )以外，点x在Q n-1, k 11 中关联至多n-4个故障元素，除了边(w, w 1 )以外，点w在Q n-1, k 11 中关联至多n-3个故障元素，因此，在Q n-1, k 11 中与点x关联的故障元素总数加上与点w关联的故障元素总数之和至多为n-3+n-4+1=2n-6 < 2n-5，故在Q n-1, k 11 中一定可以找到一个不与点x关联也不与点w关联的故障点h (或者一个端点不属于{x, w}的故障边)，设m，n为h在Q n-1, k 11 中的两个邻点，如情形1.2.2.2.1.1的讨论，故可以在Q n, k 中找到一个圈C 1 长度为2 n -2f v . 情形1.2.2.2.2   若圈C h 不含点u, 如情况1.2.1的讨论，可知在Q n, k 中能找到一个长度为2 n -2f v 的圈. 情形2   Q n, k 恰好含一个2-无故障点，设这个2-无故障点为u，则在Q n, k -{u}中每个点均是l-无故障点，其中l≥3.因为与点u关联的故障边总数为n-1，故一定存在j (∈{k, k+1, …, n, c})-维边使得uu j 是一条故障边(假设不存在这样j-维边，即与点u关联的故障边均为(u, u i )，其中i∈{1, 2, …, k-1}，那么与点u关联的故障边至多为k-1条，而k≤n-1，因此k-1≤n-2 < n-1，这里便产生矛盾，故假设不成立).由引理1知Q n, k -E j 同构于Q n (即Q n, k -E j ≅Q n )，与情形1.1的讨论方法一样，可知Q n, k 中能构造出长度至少为2 n -2f v 的圈. 情形3   Q n, k 含恰好两个2-无故障点u和点v，由引理13，就有d (u, v)=1且uv∈F e . 情形3.1   (u, v)∈F e j ，其中j∈{k, k+1, …, n, c}，由引理1，可知Q n, k -E j ≅Q n ，与情况1.1的讨论方法一样，可知Q n, k 中能构造出长度至少为2 n -2f v 的圈. 情形3.2   (u, v)∈F e i ，其中i∈{1, 2, …, k-1}.将Q n, k 按照i (i < k, 2≤k≤n-1)-维边划分得到两个n-1维的子加强超立方体Q n-1, k i0 和Q n-1, k i1 使得u∈Q n-1, k i0 且v∈Q n-1, k i1 .由于点u和点v均为2-无故障点，即在Q n-1, k i0 中，与点u关联的故障元素总数为n-2，与点v关联的故障元素总数也为n-2，故f e i0 +f v i0 ≥n-2且f e i1 +f v i1 ≥n-2，而f e +f v =2n-3且F e i ≥1，故f e i0 +f v i0 =n-2, f e i1 +f v i1 =n-2且F e i =1，由定理1，与情况1.2.1的讨论方法一样，可以在Q n, k 中构造出长度至少为2 n -2f v 的圈. 由以上各种情况的分析，完成了此定理的证明. 结论 1 互连网络中圈的嵌入问题是一个非常重要的研究课题.网络在实际投入使用时，其处理器和链路同时出现故障是不可避免的，因此，考虑含有故障点和边的网络是非常有必要的.而作为超立方体网络的一种变型结构--加强超立方体中的圈的嵌入问题更是值得我们研究.在本文中，证明了当点边错误元素总数不超过2n-4，且每个节点至少关联两条无故障边时，长度至少为2 n -2|F v |的容错圈可以嵌入到加强超立方体Q n, k 中.同时进一步研究了在条件容错模型下(2n-3)-点边容错加强超立方体中容错圈的嵌入，当点边错误元素总数不超过2n-3，错误边数至少k条，且每个节点至少关联两条无故障边时，Q n, k 中能嵌入一条长为2 n -2|F v |的容错圈. 参考文献 XU J M. Topological Structure and Analysis of Interconnection Networks[M]. Dordrecht: Kluwer Academic Publishers, 2001. TSAI C H. Fault-tolerant cycles embedded in hypercubes with mixed link and node failures[J]. Applied Mathematices Letters, 2008, 21(8):855-860. DU Z Z, XU J M. A note on cycle embedding in hypercubes with faulty vertices[J]. Information Processing Letters, 2011, 111(12):557-560. TZENG N F, WEI S. Enhanced hypercubes[J]. IEEE Transactions on Computers, 1991, 40(3): 284-294. LIU M, LIU H M. Path and cycles embedding on faulty enhanced hypercube networks[J]. Acta Mathematica Scientia, 2013, 33B (1):227-246. LIU H M. The structural features of enhanced hypercube networks[DB/OL].[2015-02-03] . http://ieeexplore.ieee.org/stamp/stamp.jsptp=&arnumber=5364139 http://ieeexplore.ieee.org/stamp/stamp.jsptp=&arnumber=5364139 , 2009:345-348. ZHANG Y J, LIU H M, LIU M. Vertex-fault-tolerant cycles embedding on enhanced hypercube networks[J]. Acta Mathematica Scientia, 2013, 33B (6): 1-10. FAN Y H, LIU H M, LIU M. Path and cycles in faulty folded hypercube[J]. Journal of Mathematics, 2013, 33(3):393-400. FU J S. Longest fault-free paths in hypercubes with vertex faults[J]. Information Science, 2006, 176(7):759-771. LIU M, LIU H M. Conditional edge-fault-tolerant hamiltonicity of enhanced hypercube[DB/OL].[2015-02-20] . http://ieeexplore.ieee.org/stamp/stamp.jsptp=&arnumber=5974791 http://ieeexplore.ieee.org/stamp/stamp.jsptp=&arnumber=5974791 . LIU M, LIU H M. Cycles in conditional faulty enhanced hypercube networks[J]. Journal of Communications and Networks, 2012, 14(2):213-221. CAO S L, LIU H M. On constraint fault-free cycles in folded hypercube[J]. International Journal of Applied Mathematics and Statistics, 2013, 42(12):38-44. DU Z Z, JING J, MA M J, et al. Cycle embedding in hypercubes with faulty vertices and edges[J]. Journal of University of Science and Technology of China, 2008, 38(9) :1020-1024. LIU H M. Properties and performance of enhanced hypercube networks[J]. Journal of Systems Science and Information, 2006, 3:251-256. LI T K, TSAI C H, M J J, et al. Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes[J]. Information Processing Letters, 2003, 87(2):107-110. 10.14188/j.1671-8836.2016.06.013 O157.5 whdxxblxb-62-6-568 国家自然科学基金资助项目(11371162, 11171129);湖北省科技创新团队项目(T201103) 2015-09-06 2016-12-24 2020-12-09 版权所有© 2016 《武汉大学学报(理学版)》编辑部 Copyright © 2016 Journal of Wuhan University (Natural Science Edition). All rights reserved. 2016 武汉大学学报(理学版) 6 62