(n-m,k-m)-星图子网络的可靠性评估

摘要

多处理器系统互连网络的子网络可靠性是衡量系统性能的一个关键指标。为了刻画（n,k）-星图中（n-m,k-m）-星图子网络的容错性能，在概率故障条件下分析了（n,k）-星图中存在无故障（n-m,k-m）-星图子网络的概率。对于1≤k≤n-1和1≤m≤k-1，得出了（n-m,k-m）-星图子网络存在概率的上下界的理论公式，给出了仅考虑点故障的（n,k）-星图的无故障（n-m,k-m）-星图子网络的搜寻算法，并基于蒙特卡罗模拟提出了评估无故障（n-m,k-m）-星图子网络的存在概率的近似方法。实验结果表明，随着顶点可靠性逐渐变小，得出的（n-m,k-m）-星图子网络存在概率的上下界与近似评估结果基本吻合；当顶点可靠性较高或（n-m,k-m）-星图子网络存在概率的上下界相差较大时，利用基于蒙特卡罗的近似方法可以得出较为精确的评估结果。

关键词

多处理器系统 / 互连网络 / (n,k)-星图 / 概率故障 / 蒙特卡罗

Key words

multiprocessor system / interconnection network / (n,k)-star graph / probabilistic failure / Monte Carlo

0 引言

多处理器系统已经成为解决科学与工程计算领域重大挑战性问题的必备工具，系统互连网络的结构性质对系统的性能起着不可忽视的作用。在构建实际多处理器系统时，除了要考虑系统的性能之外，还要充分考虑系统的制造成本。这使得系统互连网络的诸多设计要求之间包含着矛盾，选择网络时只能在不同要求中寻找一种均衡。超立方体网络^［1］和星图网络^［2］是较早被设计出的互连网络，已经被广泛应用于实际系统的构建。当今多处理器系统的应用范围越来越广，为了满足日益多元化的计算需求，又有许多互连网络被相继提出，如 k元 n方体网络^［3］、（n，k）-星图网络^［4］和cactus-based网络^［5］等。作为星图网络的推广，（n，k）-星图网络不仅保留了星图网络的许多优良性质（如对称性、可嵌入性等），而且在规模的选取上更加灵活^［4］。近来人们对（n，k）-星图的网络性质进行了一系列的研究。Chiang等^［6］确定了（n，k）-星图的直径和平均距离；Cheng等^［7］研究了（n，k）-星图的强匹配排除问题；Chang等^［8-9］分别在Preparata-Metze-Chien（PMC）模型与比较诊断模型下分析了（n，k）-星图的条件诊断度；Feng^［10］在点故障模型下给出了使得（n，k）-星图中不存在（n-m，k-m）-星图子网络所需要破坏的最小点数的上下界；Kumar等^［11］对（n，k）-星图的定向直径进行了研究。

在实际中，一些特定计算任务（如计算量不大但可靠性要求较高的任务）的调度算法只需要系统指派某个子网络来执行，这样不仅能使系统资源得到有效利用，而且可以规避大规模网络有效性差的缺点。基于这一考虑，学者们广泛关注互连网络的无故障子网络存在概率估计问题。Das等^［12］根据 n维超立方体的结构性质给出了 n维超立方体中存在无故障子超立方体的概率的计算公式。Chang等^［13］给出了不同点可靠性下无故障（n-1）维子超立方体的存在概率的计算方法；与Das等^［12］的方法相比，Chang等^［13］提出的方法在确保结果精度的同时具有更优的计算效率。近年来，采用Chang等^［13］提出的方法，许多互连网络的无故障子网络存在概率估计问题得到了研究^［14-19］。

（n，k）-星图的无故障子网络存在概率估计研究可以为基于（n，k）-星图网络构建的实际系统的任务调度算法设计提供理论参考。Li等^［20］分析了（n，k）-星图中无故障（n-1，k-1）-星图子网络的存在概率；但（n，k）-星图中任意规模子网络的存在概率估计尚未研究，这在一定程度上限制了（n，k）-星图网络在实际系统中的应用。基于此，本文将在不同点可靠性下评估（n，k）-星图中无故障（n-m，k-m）-星图子网络（ m \ge \mathrm{1}）的存在概率。

1 基本概念和性质

本文中没有解释说明而直接运用的图论术语及记号参见文献［21］。假定正整数 i和 j且满足 j \le i，令 〈i〉表示 \left\{\mathrm{1,2},\cdots ,i\right\}， A_i^j表示 i ! / ( i - j ) !。（n，k）-星图（ n和 k为整数且满足 \mathrm{1} \le k \le n - \mathrm{1}），记作 S_{n,k}，其顶点集为 V \left(S_{n,k}\right) = \left\{u_{\mathrm{1}}{u}_{\mathrm{2}}\cdots u_k\left|u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_k\in 〈n〉\right.\right. \left.\mathrm{且它}\mathrm{们两}\mathrm{两互}\mathrm{不相}\mathrm{同}\right\} \mathrm{。}两个顶点 u_{\mathrm{1}} u_{\mathrm{2}} \cdots u_k和 v_{\mathrm{1}} v_{\mathrm{2}} \cdots v_k相邻当且仅当以下两个条件之一成立：

（1） 存在一个整数 \mathrm{2} \le i \le k使得 u_{\mathrm{1}} = v_i , v_{\mathrm{1}} = u_i且对于所有的 \mathrm{2} \le s \le k \left(s\ne i\right)均有 u_s = v_s；

（2） u_{\mathrm{1}} \ne v_{\mathrm{1}}且对于所有的 \mathrm{2} \le s \le k均有 u_s = v_s。

由 S_{n,k}的定义可知， S_{n,k}是一个具有 A_n^k = n ! / \left(n-k\right) !个顶点的 \left(n-\mathrm{1}\right)-正则图。 S_{\mathrm{4,2}}和 S_{\mathrm{4,3}}如图1所示。

给定正整数 n , k , m满足 \mathrm{1} \le k \le n - \mathrm{1}， \mathrm{1} \le m \le k - \mathrm{1}。设 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m为满足 的 m个整数。设 a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}为 〈n〉中 m个两两互不相同的数，记点集

M = \left\{b_{\mathrm{1}}{b}_{\mathrm{2}}\cdots b_{i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{1}}}{b}_{i_{\mathrm{1}}+\mathrm{1}}\cdots b_{i_{\mathrm{2}}-\mathrm{1}}\right. a_{i_{\mathrm{2}}} b_{i_{\mathrm{2}}+\mathrm{1}} \cdots a_{i_m} b_{i_m+\mathrm{1}} \cdots b_k : b_{\mathrm{1}} , b_{\mathrm{2}} , \cdots , \left.b_{i_{\mathrm{1}}-\mathrm{1}},b_{i_{\mathrm{1}}+\mathrm{1}},\cdots ,b_{i_{\mathrm{2}}-\mathrm{1}},b_{i_{\mathrm{2}}+\mathrm{1}},\cdots ,b_{i_m+\mathrm{1}},\cdots ,b_k\in 〈n〉\backslash \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}\mathrm{且它}\mathrm{们两}\mathrm{两互}\mathrm{不相}\mathrm{同}\right\}

（特别地，若 i_m = k，则 b_{i_m+\mathrm{1}} \cdots b_k为空字符串）。显然， S_{n,k}中由 M导出的子图与 S_{n-m,k-m}同构。为了方便表述，用长度为 k的字符串 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}来表示 S_{n,k}中由 M导出的子图（本文称这种表示为 S_{n,k}的子网络简化表示），这里 X^t = \underset{t}{\underbrace{XX\cdots X}}。将 S_{n,k}中与 S_{n-m,k-m}同构的子图称为 S_{n-m,k-m}子网络。

引理1^［10］ S_{n,k}中共有 \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) n ! / \left(n-m\right) !个不同的 S_{n-m,k-m}子网络且任意一个 S_{n-m,k-m}子网络可用某个 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}唯一表示，其中 \mathrm{1} \le m \le k - \mathrm{1}。

2 无故障 S_{n-m,k-m}子网络的存在概率估计

2.1　理论分析

在实际中，许多多处理器系统在构建通信链路时会采用冗余设计的策略以确保通信的稳定（该情形下系统的链路故障往往可以忽略不计）^［17］。基于这一背景，本文对概率故障条件下（假定不考虑 S_{n,k}中的边故障， S_{n,k}中各个顶点具有相同的可靠性且发生故障相互独立） S_{n,k}中无故障 S_{n-m,k-m}子网络的存在概率进行估计。

根据引理1可知， S_{n,k}中不同的 S_{n-m,k-m}子网络共有 \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) n ! / \left(n-m\right) !个。将 S_{n,k}中第 i个 S_{n-m,k-m}子网络不存在故障点记为事件 A_i，这里 \mathrm{1} \le i \le \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) n ! / \left(n-m\right) !。记 S_{n,k}中顶点的可靠性概率为 p。令 R_{n,k}^m ( p )表示 S_{n,k}中存在无故障 S_{n-m,k-m}子网络的概率（这里 \mathrm{1} \le m \le k - \mathrm{1}）， \mathrm{P} \mathrm{r} \left(·\right)表示事件 ·发生的概率，则：

（1）

定理1 设 n， k， m为正整数且满足 \mathrm{1} \le k \le n - \mathrm{1}和 \mathrm{1} \le m \le k - \mathrm{1}，则

R_{n,k}^m ( p ) \le \mathrm{m} \mathrm{i} \mathrm{n} \left\{\left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right)n!/\left(n-m\right)!p^{A_{n-m}^{k-m}},\mathrm{1}\right\}。

证明 注意到 S_{n,k}中各个顶点具有相同的可靠性且发生故障相互独立。由 \left|V\left(S_{n-m,k-m}\right)\right| = A_{n-m}^{k-m}可知，对于 \mathrm{1} \le i \le \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) n ! / \left(n-m\right) !有 \mathrm{P} \mathrm{r} ( A_i ) = p^{A_{n-m}^{k-m}}成立。根据式（1），

R_{n,k}^m ( p ) \le {\displaystyle \sum _{i=\mathrm{1}}^{\left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right)n!/\left(n-m\right)!}} Pr(A_i) = \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) n ! / \left(n-m\right) ! p^{A_{n-m}^{k-m}}。

又因为 R_{n,k}^m ( p ) \le \mathrm{1}，故 R_{n,k}^m ( p ) \le \mathrm{m} \mathrm{i} \mathrm{n} \left\{\left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right)n!/\left(n-m\right)!p^{A_{n-m}^{k-m}},\mathrm{1}\right\}。定理1证毕。

引理2 设 u和 l为正整数且满足 ， x_{\mathrm{1}} , x_{\mathrm{2}} , \cdots , x_u和 y_{\mathrm{1}} , y_{\mathrm{2}} , \cdots , y_u均为 u个 〈l〉中两两互不相同的整数序列。当 x_{\mathrm{1}} , x_{\mathrm{2}} , \cdots , x_u给定时，满足 y_{\mathrm{1}} \ne x_{\mathrm{1}} , y_{\mathrm{2}} \ne x_{\mathrm{2}} , \cdots , y_u \ne x_u的 y_{\mathrm{1}} , y_{\mathrm{2}} , \cdots , y_u的选取方法有 A_l^u - {\displaystyle \sum _{i=\mathrm{1}}^u} {\left(-\mathrm{1}\right)}^{i-\mathrm{1}} \left(\begin{array}{c}u\\ i\end{array}\right) A_{l-i}^{u-i}种。

证明 记事件 B表示从 〈l〉中选取两两互不相同的 y_{\mathrm{1}} , y_{\mathrm{2}} , \cdots , y_u，事件 B_e（ \mathrm{1} \le e \le u）表示从 〈l〉中选取两两互不相同的 y_{\mathrm{1}} , y_{\mathrm{2}} , \cdots , y_u且满足 y_e = x_e。令 f \left(·\right)表示事件 ·相应的不同选取方法的种数。此时，满足 y_{\mathrm{1}} \ne x_{\mathrm{1}} , y_{\mathrm{2}} \ne x_{\mathrm{2}} , \cdots , y_u \ne x_u的 y_{\mathrm{1}} , y_{\mathrm{2}} , \cdots , y_u的不同选取方法有 f \left(B\right) - f \left(B_{\mathrm{1}}\bigcup B_{\mathrm{2}}\bigcup \cdots \bigcup B_u\right)种。由 B的定义可知， f \left(B\right) = A_l^u。由 B_e（ \mathrm{1} \le e \le u）的定义和容斥原理可知，

综上所述，当 x_{\mathrm{1}} , x_{\mathrm{2}} , \cdots , x_u给定时，满足 y_{\mathrm{1}} \ne x_{\mathrm{1}} , y_{\mathrm{2}} \ne x_{\mathrm{2}} , \cdots , y_u \ne x_u的 y_{\mathrm{1}} , y_{\mathrm{2}} , \cdots , y_u的选取方法有 A_l^u - {\displaystyle \sum _{i=\mathrm{1}}^u} {\left(-\mathrm{1}\right)}^{i-\mathrm{1}} \left(\begin{array}{c}u\\ i\end{array}\right) A_{l-i}^{u-i}种。引理2证毕。

由式（1）可知，通过厘清两个 S_{n-m,k-m}子网络的不同相交情形来计算式（1）右端前两项之和可以得出 R_{n,k}^m ( p )的下界的理论公式。

定理2 设 n， k， m为正整数且有 \mathrm{1} \le k \le n - \mathrm{1}和 \mathrm{1} \le m \le k - \mathrm{1}，令

\begin{array}{c}{R}_L=\left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right)n!/\left(n-m\right)!p^{A_{n-m}^{k-m}}-\frac{\mathrm{1}}{\mathrm{2}}\left({\displaystyle \sum _{i=\mathrm{0}}^{m-\mathrm{1}}}\left(\begin{array}{c}k-\mathrm{1}\\ i\end{array}\right)\right.\left(\begin{array}{c}k-\mathrm{1}-i\\ m-i\end{array}\right)\left(\begin{array}{c}k-\mathrm{1}-m\\ m-i\end{array}\right)A_n^m{A}_{n-m}^{m-i}{p}^{\mathrm{2}{A}_{n-m}^{k-m}-A_{n-(\mathrm{2}m-i)}^{k-(\mathrm{2}m-i)}}+\\ \left.{\displaystyle \sum _{i=\mathrm{0}}^m}\left(\begin{array}{c}k-\mathrm{1}\\ i\end{array}\right)\left(\begin{array}{c}k-\mathrm{1}-i\\ m-i\end{array}\right)\left(\begin{array}{c}k-\mathrm{1}-m\\ m-i\end{array}\right)((A_n^m{)}^{\mathrm{2}}-A_n^m{A}_{n-m}^{m-i})p^{\mathrm{2}{A}_{n-m}^{k-m}}\right),\end{array}

则 R_{n,k}^m ( p ) \ge \mathrm{m} \mathrm{a} \mathrm{x} \left\{R_L,\mathrm{0}\right\}。

证明 注意到 R_{n,k}^m ( p ) \ge \mathrm{0}。根据式（1）和定理1的证明，

下面证明 。根据引理1， S_{n,k}中任意两个 S_{n-m,k-m}子网络可表示为 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}，其中 a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}均为 m个 〈n〉中两两互不相同的整数。根据 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m和 j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m的不同取值，讨论以下情形。

情形 t \left(\mathrm{1}\le t\le m-\mathrm{1}\right) \left|\left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\}\bigcap \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\}\right| = t。

此时显然有 \mathrm{2} m - t \le k - \mathrm{1}。不妨设 i_{g_{\mathrm{1}}} , i_{g_{\mathrm{2}}} , \cdots , i_{g_t} \in \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\}。注意到 i_{g_{\mathrm{1}}} , i_{g_{\mathrm{2}}} , \cdots , i_{g_t}为 \left\{\mathrm{2,3},\cdots ,k\right\}中 t个两两互不相同的整数，有 \left(\begin{array}{c}k-\mathrm{1}\\ t\end{array}\right)种不同的选法。当 i_{g_{\mathrm{1}}} , i_{g_{\mathrm{2}}} , \cdots , i_{g_t}选定时， \left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\} \backslash \left\{i_{g_{\mathrm{1}}},i_{g_{\mathrm{2}}},\cdots ,i_{g_t}\right\}中 m - t个元素可在 \left\{\mathrm{2,3},\cdots ,k\right\} \backslash \left\{i_{g_{\mathrm{1}}},i_{g_{\mathrm{2}}},\cdots ,i_{g_t}\right\}中选取，有 \left(\begin{array}{c}k-\mathrm{1}-t\\ m-t\end{array}\right)种不同的选法； \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\} \backslash \left\{i_{g_{\mathrm{1}}},i_{g_{\mathrm{2}}},\cdots ,i_{g_t}\right\}中 m - t个元素可在 \left\{\mathrm{2,3},\cdots ,k\right\} \backslash \left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\}中选取，有 \left(\begin{array}{c}k-\mathrm{1}-m\\ m-t\end{array}\right)种不同的选法。由于 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m和 j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m的选取不受选取顺序的影响，故该情形下 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-t\\ m-t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-m\\ m-t\end{array}\right)种不同的选法。当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时，考虑以下子情形。

子情形 t - \mathrm{1} - l \left(\mathrm{1}\le l\le m-t\right) a_{i_{g_{\mathrm{1}}}} = b_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} = b_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}} = b_{i_{g_t}}且

\left|\left(\left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}\backslash \left\{a_{i_{g_{\mathrm{1}}}},a_{i_{g_{\mathrm{2}}}},\cdots ,a_{i_{g_t}}\right\}\right)\bigcap \left(\left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\}\backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}\right)\right| = l \mathrm{。}

根据 S_{n,k}的子网络简化表示的定义可知，

V \left(X^{i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{1}}}{X}^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{2}}}\cdots a_{i_m}{X}^{k-i_m}\right) \bigcap V \left(X^{j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{1}}}{X}^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{2}}}\cdots b_{j_m}{X}^{k-j_m}\right) = \mathrm{\varnothing } ,

即这一情形下两个 S_{n-m,k-m}子网络共有 \mathrm{2} A_{n-m}^{k-m}个顶点。

a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}为 〈n〉中两两互不相同的整数，有 A_n^m种不同的选法；由 a_{i_{g_{\mathrm{1}}}} = b_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} = b_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}} = b_{i_{g_t}}可知，当 a_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}}选定时 b_{i_{g_{\mathrm{1}}}} , b_{i_{g_{\mathrm{2}}}} , \cdots , b_{i_{g_t}}是确定的。注意到 \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\} \backslash \left\{a_{i_{g_{\mathrm{1}}}},a_{i_{g_{\mathrm{2}}}},\cdots ,a_{i_{g_t}}\right\}与 \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\} \backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}有 l个元素相同，不妨设 a_{x_{\mathrm{1}}} , a_{x_{\mathrm{2}}} , \cdots , a_{x_l} \in \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\} \backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}。 a_{x_{\mathrm{1}}} , a_{x_{\mathrm{2}}} , \cdots , a_{x_l}可在 \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\} \backslash \left\{a_{i_{g_{\mathrm{1}}}},a_{i_{g_{\mathrm{2}}}},\cdots ,a_{i_{g_t}}\right\}中选取，有 \left(\begin{array}{c}m-t\\ l\end{array}\right)种不同的选法；当 a_{x_{\mathrm{1}}} , a_{x_{\mathrm{2}}} , \cdots , a_{x_l}选定时满足 \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\} \backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}中有 l个元素与 a_{x_{\mathrm{1}}} , a_{x_{\mathrm{2}}} , \cdots , a_{x_l}相同的选法有 A_{m-t}^l种。 \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\} \backslash \left\{b_{j_{g_{\mathrm{1}}}},b_{j_{g_{\mathrm{2}}}},\cdots ,b_{j_{g_t}},a_{x_{\mathrm{1}}}{a}_{x_{\mathrm{2}}},\cdots ,a_{x_l}\right\}中 m - t - l个元素可在 〈n〉 \backslash \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}中选取，有 A_{n-m}^{m-t-l}种不同的选法。因此，当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时， a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}有 A_n^m \left(\begin{array}{c}m-t\\ l\end{array}\right) A_{m-t}^l A_{n-m}^{m-t-l}种不同的选法。综上可知，在子情形 t - \mathrm{1} - l下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}共有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-t\\ m-t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-m\\ m-t\end{array}\right) A_n^m \left(\begin{array}{c}m-t\\ l\end{array}\right) A_{m-t}^l A_{n-m}^{m-t-l}种不同的选法。

子情形 t - \mathrm{1} - \left(m-t+\mathrm{1}\right) a_{i_{g_{\mathrm{1}}}} = b_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} = b_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}} = b_{i_{g_t}}且

\left|\left(\left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}\backslash \left\{a_{i_{g_{\mathrm{1}}}},a_{i_{g_{\mathrm{2}}}},\cdots ,a_{i_{g_t}}\right\}\right)\bigcap \left(\left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\}\backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}\right)\right| = \mathrm{0} \mathrm{。}

令 \left\{w_{\mathrm{1}},w_{\mathrm{2}},\cdots ,w_{\mathrm{2}m-t}\right\} = \left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\} \bigcup \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\}且满足 ， c_{w_x}满足 c_{w_x} = \left\{\begin{array}{c}{a}_{w_x},w_x\in \left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\}\\ b_{w_x},w_x\in \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\}\end{array}\right.。根据 S_{n,k}的子网络简化表示的定义可知，

V \left(X^{i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{1}}}{X}^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{2}}}\cdots a_{i_m}{X}^{k-i_m}\right) \bigcap V \left(X^{j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{1}}}{X}^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{2}}}\cdots b_{j_m}{X}^{k-j_m}\right) = V \left(X^{w_{\mathrm{1}}-\mathrm{1}}{c}_{w_{\mathrm{1}}}{X}^{w_{\mathrm{2}}-w_{\mathrm{1}}-\mathrm{1}}{c}_{w_{\mathrm{2}}}\right. \left.\cdots c_{w_{\mathrm{2}m-t}}{X}^{k-w_{\mathrm{2}m-t}}\right)，

即这一情形下两个 S_{n-m,k-m}子网络共有 \mathrm{2} A_{n-m}^{k-m} - A_{n-\left(\mathrm{2}m-t\right)}^{k-\left(\mathrm{2}m-t\right)}个顶点。

a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}为 〈n〉中两两互不相同的整数，有 A_n^m种不同的选法；由 a_{i_{g_{\mathrm{1}}}} = b_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} = b_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}} = b_{i_{g_t}}可知，当 a_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}}选定时 b_{i_{g_{\mathrm{1}}}} , b_{i_{g_{\mathrm{2}}}} , \cdots , b_{i_{g_t}}是确定的。 \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\} \backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}中 m - t个元素可在 〈n〉 \backslash \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}中选取，有 A_{n-m}^{m-t}种不同的选法。因此，当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时， a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}有 A_n^m A_{n-m}^{m-t}种不同的选法。综上可知，在子情形 t - \mathrm{1} - \left(m-t+\mathrm{1}\right)下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}共有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-t\\ m-t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-m\\ m-t\end{array}\right) A_n^m A_{n-m}^{m-t}种不同的选法。

子情形 t - \mathrm{2} - s \left(\mathrm{1}\le s\le t-\mathrm{1}\right) a_{i_{g_{\mathrm{1}}}} = b_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} = b_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}} = b_{i_{g_t}}中有且仅有 s个等式成立。

根据 S_{n,k}的子网络简化表示的定义可知，

V \left(X^{i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{1}}}{X}^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{2}}}\cdots a_{i_m}{X}^{k-i_m}\right) \bigcap V \left(X^{j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{1}}}{X}^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{2}}}\cdots b_{j_m}{X}^{k-j_m}\right) = \mathrm{\varnothing } ,

即这一情形下两个 S_{n-m,k-m}子网络共有 \mathrm{2} A_{n-m}^{k-m}个顶点。

a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \dots , a_{i_m}为 〈n〉中两两互不相同的整数，有 A_n^m种不同的选法。由于 a_{i_{g_{\mathrm{1}}}} = b_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} = b_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}} = b_{i_{g_t}}中有且仅有 s个等式成立，可知成立的 s个等式有 \left(\begin{array}{c}t\\ s\end{array}\right)种不同的选法；不妨设 a_{i_{g_{\mathrm{1}}}} = b_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} = b_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_s}} = b_{i_{g_s}} , a_{i_{g_{s+\mathrm{1}}}} \ne b_{i_{g_{s+\mathrm{1}}}} , a_{i_{g_{s+\mathrm{2}}}} \ne b_{i_{g_{s+\mathrm{2}}}} , \cdots , a_{i_{g_t}} \ne b_{i_{g_t}}，则当 a_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_s}}选定时 b_{i_{g_{\mathrm{1}}}} , b_{i_{g_{\mathrm{2}}}} , \cdots , b_{i_{g_s}}是确定的；由引理2可知，当 a_{i_{g_{s+\mathrm{1}}}} , a_{i_{g_{s+\mathrm{2}}}} , \cdots , a_{i_{g_t}}选定时，符合 b_{i_{g_{s+\mathrm{1}}}} \ne a_{i_{g_{s+\mathrm{1}}}} , b_{i_{g_{s+\mathrm{2}}}} \ne a_{i_{g_{s+\mathrm{2}}}} , \cdots , b_{i_{g_t}} \ne a_{i_{g_t}}的 b_{i_{g_{s+\mathrm{1}}}} , b_{i_{g_{s+\mathrm{2}}}} , \cdots , b_{i_{g_t}}的选取方式有 A_{n-s}^{t-s} - {\displaystyle \sum _{i=\mathrm{1}}^{t-s}} {\left(-\mathrm{1}\right)}^{i-\mathrm{1}} \left(\begin{array}{c}t-s\\ i\end{array}\right) A_{n-s-i}^{t-s-i}种； \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\} \backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}中 m - t个元素可在 〈n〉 \backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}中选取，有 A_{n-t}^{m-t}种不同的选取方式。因此，当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时， a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}有 A_n^m \left(\begin{array}{c}t\\ s\end{array}\right) \left(A_{n-s}^{t-s}-{\displaystyle \sum _{i=\mathrm{1}}^{t-s}}{\left(-\mathrm{1}\right)}^{i-\mathrm{1}}{A}_{n-s-i}^{t-s-i}\right) A_{n-t}^{m-t}种不同的选法。综上可知，在子情形 t - \mathrm{2} - s下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}共有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-t\\ m-t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-m\\ m-t\end{array}\right) A_n^m \left(\begin{array}{c}t\\ s\end{array}\right) \left(A_{n-s}^{t-s}-{\displaystyle \sum _{i=\mathrm{1}}^{t-s}}{\left(-\mathrm{1}\right)}^{i-\mathrm{1}}\left(\begin{array}{c}t-s\\ i\end{array}\right)A_{n-s-i}^{t-s-i}\right) A_{n-t}^{m-t}种不同的选法。

子情形 t - \mathrm{2} - t a_{i_{g_{\mathrm{1}}}} \ne b_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} \ne b_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}} \ne b_{i_{g_t}}。

根据 S_{n,k}的子网络简化表示的定义可知，

V \left(X^{i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{1}}}{X}^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{2}}}\cdots a_{i_m}{X}^{k-i_m}\right) \bigcap V \left(X^{j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{1}}}{X}^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{2}}}\cdots b_{j_m}{X}^{k-j_m}\right) = \mathrm{\varnothing }，

即这一情形下两个 S_{n-m,k-m}子网络共有 \mathrm{2} A_{n-m}^{k-m}个顶点。

a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}为 〈n〉中两两互不相同的整数，有 A_n^m种不同的选法。由引理2可知，当 a_{i_{g_{\mathrm{1}}}} , a_{i_{g_{\mathrm{2}}}} , \cdots , a_{i_{g_t}}选定时，满足 b_{i_{g_{\mathrm{1}}}} \ne a_{i_{g_{\mathrm{1}}}} , b_{i_{g_{\mathrm{2}}}} \ne a_{i_{g_{\mathrm{2}}}} , \cdots , b_{i_{g_t}} \ne a_{i_{g_t}}的 b_{i_{g_{\mathrm{1}}}} , b_{i_{g_{\mathrm{2}}}} , \cdots , b_{i_{g_t}}的选取方法有 A_n^t - {\displaystyle \sum _{i=\mathrm{1}}^t} {\left(-\mathrm{1}\right)}^{i-\mathrm{1}} \left(\begin{array}{c}t\\ i\end{array}\right) A_{n-i}^{t-i}种； \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\} \backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}中 m - t个元素可在 〈n〉 \backslash \left\{b_{i_{g_{\mathrm{1}}}},b_{i_{g_{\mathrm{2}}}},\cdots ,b_{i_{g_t}}\right\}中选取，有 A_{n-t}^{m-t}种选法。因此，当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时， a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}有 A_n^m \left(A_n^t-{\displaystyle \sum _{i=\mathrm{1}}^t}{\left(-\mathrm{1}\right)}^{i-\mathrm{1}}\left(\begin{array}{c}t\\ i\end{array}\right)A_{n-i}^{t-i}\right) A_{n-t}^{m-t}种不同的选法。综上可知，在子情形 t - \mathrm{2} - t下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}共有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-t\\ m-t\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-m\\ m-t\end{array}\right) A_n^m \left(A_n^t-{\displaystyle \sum _{i=\mathrm{1}}^t}{\left(-\mathrm{1}\right)}^{i-\mathrm{1}}\left(\begin{array}{c}t\\ i\end{array}\right)A_{n-i}^{t-i}\right) A_{n-t}^{m-t}种不同的选法。

情形 m \left|\left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\}\bigcap \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\}\right| = m。

此时有 m \le k - \mathrm{1}，且 i_{\mathrm{1}} = j_{\mathrm{1}} , i_{\mathrm{2}} = j_{\mathrm{2}} , \cdots , i_m = j_m。显然， a_{i_{\mathrm{1}}} = b_{j_{\mathrm{1}}} , a_{i_{\mathrm{2}}} = b_{j_{\mathrm{2}}} , \cdots , a_{i_m} = b_{j_m}不能同时成立，这意味着 V \left(X^{i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{1}}}{X}^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{2}}}\cdots a_{i_m}{X}^{k-i_m}\right) \bigcap V \left(X^{j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{1}}}{X}^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{2}}}\cdots b_{j_m}{X}^{k-j_m}\right) = \mathrm{\varnothing }，即这一情形下两个 S_{n-m,k-m}子网络共有 \mathrm{2} A_{n-m}^{k-m}个顶点。

注意到 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m为 \left\{\mathrm{2,3},\cdots ,k\right\}中 m个两两互不相同的整数，有 \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right)种不同的选法；当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m选定时 j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m是确定的。当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时，考虑以下子情形。

子情形 m - s \left(\mathrm{1}\le s\le m-\mathrm{1}\right) a_{i_{\mathrm{1}}} = b_{j_{\mathrm{1}}} , a_{i_{\mathrm{2}}} = b_{j_{\mathrm{2}}} , \cdots , a_{i_m} = b_{j_m}中有且仅有 s个等式成立。

a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}为 〈n〉中两两互不相同的整数，有 A_n^m种不同的选法。由于 a_{i_{\mathrm{1}}} = b_{j_{\mathrm{1}}} , a_{i_{\mathrm{2}}} = b_{j_{\mathrm{2}}} , \cdots , a_{i_m} = b_{j_m}中有且仅有 s个等式成立，可知成立的 s个等式有 \left(\begin{array}{c}m\\ s\end{array}\right)种不同的选法；不妨设 a_{i_{\mathrm{1}}} = b_{j_{\mathrm{1}}} , a_{i_{\mathrm{2}}} = b_{j_{\mathrm{2}}} , \cdots , a_{i_s} \ne b_{j_s} , a_{i_{s+\mathrm{1}}} \ne b_{j_{s+\mathrm{1}}} , a_{i_{s+\mathrm{2}}} \ne b_{j_{s+\mathrm{2}}} , \cdots , a_{i_m} \ne b_{j_m}，则当 a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_s}选定时 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_s}是确定的；由引理2可知，当 a_{i_{s+\mathrm{1}}} , a_{i_{s+\mathrm{2}}} , \cdots , a_{i_m}选定时，满足 b_{j_{s+\mathrm{1}}} \ne a_{i_{s+\mathrm{1}}} , b_{j_{s+\mathrm{2}}} \ne a_{i_{s+\mathrm{2}}} , \cdots , b_{j_m} \ne a_{i_m}的 b_{j_{s+\mathrm{1}}} , b_{j_{s+\mathrm{2}}} , \cdots , b_{j_m}的选取方法有 A_{n-s}^{m-s} - {\displaystyle \sum _{i=\mathrm{1}}^{m-s}} {\left(-\mathrm{1}\right)}^{i-\mathrm{1}} \left(\begin{array}{c}m-s\\ i\end{array}\right) A_{n-s-i}^{m-s-i}种。又因为 a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}的选取不受选取顺序的影响，故当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时， a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}有 \frac{\mathrm{1}}{\mathrm{2}} A_n^m \left(\begin{array}{c}m\\ s\end{array}\right) \left(A_{n-s}^{m-s}-{\displaystyle \sum _{i=\mathrm{1}}^{m-s}}{\left(-\mathrm{1}\right)}^{i-\mathrm{1}}\right. \left.\left(\begin{array}{c}m-s\\ i\end{array}\right)A_{n-s-i}^{m-s-i}\right)种不同的选取方式。综上可知，在子情形 m - s下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}共有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) A_n^m \left(\begin{array}{c}m\\ s\end{array}\right) \left(A_{n-s}^{m-s}-{\displaystyle \sum _{i=\mathrm{1}}^{m-s}}{\left(-\mathrm{1}\right)}^{i-\mathrm{1}}\left(\begin{array}{c}m-s\\ i\end{array}\right)A_{n-s-i}^{m-s-i}\right)种不同的选法。

子情形 m - m a_{i_{\mathrm{1}}} \ne b_{j_{\mathrm{1}}} , a_{i_{\mathrm{2}}} \ne b_{j_{\mathrm{2}}} , \cdots , a_{i_m} \ne b_{j_m}。

a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}为 〈n〉中两两互不相同的整数，有 A_n^m种不同的选法；由引理2可知，当 a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}选定时，符合 b_{j_{\mathrm{1}}} \ne a_{i_{\mathrm{1}}} , b_{j_{\mathrm{2}}} \ne a_{i_{\mathrm{2}}} , \cdots , b_{j_m} \ne a_{i_m}的 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}的选取方式有 A_n^m - {\displaystyle \sum _{i=\mathrm{1}}^m} {\left(-\mathrm{1}\right)}^{i-\mathrm{1}} \left(\begin{array}{c}m\\ i\end{array}\right) A_{n-i}^{m-i}种。注意到 a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}的选取不受选取顺序的影响。因此，当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时， a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}有 \frac{\mathrm{1}}{\mathrm{2}} A_n^m \left(A_n^m-{\displaystyle \sum _{i=\mathrm{1}}^m}{\left(-\mathrm{1}\right)}^{i-\mathrm{1}}\left(\begin{array}{c}m\\ i\end{array}\right)A_{n-i}^{m-i}\right)种不同的选取方式。综上可知，在子情形 m - m下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}共有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) A_n^m \left(A_n^m-{\displaystyle \sum _{i=\mathrm{1}}^m}{\left(-\mathrm{1}\right)}^{i-\mathrm{1}}\left(\begin{array}{c}m\\ i\end{array}\right)A_{n-i}^{m-i}\right)种不同的选法。

情形 m + \mathrm{1} \left|\left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\}\bigcap \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\}\right| = \mathrm{0}。

此时有 \mathrm{2} m \le k - \mathrm{1}，且 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m两两互不相同。 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m为 \left\{\mathrm{2,3},\cdots ,k\right\}中 m个两两互不相同的整数，有 \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right)种不同的选法； j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m可以在 \left\{\mathrm{2,3},\cdots ,k\right\} \backslash \left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\}中选取，有 \left(\begin{array}{c}k-\mathrm{1}-m\\ m\end{array}\right)种不同的选取方式。由于 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m和 j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m的选取不受选取顺序的影响，故该情形下 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-m\\ m\end{array}\right)种不同的选法。当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时，考虑以下子情形。

子情形 \left(m+\mathrm{1}\right) - l \left|\left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}\bigcap \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\}\right| = l \left(\mathrm{1}\le l\le m\right)。

根据 S_{n,k}的子网络简化表示的定义可知，

V \left(X^{i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{1}}}{X}^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{2}}}\cdots a_{i_m}{X}^{k-i_m}\right) \bigcap V \left(X^{j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{1}}}{X}^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{2}}}\cdots b_{j_m}{X}^{k-j_m}\right) = \mathrm{\varnothing } ,

即这一情形下两个 S_{n-m,k-m}子网络共有 \mathrm{2} A_{n-m}^{k-m}个顶点。

a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}为 〈n〉中两两互不相同的整数，有 A_n^m种不同的选法；注意到 \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}与 \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\}有 l个元素相同，不妨设 a_{x_{\mathrm{1}}} , a_{x_{\mathrm{2}}} , \cdots , a_{x_l} \in \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\}。 a_{x_{\mathrm{1}}} , a_{x_{\mathrm{2}}} , \cdots , a_{x_l}可在 \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}中选取，有 \left(\begin{array}{c}m\\ l\end{array}\right)种不同的选法；当 a_{x_{\mathrm{1}}} , a_{x_{\mathrm{2}}} , \cdots , a_{x_l}选定时，满足 \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\}中有 l个元素与 a_{x_{\mathrm{1}}} , a_{x_{\mathrm{2}}} , \cdots , a_{x_l}相同的选法有 A_m^l种。 \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\} \backslash \left\{a_{x_{\mathrm{1}}},a_{x_{\mathrm{2}}},\cdots ,a_{x_l}\right\}中 m - l个元素可在 〈n〉 \backslash \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}中选取，有 A_{n-m}^{m-l}种不同的选法。因此，当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时， a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}有 A_n^m \left(\begin{array}{c}m\\ l\end{array}\right) A_m^l A_{n-m}^{m-l}种不同的选法。综上可知，在子情形 \left(m+\mathrm{1}\right) - l下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}共有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-m\\ m\end{array}\right) A_n^m \left(\begin{array}{c}m\\ l\end{array}\right) A_m^l A_{n-m}^{m-l}种不同的选法。

子情形 \left(m+\mathrm{1}\right) - \left(m+\mathrm{1}\right) \left|\left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}\bigcap \left\{b_{j_{\mathrm{1}}},b_{j_{\mathrm{2}}},\cdots ,b_{j_m}\right\}\right| = \mathrm{0}。

令 \left\{w_{\mathrm{1}},w_{\mathrm{2}},\cdots ,w_{\mathrm{2}m}\right\} = \left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\} \bigcup \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\}且满足 ， c_{w_x}满足 c_{w_x} = \left\{\begin{array}{c}{a}_{w_x},w_x\in \left\{i_{\mathrm{1}},i_{\mathrm{2}},\cdots ,i_m\right\}\\ b_{w_x},w_x\in \left\{j_{\mathrm{1}},j_{\mathrm{2}},\cdots ,j_m\right\}\end{array}\right.。根据 S_{n,k}的子网络简化表示的定义可知， V \left(X^{i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{1}}}{X}^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}}{a}_{i_{\mathrm{2}}}\cdots a_{i_m}{X}^{k-i_m}\right) \bigcap V \left(X^{j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{1}}}{X}^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}}{b}_{j_{\mathrm{2}}}\cdots b_{j_m}{X}^{k-j_m}\right) = V \left(X^{w_{\mathrm{1}}-\mathrm{1}}{c}_{w_{\mathrm{1}}}{X}^{w_{\mathrm{2}}-w_{\mathrm{1}}-\mathrm{1}}{c}_{w_{\mathrm{2}}}\right. \left.\cdots c_{w_{\mathrm{2}m}}{X}^{k-w_{\mathrm{2}m}}\right)，即这一情形下两个 S_{n-m,k-m}子网络共有 \mathrm{2} A_{n-m}^{k-m} - A_{n-\mathrm{2}m}^{k-\mathrm{2}m}个顶点。

a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}为 〈n〉中两两互不相同的整数，有 A_n^m种不同的选法； b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}为 〈n〉 \backslash \left\{a_{i_{\mathrm{1}}},a_{i_{\mathrm{2}}},\cdots ,a_{i_m}\right\}中两两互不相同的整数，有 A_{n-m}^m种选法。因此，当 i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m , j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m选定时， a_{i_{\mathrm{1}}} , a_{i_{\mathrm{2}}} , \cdots , a_{i_m}和 b_{j_{\mathrm{1}}} , b_{j_{\mathrm{2}}} , \cdots , b_{j_m}有 A_n^m A_{n-m}^m种不同的选法。综上可知，在子情形 \left(m+\mathrm{1}\right) - \left(m+\mathrm{1}\right)下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}共有 \frac{\mathrm{1}}{\mathrm{2}} \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right) \left(\begin{array}{c}k-\mathrm{1}-m\\ m\end{array}\right) A_n^m A_{n-m}^m种不同的选法。

由上述分析可知， i_{\mathrm{1}} , i_{\mathrm{2}} , \cdots , i_m和 j_{\mathrm{1}} , j_{\mathrm{2}} , \cdots , j_m的所有情形都已考虑，各个情形下 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}和 X^{j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{1}}} X^{j_{\mathrm{2}}-j_{\mathrm{1}}-\mathrm{1}} b_{j_{\mathrm{2}}} \cdots b_{j_m} X^{k-j_m}的相交情况见表1。

因此，

即有 成立。定理2证毕。

2.2　有效性分析

要得出 R_{n,k}^m ( p )的精确值需要厘清不同数目 S_{n-m,k-m}子网络的所有相交情况。然而， S_{n-m,k-m}子网络之间的相交情况会随着子网络数目的增大变得十分复杂。因此，本文仅给出了 R_{n,k}^m ( p )的上下界。下面对2.1小节得出的 R_{n,k}^m ( p )的上下界进行有效性分析。记 \overline{R_{n,k}^m(p)} = \mathrm{m} \mathrm{i} \mathrm{n} \left\{\left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right)n!/\left(n-m\right)!p^{A_{n-m}^{k-m}}=R_U,\mathrm{1}\right\}， \underline{R_{n,k}^m(p)} = \mathrm{m} \mathrm{a} \mathrm{x} \left\{R_L,\mathrm{0}\right\}。以不同规模的 S_{n,k} \left(S_{\mathrm{7,4}},S_{\mathrm{8,4}},S_{\mathrm{7,5}},S_{\mathrm{7,6}}\right)作为实验对象，对 S_{n,k}中存在无故障 S_{n-m,k-m}（ m = \mathrm{2,3}）子网络的概率的上界 \overline{R_{n,k}^m(p)}和下界 \underline{R_{n,k}^m(p)}进行数值计算，分别得出了满足 R_L \ge \mathrm{0}、 R_U \le \mathrm{1}和 \overline{R_{n,k}^m(p)} - \underline{R_{n,k}^m(p)} \le \delta（ \delta = \mathrm{0.01}）的 p的取值范围，具体结果见表2。

从表2可以看出，当 m不变时，满足 R_L \ge \mathrm{0}、 R_U \le \mathrm{1}和 \overline{R_{n,k}^m(p)} - \underline{R_{n,k}^m(p)} \le \delta的 p的取值范围均随着 S_{n,k}的规模的增大而变得越来越大；当 S_{n,k}的规模给定时， m的值越小，满足 R_L \ge \mathrm{0}、 R_U \le \mathrm{1}和 \overline{R_{n,k}^m(p)} - \underline{R_{n,k}^m(p)} \le \delta的 p的取值范围越大。这意味着，对于较大规模的 S_{n,k}，顶点可靠性 p在很大范围内取值都可以满足 R_L \ge \mathrm{0}、 R_U \le \mathrm{1}和 \overline{R_{n,k}^m(p)} - \underline{R_{n,k}^m(p)} \le \delta；进一步地，当上界 \overline{R_{n,k}^m(p)}和下界 \underline{R_{n,k}^m(p)}的差值较小（如 \overline{R_{n,k}^m(p)} - \underline{R_{n,k}^m(p)} \le \delta）时，可以将 \frac{\mathrm{1}}{\mathrm{2}} ( \overline{R_{n,k}^m(p)} + \underline{R_{n,k}^m(p)} )看作 R_{n,k}^m ( p )的较为精确的估计值。

3 无故障 S_{n-m,k-m}子网络搜寻算法

3.1　算法描述

给出在带有点故障的 S_{n,k}中搜寻无故障 S_{n-m,k-m}子网络的算法有助于基于 S_{n,k}构建的多处理器系统的任务分配算法的设计，具有一定的现实意义。

算法1 无故障 S_{n-m,k-m}子网络搜寻算法

输入：（n，k）-星图 S_{n,k}和 S_{n-m,k-m}子网络的规模参数 n， k， m（ \mathrm{1} \le k \le n - \mathrm{1}， \mathrm{1} \le m \le k - \mathrm{1}）以及 S_{n,k}中一个故障点集 F。

输出： S_{n,k}中无故障 S_{n-m,k-m}子网络的集合 S。

1. 令

2. while F \ne \mathrm{\varnothing } do

3. 选择一个点 b_{\mathrm{1}} b_{\mathrm{2}} \cdots b_k \in F

4.

5. F ≔ F \backslash \left\{b_{\mathrm{1}}{b}_{\mathrm{2}}\cdots b_k\right\}

6. end while

7. 返回 S。

算法1的正确性可由以下讨论得出：

由引理1， S_{n,k}中任一个 S_{n-m,k-m}子网络可用某个 X^{i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{1}}} X^{i_{\mathrm{2}}-i_{\mathrm{1}}-\mathrm{1}} a_{i_{\mathrm{2}}} \cdots a_{i_m} X^{k-i_m}唯一表示，其中 \mathrm{1} \le m \le k - \mathrm{1}， 。可知， S_{n,k}中所有 S_{n-m,k-m}子网络的集合可表示为 。根据 S_{n,k}的子网络简化表示的定义，点 b_{\mathrm{1}} b_{\mathrm{2}} \cdots b_k \in V \left(S_{n,k}\right)发生故障会使得 中 \left(\begin{array}{c}k-\mathrm{1}\\ m\end{array}\right)个不同的 S_{n-m,k-m}子网络遭到破坏。

3.2　无故障 S_{n-m,k-m}子网络搜寻算法实例

本节使用MATLAB实现算法1。分别以 S_{\mathrm{5,3}}和 S_{\mathrm{5,4}}为例，在随机生成不同的故障点集 F之后，利用算法1搜寻 S_{n,k}中不同规模的无故障 S_{n-m,k-m}子网络（ m = \mathrm{1,2}），部分结果见表3和表4。由实验结果可以看出，若仅考虑点故障的发生且 S_{n,k}中所有故障点已知，则利用算法1可以搜寻出 S_{n,k}中所有的无故障 S_{n-m,k-m}子网络。

4 基于蒙特卡罗的 R_{n,k}^m ( p )的近似评估方法

4.1　算法描述

当基于 S_{n,k}构建的多处理器系统需指派 S_{n-m,k-m}子网络执行用户任务时，相应算法的设计依赖于精确的无故障 S_{n-m,k-m}子网络的存在概率估计结果。注意到，当 R_{n,k}^m ( p )的上下界的差值较大时，利用上界 \overline{R_{n,k}^m(p)}和下界 \underline{R_{n,k}^m(p)}不能较为准确地评估 R_{n,k}^m ( p )。下面给出一个基于蒙特卡罗的 R_{n,k}^m ( p )的近似计算方法。

算法2 R_{n,k}^m ( p )的基于蒙特卡罗的近似评估算法

输入：（n，k）-星图 S_{n,k}和 S_{n-m,k-m}子网络的规模参数 n， k， m（ \mathrm{1} \le k \le n - \mathrm{1}， \mathrm{1} \le m \le k - \mathrm{1}）、顶点可靠性 p和模拟次数 N。

输出： S_{n,k}中无故障 S_{n-m,k-m}子网络的存在概率 R_{n,k}^m ( p )。

1. 把 S_{n,k}中 n ! / \left(n-k\right) !个顶点分别记为 T [ \mathrm{0} ] , T [ \mathrm{1} ] , \cdots , T [ n ! / \left(n-k\right) ! - \mathrm{1} ]

2. for i = 1 to N do

3. 生成［0，1］内服从均匀分布的 n ! / \left(n-k\right) !个随机数 \gamma \left[\mathrm{0}\right] , \gamma \left[\mathrm{1}\right] , \cdots , \gamma \left[n!/\left(n-k\right)!-\mathrm{1}\right]

4. set F ≔ \mathrm{\varnothing }

5. for j = 0 to n ! / \left(n-k\right) ! - \mathrm{1} do

6. if then

7. F ≔ F \bigcup \left\{T[j]\right\}

8. end if

9. end for

10. 以规模参数 n， k， m及故障点集 F为输入调用算法1，将得到的无故障 S_{n-m,k-m}子网络的集合记为 S

11. if \left|S\right| > \mathrm{0} then

12. set x \left(i\right) ≔ \mathrm{1}

13. else

14. set x \left(i\right) ≔ \mathrm{0}

15. end if

16. end for

17. set R_{n,k}^m ( p ) ≔ {\displaystyle \sum _{i=\mathrm{1}}^N} x\left(i\right)/N

18. 返回 R_{n,k}^m ( p )。

算法2的正确性可由以下讨论得出：

将生成的［0，1］内服从均匀分布的 n ! / \left(n-k\right) !个随机数 \gamma \left[\mathrm{0}\right] , \gamma \left[\mathrm{1}\right] , \cdots , \gamma \left[n!/\left(n-k\right)!-\mathrm{1}\right]与 S_{n,k}的顶点 T [ \mathrm{0} ] , T [ \mathrm{1} ] , \cdots , T [ n ! / \left(n-k\right) ! - \mathrm{1} ]一一对应，把符合 的对应顶点记成故障点，剩余顶点记成非故障点，则这一网络状态下 S_{n,k}的顶点可靠性为 p。在该网络状态下借助算法1可以得到 S_{n,k}中无故障 S_{n-m,k-m}子网络的集合 S；重复以上模拟过程N次，若存在无故障 S_{n-m,k-m}子网络（即 \left|S\right| > \mathrm{0}）的累计模拟次数为 {\displaystyle \sum _{i=\mathrm{1}}^N} x\left(i\right)，则此时 {\displaystyle \sum _{i=\mathrm{1}}^N} x\left(i\right)/N可以看作 R_{n,k}^m ( p )的估计值，且模拟次数N越大该估计值越精确。

4.2　实验分析

以不同规模的 S_{n,k} \left(S_{\mathrm{7,4}},S_{\mathrm{8,4}},S_{\mathrm{7,5}},S_{\mathrm{7,6}}\right)作为实验对象，本节借助MATLAB实现算法2对 S_{n,k}中无故障 S_{n-m,k-m}子网络（ m = \mathrm{2,3}）的存在概率进行估计，并将所得的近似评估结果与定理1和定理2给出的上下界进行对比。对于某一选定的 S_{n,k}，若 S_{n,k}的顶点可靠性 p在［0，1］内给定时，执行算法2（设置模拟次数 N = \mathrm{10} \mathrm{000}）对 S_{n,k}中无故障 S_{n-m,k-m}子网络的存在概率 R_{n,k}^m ( p )进行估算，并根据定理1和定理2对 R_{n,k}^m ( p )的上界 \overline{R_{n,k}^m(p)}和下界 \underline{R_{n,k}^m(p)}进行计算，具体实验结果如图2所示。

通过图2可以看出，对于任意的 S_{n,k}，随着顶点可靠性 p逐渐减小，利用算法2得出的 R_{n,k}^m ( p )的近似评估结果与 R_{n,k}^m ( p )的上下界基本吻合，这表明当上界 \overline{R_{n,k}^m(p)}和下界 \underline{R_{n,k}^m(p)}的差满足精度要求时，利用上下界的平均值 \frac{\mathrm{1}}{\mathrm{2}} ( \overline{R_{n,k}^m(p)} + \underline{R_{n,k}^m(p)} )和算法2都能得出较为精确的 R_{n,k}^m ( p )；当上下界之间的差值不满足精度要求时，利用上界 \overline{R_{n,k}^m(p)}和下界 \underline{R_{n,k}^m(p)}无法较为准确的估计 R_{n,k}^m ( p )，此时利用算法2得出的结果是较为精确的（模拟次数N越大结果越精确）。

5 结论

对于 \mathrm{1} \le k \le n - \mathrm{1}和 \mathrm{1} \le m \le k - \mathrm{1}，本文在概率故障条件下估计了 S_{n,k}中无故障 S_{n-m,k-m}子网络的存在概率 R_{n,k}^m ( p )，得出了 R_{n,k}^m ( p )的上下界，给出了在仅考虑点故障的 S_{n,k}中搜寻无故障 S_{n-m,k-m}子网络的算法，并基于蒙特卡罗模拟提出了 R_{n,k}^m ( p )的近似评估方法。结果表明，当 R_{n,k}^m ( p )的上下界的差值满足评估精度时，上界和下界的平均值可以看作 R_{n,k}^m ( p )的较为精确的估计值，且该平均值与近似评估方法得出的结果是一致的；当 R_{n,k}^m ( p )的上下界的差值不满足评估精度时，利用基于蒙特卡罗的近似方法可以得出较为精确的评估结果。

值得注意的是，为了达到预期评估精度，基于蒙特卡罗的无故障 S_{n-m,k-m}子网络存在概率的近似评估方法往往需设置较大的模拟次数，这可能会导致评估效率大大降低，其原因如下：当 S_{n,k}的顶点可靠性为 p时，算法2的每次模拟过程中生成的故障点集 F满足 | F | \approx ⌊\frac{n!}{(n-k)!}(\mathrm{1}-p)⌋（这是由于 | V ( S_{n,k} ) | = \frac{n!}{(n-k)!}且 \mathrm{1} - \frac{|F|}{|V(S_{n,k})|}可以看作 p的估计值），这表明在算法2的步骤10中调用算法1时算法1的步骤2—步骤6循环体的执行次数约为 ⌊\frac{n!}{(n-k)!}(\mathrm{1}-p)⌋；若 ⌊\frac{n!}{(n-k)!}(\mathrm{1}-p)⌋和模拟次数 N均较大时，利用算法2估计 R_{n,k}^m ( p )的效率会较低。高效的无故障子网络存在概率的近似评估方法值得进一步研究。

参考文献

[1] HAYES J P, MUDGE T, STOUT Q F, et al. A Microprocessor-based Hypercube Supercomputer[J]. IEEE Micro, 1986, 6(5): 6-17. DOI: 10.1109/MM.1986.304707 .

[2] AKERS S B, KRISHNAMURTHY B. A Group-theoretic Model for Symmetric Interconnection Networks[J]. IEEE Trans Comput, 1989, 38(4): 555-566. DOI: 10.1109/12.21148 .

[3] BROOKS E D III. The Indirect K-ary N-cube for a Vector Processing Environment[J]. Parallel Comput, 1988, 6(3): 339-348. DOI: 10.1016/0167-8191(88)90074-9 .

[4] CHIANG W K, CHEN R J. The (N, K)-star Graph: a Generalized Star Graph[J]. Inf Process Lett, 1995, 56(5): 259-264. DOI: 10.1016/0020-0190(95)00162-1 .

[5] LIU X Q, ZHOU S M, LIU J F, et al. Reliability Analysis of the Cactus-based Networks Based on Subsystem[J]. Comput J, 2024, 67(1): 142-152. DOI: 10.1093/comjnl/bxac163 .

[6] CHIANG W K, CHEN R J. Topological Properties of the (N, K)-star Graph[J]. Int J Found Comput Sci, 1998, 9(2): 235-248. DOI: 10.1142/s0129054198000167 .

[7] CHENG E, KELM J, RENZI J. Strong Matching Preclusion of (N, K)-star Graphs[J]. Theor Comput Sci, 2016, 615: 91-101. DOI: 10.1016/j.tcs.2015.11.051 .

[8] CHANG N W, HSIEH S Y. Conditional Diagnosability of (N, K)-star Graphs Under the PMC Model[J]. IEEE Trans Dependable Secure Comput, 2018, 15(2): 207-216. DOI: 10.1109/TDSC.2016.2562620 .

[9] CHANG N W, DENG W H, HSIEH S Y. Conditional Diagnosability of (N, K)-star Networks Under the Comparison Diagnosis Model[J]. IEEE Trans Reliab, 2015, 64(1): 132-143. DOI: 10.1109/TR.2014.2354912 .

[10] FENG K. Subnetwork Preclusion of (N, K)-star Networks[J]. Int J Found Comput Sci, 2022, 33(5): 439-451. DOI: 10.1142/s0129054122500095 .

[11] AJISH KUMAR K S, SASIDHARAN B, SUDEEP K S. On Oriented Diameter of (N, K)-star Graphs[J]. Discret Appl Math, 2022. DOI: 10.1016/j.dam.2022.04.017 .

[12] DAS C R, KIM J. A Unified Task-based Dependability Model for Hypercube Computers[J]. IEEE Trans Parallel Distrib Syst, 1992, 3(3): 312-324. DOI: 10.1109/71.139205 .

[13] CHANG Y, BHUYAN L N. A Combinatorial Analysis of Subcube Reliability in Hypercubes[J]. IEEE Trans Comput, 1995, 44(7): 952-956. DOI: 10.1109/12.392856 .

[14] LIN L M, XU L, ZHOU S M, et al. The Reliability of Subgraphs in the Arrangement Graph[J]. IEEE Trans Reliab, 2015, 64(2): 807-818. DOI: 10.1109/TR.2015.2413372 .

[15] KUNG T L, TENG Y H, LIN C K, et al. Combinatorial Analysis of the Subsystem Reliability of the Split-star Network[J]. Inf Sci, 2017, 415/416: 28-40. DOI: 10.1016/j.ins.2017.06.012 .

[16] HUANG Y Z, LIN L M, WANG D J. On the Reliability of Alternating Group Graph-based Networks[J]. Theor Comput Sci, 2018, 728: 9-28. DOI: 10.1016/j.tcs.2018.03.010 .

[17] 冯凯, 刘彤. 概率故障条件下K元(N-M)方体子网络的可靠性[J]. 计算机应用, 2023, 43(4): 1198-1205. DOI: 10.11772/j.issn.1001-9081.2022030414 .

[18] FENG K, LIU T. Reliability of K-ary (N-M)-cube Subnetworks Under Probabilistic Fault Condition[J]. J Comput Appl, 2023, 43(4): 1198-1205. DOI: 10.11772/j.issn.1001-9081.2022030414 .

[19] 冯凯, 马鑫玉. (N, K)-冒泡排序网络的子网络可靠性[J]. 计算机科学, 2021, 48(4): 43-48. DOI: 10.11896/jsjkx.201100139 .

[20] FENG K, MA X Y. Subnetwork Reliability of (N, K)-bubble-sort Networks[J]. Comput Sci, 2021, 48(4): 43-48. DOI: 10.11896/jsjkx.201100139 .

[21] LV M J, FAN J X, FAN W B, et al. Fault Diagnosis Based on Subsystem Structures of Data Center Network B Cube[J]. IEEE Trans Reliab, 2022, 71(2): 963-972. DOI: 10.1109/TR.2021.3140069 .

[22] LI X W, ZHOU S M, XU X, et al. The Reliability Analysis Based on Subsystems of (N, K)-star Graph[J]. IEEE Trans Reliab, 2016, 65(4): 1700-1709. DOI: 10.1109/TR.2016.2570544 .

[23] BONDY J A, MURTY U S R. Graph Theory[M]. London: Springer London, 2008. DOI: 10.1007/978-1-84628-970-5 .

基金资助

国家自然科学基金(61502286)

山西省基础研究计划项目(20210302123438)