师海忠，王国亮

(西北师范大学数学与数学统计学院，兰州 730070)

互连网络是并行处理系统的重要组成部分。互连网络常被模型化为一个无向图，图的顶点对应处理机，图的边对应网络的通讯连线［1-3］。1989 年 S.B.Akers等［8］提出了互连网络群模型，1998年师海忠［5］提出了互连网络环模型，并于2011年又提出了互连网络向量图模型［7］。完全对换网络是利用群模型设计出来的一类互连网络。容错性是互连网络的一个重要性质。互连网络的容错性是指该网络能容忍多少组件或连线同时发生故障，剩余的子网络中仍然含有某些特殊结构并能正常工作。基于此，Becker和Simon等［12-14］研究了在n维超级立方体网络中使每个(n-k)维子立方体网络失灵的失灵边的最小数目fH(n，k)，并给出了相关结果。Latifi等［9-11］研究了在n维星网络中使每个(n-k)维子星网络失灵的失灵点和失灵边的最小数目Fs(n，k)和fs(n，k)，并给出相关结果。随后，Shiying Wang等［15］研究了在 n维冒泡排序网络中使每个(n-k)维子冒泡排序网络失灵的失灵点和失灵边的最小数目FB(n，k)和fB(n，k)，并给出了相关结果。本文研究在n维完全对换网络中使每个(n-k)维子完全对换网络失灵的失灵点和失灵边的最小数目，分别记为FCT(n，k)和 fCT(n，k)。

1 概念及基本性质

定义1 设G是一个有限群，e是它的单位圆，Ω={g1，g2，…，gn}是 G 的一个生成子集且满足:1)gi∈Ω⇒g-1i∈Ω;2)e∉Ω。Cayley图 Γ=(G，Ω)是一个简单图，它的顶点集和边集分别如下［2］:

定义2 一个对换就是指交换2个数的位置所得的置换。对换图是一个无环图，它有n个顶点，分别用符号 1，2，…，n 来表示，它的边(i，j)对应于一个对换，即在1，2，…，n中把i和j交换得到的置换，称这个图为对换图［6］。

定义3 完全对换网络是特殊的Cayley图Γ(Sn，Ω)，其中Sn是n 个符号1，2，…，n 上的对称群，Sn的生成集 Ω={(i，j)1≤i＜j≤n，(这里(i，j)表示交换i和j的位置得到的置换)}，即Ω对应的对换图为n阶完全图［4］，简记为CTn。完全对换网络CT3和CT4如图1所示。

性质1 完全对换网络CTn有n!个顶点，n(n-1)n!/4条边，且是 n(n-1)/2正则二部图，它是顶点可迁和边可迁的，其直径为n-1。

令 Λn为符号集{1，2，…，n-1，n，X}，其中 X表示与数字不相关的符号。CTn的每个子完全对换网络能被Λn中的字符串通过重复X唯一表示。显然，符号X的数目决定了子完全对换网络的维数。例如X3X2X是一个子完全对换网络CT3，它包含了以下 6 个顶点:{13425，13524，43125，43521，53124，53421}，共有 n种方法划分 CTn为 n个不相交的CTn-1，即通过固定第1到第n位的数字来实现。

图1 完全对换网络CT3和CT4(相同字母的边被省去)

2个CTn-k在CTn中是不相交的，如果它们没有共同的顶点;2个CTn-k在CTn中是不相同的，如果它们的顶点集不同。根据以上定义，可以得到如下重要性质:

性质2 给定 2个整数 n≥1，k∈{0，1，…，n-1}，则在CTn中含有k!个不相交的CTn-k和k!个不相同的 CTn-k。这里=表示从n个物体中取出k个物体的组合数。

证明 当k=0时，显然成立。下证当k≥1时结论成立。根据2个CTn-k在CTn中是不相交的定义可知:从n个数中取出k个数，并把这k个数全排列，其余(n-k)个数均为X，则构成的CTn-k没有相同的顶点，即共有 k!个不相交的。根据2个CTn-k在CTn中是不相同的定义可知:把上述取出的k个数放在n个位置中的第k个位置上，共有种放法。则构成CTn-k的顶点集不同，即共有k!个不相同的CTn-k。

2 主要结果

fCT(n，k)(或 FCT(n，k))表示在 n 维完全对换网络CTn中，使每个(n-k)维子完全对换网络失灵的失灵边(或点)的最小数目。为了以下引理的完整性，令fCT(n，n-1)=+∞。由性质2可得如下引理:

引理1 给定一个整数 k∈{0，1，…，n-1}，则k!≤FCT(n，k)≤fCT(n，k)≤k!。

证明 由性质2可知，CTn中含有k!个不相交的CTn-k，若使所有不相交的CTn-k失灵，则在每个CTn-k中须至少出现1个失灵点，故k!≤FCT(n，k)。令F是一个在CTn中使每个CTn-k失灵的失灵边最小数目的边集，对F中的每条边，可以选取每条边上的一个顶点，则个失灵点可以使CTn中所有 CTn-k失灵，故 FCT(n，k)≤=fCT(n，k)，fCT(n，k)的上界可以通过使每个 CTn-k中的一条边失灵得到。结合以上不等式得:k!≤FCT(n，k)≤fCT(n，k)≤k!。

以下定理给出FCT(n，k)和fCT(n，k)在一些特殊情况下的精确值。

定理1 CTn是n维完全对换网络，则

1)FCT(n，0)=fCT(n，0)=1;

2)FCT(n，1)=n;

3)当 n≥2 时，FCT(n，n-1)=n!;

4)当 n≥3 时，FCT(n，n-2)=n!/2;

5)当n≥2 时，fCT(n，n-2)=n(n-1)n!/4。

证明

1)CTn中的任意一条边都能使CTn失灵，则fCT(n，0)≤1。由引理 1 知:fCT(n，0)≥1，故 FCT(n，0)=fCT(n，0)=1;

2)由性质2知:在CTn中含有n2个不相同的CTn-1，顶点 123…n将使 n个 CTn-1即 1Xn-1，X2Xn-2，X23Xn-3，…Xn-1n 都失灵;对每个 2≤i≤n-1，顶点i(i+1)…n1…(i-1)将使 n个CTn-1即 iXn-1，X(i+1)Xn-2，X2(i+2)Xn-3，…，Xn-1(i-1)都失灵;顶点n12…(n-1)将使n个CTn-1即nXn-1，X1Xn-2，X22Xn-3，…Xn-1(n-1)都失灵。这样 FCT(n，1)≤n，由引理 1 知:FCT(n，1)≥n，故FCT(n，1)=n。

3)给定一个整数n≥2。事实上，要使CTn中的每个CT1失灵，则须使CTn的所有点失灵，故FCT(n，n-1)=n!。

4)给定一个整数n≥3。令(Y，V(CTn)Y)是CTn的一个二部划分，Y中的每个顶点失灵保证了CTn中的所有CT2失灵，则FCT(n，n-2)≤n!/2，由引理1 知:FCT(n，n-2)≥n!/2，故 FCT(n，n-2)=n!/2。

5)给定一个整数n≥3。要使CTn中所有CT2失灵，实际上就是使CTn中所有边都失灵，故fCT(n，n-2)=n(n-1)n!/4。

定理2 当 n=4或 n=5时，fCT(n，1)=n+4。

证明 当n=4时，可以找到以下8条失灵边使CT4中所有 CT3失灵，失灵边如下:1XX2，XX23，X23X，23XX，3XX4，XX41，X41X，41XX，则fCT(4，1)≤8。由引理3 知:fCT(4，1)≥8，故 fCT(4，1)=8。当n=5时，可以找到以下9条边使CT5中所有 CT4失灵，失灵边如下:1X2X3，X2X34，2X34X，X34X5，34X5X，4X5X1，X5X12，5X12X，X12X3，则 fCT(5，1)≤9。由引理 3 知:fCT(5，1)≥9，故 fCT(5，1)=9。

综上所述，当 n=4或 n=5时，fCT(n，1)=n+4。

当n≥6时，定理3将给出 fCT(n，1)的精确值，为了更好地理解定理3的证明过程，首先给出如下例子:

例1 当n=7时，使CT7中所有CT6失灵的失灵边见表1。

表1 失灵边

由表1可以看出，后一条失灵边是由前一条失灵边按下述方式得到:

1)当失灵边的第1位是X时，后一条失灵边由该失灵边作个循环即可。例如:前一条失灵边为X234X56，后一条失灵边由该失灵边作个循环，即为234X56X。

2)当失灵边的第1位不是X时，后一条失灵边由该失灵边从第2位开始，各个位上的X或数字都向前移动一位，最后一位数字填上从后往前的第1位数字加1(注意:当该数字为7+1时取为1)。最后，当2个X第2次分别位于第(7-3)和第7位时停止。

根据性质2知:完全对换网络CT7中含有49个不相同的CT6，该表的前9条失灵边使CT7中的45个CT6失灵，而最后一条边使余下的4个CT6失灵，所以这10条边可使CT7中的所有CT6都失灵，即 fCT(7，1)≤10。又由引理 3知:fCT(7，1)≥10，故 fCT(7，1)=10。

更一般地，对任意整数n≥6，有如下定理:

定理3 当n≥6时，fCT(n，1)=n+3。

证明 通过以下方法构造使CTn中所有CTn-1失灵的失灵边最小数目的边集。

第1步 首先选择1X23…(n-3)X(n-2)作为失灵边。

第2步 后一条失灵边是由前一条失灵边得到，具体方法如下:

1)当失灵边的第1位是X时，后一条失灵边由该失灵边作个循环即可。例如:前一条失灵边为X234X56，后一条失灵边由该失灵边作个循环，即为234X56X。

2)当失灵边的第1位不是X时，后一条失灵边由该失灵边从第2位开始各个位上的X或数字都向前移动1位，最后一位数字填上从后往前的第1位数字加1(注意:当该数字为n+1时取为1)。

第3步 当2个X第2次分别位于第(n-3)和第n位时停止。

引理4 当 n是素数时，Fs(n，2)=n(n-1)［10］。这里，Fs(n，2)是使 Sn中所有 Sn-2失灵的失灵点的最小数目。

当n是素数，k=2时，定理4将给出FCT(n，2)的精确值，为了更好地理解定理4的证明过程，给出下面的例子。

例2 当n=5，k=2时，使完全对换网络CT5中所有CT3失灵的失灵点构造如下:选择标号为(1，1+I，1+2I，1+3I，1+4I)的顶点，其中 1≤I≤4。当括号里的数字超过5时，取其模5的值。由以上选择，可得到以下 4个顶点{(12345)，(13524)，(14253)，(15432)}，让这4 个顶点都循环绕动一周，则每个顶点可生成5个标号不同的顶点，这4个顶点共生成20个标号不同的顶点，这20个顶点作为星网络S5中的失灵点时，每个顶点可使S5中的6个S3失灵，但作为完全对换网络CT5的失灵点时，每个顶点可使CT5中的10个CT3失灵(因为星网络的第1位总是X)，故这20个顶点可使CT5中的200个CT3失灵，即FCT(5，2)≤20。由引理2知:由于 FCT(5，2)≥20，因此FCT(5，2)=20。

更一般地，当n是素数，k=2时，有如下定理:

定理4 当n是素数时，FCT(n，2)=n(n-1)。

证明 通过以下方法构造失灵点集。

第1 步 选取标号为(1，1+I，1+2I，…，1+(n-1)I)的顶点，其中1≤I≤n-1。当括号里的数字超过n时，取其模n的值。

第2步 让上一步中所得的每个顶点都循环绕动一周。

通过以上方法共得到n(n-1)个标号不同的顶点，这n(n-1)个顶点作为Sn中的失灵点时，每个顶点可使个Sn-2失灵，而这n(n-1)个顶点作为CTn中的失灵点时，每个顶点可使个CTn-2失灵，即CTn中的每个失灵点比Sn中的每个失灵点多失灵()个。由引理4知:这n(n-1)个顶点可使 Sn中2!个 Sn-2失灵，所以这 n(n-1)个顶点可使 CTn中的 2!个失灵，而CTn中共有2!个CTn-2，即这n(n-1)个顶点可使CTn中所有的 CTn-2失灵，也就是说，FCT(n，2)≤n(n-1)。由引理 2 知:FCT(n，2)≥n(n-1)，故 FCT(n，2)=n(n-1)。

猜想 当0≤k≤n-1时，FCT(n，k)=k!

由以上定理知:该猜想对 k=0，1，n-2，n-1成立;对k=2，n为素数时也成立。

当k=2时，如下定理给出了 fCT(n，2)与fS(n，2)之间的关系。

定理5 对任意素数n，fCT(n，2)=fS(n，2)+2n(n-1)，这里 fCT(n，2)是使 CTn中所有 CTn-2失灵的失灵边的最小数目，fS(n，2)是使Sn中所有Sn-2失灵的失灵边的最小数目。

证明 由文献［9］知，若把使Sn中所有Sn-2失灵的失灵边排成1个矩阵，这个矩阵的行数为失灵边的最小数目，这个矩阵的列数为n，并且这个矩阵有如下特性:除这个矩阵的第1列外，从其余(n-1)列中任意选取2列，选取的这2列中都将出现的所有组合数。同样，若把使CTn中所有CTn-2失灵的失灵边排成一个矩阵，这个矩阵的行数为失灵边的最小数目，这个矩阵的列数为n，并且这个矩阵有如下特性:从这这个矩阵n列中任意选取2列，选取的这2列中都将出现的所有组合。若把Sn中使所有Sn-2失灵的失灵边作为CTn中使CTn-2失灵的失灵边时，则在CTn中共有n(n-1)(n-2)个CTn-2没有失灵，且在CTn失灵边的最小数目组成的矩阵中，没有出现的组合数的列数为:第1列和第2列，第1列和第3列，第1列和第4列…，第1列和第 n列。选取以下边集:

从以上边集可以看出:在前n(n-1)条边中，每条边可以使个CTn-2失灵，这n(n-1)条边共使n(n-1)(n-3)个CTn-2失灵;在后n(n-1)条边中，每条边可以使个 CTn-2失灵，这n(n-1)条边共使2n(n-1)个 CTn-2失灵，即这2n(n-1)条边可使余下的n(n-1)(n-1)个CTn-2失灵。这些边集和Sn中选取的使所有Sn-2失灵的失灵边集构成的矩阵，在其中任意选取2列都会出现的所有组合数，并且选取的这些边集是最优的，因此 fCT(n，2)=fS(n，2)+2n(n-1)。

引理5 对任意素数 n，fS(n，2)=3n(n-1)［11］。

由引理5和定理5可得推论1。

推论1 对任意素数n，fCT(n，2)=5n(n-1)。

引理6 当n不是素数时，fS(n，2)≤(n-1)n(p-1)，p是大于等于 n 的最小素数［9］。

由引理6和定理5可得推论2。

推论2 当n不是素数时，fCT(n，2)≤(n-1)n(p-1)+2n(n-1)，p是大于等于n的最小素数。

3 结束语

本文研究了在n维完全对换网络中使每个(n-k)维子完全对换网络失灵的失灵点和失灵边的最小数目FCT(n，k)和 fCT(n，k)，并给出了相关结果。然而关于完全对换网络CTn中FCT(n，k)和fCT(n，k)(2≤k≤n-3)的精确值尚未知，另外关于完全对换网络的其它性质还有待于进一步研究。

［1］Bondy J A，Marty U S R.Graph Theory［M］.London:Springer，2008.

［2］徐俊明，组合网络理论［M］.北京:科学出版社，2007.

［3］高随祥.图论与网络流理论［M］.北京:高等教育出版社，2009.

［4］Lakshmivarahan S，Jwo J S，Dhall S K.Symmetry in interconnection networks based on Cayley graphs of permutation groups:A survey［J］.Parallel Computing，1993.19:361-407.

［5］师海忠.互连网络的代数环模型［D］.北京:中国科学院数学与系统科学研究院应用数学研究所，1998.

［6］师海忠，路建波.关于互连网络的几个猜想［J］.计算机工程与应用，2008，44(31):112-115.

［7］师海忠，牛攀峰，马继勇，侯斐斐.互连网络的向量图模型［J］.运筹学学报，2011，15(3):115-123.

［8］Akers S B，krishnamurthy B.A group-theoretic model for symmetric interconnection networks［J］.IEEE Transactions on Computers，1989，38(4):555-565.

［9］Shahram Latifi，Ebrahim Saberinia，Xiaolong Wu，Robustness of star graph network under link failure［J］.Information Sciences，2008，178(3):802-806.

［10］Shahram Latifi，A study of fault tolerance in star graph［J］.Information Processing Letters，2007，102(5):196-200.

［11］David Walker，Shahram Latifi，Improving bounds on link failure tolerance of the star graph［J］.Information Sciences，2010，180(13):2571-2575.

［12］Jung-Sheng Fu，Fault-free Hamiltonian cycles in twisted cubes with conditional link faults［J］.Theoretical Computer Science，2008，407(1-3):318-329.

［13］Bernd Becker，Hans-Ulrish Simon，How robust is the ncube?［C］//Proceeding of 27th Annual Symposium on Foundations of Computer Science.［S.l.］:［s.n.］，1986:283-291.

［14］Tung-Yang Ho，Ting-Yi Sung，Lih-Hsing Hsu，Anote on edge fault tolerance with respect to hypercubes［J］.Applied Mathematics Letters，2005，18(10):1125-1128.

［15］Shiying Wang，Yuxing Yang，Fault tolerance in bubblesort graph networks［J］.Theoretical Computer Science，2012，421:62-69.