0 引言

超立方体是现今最著名、最通用, 也是最有效的互连网络的拓扑结构.在高性能计算中尤其在大型工业计算中有着非常重要的作用.因其结构正则、对称以及相对小的传输延迟，许多好的算法易于嵌入等优良性质而受到广泛关注^[1].但是超立方体也有它固有的缺点，比如较大的直径，因此设计和维护高维的超立方体网络的复杂度比较高.为了获得比超立方体更优良的性质, 人们提出了超立方体的一系列变型结构, 如广义超立方体, 折叠超立方体, 纽立方体, 增广超立方体以及加强超立方体等等.

在现实网络中，处理器或者处理器连线发生故障是不可避免的，这就要求网络具有一定的容错性.也就是说当网络中一定数目的节点或者连线坏掉时，网络仍然可以有效的工作.在标准容错情况下，故障边的分布不受点的限制.超立方体网络及其变形网络在标准容错条件下已经有许多结论，关于超立方体及其变形结构性质以及点边容错性质，最近文献[2]得到了许多好的结果.例如，文献[2]证明了在超立方体Q_n(n≥5)中，当|F_v|+|F_e|≤2n-4, |F_e|≤n-2时，则Q_n-F_v-F_e包含一条长度至少为2ⁿ-2|F_v|的无故障圈. Du等^[3]证明了当|F_v|=2n-3时，则Q_n(n≥5)中能嵌入一条长度至少为2ⁿ-2|F_v|的无故障圈.由于加强超立方体Q_{n, k}1≤k≤n-1是在n-维超立方体Q_n中添加2^n-1条的边得到的新结构^[4]，因此超立方体是加强超立方体的一个支撑子图，那么上述研究结论在加强超立方体Q_{n, k}中均成立.Liu在文献[5]中研究加强超立方体存在大量故障点和故障边时圈的一些性质，即当|F_e|≤n-1且|F_v|+|F_e|≤2n-4时，则Q_{n, k}(n≥4)中能找到一条长为2ⁿ-2|F_v|的容错圈. Liu在文献[6]中研究了加强超立方体Q_{n, k}(n≥3, 1≤k≤n-1)的泛圈性问题，证明了当n和k奇偶性不同时，Q_{n, k}中每一条边均在长为n-k+2到2ⁿ-1的奇圈上.Zhang^[7]证明了当n和k奇偶性相同时，若|F_v|=2，Q_{n, k}中含有长度从4到2ⁿ-4的偶圈，而且含有长度从n-k+2到2ⁿ-3的所有奇圈.同时文献[7]还证明了当|F_v|≤n-2时，若n和k奇偶性相同，Q_{n, k}中存在长度为2ⁿ-2|F_v|的偶圈；若n和k奇偶性不同，Q_{n, k}中存在长度为2ⁿ-2|F_v|的偶圈同时有长度为2ⁿ-2|F_v|+1的奇圈. Fan^[8]证明了在折叠超立方体FQ_n(n≥4)中，当|F_v|=2n-3，则FQ_n-F_v中存在一个长度至少为2ⁿ-2f_v的圈.

然而，由于网络的不同部分可能有不同的可靠性，我们就可以假设在一些部分的某些子集中，这些部分并不是同时坏掉的.Fu^[9]提出了条件容错模型，即在网络模型中，所有的点都至少与两条非故障边相连.在这种模型下，也得到了一些结论.例如, Liu^[10]证明了在约束条件：1)|F_e|≤2n-3和2)每个节点至少关联两条无故障边时，Q_{n, k}中能找到一条长为2ⁿ的容错圈. Liu^[11]进一步研究了条件容错模型下若加强超立方体Q_{n, k}满足约束条件：1)|F_e|≤2n-3和2)每个节点至少关联两条无故障边时，当n和k有相同的奇偶性，那么在Q_{n, k}中存在偶长为4到2ⁿ的的容错圈；当n和k有不同的奇偶性，那么在Q_{n, k}中存在奇长为n-k+2到2ⁿ-1的容错圈.Cao^[12]证明了在折叠超立方体FQ_n(n≥3)中，若|F_e|+|F_v|≤2n-3，|F_e|≥1且每个点至少关联两条非故障边，则在FQ_n-F_v-F_e中存在一个长度至少为2ⁿ-2f_v的圈.

本文讨论了加强超立方体网络中存在大量故障点和故障边时圈的一些性质.

1 相关定义及引理

G=(V, E)表示一个图，V为点集，E为边集.图中的一条路定义为一个点和边交替出现的序列P=v₀e₁v₁e₂v₂…e_iv_i…e_kv_k(1≤i≤k)，其中点v₁, v₂, …, v_k互不相同.边e_i的端点是v_i-1和v_i，称P是从v₀到v_k的一条路或一条(v₀, v_k)路. k称为路P的长度.在简单图中，P可以由其顶点序列来表示P[v₀, v_k]=〈v₀, v₁, v₂, …, v_k〉.若v₀=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₁x₂…x_n:x_i∈{0, 1}, i=1, 2, …, n}，超立方体中每个点x都可以用一个长为n的二元位串表示，即x=x₁x₂…x_n，x_i=0, 1.设x=x₁x₂…x_i-1x_ix_i+1…x_n和y为V(Q_n)中两个点，x和y之间有边相连当且仅当y满足：

Q_n中两个顶点x=x₁x₂…x_n和y=y₁y₂…y_n之间的Hamming距离定义为，表示两顶点的二元字符串中对应的不同分量的个数(或表示为d_H(x, y)).用d_Qn(x, y)表示Q_n中两点x和y之间的距离，即连接x和y两点之间的最短路的长度.由上述定义可知，在Q_n中有d_Qn(x, y)=d_H(x, y).称连接u, uⁱ之间的边(u, uⁱ)为Q_n中的i-维边，记E_i={(u, uⁱ)|h(u, uⁱ)=1}，i∈{1, 2, …, n}，即Q_n中所有i-维边的集合.由此可知.

超立方体Q_n可以沿着第i(1≤i≤n)-维划分，得到两个子图.分别用Q_n-1ⁱ⁰和Q_n-1ⁱ¹表示这两个子图.从划分的定义来看，可知这样得到的两个子图Q_n-1ⁱ⁰和Q_n-1ⁱ¹是两个(n-1)-维超立方体子图.一个点x=x₁x₂…x_n是Q_n-1ⁱ⁰中的一个点当且仅当此点的第i位为x_i=0；类似的，点x是Q_n-1ⁱ¹中的一个点当且仅当此点的第i位为x_i=1.

下面给出加强超立方体Q_{n, k}的定义.

定义1  n维加强超立方体记为

其定义如下

设x=x₁x₂…x_i-1x_ix_i+1…x_n和y为V(Q_{n, k})中两个点，x=x₁x₂…x_i-1x_ix_i+1…x_n和y之间有边相连当且仅当y满足下列条件之一：

或者

2) , 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)，其中补边集记为

边(u, uⁱ)代表Q_{n, k}中的超立方体的i维边，其定义为：

在本文中，记F_v为故障点的集合，F_e为故障边的集合，F_e^c为Q_{n, k}中故障补边的集合，F_eⁱ为Q_{n, k}中超立方体的故障i维边的集合，且|F_e|=f_e，|F_v|=f_v，F_e^c=F_e∩E_c，F_eⁱ=F_e∩E_i，|F_e^c|=f_e^c，|F_eⁱ|=f_eⁱ.

引理1^[5]  在加强超立方体Q_{n, k}中，对任意的j∈{k, k+1, …, n}∪{c}，则有Q_{n, k}-E_j同构于Q_n.

引理2^[5]  在加强超立方体Q_{n, k}(n≥3, 1≤k≤n-1)中，若f_e+f_v≤2n-4，f_e≤n-1，则Q_{n, k}-F_e-F_v中存在一个长度至少为2ⁿ-2f_v的圈.

引理3^[13]  在超立方体Q_n(n≥3)中，若f_e+f_v≤2n-4，f_e≤2n-5且Q_n中每个点至少关联两条无故障边，则在Q_n-F_e-F_v中存在一个长度至少为2ⁿ-2f_v的圈.

引理4^[10]  在加强超立方体Q_{n, k}(n≥3, 1≤k≤n-1)中，若f_e≤2n-3且Q_{n, k}中每个点至少关联两条无故障边，则在Q_{n, k}-F_e中存在一个长度为2ⁿ的圈.

引理5^[6]  在加强超立方体Q_{n, k}(n≥3, 1≤k≤n-1)中，若n和k奇偶性不同，则Q_{n, k}中每一条边均在长为n-k+2到2ⁿ-1的奇圈上.

引理6^[8]  在折叠超立方体FQ_n(n≥4)中，若f_v=2n-3，则在FQ_n-F_v中存在一个长度至少为2ⁿ-2f_v的圈.

引理7^[12]  在折叠超立方体FQ_n(n≥3)中，若f_e+f_v≤2n-3，f_e≥1且FQ_n中每个点至少关联两条无故障边，则在FQ_n-F_v-F_e中存在一个长度至少为2ⁿ-2f_v的圈.

引理8^[14]  将加强超立方体Q_{n, k}沿着第i(1≤i≤n)-维划分，可以得到两个子图.我们分别用Q_{n-1, k}ⁱ⁰(Q_n-1ⁱ⁰)和Q_{n-1, k}ⁱ¹(Q_n-1ⁱ¹)来表示这两个子图.当i < k时，得到的两个子图Q_{n-1, k}ⁱ⁰和Q_{n-1, k}ⁱ¹是两个(n-1)-维的加强超立方体子图；当i≥k时，得到的两个子图Q_n-1ⁱ⁰和Q_n-1ⁱ¹是两个(n-1)-维的超立方体子图.一个点x=x₁x₂…x_n是Q_{n-1, k}ⁱ⁰(Q_n-1ⁱ⁰)中的一个点当且仅当此点的第i位为x_i=0；类似的，此点x是Q_{n-1, k}ⁱ¹(Q_n-1ⁱ¹)中的一个点当且仅当此点的第i位为x_i=1.

引理9^[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ⁿ-2f_v-1的(u, v)路；当d(u, v)为偶数时，u和v之间存在一条长为2ⁿ-2f_v-2的(u, v)路.

引理10^[15]  在超立方体Q_n(n≥2)中，设u和v为Q_n中任意两点，则u和v之间存在一条长为l的(u, v)路，其中d(x, y)≤l≤2ⁿ-1且l与d(x, y)奇偶性相同.

2 条件(2n-4)-点边容错下加强超立方体中容错圈的嵌入

若一个点恰好关联了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ⁿ-2f_v的圈.

证  记F_v为Q_{n, k}中故障点的集合，F_e为Q_{n, k}中故障边的集合，F_e^c为Q_{n, k}中故障补边的集合，F_eⁱ为Q_{n, k}中超立方体故障i-维边的集合，且

由引理2，当f_e+f_v≤2n-4，f_e≤n-1时，Q_{n, k}-F_e-F_v含一个长度至少为2ⁿ-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ⁱ)为与点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，则有

又因为Q_{n, k}-{u}中每个点均为l-无故障点，其中l≥3，并且与点u关联的j维边为故障边，所以可知Q_{n, k}-E_j中每个点至少关联两条无故障边，故Q_{n, k}-E_j满足引理3的约束条件，于是由引理3知，在中存在一个长度至少为2ⁿ-2f_v的圈，又因为，即在Q_{n, k}-F_e-F_v中能找到一个长度至少为2ⁿ-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ⁿ∪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ⁿ-2f_v的圈.

情形2.2  F_e^k∪F_e^k+1∪…∪F_eⁿ∪F_e^c=∅，即Q_{n, k}中的故障边全部在集合E₁∪E₂∪…∪E_k-1中，也就是说Q_{n, k}中的故障边全部分布在Q_{n, k}-E_c(≅Q_n)中，即.因为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ⁿ的圈.

情形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ⁿ-2f_v的圈，又由于Q_n-F_v-F_e⊂Q_{n, k}-F_e-F_v，即在Q_{n, k}-F_e-F_v中能找到一个长度至少为2ⁿ-2f_v的圈.定理1得证.

3 条件(2n-3)-点边容错下加强超立方体中容错圈的嵌入

下面将在定理1的基础上增加故障元素至2n-3来讨论此时加强超立方体中容错圈的嵌入问题，主要证明当Q_{n, k}满足约束条件：1)|F_v|+|F_e|≤2n-3, |F_e|≥k和2)每个节点至少关联两条无故障边时，Q_{n, k}(n≥5)中能嵌入一条长为2ⁿ-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)均为故障边，此时，得到故障元素总数至少为

这与条件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ⁿ-2f_v的容错圈.

证  记F_v为Q_{n, k}中故障点的集合，F_e为Q_{n, k}中故障边的集合，F_e^c为Q_{n, k}中故障补边的集合，F_eⁱ为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ⁱ|=f_eⁱ.由定理1可知，当f_e+f_v≤2n-4时，Q_{n, k}-F_e-F_v含一个长度至少为2ⁿ-2f_v的圈.由引理6和引理7可知，当f_e+f_v=2n-3且k=1时，Q_{n, 1}(=FQ_n)中含一个长度至少为2ⁿ-2f_v的圈.由引理4可知，当f_v=0, f_e=2n-3时，Q_{n, k}中能找到一条长为2ⁿ的容错圈.因此，只需要考虑如下情况：当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ⁿ-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ⁿ∪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的限制条件，则可知在中含有一个长度至少为2ⁿ-2f_v的圈.又由于Q_n-F_v-，于是可知在Q_{n, k}-F_e-F_v中存在一个长度至少为2ⁿ-2f_v的圈.

情形1.2  F_e^k∪F_e^k+1∪…∪F_eⁿ∪F_e^c≠∅，即所有的故障边均分布在F_e¹∪F_e²∪…∪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}ⁱ⁰和Q_{n-1, k}ⁱ¹中每个点至少关联两条无故障边.设F_vⁱ⁰F_vⁱ¹表示Q_{n-1, k}ⁱ⁰Q_{n-1, k}ⁱ¹中的故障点集合，F_eⁱ⁰F_eⁱ¹表示Q_{n-1, k}ⁱ⁰Q_{n-1, k}ⁱ¹中的故障边集合，令|F_vⁱ⁰|=f_vⁱ⁰，|F_vⁱ¹|=f_vⁱ¹，|F_eⁱ⁰|=f_eⁱ⁰，|F_eⁱ¹|=f_eⁱ¹.设F_hⁱ为横跨Q_{n-1, k}ⁱ⁰和Q_{n-1, k}ⁱ¹之间的超立方体的i-维故障边，|F_hⁱ|=f_hⁱ.由于f_e≥k≥2且所有的故障边均分布在F_e¹∪F_e²∪…∪F_e^k-1中，那么就有max{|F_e¹|, |F_e²|, …, |F_e^k-1|}≥2.

情形1.2.1  max{|F_e¹|, |F_e²|, …, |F_e^k-1|}≥3.

令f_hⁱ=max{|F_e¹|, |F_e²|, …, |F_e^k-1|}≥3(i∈1, 2, …, k-1)，这样的i-维边确定后，将Q_{n, k}按照i-维边划分得到两个子加强超立方体Q_{n-1, k}ⁱ⁰和Q_{n-1, k}ⁱ¹.不妨假设f_eⁱ⁰+f_vⁱ⁰≤f_eⁱ¹+f_vⁱ¹，那么则有2(f_eⁱ⁰+f_vⁱ⁰)≤f_eⁱ⁰+f_vⁱ⁰+f_eⁱ¹+f_vⁱ¹≤2n-6，故f_eⁱ⁰+f_vⁱ⁰≤n-3且f_eⁱ¹+f_vⁱ¹≤2n-6.由于Q_{n-1, k}ⁱ¹中每个点至少关联两条无故障边，故由定理1可知，在Q_{n-1, k}ⁱ¹中存在一个长度至少为2^n-1-2f_vⁱ¹的圈C_h.由于C_h长度为2^n-1-2f_vⁱ¹，即在C_h上至少存在2^n-2-f_vⁱ¹条相互不相交且不同的边.由于n≥5，故2^n-2>2n-3，又f_v+f_e=2n-3，故2^n-2-f_vⁱ¹>f_v+f_e-f_vⁱ¹=f_eⁱ⁰+f_vⁱ⁰+f_eⁱ¹+f_hⁱ>f_eⁱ⁰+f_vⁱ⁰+f_hⁱ，因此在C_h上至少存在一条边(a, b)使得边(a, aⁱ)，(b, bⁱ)和(aⁱ, bⁱ)均为无故障边.令P[a, b]是C_h-{(a, b)}上连接点a和点b的一条路，其长度为2^n-1-2f_vⁱ¹-1.由引理9可知，Q_{n-1, k}ⁱ⁰中点aⁱ和点bⁱ之间存在一条长度至少为2^n-1-2f_vⁱ⁰-1的无故障路P[aⁱ, bⁱ]，故可以在Q_{n, k}中构造出一个圈为C=P[a, b]⊕(b, bⁱ)⊕P[bⁱ, aⁱ]⊕(aⁱ, a)(用“⊕”来表示路的连接符号，它也可以用来连接边)，其长度为2^n-1-2f_vⁱ⁰-1+2+2^n-1-2f_vⁱ¹-1=2ⁿ-2f_v.

情形1.2.2  max{|F_e¹|, |F_e²|, …, |F_e^k-1|}=2，即max{2, k}≤f_e≤2(k-1).不失一般性，假设|F_e¹|≥|F_e²|≥…≥|F_e^k-1|，即|F_e¹|=2.将Q_{n, k}按照1-维边划分得到两个子加强超立方体Q_{n-1, k}¹⁰和Q_{n-1, k}¹¹.不妨假设f_e¹⁰+f_v¹⁰≤f_e¹¹+f_v¹¹，于是就有f_e¹⁰+f_v¹⁰≤n-3且f_e¹¹+f_v¹¹≤2n-5，我们可以分以下几种情况讨论：

情形1.2.2.1  1≤f_e¹⁰+f_v¹⁰≤n-3且f_e¹¹+f_v¹¹≤2n-6，参照情形1.2.1，可以在Q_{n, k}中构造出长度至少为2ⁿ-2f_v的圈.

情形1.2.2.2  f_e¹⁰+f_v¹⁰=0且f_e¹¹+f_v¹¹=2n-5.由于f_v¹¹=f_v≥1，设u为Q_{n-1, k}¹¹中的一个故障点，由定理1(假设u为无故障点)，则在Q_{n-1, k}¹¹中存在一个不含任何除了u以外的其他故障元素的h-圈C_h，其长度为h=2^n-1-2(f_v¹¹-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¹)和(y, y¹)是Q_{n, k}中两条无故障边.由于x和y是点u在圈C_h上的两个邻点，则d (x, y)=2，因此d (x¹, y¹)=2.由于f_e¹⁰+f_v¹⁰=0，即Q_{n-1, k}¹⁰是一个无故障加强超立方体，又因为Q_n-1¹⁰⊂Q_{n-1, k}¹⁰，由引理10可知，当d (x¹, y¹)=2时，点x¹和y¹之间存在一条长度为2^n-1-2的路P₁=P[x¹, y¹].由于C_h=P[y, x]⊕(x, y)，则C=P[y, x]⊕(x, x¹)⊕P[x¹, y¹]⊕(y¹, y)为所求，其长度为2ⁿ-2f_v.

情形1.2.2.2.1.2  若(x, x¹)和(z, z¹)是Q_{n, k}中两条无故障边(关于(y, y¹)和(w, w¹)是Q_{n, k}中两条无故障边的讨论是类似的).由于w (≠u)和z (≠u)分别为点x和y在C_h上的邻点，则d (x, z)=3，因此d (x¹, z¹)=3.因为Q_{n-1, k}¹⁰是无故障加强超立方体，Q_n-1¹⁰⊂Q_{n-1, k}¹⁰，故由引理10可知，当d (x¹, z¹)=3时，点x¹和点z¹之间存在一条长度为2^n-1-1的路P₂=P[x¹, z¹].由于C_h=P[z, x]⊕(x, u)⊕(u, y)⊕(y, z)，因此我们需要的圈可以构造为

其长度为2ⁿ-2f_v.

情形1.2.2.2.1.3  若(x, x¹)和(y, y¹)是Q_{n, k}中两条故障边.由于Q_{n, k}中每个点均是l-无故障点，其中l≥3, 故除了点u和边(x, x¹)以外，点x在Q_{n-1, k}¹¹中关联至多n-4个故障元素，除了点u和边(y, y¹)以外，点y在Q_{n-1, k}¹¹中关联至多n-4个故障元素，因此，在Q_{n-1, k}¹¹中与点x关联的故障元素总数加上与点y关联的故障元素总数之和至多为n-4+n-4+1=2n-7 < 2n-5，故在Q_{n-1, k}¹¹中一定可以找到一个端点不属于{x, y}的故障边(或者一个不与点x关联也不与点y关联的故障点)，不妨假设在Q_{n-1, k}¹¹中存在这样的故障边(a, b)(至于存在这样的故障点的情形讨论是一样的)，故由定理1(假设(a, b)为无故障边)可知，在Q_{n-1, k}¹¹中存在一个圈C₁不含除了(a, b)以外的其他故障元素，其长度为2^n-1-2f_v¹¹.圈C₁不含(a, b)的情况较容易讨论，不妨讨论圈C₁含(a, b)的情况.由于故障边(a, b)的端点不属于{x, y}，故边(a, a¹)和(b, b¹)是非故障边.由于d (a, b)=1，d (a, a¹)=1，d (b, b¹)=1，因此d (a¹, b¹)=1.由引理10，在超立方体Q_n-1¹⁰中，当d (a¹, b¹)=1时，点a¹和点b¹之间存在一条长为2^n-1-1的路P[a¹, b¹].由于圈C₁=P[b, a]⊕(a, b), 因此有圈C=P[b, a]⊕(a, a¹)⊕P[a¹, b¹]⊕(b¹, b)，其长度为2^n-1-1+2+2^n-1-2f_v¹¹-1=2ⁿ-2f_v.

情形1.2.2.2.1.4  若(x, x¹)和(w, w¹)是Q_{n, k}中两条故障边(关于(y, y¹)和(z, z¹)是Q_{n, k}中两条故障边的讨论是类似的).由于Q_{n, k}中每个点均是l-无故障点，其中l≥3, 故除了点u和边(x, x¹)以外，点x在Q_{n-1, k}¹¹中关联至多n-4个故障元素，除了边(w, w¹)以外，点w在Q_{n-1, k}¹¹中关联至多n-3个故障元素，因此，在Q_{n-1, k}¹¹中与点x关联的故障元素总数加上与点w关联的故障元素总数之和至多为n-3+n-4+1=2n-6 < 2n-5，故在Q_{n-1, k}¹¹中一定可以找到一个不与点x关联也不与点w关联的故障点h (或者一个端点不属于{x, w}的故障边)，设m，n为h在Q_{n-1, k}¹¹中的两个邻点，如情形1.2.2.2.1.1的讨论，故可以在Q_{n, k}中找到一个圈C₁长度为2ⁿ-2f_v.

情形1.2.2.2.2  若圈C_h不含点u, 如情况1.2.1的讨论，可知在Q_{n, k}中能找到一个长度为2ⁿ-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∈{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ⁿ-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ⁿ-2f_v的圈.

情形3.2  (u, v)∈F_eⁱ，其中i∈{1, 2, …, k-1}.将Q_{n, k}按照i (i < k, 2≤k≤n-1)-维边划分得到两个n-1维的子加强超立方体Q_{n-1, k}ⁱ⁰和Q_{n-1, k}ⁱ¹使得u∈Q_{n-1, k}ⁱ⁰且v∈Q_{n-1, k}ⁱ¹.由于点u和点v均为2-无故障点，即在Q_{n-1, k}ⁱ⁰中，与点u关联的故障元素总数为n-2，与点v关联的故障元素总数也为n-2，故f_eⁱ⁰+f_vⁱ⁰≥n-2且f_eⁱ¹+f_vⁱ¹≥n-2，而f_e+f_v=2n-3且F_eⁱ≥1，故f_eⁱ⁰+f_vⁱ⁰=n-2, f_eⁱ¹+f_vⁱ¹=n-2且F_eⁱ=1，由定理1，与情况1.2.1的讨论方法一样，可以在Q_{n, k}中构造出长度至少为2ⁿ-2f_v的圈.

由以上各种情况的分析，完成了此定理的证明.

4 结论

互连网络中圈的嵌入问题是一个非常重要的研究课题.网络在实际投入使用时，其处理器和链路同时出现故障是不可避免的，因此，考虑含有故障点和边的网络是非常有必要的.而作为超立方体网络的一种变型结构--加强超立方体中的圈的嵌入问题更是值得我们研究.在本文中，证明了当点边错误元素总数不超过2n-4，且每个节点至少关联两条无故障边时，长度至少为2ⁿ-2|F_v|的容错圈可以嵌入到加强超立方体Q_{n, k}中.同时进一步研究了在条件容错模型下(2n-3)-点边容错加强超立方体中容错圈的嵌入，当点边错误元素总数不超过2n-3，错误边数至少k条，且每个节点至少关联两条无故障边时，Q_{n, k}中能嵌入一条长为2ⁿ-2|F_v|的容错圈.