基于VLSI技术的迅猛发展, 一个多处理机系统含有大量的节点.在系统实现过程中, 无论节点还是链接发生故障的可能性都是不可避免的, 因此对系统作容错性能分析是非常重要的课题.当故障发生时, 一个系统能保持一定的功能, 则称该系统是容错的.判断一个系统是否保持一定功能的标准之一就是看系统是否含有某种拓扑结构, 这种问题经常表现为把一种结构嵌入到另一种结构中.本文主要关注在节点发生故障时, 系统中每条链接是否在各种长度的圈型结构中.通常用$ G = (V, E) $来表示一个图, 图的顶点集$ V $表示网络节点集合(或称点集), 图的边集$ E $表示网络链接集合(或称边集).网络$ G $中最小圈长, 称为$ G $的围长, 用$ g(G) $表示.若图$ G $含有长为$ l $的圈, 其中$ g(G) \leq l \leq v(G) $, $ v(G) = |V | $是$ G $的节点数（或称阶）, 则称$ G $是泛圈的(pancyclic).网络是否具有泛圈性可以度量该网络是否可以嵌入任意长度的圈.若$ G $中每条边均位于长从$ g(G) $到$ v(G) $的圈上, 则称$ G $是边泛圈的(edge-pancyclic).若含有从$ g(G) $到$ v(G) $的所有偶数长度的圈(简称偶圈), 称$ G $是偶泛圈的(bipancyclic)；若对$ G $中的每条边, 均存在长度从$ g(G) $到$ v(G) $的所有偶圈经过该边, 则称G是边偶泛圈的(edge-bipancyclic).如果$ G $的点集可以划分为两个非空不交子集$ X $、$ Y $, 使得$ G $中每条边的端点分别属于$ X $、$ Y $, 则称$ G $为二部图.二部图不含长度为奇数的圈（简称奇圈）.因此二部图仅研究其偶泛圈性和边偶泛圈性.以超立方体为拓扑结构的网络简称超立方体网络, 它是典型的二部图, 由于其结构正则, 对称, 具有点边传递性、相对小的传输延迟、路可嵌入性、圈可嵌入性、树能以膨胀系数1嵌入等优良性质而受到广泛关注(见文献[1-3]), 在高性能计算机中, 尤其在大型工业计算和研究中, 超立方体结构有着非常重要的作用. $ n $-维超立方体, 记为$ Q_{n} $.随着可靠性容错性要求的越来越高, 许多改进的超立方体拓扑结构相继提出, 比如折叠超立方体$ FQ_{n} $, 加强超立方体$ Q_{n, k} $, 可扩超立方体$ AQ_{n} $, 交叉超立方体$ CQ_{n} $, 广义超立方体等等^[3].

超立方体及其变形结构的泛圈性以及容错泛圈性的研究近来得到了许多好的结果.文献[4]证明了$ Q_{n, k} $为二部图当且仅当$ n $和$ k $有相同奇偶性.因此, 当$ n $和$ k $有相同奇偶性时, 对$ Q_{n, k} $需要考虑偶泛圈的嵌入; 当$ n $和$ k $有不同奇偶性时, 要同时考虑奇圈和偶圈的嵌入.文献[5]证明了当$ |Fv| = 1 $时, 若$ n $和$ k $有相同奇偶性, 则$ Q_{n, k} $中存在长度从$ 4 $到$ 2^{n}-2 $的偶圈；若$ n $和$ k $奇偶性不同, 则$ Q_{n, k} $中不仅存在长度从$ 4 $到$ 2^{n}-2 $的偶圈, 而且还存在长度从$ n-k+2 $到$ 2^{n}-1 $的所有奇圈.在此基础上, 文献[6]进一步证明了当$ |F_{v}| = 2 $, 若$ n $和$ k $有相同奇偶性, 则$ Q_{n, k} $中存在长度从$ 4 $到$ 2^{n}-4 $的偶圈；若$ n $和$ k $有不同奇偶性, 则在$ Q_{n, k} $中不仅存在长度从$ 4 $到$ 2n-4 $的偶圈, 而且还存在长度从$ n-k + 2 $到$ 2^{n }-3 $的奇圈.同时文献[6]还证明了当$ |F_{v}| \leq 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 $的奇圈.折叠超立方体是加强超立方体中$ k = 1 $时的一种特殊情形, 关于折叠立方体的容错性能也有很多好的结果.文献[7]证明了在折叠超立方体$ FQ_{n}(n \geq 4) $中, 当$ |F_{v}| = 2n-3 $, $ FQ_{n}-F_{v} $中存在一个长度至少为$ 2^{n}-2|F_{v}| $的圈.文献[8]进一步推广上述结论, 证明了在折叠超立方体$ FQ_{n}(n \geq 3) $中, 若$ |F_{e}| + |F_{v}|\leq 2n-3 $, $ |F_{e}| \geq 1 $, 且$ FQ_{n} $中每个点至少关联两条无故障边, 则在$ FQ_{n}-Fv-Fe $中存在一个长度至少为$ 2^{n}-2|Fv| $的圈.文献[9]证明了当$ |F_{e}| + |F_{v}| \leq 2n-4 $和$ |F_{e}|\leq n-1 $时, $ Q_{n, k}(n \geq 4) $中能找到一条长为$ 2^{n}-2|F_{v}| $的容错圈.文献[10]证明了当$ |Fe| \leq 2n-3 $且$ Q_{n, k} $中每个点至少关联两条无故障边时, 若$ n $和$ k $有相同奇偶性, 则$ Q_{n, k} $是偶泛圈的；若$ n $和$ k $有不同奇偶性, 则在$ Q_{n, k} $中不仅可以构造长度从$ 4 $到$ 2^{n} $的偶圈, 而且还存在长度从$ n-k + 2 $到$ 2^{n}-1 $的奇圈.^[11]证明当$ n $和$ k $有相同的奇偶性时, $ Q_{n, k}(n \geq 3, 1 \leq k \leq n-1) $是$ n-2 $-边容错超哈密顿脆弱的, 也就是说, 若$ |Fe| \leq n - 2 $, $ FQ_{n}- F_{e} $中任意两个奇偶性不同的点之间存在一条长为$ 2^{n}-1 $的路.文献[4]研究了$ Q_{n, k} $的边泛圈问题, 证明了在无故障加强超立方体$ Q_{n, k} $中, 当$ n $和$ k $有相同奇偶性时, $ Q_{n, k} $中每一条边均在长度从$ 4 $到$ 2^{n}- 2 $的偶圈（即$ Q_{n, k} $是边偶泛圈的）；当$ n $和$ k $有不同奇偶性时, $ Q_{n, k} $中每一条边不仅均在长度从$ 4 $到$ 2^{n}-2 $的偶圈上, 而且还均在长度从$ n-k + 2 $到$ 2^{n}-1 $的奇圈上.然而关于故障加强超立方体中容错边泛圈的嵌入问题目前还没有相关研究结果, 本文对$ Q_{n, k} $的结构性质作了进一步探讨, 并证明当$ |F_{v}| = 1 $时, 若$ n $和$ k $有相同奇偶性, 则$ Q_{n, k} $中每一条边均在长度从$ 4 $到$ 2^{n}-2 $的偶圈上；当$ n $和$ k $有不同奇偶性时, $ Q_{n, k} $中每一条边不仅均在长度从$ 4 $到$ 2^{n}- 2 $的偶圈上, 而且还均在长度从$ n-k + 4 $到$ 2^{n}-3 $的奇圈上.特别的, 对于$ Q_{n, k} $中每一条$ j \in \{k, k + 1, \cdots, n, c\}- $维边, 它们还均在长度为$ n-k + 2 $的奇圈上.同时还证明了当$ |F_{v}| \leq n-2 $时, $ Q_{n, k} $$ (1 \leq k \leq n-2) $中每一条边均在长度从$ 4 $到$ 2^{n}-2|F_{v}| $的偶圈上.

文中没有说明的符号和定义参看文献[3].由于系统可以用图表示, 我们经常用图的概念来表示网络的概念. $ G = (V, E) $表示一个简单无向图, 其中$ V $为点集, $ E $为边集.设$ x $和$ y $是图$ G $中两顶点, 连接$ x $和$ y $长度为$ k $的$ xy $路(path), 记为$ xy $路或是$ P[x, y ] $, 是指点和边交替出现的序列$ P = v_{0}( = x)e_{1}v_{1}e_{2}v_{2}\cdots v_{i-1}e_{i}v_{i} \cdots e_{k}v_{k}( = y) $, 且除点$ x $和$ y $外, 其余的顶点互不相同, 边$ e_{i} $的端点是$ v_{i-1} $和$ v_{i} $, $ x $和$ y $称为$ P $的端点(end-vertices), 其余的顶点称为内部点(internal vertices). $ P $中边的数目$ k $称为$ P $的长度.两个端点相同的路称为圈(cycle).在简单图中, 路$ P $可以表示为$ P[v_{0}, v_{k}] = (v_{0}, v_{1}, v_{2}, \cdots, v_{k}) $.若$ v_{0} = v_{k} $, 则称$ P $为圈(cycle).包含图中所有顶点的路称为哈密顿路(hamiltonian path).包含图中所有顶点的圈称为哈密顿圈(hamiltonian cycle).图$ G $中最短圈的长度称为$ G $的围长(girth), 记为$ g(G) $.图$ G $中连接点$ u $和$ v $之间的最短路的长度称为两点间的距离(distance), 记为$ d_{G}(u, v) $.对于已知的图$ G $, 简记为$ d(u, v) $.图中任意两顶点$ u $和$ v $之间距离的最大值, 称为图的直径(diameter), 记为$ D(G) $.

如果图$ G $含有长为$ l $的圈, 其中$ g (G) \leq l \leq v(G) $, $ g (G) $是图$ G $的围长, $ v(G) $是图$ G $的阶, 称图$ G $是泛圈的.如果图$ G $是泛圈的, 则一定是哈密顿的.网络是否具有泛圈性可以度量该网络是否可以嵌入任意长度的圈.泛圈性的概念被推广到点泛圈性和边泛圈性.如果图$ G $的每个顶点位于长从$ g (G) $到$ v(G) $的圈上, 则称$ G $是点泛圈的(vertex-pancyclic).如果图的每条边位于长从$ g (G) $到$ v(G) $的圈上, 则称$ G $是边泛圈的(edge-pancyclic).显然, 边泛圈的图一定是点泛圈的.因为二部图不含奇圈, 故对二部图提出了偶泛圈的概念.如果图$ G $含有长为$ l $的偶圈, 其中$ g (G) \leq l \leq v(G) $, 称图$ G $是偶泛圈的(even-pancyclic).如果图$ G $中的任意两个顶点$ x $与$ y $之间长为$ l $的路, 其中$ d_{G}(x, y)\leq l \leq v(G)-1 $且$ 2 | l-d_{G}(x, y) $, 则称$ G $是偶泛连通的(even-panconnected).

$ n $维超立方体$ Q_{n} $是一个简单图, 其每个点$ x $都可以用一个长为$ n $的二元位串表示.即点集$ V (Q_{n}) = \{x_{1}x_{2}\cdots x_{n} : x_{i} = \{0, 1\}, i = 1, 2, \cdots, n\} $.两个顶点相邻当且仅当它们对应的字符串中有且只有一位不同, 即点$ x = x_{1}x_{2}\cdots x_{n} $和$ y $之间有边相连当且仅当$ y $满足：$ y = x_{1}x_{2}\cdots x_{i-1}\overline{x_{i}}x_{i+1}\cdots x_{n} $, $ \overline{x_{i}} = 1-x_{i} $. $ Q_{n} $中两个顶点$ x = x_{1}x_{2}\cdots x_{n} $和$ y = y_{1}y_{2}\cdots y_{n} $之间的Hamming距离定义为$ h(x, y) = \sum_{i = 1}^{n}|x_{i}-y_{i}| $, 即表示两顶点的二元字符串中对应的不同分量的个数（或表示为$ d_{H}(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 \in \{1, 2, \cdots, n\}\} $, 因此$ E(Q_{n}) = \bigcup_{i = 1}^{n}E_{i} $.

$ Q_{n, k} $作为超立方体的一种简单变型, 它的顶点集和$ Q_{n} $的顶点集一样, 只不过是通过在$ Q_{n} $中添加一些补边所得到的.它是这样定义的：

定义1  加强超立方体$ Q_{n, k} = (V, E) $$ (1\leq k \leq {n-1}) $是一个简单无向图.它和超立方体有一样的顶点集即$ V = \{x_1x_2\cdots x_n:x_i = 0\ \; \rm{or} \; 1 $, $ 1\leq i \leq n\} $.两顶点$ x = x_1x_2\cdots x_n $和$ y $有一条边相连当且仅当$ y $满足下列两个条件之一

(1) $ y = x_1x_2\cdots x_{i-1}\bar{x}_ix_{i+1}\cdots x_n, 1\leq i\leq n $, 或

(2) $ y = x_1x_2\cdots x_{k-1}\bar{x}_k\bar{x}_{k+1}\cdots \bar{x}_n $.

由加强超立方体$ Q_{n, k} $的定义可以看出加强超立方体$ Q_{n, k} $包含超立方体$ Q_n $作为它的子图.加强超立方体$ Q_{n, k} $是在超立方体$ Q_n $中添加$ 2^{n-1} $条补边（the complementary edge）后得到的, 即$ E(Q_{n, k}) = E_{c} \cup E(Q_{n}) $, 其中$ E_{c} = \{(u, \overline{u}) \in E(Q_{n, k})|h(u, \overline{u}) = n-k +1\} $为补边集.边$ (u, u^{i}) $为$ Q_{n, k} $中的$ i $-维超立方体的边, 于是$ E(Q_{n, k}) = E_{c} \cup E_{1 }\cup E_{2}\cup \cdots \cup E_{n} $.

记$ 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}\cap F_{c} $, $ |F_{e}^{c}| = f_{e}^{c} $, $ |F_{e}^{i}| = f_{e}^{i} $.

下面给出主要证明很重要的一些引理.

引理1  (见文献[12])在超立方体$ Q_{n}(n \geq 3) $中, 若$ f_{v}\leq n-2 $, 则$ Q_{n} $中每一条无故障边均在长度从$ 4 $到$ 2^{n}-2f_{v} $的圈上.

引理2  (见文献[13])加强立方体$ Q_{n, k}(1\leq k\leq n-1) $能够沿着顶点的第$ i(1\leq i\leq n) $个坐标将其分成两个子图.我们用$ Q_{n, k}^{i0} $和$ Q_{n, k}^{i1} $分别来表示这两部分.一个点$ x = x_1x_2\dots x_n $属于$ Q_{n, k}^{i0} $当且仅当该点的第$ i $位$ x_i = 0 $.同样地, 一个点$ x = x_1x_2\dots x_n $属于$ Q_{n, k}^{i1} $当且仅当该点的第$ i $位$ x_i = 1 $.当$ i<k $, $ Q_{n, k}^{i0} $和$ Q_{n, k}^{i1} $是两个$ (n-1) $ -维的加强立方体；当$ i\geq k $, $ Q_{n-1}^{i0} $和$ Q_{n-1}^{i1} $是两个$ (n-1) $ -维的超立方体.

引理3  (见文献[14])若$ f_{v} \leq n-2 $, 则$ Q_{n} $中任意两相邻节点之间均存在长度从$ 3 $到$ 2^{n}-2f_{v}-1 $的奇长的路.

引理4  (见文献[15]) $ Q_{n}(n \geq 3) $中, 任意两点$ u $和$ v $之间均存在长度为$ l $的路, 且$ d_{H}(u, v)\leq l \leq 2^{n}-1 $, 且$ l $与$ d_{H}(u, v) $同奇偶.

引理5  (见文献[16])如果$ |F_{e}| + |F_{v}|\leq n-2 $, 则$ Q_{n} $中任意两点$ u $和$ v $之间均存在长度为$ l $的路, $ d_{H}(u, v) + 2 \leq l \leq 2^{n}-2f_{v}-1 $, 且$ l $与$ d_{H}(u, v) $同奇偶, 其中$ f_{e} $表示$ Q_{n} $中故障边的数目, $ f_{v} $表示$ Q_{n} $中故障顶点的数目.

引理6  (见文献[1])设$ u $和$ v $是$ Q_{n} $中任意两点, 且$ d_{Q_{n}}(u, v) = d $, 则在$ Q_{n} $中存在$ n $条内点不交的路, 其中$ d $条长度为$ d $, $ n-d $条长度为$ d + 2 $.

引理7  (见文献[17])超立方体$ Q_{n}(n \geq 4) $中, 当$ f_{v} = n-1 $且$ Q_{n} $中每个点至少关联两个无故障点时, $ Q_{n} $中每一条边均在长度从$ 6 $到$ 2^{n }-2f_{v} $的偶圈上.

引理8  (见文献[15])超立方体$ Q_{n}(n\geq3) $中每一条边均在长度从$ 4 $到$ 2^{n } $的偶圈上.

首先讨论当$ |F_{v}| = 1 $时, 若$ n $和$ k $有相同奇偶性, 则$ Q_{n, k}(n \geq 4) $中每一条边均在长度从$ 4 $到$ 2^{n}-2 $的偶圈上；若$ n $和$ k $有不同奇偶性, 则$ Q_{n, k} $中每一条边不仅均在长度从$ 4 $到$ 2^{n }-2 $的偶圈上, 而且还均在长度从$ n-k +4 $到$ 2^{n}-3 $的奇圈上, 特别的对于$ Q_{n, k} $中每一条$ j \in \{k, k + 1, \cdots, n, c\} $ -维边它们还均在长度为$ n- k + 2 $的奇圈上, 而对于$ Q_{n, k} $中每一条$ j \in \{ 1, 2, \cdots, k-1\} $-维边则不能保证它们均在长度为$ n- k + 2 $的奇圈上, 例如$ Q_{4, 3} $中的$ 1 $-维边$ (0001, 1001) $就不在长度为$ n - k + 2 = 3 $的圈上, $ 2 $-维边$ (0101, 0001) $也不在长度为$ n-k+2 = 3 $的圈上, 但长在为$ 5 $的奇圈上, 即$ 0001 \rightarrow 1001 \rightarrow 1000 \rightarrow 0000 \rightarrow 0010 \rightarrow 0001 $.

定理1  当$ f_{v} = 1 $时, $ Q_{n, k}(n \geq 4) $中每一条边均在长度从$ 4 $到$ 2^{n}-2 $的偶圈上.

证明  由加强超立方体$ Q_{n, k} $的定义可知, $ V (Q_{n, k}) = V (Q_{n}) $, $ E(Q_{n, k}) = E_{c} \cup E(Q_{n}) $, 我们可以通过无故障边$ e $的分布来分如下两种情况来考虑：

当$ e \in E(Q_{n}) $时, 由引理$ 1 $, 则$ Q_{n} $中每一条无故障边均在长度从$ 4 $到$ 2^{n}-2 $的圈上.

当$ e \in E_{c} $时, 由引理$ 2 $, 将$ Q_{n, k} $按照$ k $维划分得到两个$ (n-1) $-维的立方体$ Q_{n-1}^{k0} $和$ Q_{n-1}^{k1} $, 即$ Q_{n, k} = Q_{n-1}^{k0}\cup Q_{n-1}^{k1} $.当$ e \in E_{c} $时, $ e $的两个端点分别在$ Q_{n-1}^{k0} $和$ Q_{n-1}^{k1} $中, 设$ e = (x, \overline{x}) $, $ x \in V (Q_{n-1}^{k0}) $, $ \overline{x} \in V (Q_{n-1}^{k1}) $.设$ F_{v}^{k0}(F_{v}^{k1}) $表示$ Q_{n-1}^{k0}(Q_{n-1}^{k0}) $中的故障点集, $ |F_{v}^{k0}| = f_{v}^{k0} $, $ |F_{v}^{k1}| = f_{v}^{k1} $.由于$ f_{v} = f_{v}^{k0}+ f_{v}^{k1} = 1 $, 不失一般性, 设$ f_{v}^{k0} = 1 $, $ f_{v}^{k1} = 0 $.因此$ Q_{n-1}^{k0} $中每个点在$ Q_{n-1}^{k0} $中均关联至少两个无故障点.设点$ y $是点$ x $在$ Q_{n-1}^{k0} $中的一个非故障邻点, 由$ f_{v}^{k1} = 0 $, 点$ \overline{y} $是$ Q_{n-1}^{i1} $中的非故障点.由引理$ 3 $, 在$ Q_{n-1}^{i0} $中, 点$ x $和$ y $之间存在长为$ l_{0} $的路$ P_{0} $, 其中$ 3 \leq l_{0} \leq 2^{n-1}-3 $.由于边$ (x, y) $是$ Q_{n-1}^{k0} $中一条无故障边, 因此, 在$ Q_{n-1}^{k0} $中, 点$ x $和$ y $之间存在长为$ l'_{0} $的路$ P'_{0} $, 其中$ 1 \leq l'_{0} \leq 2^{n-1}-3 $.由于$ d(x, y) = d(\overline{x}, \overline{y}) = 1 $, 由引理$ 4 $, 点$ \overline{x} $和点$ \overline{y} $之间存在长为$ l_{1 } $的路, 其中$ 1 \leq l_{1} \leq 2^{n-1}-1 $.于是可以构造圈$ C = (x, \overline{x})\cup P_{1}[\overline{x}, \overline{y}] \cup (\overline{y}, y) \cup P'_{0}[y, x] $, 其长度为$ l = l'_{0} +l_{1} +2 $, 由于$ 1\leq l'_{0} \leq 2^{n-1}-3 $, $ 1\leq l_{1}\leq 2^{n-1}-1 $, 于是$ 4\leq l \leq 2^{n}-2 $,

引理9  将$ Q_{n, k} $按照$ k $维划分得到两个$ (n-1) $-维的子立方体$ Q_{n-1}^{k0} $和$ Q_{n-1}^{k1} $, 设$ (x, x^{i}) $是$ Q_{n-1}^{k0} $中一条边$ ( i \neq k) $, 则点$ x^{k} $、$ \overline{x} $、$ (x^{i})^{k} $和$ \overline{x^{i}} $均在$ Q_{n-1}^{k1} $中.当$ i \in \{1, 2, \cdots, k - 1\} $, 则$ d_{H}(\overline{x}, (x^{i})^{k}) = d_{H}(x^{k}, \overline{x^{i}}) = n - k + 1 $；当$ i \in \{k + 1, k + 2, \cdots, n\} $, 则$ d_{H}(\overline{x}, (x^{i})^{k}) = d_{H}(x^{k}, \overline{x^{i}}) = n - k - 1 $.

证明  当$ i \in \{1, 2, \cdots, k - 1\} $, 设$ x = x_{1}\cdots x_{i}\cdots x_{k}x_{k+1}\cdots x_{n} $, 则

$ x^{i} = x_{1}\cdots \overline{x}_{i}\cdots x_{k}x_{k+1} \cdots x_{n}, \overline{x} = x_{1}\cdots x_{i}\cdots \overline{x}_{k}\overline{x}_{k+1}\cdots \overline{x}_{n}, $

$ \overline{x^{i}} = x_{1}\cdots \overline{x}_{i}\cdots \overline{x}_{k}\overline{x}_{k+1}\cdots \overline{x}_{n}, x^{k} = x_{1}\cdots x_{i}\cdots \overline{x}_{k}x_{k+1} \cdots x_{n}, $

$ (x^{i})^{k} = x_{1}\cdots \overline{x}_{i}\cdots \overline{x}_{k}x_{k+1}\cdots x_{n}, $

故$ d_{H}(x, x^{i}) = 1 $, 则$ d_{H}(\overline{x}, (x^{i})^{k}) = d_{H}(x^{k}, \overline{x^{i}}) = n - k + 1 $.

当$ i \in \{k+1, k+2, \cdots, n\} $, 设$ x = x_{1}\cdots x_{k}x_{k+1} \cdots x_{i}\cdots x_{n} $, 则

$ x^{i} = x_{1}\cdots x_{k}x_{k+1} \cdots \overline{x}_{i}\\ \cdots x_{n}, \overline{x} = x_{1}\cdots \overline{x}_{k}\overline{x}_{k+1} \cdots \overline{x_{i}} \cdots \overline{x}_{n}, $

$ \overline{x^{i}} = x_{1}\cdots \overline{x}_{k}\overline{x}_{k+1} \cdots x_{i}\cdots \overline{x}_{n}, x^{k} = x_{1}\cdots \overline{x}_{k}x_{k+1}\cdots x_{i}\\ \cdots x_{n}, $

$ (x^{i})^{k} = x_{1}\cdots \overline{x}_{k}x_{k+1}\cdots \overline{x}_{i}\cdots x_{n}, $

故$ d_{H}(x, x^{i}) = 1 $, 则$ d_{H}(\overline{x}, (x^{i})^{k}) = d_{H}(x^{k}, \overline{x^{i}}) = n - k - 1 $.

引理10  当$ f_{v} = 1 $时, 则$ Q_{n} $中任意两个不同的非故障点$ u $和$ v $之间均存在任意长度为$ l $的无故障路, 其中$ d_{H}(u, v) \leq l \leq 2^{n} - 3 $, 且$ l $与$ d_{H}(u, v) $同奇偶.

证明  由$ f_{v} = 1 $及引理5, $ Q_{n} $中任意两个不同的非故障点$ u $和$ v $之间存在长度为$ l $的无故障路, $ d_{H}(u, v)+2 \leq l \leq 2^{n}-3 $, 其中$ l $与$ d_{H}(u, v) $同奇偶.故我们只需要证明$ Q_{n} $中任意两个不同的非故障点$ u $和$ v $之间存在长度为$ d_{H}(u, v) $的无故障路.当$ d_{H}(u, v) = 1 $时, 即$ (u, v) $为一条非故障边, 此时, 点$ u $和$ v $之间存在长度为$ 1 $的无故障路；当$ d_{H}(u, v)\geq 2 $时, 由引理6可知, 若$ Q_{n} $中没有故障点, 那么$ Q_{n} $中点$ u $和$ v $之间存在$ d_{H}(u, v) $条内点不相交的路, 其长度为$ d_{H}(u, v) $.由于$ f_{v} = 1 $, 故$ Q_{n} $中点$ u $和$ v $之间存在至少$ d_{H}(u, v)-1 (\geq 1) $条内点不相交的路, 其长度为$ d_{H}(u, v) $.于是当$ f_{v } = 1 $时, 则$ Q_{n} $中任意两个不同的非故障点$ u $和$ v $之间均存在长度为$ l $的无故障路, $ d_{H}(u, v)\leq l \leq 2^{n}-3 $, 其中$ l $与$ d_{H}(u, v) $同奇偶.

定理2  当$ f_{v} = 1 $且$ n $和$ k $具有不同奇偶性时, $ Q_{n, k}(n \geq 4) $中每一条边均在长度从$ n - k + 4 $到$ 2^{n} - 3 $的奇圈上, 特别的对于$ Q_{n, k} $中每一条$ j \in \{k, k + 1, k + 2, \cdots, n, c\} $-维边均在长度为$ n - k + 2 $的奇圈上.

证明  由引理2, 将$ Q_{n, k} $按$ k $维划分得到两个$ (n-1) $-维的立方体$ Q_{n-1}^{k0} $和$ Q_{n-1}^{k1} $, 即$ Q_{n, k} = Q_{n-1}^{k0}\cup Q_{n-1}^{k1} $.设$ F_{v}^{k0} (F_{v}^{k1}) $表示$ Q_{n-1}^{k0} ( Q_{n-1}^{k1}) $中的故障点集, $ |F_{v}^{k0}| = f_{v}^{k0} $, $ |F_{v}^{k1}| = f_{v}^{k1} $.由于$ f_{v} = f_{v}^{k0} + f_{v}^{k1} $, 不失一般性, 我们可以假设$ f_{v}^{k0} = 1 $, 且$ f_{v}^{k1} = 0 $, 即$ Q_{n-1}^{k0} $中只存在一个故障点, $ Q_{n-1}^{k1} $是一个无故障超立方体.由加强超立方体$ Q_{n, k} $的定义可知, $ V (Q_{n, k}) = V (Q_{n}) $, $ E(Q_{n, k}) = E_{c}\cup E(Q_{n}) $, 可以通过无故障边$ e $的分布来分如下两种情况来讨论.

情形1   $ e \in E(Q_{n-1}^{k0}) $, 设$ e = (x, x^{i}) $, 则$ i \in \{1, 2, \cdots, k - 1, k+1, \cdots, n\} $.

由引理1, 在$ Q_{n-1}^{k0} $中存在长为$ l_{0} $的含边$ e $的圈$ C_{0} $, 其中$ 4 \leq l_{0} \leq 2^{n-1} - 2 $.设$ (u, v) $是圈$ C_{0} $上不同于边$ e $的一条边, 则$ C_{0} $可分解为两段, 即边$ (u, v) $和连接点$ u, v $的通过边$ e $一条路$ P_{0}[v, u] $, 即$ C_{0} = (u, v) \cup P_{0}[v, u] $, 且$ 3 \leq l(P_{0}) \leq 2^{n-1} - 3 $.又由于边$ (x, x^{i}) $是$ Q_{n-1}^{k0} $中的一条无故障边, 因此在$ Q_{n-1}^{k0} $中存在含边$ e $的长度为$ l'_{0} $的路$ P'_{0} $, 其中$ 1 \leq l'_{0} \leq 2^{n-1}-3 $.由于$ d_{H}(u, v) = 1 $, 由引理9, 有$ d_{H}(\overline{u}, v^{k}) = n - k + 1 $（或者$ n - k - 1 $）, 因为$ n $和$ k $有不同奇偶性, 那么$ n - k + 1 $（或者$ n - k - 1 $）为偶数.由于$ Q_{n-1}^{k1} $是一个无故障超立方体, 由引理4, 在$ Q_{n-1}^{k1} $中, 点$ \overline{u} $和点$ v^{k} $之间存在长度为$ l_{1} $的路$ P_{1} $, 其中$ l_{1} $为偶数, $ n - k + 1 \leq l_{1}(P_{1}) \leq 2^{n-1} - 2 $.于是可以构造圈$ C = P'_{0}[u, v] \cup (v, v^{k}) \cup P_{1}[v^{k}, \overline{u}] \cup (\overline{u}, u) $, 其长度为$ l = l'_{0} + l_{1} + 2 $.由于$ 1 \leq l'_{0} \leq 2^{n-1 }- 3 $且$ n - k + 1 \leq l_{1}(P_{1}) \leq 2^{n-1} - 2 $, 故$ n - k + 4 \leq l \leq 2^{n} - 3 $.即$ Q_{n, k} $中每一条边均在长度从$ n - k + 4 $到$ 2^{n} - 3 $的奇圈上.事实上, 上述长度为$ n - k + 4 $的圈是通过如下方式构造出来的, 即$ (x, x^{i}) \cup (x^{i}, (x^{i})^{k}) \cup P_{1}[(x^{i})^{k}, \overline{x}] \cup (\overline{x}, x) $是一个包含边$ e = (x, x^{i}) $的长度为奇数$ l_{1} + 3 $, 其中$ n - k + 4 \leq l_{1} + 3 \leq 2^{n-1} - 3 $.

下面单独考虑$ Q_{n-1}^{k0} $中的$ j(\in \{k+1, k+2, \cdots, n\}) $-维边$ e = (x, x^{j}) $.设$ l_{min} $表示含边$ e $的且长度最短的圈长.因为$ d_{H}(x, x^{j}) = 1 $, 故由引理9, $ d_{H}(x, (x^{i})^{k}) = n-k-1 $.因为$ n $和$ k $有不同奇偶性, 那么$ n-k-1 $为偶数.由引理4, 在$ Q_{n-1}^{k0} $中, 点$ x $和点$ (x^{i})^{k} $之间存在长度为$ l'_{1} $的最短路$ P'_{1} $, 其中$ l'_{1} = n-k-1 $.构造圈$ C = (x, \overline{x})\cup P'_{1}[\overline{x}, (x^{i})^{k}]\cup((x^{i})^{k}, x^{i})\cup(x^{i}, x) $, 其最短长度为$ l_{min} = l'_{1} + 3 $, 即$ l_{min} = n - k + 2 $.因此对于$ Q_{n-1}^{k0} $中的每一条$ j(\in \{ k+1, k+2, \cdots, n\}) $-维边, 它们还均在长度为$ n - k + 2 $的奇圈上.

情形2  $ e \in E(Q_{n-1}^{k1}) $, 设$ e = (y, y^{i}) $, 则$ i \in \{1, 2, \cdots, k - 1, k+1, \cdots, n \} $.

由于$ Q_{n-1}^{k1} $是一个无故障超立方体, 故由引理4, 点$ y $与点$ y^{i} $之间存在长度为$ l_{1} $的路$ P_{1}[y, y^{i}] $, 其长度为$ 1 \leq l_{1} \leq 2^{n-1}-1 $, 即在$ Q_{n-1}^{k1} $中存在含边$ e $的圈$ C_{1} = P_{1}[y, y^{i}]\cup(y^{i}, y). $设边$ (u, v) $是圈$ C_{1} $上不同于边$ e $的一条边, 那么$ C_{1} = P_{1}[u, v] \cup (v, u) $.由于$ Q_{n-1}^{k1} $中只有一个故障点, 故集合$ \{\overline{u}, v^{k}\} $和$ \{u^{k}, \overline{v}\} $中至少有一个集合里面元素均为非故障点, 不失一般性, 我们可以假设集合$ \{\overline{u}, v^{k}\} $中元素均为非故障的.因为$ d_{H}(u, v) = 1 $, 由引理9, $ d_{H}(\overline{u}, v^{k}) = n - k + 1 $（或者$ n - k - 1 $), 因为$ n $和$ k $有不同奇偶性, 那么$ n - k + 1 $（或者$ n - k - 1 $）为偶数.由于$ Q_{n-1}^{k0} $中中只有一个故障点, 故由引理10, 在$ Q_{n-1}^{k0} $中, 点$ \overline{u} $和点$ v^{k} $之间存在长度为$ l_{0} $的路$ P_{0} $, 其中$ n - k + 1 \leq l_{0} \leq 2^{n-1} - 4 $.存在圈$ C = P_{1}[u, v] \cup (v, v^{k}) \cup P_{0}[v^{k}, \overline{u}] \cup (\overline{u}, u) $, 长度为$ l = l_{0} + l_{1} + 2 $.由于$ 1 \leq l_{1} \leq 2^{n-1} - 1 $且$ n - k + 1 \leq l_{0} \leq 2^{n-1} - 4 $, 故$ n - k + 4 \leq l \leq 2^{n} - 3 $.即$ Q_{n-1}^{k1} $中每一条边均在长度从$ n - k + 4 $到$ 2^{n} - 3 $的奇圈上.

下面单独考虑$ Q_{n-1}^{k1} $中的$ j(\in \{k + 1, k + 2, \cdots, n\}) $-维边$ e = (x, x^{j}) $.设$ l_{min} $表示含边$ e $的且长度最短的圈长.由于$ Q_{n-1}^{k0} $中只有一个故障点, 故集合$ \{\overline{y}, (y^{i})^{k}\} $和$ \{y^{k}, \overline{y^{i}}\} $中至少有一个集合里面元素均为非故障点, 不失一般性, 我们可以假设集合$ \{\overline{y}, (y^{i})^{k}\} $中元素均为非故障的.因为$ d_{H}(y, y^{i}) = 1 $, 故由引理9, $ d_{H}(\overline{y}, (y^{i})^{k}) = n - k -1 $.由于$ Q_{n-1}^{k0} $中只有一个故障点, 由引理10, 在$ Q_{n-1}^{k0} $中, 点$ \overline{y} $和点$ (y^{i})^{k} $之间存在长度为$ l'_{0} $的最短路$ P'_{0} $, 其中$ l'_{0} = n - k - 1 $.构造圈$ C = (y, y^{i}) \cup (y^{i}, (y^{i})^{k}) \cup P'_{0}[(y^{i})^{k}, \overline{y}] \cup (\overline{y}, y) $, 其最短长度为$ l_{min} = l'_{0}+3 $, 即$ l_{min} = n-k+2 $.因此对于$ Q_{n-1}^{k1} $中的每一条$ j(\in \{k+1, k+2, \cdots, n\}) $-维边, 它们还均在长度为$ n - k + 2 $的奇圈上.

情形3  $ e \in E_{k} $, 设$ e = (x, x^{k}) $, 其中$ x \in V (Q_{n-1}^{k0}) $且$ x^{k} \in V (Q_{n-1}^{k1}) $.

由于$ Q_{n-1}^{k0} $中只有一个故障点, 故$ Q_{n-1}^{k0} $中每个点至少关联两个无故障点(对于$ n \geq 4 $).设$ x^{i} $为$ x $的一个无故障邻点.由引理3, 在$ Q_{n-1}^{k0} $中, 点$ x $和点$ x^{i} $之间存在长度为$ l_{0} $的路$ P_{0} $, 其中$ 3 \leq l_{0} \leq 2^{n-1} - 3 $.我们知道边$ (x, x^{i}) $是$ Q_{n-1}^{k0} $中一条无故障边, 因此点$ x $和点$ x^{i} $之间存在长度为$ l'_{0} $的路$ P'_{0} $, 其中$ 1 \leq l'_{0}\leq 2^{n-1} - 3 $.因为$ d_{H}(x, x^{i}) = 1 $, 故由引理9, $ d_{H}(x^{k}, \overline{x^{i}}) = n - k + 1 $ (或者$ n - k - 1 $).因为$ n $和$ k $有不同奇偶性, 那么$ n - k + 1 $ (或者$ n - k - 1 $)为偶数.由引理4, 点$ x^{k} $和点$ \overline{x^{i}} $之间存在长度为$ l_{1} $的路$ P_{1 } $, 其中$ n-k +1 \leq l_{1} \leq 2^{n-1}-2 $.圈$ C = P'_{0}[x, x^{i}] \cup (x^{i}, \overline{x^{i}}) \cup P_{1}[\overline{x^{i}}, x^{k}] \cup (x^{k}, x) $为所求, 其长度为$ l' = l'_{0}+l_{1}+2 $, 由于$ 1 \leq l'_{0}\leq 2^{n-1}-3 $且$ n-k+1\leq l_{1} \leq 2^{n-1}-2 $, 故$ n-k+4 \leq l' \leq 2^{n}-3 $, 即$ Q_{n, k} $中每一条$ k $-维边均在长度从$ n - k + 4 $到$ 2^{n}-3 $的奇圈上.设$ l_{min} $表示含边$ e $的且长度最短的圈长.由于$ d_{H}(x, \overline{x}) = n-k +1 $, 那么$ d_{H}(x^{k}, \overline{x}) = n-k $.由引理4, 点$ x^{k} $和点$ x $之间存在一条长度为$ l'_{1} $的最短路$ P'_{1} $, 其中$ l'_{1} = l(P'_{1}) = n-k $.我们可以构造一个含边$ e $的且长度最短的圈$ C_{min} = (x, x^{k})\cup P'_{1}[x^{k}, \overline{x}]\cup(\overline{x}, x) $, 其长度为$ l_{min} = l'_{1} +2 = n-k +2 $, 故$ Q_{n, k} $中每一条$ k $-维边均在长度从$ n - k + 2 $到$ 2^{n} - 3 $的奇圈上.

情形4  $ e \in E_{c } $, 设$ e = (x, \overline{x}) $, 其中$ x \in V (Q_{n-1}^{k0}) $且$ \overline{x} \in V (Q_{n-1}^{k1}) $.

因为$ d_{H}(x, \overline{x}) = n - k + 1 $, 由引理10, 在$ Q_{n}(\subseteq Q_{n, k}) $中, 点$ x $和点$ \overline{x} $之间存在长为$ l' $的路$ P' $, 其中$ n - k + 1 \leq l' \leq 2^{n} - 4 $.我们可以构造圈$ C = P'[x, \overline{ x}] \cup (\overline{x}, x) $, 其长度为$ l = l' + 1 $, 即$ n - k + 2 \leq l \leq 2^{n} - 3 $.

综上所述, 定理得证.

下面研究在故障点数更多的情况下加强超立方体中边泛圈的嵌入问题, 可以证明当$ |F_{v}| \leq n - 2 $时, $ Q_{n, k}(1 \leq k \leq n - 2) $中每一条边均在长度从$ 4 $到$ 2^{n} - 2f_{v} $的偶圈上.

定理3  当$ f_{v} \leq n - 2 $时, $ Q_{n, k}(1 \leq k \leq n - 2, n\geq 4) $中每一条边均在长度从$ 4 $到$ 2^{n} - 2f_{v} $的偶圈上.

证明  由加强超立方体$ Q_{n, k} $的定义可知, $ V (Q_{n, k}) = V (Q_{n}) $, $ E(Q_{n, k}) = E_{c} \cup E(Q_{n}) $, 由无故障边$ e $的分布我们可以分如下两种情况来考虑：

当$ e\in E(Q_{n}) $时, 由引理1, $ Q_{n} $中每一条边均在长度从4到$ 2^{n} - 2f_{v} $的圈上.

当$ e \in E_{c} $时, 设$ e = (x, \overline{x}) $.由引理2, $ Q_{n, k} = Q_{n-1}^{n0}\cup Q_{n-1}^{n1} $.设$ x \in V (Q_{n-1}^{n0}) $, $ \overline{x} \in V (Q_{n-1}^{n1}) $.由于$ f_{v} = f_{v}^{n0} + f_{v}^{n1}\leq n-2 $, 分以下两种情况讨论

情形1  $ 1 \leq f_{v}^{n0}\leq n - 3 $, $ 1 \leq f_{v}^{n1}\leq n - 3 $.

由于点$ x $在$ Q_{n-1}^{n0} $中有$ n - 1 $个邻点, 故$ x $在$ Q_{n-1}^{n0} $中有$ n-1 - f_{v}^{n0} $个非故障邻点, 而$ n-1 - f_{v}^{n0}\geq n - 2 -f_{v}^{n0}\geq f_{v} - f_{v}^{n0} = f_{v}^{n1} $, 即点$ x $在$ Q_{n-1}^{n0} $中的非故障邻点总数大于在$ Q_{n-1}^{n1} $中的故障点数, 那么在$ Q_{n-1}^{n0} $中存在$ x $的一个无故障邻点$ x^{i} $使得$ \overline{x^{i}} $为$ Q_{n-1}^{n1} $中的一个非故障点.由引理3, 在$ Q_{n-1}^{n0} $中, 点$ x $和点$ x^{i} $之间存在长度为$ l_{1} $的路$ P_{1} $, 其中$ 3 \leq l_{1} \leq 2^{n-1} - 2f_{v}^{n0}- 1 $, 而$ (x, x^{i}) $为一条非故障边, 故在$ Q_{n-1}^{n0} $中, 点$ x $和点$ x^{i} $之间存在长度为$ l'_{1} $的路$ P'_{1} $, 其中$ 1 \leq l'_{1}\leq 2^{n-1} - 2f_{v}^{n0}- 1 $.由于$ Q_{n-1}^{n0} $中点$ x $与$ x^{i} $是相邻的, 同理, 由引理3, 在$ Q_{n-1}^{n1} $中, 点$ \overline{x} $和点$ \overline{x^{i}} $之间存在长度为$ l_{2} $的路$ P_{2} $, 其中$ 3 \leq l_{2} \leq 2^{n-1} - 2f_{v}^{n1} -1 $, 而$ (\overline{x}, \overline{x^{i}}) $为一条非故障边, 故在$ Q_{n-1}^{n1} $中, 点$ \overline{x} $与点$ \overline{x^{i}} $之间存在长度为$ l'_{2} $的路$ P'_{2} $, 其中$ 1 \leq l'_{2}\leq 2^{n-1} - 2f_{v}^{n1} -1 $.故补边$ (x, \overline{x}) $在长度为的$ l $圈$ C $上, 其长度$ l = l'_{1} +l'_{2} +2 $, 即$ 4 \leq l \leq 2^{n} - 2f_{v} $.

情形2  $ f_{v}^{n0}\leq n - 2 $, $ f_{v}^{n1} = 0 $.

此时, $ Q_{n-1}^{n1} $不含故障节点, 故障点全部分布在$ Q_{n-1}^{n0} $中, 由于$ Q_{n-1}^{n0} $中每点有$ n -1 $个邻点, 而故障点总数不会超过$ n-2 $, 故$ Q_{n-1}^{n0} $中每点至少关联两个无故障点, 或者存在一个点同时与$ n-2 $个故障点相邻.下面分这两种情况讨论:

情形2.1  若$ Q_{n-1}^{n0} $中每点至少关联两个无故障点, 设$ x $在$ Q_{n-1}^{n0} $中的一个无故障邻点为$ x^{i} $, 由引理7, 在$ Q_{n-1}^{n0} $中, 边$ (x, x^{i}) $在长度为$ l_{1} $的圈上, $ 6 \leq l_{1} \leq 2^{n-1} - 2f_{v} $, 故在$ Q_{n-1}^{n0} $中, 点$ x $与点$ x^{i} $之间存在长度为$ l'_{1} $的路$ P'_{1} $, 其中$ 1 \leq l'_{1} \leq 2^{n-1} - 2f_{v} -1 $.由引理8, 在$ Q_{n-1}^{n1} $中, 边$ (\overline{x^{i}}, \overline{x}) $在长度为$ l_{2} $的圈上, $ 4 \leq l_{2} \leq 2^{n-1} $.故在$ Q_{n-1}^{n1} $中, 点$ \overline{x} $与点$ \overline{x^{i}} $之间存在长度为$ l'_{2} $的路$ P'_{2} $, 其中$ 1 \leq l'_{2} \leq 2^{n-1}-1 $.故补边($ x, \overline{x}) $在长度为的$ l $圈$ C $上, 其长度$ l = l'_{1} +l'_{2} +2 $, 即$ 4 \leq l \leq 2^{n} - 2f_{v} $.

情形2.2  若$ Q_{n, k} $中$ n - 2 $个故障点同时与点$ x $相邻, 由于$ k \leq n - 2 $, 则存在某个$ j \in \{k, k + 1, \cdots, n, c\} $使得$ x^{j} $为一个故障点, 将$ Q_{n, k} $按照$ j $维划分得到两个子立方体$ Q_{n-1}^{j0} $和$ Q_{n-1}^{j1} $, 即$ Q_{n, k} = Q_{n-1}^{j0}\cup Q_{n-1}^{j1} $.设$ f_{v}^{j0} $与$ f_{v}^{j1} $分别表示$ Q_{n-1}^{j0} $和$ Q_{n-1}^{j1} $中故障点的数量, 那么$ f_{v}^{j0}\leq n-3 $且$ f_{v}^{j1} = 1 $, 与情况1讨论方法一样, 我们可以得到补边$ (x, \overline{x}) $在长度为的$ l $圈上, 其长度为$ 4 \leq l \leq 2^{n }- 2f_{v} $.

综上所述, 定理得证.

网络是否具有泛圈性可以度量该网络是否可以嵌入任意长度的圈.加强超立方体是超立方体的变形结构, 其连通性、安全性、可靠性以及传输延迟等性质都优于超立方体, 对其性能和容错性的研究是非常重要的.本文主要探讨含有故障点的加强超立方体的边泛圈性.得到了如下结论

(1) 当$ |F_{v}| = 1 $时, 若$ n $和$ k $有相同奇偶性, 则$ Q_{n, k} $中每一条边均在长度从4到$ 2^{n} - 2 $的圈上；当$ n $和$ k $有不同奇偶性时, $ Q_{n, k} $中每一条边不仅均在长度从4到$ 2^{n} - 2 $的偶圈上, 而且还均在长度从$ n - k + 4 $到$ 2^{n} - 3 $的奇圈上, 特别的对于$ Q_{n, k} $中每一条$ j(\in \{k, k + 1, \cdots, n, c\}) $-维边它们还均在长度为$ n- k + 2 $的奇圈上.

(2) 当$ |F_{v}| \leq n - 2 $时, $ Q_{n, k} $中每一条边均在长度从4到$ \; 2^{n} - 2|F_{v}| $的偶圈上.当$ n $和$ k $有不同奇偶性时, 对含有更多故障节点和故障边的加强超立方体$ Q_{n, k} $的边奇泛圈性质的研究是下一步的工作.