( , )n k
网络的容错性
并行分布式多处理器系统的基础拓扑通常以图为数学模型，其中图的顶点代
表处理器，边代表处理器间的直接通信联系。
( , )n k
网络作为多处理器系统的主
要候选拓扑之一而得到广泛关注。
( , )n k
网络具体定义如下：
对给定的一个正整数
n
，用
n
I
表示集合
{1, 2, , }nL
，用
( , )P n k
表示
n
I
中
k
个
元素组成的排列的全体, 即
1 2
( , ) { | }
k i n i j
a a a a I jP n k i a a¼ Î ¹= ¹时且当
。一个
( , )n k
网 络 的 顶 点 集 是
( , )P n k
; 顶 点 之 间 的 邻 接 关 系 定 义 如 下 : 一 个 顶 点
1 2 k
au a a¼=
与下述两类顶点相邻：
(1)顶点
2 1 1 1
, {2,3, , }
i i i k
v a aa a a a i k
- +
= μ ¼ L
;
(2)顶点
2 1 2
{ , , , },
k n k
a a I av a ab b¼ Î - ¼=
。
(4,2)
网络如下图所示：
一个由
N
个顶点组成的网络可以用一个
N N´
矩阵
( )
ij
A a=
来表示，其中
1
ij
a =
表示在该网络中第
i
个顶点与第
j
个顶点相邻，
0
ij
a =
表示在该网络中第
i
个顶点与第
j
个顶点不相邻。人们称这样的矩阵为这个网络的邻接矩阵。附件 1
和附件 2 分别给出了
(6, 4)
网络和
(7, 4)
网络的邻接矩阵。
一个多处理机系统在运行过程中一些处理器（顶点）发生故障是不可避免的，
