如何使用矩阵表达和简化二元关系

发表于 2024-11-22 更新于 2024-11-23 分类于 Sundry Waline：

系统结构的矩阵表达

邻接矩阵

邻接矩阵A是表达系统间要素基本二元关系或直接联系情况的方阵。若 $A = (a_{ij})_{n \times n}$ ，则其定义式为：

a_{ij} = \begin{cases} 1, S_iRS_j(S_i对S_j有某种二元关系) \\ 0, S_i\bar{R}S_j(S_i对S_j没有某种二元关系) \end{cases}

假设有如下邻接矩阵

A = \begin{bmatrix} 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 0 \quad 0 \\ 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 1 \quad 1 \\ 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 0 \quad 0 \\ 0 \quad 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ \end{bmatrix}

在邻接矩阵中，若有一列（如第j列）元素全为0，则第j个元素是系统的输入元素；若有一行（如第i行）元素全为0，则第i个元素是输出元素。

可达矩阵

若在要素 $S_i 和 S_j$ 之间存在某种传递性二元关系，则称 $S_i是可以到达S_j$ 的。

所谓可达矩阵M，就是表明系统要素之间任意次传递性二元关系或有向图上两个节点之间通过任意长的路径可以到达情况的方阵。

若 $M=(m_{ij})_{n \times n}$ ，且在无回路条件下的最大路长或传递次数为r，即 $0 \le t \le r$ ，则可达矩阵的定义式为：

m_{ij} = \begin{cases} 1, S_iR^tS_j, (存在从i至j的路长最大为r的通路), \\ 0, S_i\bar{R}^tS_j, (不存在从i至j的通路) \end{cases}

当t=1时，表示基本的二元关系，M即为A，当t=0时，表示 $S_i$ 自身到达，也称反射性的二元关系，当 $t \ge 2$ 时，表示传递性二元关系。

矩阵A和M的元素均为1或0，是 $n \times n$ 阶的0-1矩阵，且符合布尔代数的运算规则，即 $0+0=0,0+1=1,1+0=1,1+1=1, 0 \times 0 = 0, 0 \times 1 = 0, 1 \times 0 = 0, 1 \times 1 = 1$

通过对邻接矩阵A的运算，可求出系统要素的可达矩阵M，其计算公式为：

M = (A + I)^r

其中I为与A同阶的单位矩阵（其主对角线元素全为1，其他都为0，反应要素自身零步到达自身）；r为最大传递次数。

以刚才的邻接矩阵为例，

A + I = \begin{bmatrix} 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 1 \quad 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 0 \quad 0 \quad 1 \quad 1 \quad 0 \quad 0 \quad 0 \\ 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 1 \quad 1 \\ 0 \quad 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 0 \\ 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 1 \quad 0 \\ 0 \quad 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 1 \\ \end{bmatrix}

在此基础上，我们继续计算通过两步的到达情况

(A + I)^2 = A^2 + A + I = \begin{bmatrix} 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 1 \quad 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 0 \quad 0 \quad 1 \quad 1 \quad ① \quad ① \quad 0 \\ 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 1 \quad 1 \\ 0 \quad 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 0 \\ 0 \quad 0 \quad 0 \quad 1 \quad ① \quad 1 \quad 0 \\ ① \quad 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 1 \\ \end{bmatrix}

其中①表示要素间通过两步到达的情况，其中展开平方公式时利用了 $I^2 = I$ （矩阵运算结果）, $A + A = A$ (布尔代数)。

进一步计算发现 $(A+I)^3 = (A+I)^2$ ，那么说明r=2，即最大传递次数为2时，就找到了所有的可达关系，因此

M = (A + I)^2 = \begin{bmatrix} 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 1 \quad 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 0 \\ 0 \quad 0 \quad 1 \quad 1 \quad 1 \quad 1 \quad 0 \\ 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 1 \quad 1 \\ 0 \quad 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 0 \\ 0 \quad 0 \quad 0 \quad 1 \quad 1 \quad 1 \quad 0 \\ 1 \quad 1 \quad 0 \quad 0 \quad 0 \quad 0 \quad 1 \\ \end{bmatrix}

其他矩阵

缩减矩阵

根据强连接要素的可替换性，在已有的可达矩阵M中，将具有强连接关系的一组要素看作一个要素，保留其中的某个代表，删除其余要素及其在M中的行和列，即可得到该可达矩阵M的缩减矩阵M’，具体什么是强连接元素，后续简化过程中会提到

骨架矩阵

对于给定系统，A的可达矩阵M是唯一的，但实现某一可达矩阵M的的邻接矩阵A可以有多个。把实现某一可达矩阵M，具有最小二元关系个数（1的个数）的邻接矩阵叫做M的最小二元关系矩阵，或叫做骨架矩阵，记作A’

如何简化：建立递阶结构模型的规范方法

建立反应系统问题要素见层次关系的递阶结构模型，可在可达矩阵M的基础上进行，一般要经过四个步骤：区域划分，级位划分，骨架矩阵提取，多级递阶有向图绘制。

区域划分

区域划分是将系统的构成要素集合S分成关于给定二元关系R的相互独立的区域的过程。

为此，需要首先以可达矩阵M为基础，划分与要素相关联的系统要素的类型，并找出在整个系统中有明显特征的要素，有关要素集合的定义如下：

（1）可达集 $R(S_i)$ ，系统要素 $S_i$ 的可达集是在可达矩阵中由 $S_i$ 可到达的诸要素所构成的集合，其定义式为

R(S_i) = \{ S_j | S_j \sub S, m_{ij}=1, j=1,2,\ldots,n \}

在给出的可达矩阵中有

R(S_1) = \{S_1\} \\ R(S_2) = \{S_1,S_2\} \\ R(S_3) = \{S_3,S_4,S_5,S_6\} \\ R(S_4) = R(S_6) = \{S_4,S_5,S_6\} \\ R(S_5) = \{S_5\} \\ R(S_7) = \{S_1,S_2,S_7\}

（2）先行集 $A(S_i)$ 。系统要素 $S_i$ 的先行集是在可达矩阵中可达到 $S_i$ 的诸要素的集合，其定义式为：

A(S_i) = \{ S_j | S_j \sub S, m_{ji}=1, j=1,2,\ldots,n \}

在给出的可达矩阵中有

A(S_1) = \{S_1,S_2,S_7\} \\ A(S_2) = \{S_2,S_7\} \\ A(S_3) = \{S_3\} \\ A(S_4) = A(S_6) = \{S_3,S_4,S_6\} \\ A(S_5) = \{S_3,S_4,S_5,S_6\} \\ A(S_7) = \{S_7\}

（3）共同集 $C(S_i)$ ，系统要素 $S_i$ 的共同集是 $S_i$ 的可达集和先行集的交集，其定义式为：

C(S_i) = \{ S_j | S_j \sub S, m_{ij}=1, m_{ji}=1, j=1,2,\ldots,n \}

在给出的可达矩阵中有

C(S_1) = \{S_1\} \\ C(S_2) = \{S_2\} \\ C(S_3) = \{S_3\} \\ C(S_4) = C(S_6) = \{S_4,S_6\} \\ C(S_5) = \{S_5\} \\ C(S_7) = \{S_7\}

（4）起始集B(S)和终止集E(S)。系统要素集合S的起始集实在S中只影响（到达）其他要素而不受其他要素影响的要素构成的集合。系统要素集合S的终止集是在S中，只受其他要素影响而不影响其他要素的要素的集合。

起始集的定义式如下：

B(S) = \{S_i | S_i \sub S, C(S_i) = A(S_i), i = 1,2,\ldots,n\}

这个定义的意思是，如果 $S_i$ 是起始集中的元素，则其先行集是可达集的子集，也就是说任何可达 $S_i$ 的元素，都可以由 $S_i$ 到达

之前的可达矩阵的起始集 $B = \{S_3,S_7\}$

终止集的定义式如下：

E(S) = \{S_i | S_i \sub S, C(S_i) = R(S_i), i = 1,2,\ldots,n\}

这个定义的意思是，如果 $S_i$ 是终止集中的元素，则其可达集是先行集集的子集，也就是说任何 $S_i$ 可达的元素，都可以到达 $S_i$

这样，要区分系统要素集合S是否可分割，只要研究系统起始集B中的要素及其可达集元素能否分割，或者研究终止集及其先行集要素是否可分割

利用起始集B判断区域是否可以划分的规则如下：

在B中任取两个元素 $b_u,b_v$ :

如果 $R(b_u) \cap R(b_v) \ne \emptyset$ ，则 $b_u,b_v$ 以及 $R（b_u），R（b_v）$ 中的要素属于同一区域，若对所有u,v都有此结果，则区域不可分
如果 $R(b_u) \cap R(b_v) = \emptyset$ ，则 $b_u,b_v$ 以及 $R（b_u），R（b_v）$ 中的要素不属于同一区域，若对所有u,v都有此结果，则S至少可以被划分为两个区域

区域划分的结果可记为： $II(S) = P_1,P_2,\ldots P_m$ ，经过区域划分后的可达矩阵是一个块对角矩阵（记作M(P)）

因为 $B = \{S_3,S_7\}$ ，且有 $R(S_3) \cap R(S_7) = \emptyset$ ，所以 $S_3,S_4,S_5,S_6$ 和 $S_1,S_2,S_7$ 分属两个相对独立的区域，即有 $II(S) = P_1,P_2 = \{S_3,S_4,S_5,S_6\},\{S_1,S_2,S_7\}$

此时的可达矩阵M变为如下块对角矩阵M(P)

级位划分

区域内的级位划分，即确定某区域内各要素所处的层次地位，这是建立多级递阶结构模型的关键。

设P是有区域划分得到的某区域的要素集合，若用 $L_1,L_2,\ldots,L_l$ 表示从高到低的各级要素集合，则级位划分结果可记为 $II(P) = L_1,L_2,\ldots,L_l$

某系统要素集合的最高级要素即该系统的终止集要素。级位划分的基本做法为，找出整个系统要素集合的最高级要素（终止集要素）后，可将他们去掉，再求剩余要素集合的最高级要素，以此类推，直到求道最低一级要素集合（即 $L_l$ ）

为此，令 $L_0 = \emptyset$ ，最高级要素为 $L_1$ ，没有零级元素，则有：

L_1 = \{S_i | S_i \sub P - L_0, C_0(S_i) = R_0{S_i}, i = 1,2,\ldots n \} \\ L_2 = \{S_i | S_i \sub P - L_0 - L_1, C_1(S_i) = R_1{S_i}, i \le n \} \\ ... \\ L_k = \{S_i | S_i \sub P - L_0 - L_1 - \ldots - L_{k-1}, C_{k-1}(S_i) = R_{k-1}{S_i}, i \le n \} \\

对 $P_1 = \{S_3,S_4,S_5,S_6\}$ 进行级位划分的过程如下所示

要素合集	$S_i$	$R(S_i)$	$A(S_i)$	$C(S_i)$	$C(S_i) = R(S_i)$	$II(P_1)$
$P_1 - L_0$	$3 \\ 4 \\ 5 \\ 6$	$3,4,5,6 \\ 4,5,6 \\ 5 \\ 4,5,6$	$3 \\ 3,4,6 \\ 3,4,5,6 \\ 3,4,6$	$3 \\ 4,6 \\ 5 \\ 4,6$	$false \\ false \\ true \\ false$	$L_1 = \{S_5\}$
$P_1 - L_0 - L_1$	$3 \\ 4 \\ 6$	$3,4,6 \\ 4,6 \\ 4,6$	$3 \\ 3,4,6 \\ 3,4,6$	$3 \\ 4,6 \\ 4,6$	$false \\ true \\ true$	$L_2 = \{S_4,S_6\}$
$P_1 - L_0 - L_1 - L_2$	$3$	$3$	$3$	$3$	$true$	$L_3 = \{S_3\}$