0 引言

设M是图G中的边子集且M中任意两条边无公共端点，则称M为G的一个匹配。若|G|为偶数，G中匹配M满足|M|=|G|/2，则称M为G的一个完美匹配。若|G|为奇数，G中匹配M满足|M|=(|G|－1)/2，则称M为G的一个几乎完美匹配。若图G中存在完美匹配或几乎完美匹配，则称G是可匹配的；否则称G是不可匹配的。对于图G中任意一点v，G中所有与v相邻的点构成的集合称为v的邻域，记为N_G(v)；G中与点v相关联的边的数目称为v的度，记为d_G(v)。若V(G)可以划分成两个非空子集X和Y，使得每条边都有一个端点在X中，另一个端点在Y中，则称G为一个二部图，(X, Y)为G的一个二分类。对于文中其他未加定义而被使用的图论术语和记号参见文献[1]。

并行计算机系统通常以某个无向简单图G=(V(G), E(G))作为其基本的互连网络，其中V(G)中每个顶点对应一个处理器，E(G)中每条边对应一对处理器之间的一条直接通信线路。对于某些特定的系统，要求其互连网络中每个处理器在任意时间都需要被指定一个与其配对的处理器，这些处理器对之间通过相互通信协同工作，整个系统才能正常运行。为了优化资源配置、降低通信延迟，人们希望这样的处理器对之间是通过直接的物理连线连接的。在此背景下，Brigham等^[2]提出了互连网络的匹配排除问题，即一个互连网络中至少需要多少条边发生故障才可以使该网络是不可匹配的。在实际构建的系统中元器件和通信信道发生故障是随机的、不可预知的，互连网络中某些点和边可能同时发生故障。基于这一考虑，Park等^[3]对匹配排除问题进行了推广，提出了互连网络的强匹配排除问题。设G=(V(G), E(G))是一个无向简单图，F⊆V(G)∪E(G)为G中的故障集。若G\F是不可匹配的，则称F为G的一个强匹配排除集。G的含元素最少的强匹配排除集中元素的个数称为G的强匹配排除数，记为smp(G)。若G中强匹配排除集F满足|F|=smp(G)，则称F为G的一个最小强匹配排除集。近来，互连网络的强匹配排除问题得到了大量的关注^[4-5]。对于带有故障诊断算法的系统，系统发生故障导致出现孤立点的可能性很小。Park等^[6]于2013年对条件故障下(即假定系统不会由于发生故障而产生孤立点)互连网络的强匹配排除问题进行了研究。称图G中相应的强匹配排除集为G的条件强匹配排除集，相应的强匹配排除数记为smp₁(G)。

k元n方体(k≥2, n≥1)，记为Q_n^k，是一个具有kⁿ个顶点的正则连通图，其中任一顶点可标号为u=u₁u₂…u_n，这里对于任一整数i(1≤i≤n)均有0≤u_i≤k－1。两个顶点u=u₁u₂…u_n和v=v₁v₂…v_n相邻当且仅当存在j∈{1, 2, …, n}，使得u_j=v_j±1(mod k)且对于任意的l∈{1, 2, …, n}\{j}均有u_l=v_l。这样的一条边(u, v)称为Q_n^k的一条j维边。为了便于表述，下文类似之处省略“(mod k)”。对于1≤d≤n，通过去除Q_n^k中所有的d维边，可以将Q_n^k沿d维划分为Q_(d)[0], Q_(d)[1], …, Q_(d)[k－1]，其中Q_(d)[p]为Q_n^k的由点集{u=u₁u₂…u_d…u_n∈V(Q_n^k):u_d=p}导出的子图，这里0≤p≤k－1。容易得出，Q_(d)[p]和Q_n－1^k是同构的。k元n方体是并行计算机系统最常用的互连网络拓扑结构之一，其具有易执行、低延迟和高带宽等优良的性质。k元n方体已经得到了广泛的研究^[7-10]。目前，以k元n方体为互连网络构建的著名并行计算机系统有iWarp^[11]、Cray T3E^[12]以及IBM Blue Gene^[13]等。Wang等在文献[7]和文献[8]中分别研究了k元n方体的匹配排除问题和强匹配排除问题。本文将对条件故障下k元n方体的强匹配排除问题进行研究。

1 主要结果

由定义可知，图中一个条件强匹配排除集是一个特殊的强匹配排除集。下面的性质显然成立。

性质1  若图G中有强匹配排除集和条件强匹配排除集，则smp(G)≤smp₁(G)。

性质2^[6]  对于图G中的一条路(u, z, v)，构造故障集F_uzv如下：

1)F_uzv包含(N_G(u)∩N_G(v))\{z}中的每个点；

2) 若(u, v)∈E(G)，F_uzv包含边(u, v)；

3) 对任意的w∈N_G(u)\N_G(v)，F_uzv或者包含w或者包含(u, w)；

4) 对任意的w∈N_G(v)\N_G(u)，F_uzv或者包含w或者包含(v, w)。

若G\F_uzv不含孤立点且|G\F_uzv|为偶数，则F_uzv为G的一个条件强匹配排除集。

性质2给出了在图G中构造条件强匹配排除集的一种简单而且直观的方法，称这种类型的条件强匹配排除集为平凡的。显然，对于G中任一平凡的条件强匹配排除集F_uzv，有|F_uzv|=d_G(u)+d_G(v)－2－g_G(u, v)，其中${g_G}\left( {u, v} \right) = \left\{ \begin{array}{l} \left| {{N_G}\left( u \right) \cap {N_G}\left( v \right)} \right|, \;\;\;\;\;\left( {u, v} \right) \in E\left( G \right)\\ \left| {{N_G}\left( u \right) \cap {N_G}\left( v \right)} \right|-1, \;\;\;\left( {u, v} \right) \notin E\left( G \right) \end{array} \right. $。

引理1^[8]  设k≥3为整数，smp(Q₁^k)=2。

注意到Q^k₁为一个长为k的圈。当3≤k≤5时，设F为Q^k₁中任一故障集，易知或者Q^k₁\F是可匹配的或者Q^k₁\F含有孤立点，即此时Q^k₁中无条件强匹配排除集。

定理1  设k≥6为整数，smp₁(Q₁^k)=2。

证明 当k为奇数时，设F={k－1, (2, 3)}；当k为偶数时，设F={(0, k－1), (2, 3)}。无论k为奇数还是偶数，Q^k₁\F不含孤立点且被划分为两条点不交的含有奇数个顶点的路。显然，Q^k₁\F是不可匹配的，这意味着smp₁(Q^k₁)≤2。由性质1和引理1知，2=smp(Q^k₁)≤smp₁(Q^k₁)。因此，smp₁(Q^k₁)=2。证毕。

注:定理1的证明中构造的条件强匹配排除集是平凡的，但是不是所有的Q^k₁(k≥6) 的条件强匹配排除集都是平凡的。例如，设F={(0, 9), (4, 5)}为Q₁¹⁰中的故障集，此时Q₁¹⁰\F是不可匹配的且不含孤立点，而F不是一个平凡的条件强匹配排除集；设F={10, (4, 5)}为Q₁¹¹中的故障集，此时Q₁¹¹\F是不可匹配的且不含孤立点，而F不是一个平凡的条件强匹配排除集。

引理2^[6]  设G为m正则连通二部图，其中m≥3，则smp₁(G)=2且G中任一个最小条件强匹配排除集均由同一部集中的两个点构成。

定理2  设k≥4为偶整数，n≥2为整数。令V₁={u₁u₂…u_n:u₁u₂…u_n∈V(Q_n^k), $\sum\limits_{i = 1}^n {{u_i}} $=0(mod 2)}，V₂=V(Q_n^k)\V₁，则smp₁(Q_n^k)=2且Q_n^k中任一个最小条件强匹配排除集均由V₁或V₂中的两个点构成。

证明 对任意的u₁u₂…u_n∈V₁，设v₁v₂…v_n∈N_Qn^k(u₁u₂…u_n)。由定义，存在j∈{1, 2, …, n}，使得u_j=v_j±1(mod k)且对于任意的l∈{1, 2, …, n}\{j}均有u_l=v_l。由于k为偶数，可知u_j与v_j奇偶性不同。故$\sum\limits_{i = 1}^n {{u_i}} $与$\sum\limits_{i = 1}^n {{v_i}} $有不同奇偶性，这意味着v₁v₂…v_n∈V₂。同理可证，对于V₂中任一点，其邻点必在V₁中。因此，Q_n^k为一个二部图，且(V₁, V₂)为它的一个二分类。注意到Q_n^k是2n正则连通图。由引理2可知，smp₁(Q_n^k)=2且任一个最小条件强匹配排除集均由V₁或V₂中的两个点构成。证毕。

引理3  设k≥3为整数，n≥1为整数，则有：

1) 若Q_n^k中的圈C至少含某两维的边，则|C|≥4。

2) 若k≥4，则Q_n^k中不含3圈。

证明 设C=(u₁¹u₂¹…u_n¹, u₁²u₂²…u_n², …, u₁^pu₂^p…u_n^p, u₁¹u₂¹…u_n¹)为Q_n^k中的一个圈。

1) 假定C中至少含某两维的边。断言如下：若C中包含r维边(其中1≤r≤n)，则C中至少有两条r维边。若不然的话，假定C中只有一条r维边，不失一般性设(u₁¹u₂¹…u_n¹, u₁²u₂²…u_n²)为C中的r维边。由定义可知，u_r¹=u_r²±1(mod k)且对于任意的l∈{1, 2, …, n}\{r}均有u_l¹=u_l²。注意到(u₁²u₂²…u_n², u₁³u₂³…u_n³)，(u₁³u₂³…u_n³, u₁⁴u₂⁴…u_n⁴)，…，(u₁^p－1u₂^p－1…u_n^p－1, u₁^pu₂^p…u_n^p)均不是r维边。由定义可知，u_r²=u_r³=…=u_r^p－1=u_r^p。因此u_r¹≠u_r^p，这与(u₁^pu₂^p…u_n^p, u₁¹u₂¹…u_n¹)不是C中r维边矛盾。断言证毕。由断言可知，若C中至少含某两维的边，则|C|≥2×2=4。

2) 假定C中仅含r维边(其中1≤r≤n)。由定义可知，对于任意的l∈{1, 2, …, n}\{r}均有u_l¹=u_l²=…=u_l^p。此时必有|C|=k。结合(1) 中结论可知，当k≥4时，Q_n^k中任一个圈的长度均大于等于4，这意味着Q_n^k中不含3圈。证毕。

引理4  设k≥3为整数，n≥1为整数。对于任意两个不同的点u, v∈V(Q_n^k)，|N_Qn^k(u)∩N_Qn^k(v)|≤2。

证明 对n用归纳法来证明结论成立。当k≥3且n=1时，Q_n^k为一个长为k的圈。对于任意两个不同的点u, v∈V(Q_n^k)，此时有|N_Qn^k(u)∩N_Qn^k(v)|≤|N_Qn^k(u)|=2。假设k≥3且n≥2时，对于任意两个不同的点u, v∈V(Q_n－1^k)有|N_Qn－1^k(u)∩N_Qn－1^k(v)|≤2。设u=u₁u₂…u_n和v=v₁v₂…v_n为Q_n^k中任意两点，考虑以下两种情形：

1) 存在d∈{1, 2, …, n}使得u_d=v_d。

将Q_n^k沿d维划分为Q_(d)[0], Q_(d)[1], …, Q_(d)[k－1]。此时，u, v∈V(Q_(d)[u_d])。断言如下：对任意的w=w₁w₂…w_n∈V(Q_n^k)\V(Q_(d)[u_d])，w∉N_Qn^k(u)∩N_Qn^k(v)。若不然的话，假定w∈N_Qn^k(u)∩N_Qn^k(v)，那么(u, w)和(v, w)均为d维边，即对于任意的l∈{1, 2, …, n}\{d}均有u_l=w_l=v_l。这意味着u=v，与条件矛盾。断言证毕。由断言可知，|N_Qn^k(u)∩N_Qn^k(v)|=|N_Q(d)[u_d](u)∩N_Q(d)[u_d](v)|。注意到Q_(d)[u_d]和Q_n－1^k是同构的。由归纳假设可知，|N_Q(d)[u_d](u)∩N_Q(d)[u_d](v)|≤2。因此，|N_Qn^k(u)∩N_Qn^k(v)|≤2。

2) 对任意d∈{1, 2, …, n}有u_d≠v_d。

将Q_n^k沿1维划分为Q₍₁₎[0], Q₍₁₎[1], …, Q₍₁₎[k－1]。此时，u∈V(Q₍₁₎[u₁])，v∈V(Q₍₁₎[v₁])。断言如下：对任意的w=w₁w₂…w_n∈V(Q_n^k)\(V(Q₍₁₎[u₁])∪V(Q₍₁₎[v₁]))，w∉N_Qn^k(u)∩N_Qn^k(v)。若不然的话，假定w∈N_Qn^k(u)∩N_Qn^k(v)。那么(u, w)和(v, w)均为1维边，即对于任意的l∈{2, 3, …, n}均有u_l=w_l=v_l，与情形假设矛盾。由断言可知，N_Qn^k(u)∩N_Qn^k(v)⊆V(Q₍₁₎[u₁])∪V(Q₍₁₎[v₁])。若N_Qn^k(u)∩N_Qn^k(v)∩V(Q₍₁₎[u₁])=Ø，则|N_Qn^k(u)∩N_Qn^k(v)∩V(Q₍₁₎[u₁])|=0。若存在x=x₁x₂…x_n∈N_Qn^k(u)∩N_Qn^k(v)∩V(Q₍₁₎[u₁])，则x₁=u₁且(v, x)为1维边。此时，对于任意的l∈{2, 3, …, n}均有x_l=v_l。可知，x=u₁v₂…v_n是唯一的，即|N_Qn^k(u)∩N_Qn^k(v)∩V(Q₍₁₎[u₁])|=1。因此，|N_Qn^k(u)∩N_Qn^k(v)∩V(Q₍₁₎[u₁])|≤1。同理可证，|N_Qn^k(u)∩N_Qn^k(v)∩V(Q₍₁₎[v₁])|≤1。从而可知，|N_Qn^k(u)∩N_Qn^k(v)|=|N_Qn^k(u)∩N_Qn^k(v)∩V(Q₍₁₎[u₁])|+ |N_Qn^k(u)∩N_Qn^k(v)∩V(Q₍₁₎[v₁])|≤2。

综上可知，对于任意两个不同的点u, v∈V(Q_n^k)，|N_Qn^k(u)∩N_Qn^k(v)|≤2。证毕。

引理5  设k≥3为整数，n≥2为整数。若Q_n^k中任意两点u=u₁u₂…u_n和v=v₁v₂…v_n满足|N_Qn^k(u)∩N_Qn^k(v)|=2，则(u, v)∉E(Q_n^k)。

证明 反证法。假设(u, v)∈E(Q_n^k)。设N_Qn^k(u)∩N_Qn^k(v)={w, x}。此时，(u, v, w, u)和(u, v, x, u)均为Q_n^k中的3圈。由引理3可知，此时k=3，(u, v, w, u)仅含某一维的边且(u, v, x, u)也仅含某一维的边。不失一般性，设(u, v, w, u)仅含d维边(1≤d≤n)，则(u, v)，(u, w)和(u, x)均为d维边。由定义，u在Q_n^k中有且仅有两条d维边，矛盾。故假设不成立。

证毕。

定理3  设k≥3为奇整数，n≥2为整数，则min{|F_uzv|:F_uzv为Q_n^k中平凡的条件强匹配排除集}=4n－3。

证明 由引理4和引理5可知，对于任意两个不同的点u, v∈V(Q_n^k)，g_Qn^k(u, v)≤1。注意到Q_n^k是2n正则的。设F_uzv为Q_n^k中任一条路(u, z, v)对应的平凡的条件强匹配排除集，则|F_uzv|=4n－2－g_Qn^k(u, v)≥4n－3。

设(u, z, v)=(0000…0, 0100…0, 1100…0) 为Q_n^k中一条路，V₁={x:x∈N_Qn^k(0000…0)\{0100…0, 1000…0}}，V₂={y:y∈N_Qn^k(1100…0)\{0100…0, 1000…0}}。令F_uzv^*={1000…0, (u, x), (v, y):x∈V₁, y∈V₂}。易知，Q_n^k\F_uzv^*不含孤立点且|Q_n^k\F_uzv^*|=kⁿ－1为偶数。故F_uzv^*为Q_n^k中一个平凡的条件强匹配排除集且|F_uzv^*|=2(2n－2)+1=4n－3。

综上可知，min{|F_uzv|:F_uzv为Q_n^k中平凡的条件强匹配排除集}=4n－3。证毕。

引理6^[8]  设k≥3为奇整数，n≥2为整数，则smp(Q_n^k)=2n。进一步地，Q_n^k中任一个最小强匹配排除集F满足Q_n^k\F中有一个孤立点且|Q_n^k\F|为偶数。

定理4  设k≥3为奇整数，n≥2为整数，则2n+1≤smp₁(Q_n^k)≤4n－3。

证明 设Q_n^k中的故障集F⊆V(Q_n^k)∪E(Q_n^k)满足|F|≤2n且Q_n^k\F不含孤立点。由引理6可知，Q_n^k\F是可匹配的，这意味着smp₁(Q_n^k)>2n，即smp₁(Q_n^k)≥2n+1。

由定义，smp₁(Q_n^k)≤min{|F_uzv|:F_uzv为Q_n^k中平凡的条件强匹配排除集}。由定理3可知，smp₁(Q_n^k)≤4n－3。证毕。

由定理4，显然有下面的结论成立。

推论1  设k≥3为奇整数，则smp₁(Q₂^k)=5。

2 结语

目前，随着高性能并行计算机技术的发展，人们越来越关注具有优良性能的互连网络拓扑结构。互连网络的容错性是衡量互连网络性能的关键指标，它主要考虑在发生故障时网络中某些特有性质的保持能力。本文对条件故障下使得Q_n^k中不存在完美匹配或几乎完美匹配所需要的最小故障数smp₁(Q_n^k)进行了研究。对于k≥4为偶数且n≥2，得出了smp₁(Q_n^k)的精确值并刻画了其所有相应的最小故障集；对于k≥3为奇数且n≥2，给出了该参数一个较好的界，推论1表明得出的上下界是可达的。这一结论可以帮助工程师更精确地分析有故障发生时k元n方体的可匹配性，为设计以k元n方体为拓扑结构的互连网络提供理论参考。当k≥3为奇数且n≥3时，smp₁(Q_n^k)精确值的计算是值得进一步研究的方向。