离散数学-复合关系与逆关系

复合关系

定义

设R是集合A到B的二元关系，S是集合B到C的二元关系，R和S的复合记作：$R \circ S$，它是集合A到C的二元关系，仅当$( a,b) \in R$且$(b,c) \in R$时，$(a,c) \in R \circ S$。

复合关系的矩阵表示

表示方法

设$A = {a_1,a_2,a_3,…,a_n}, B = {b_1,b_2,b_3,…,b_m},C = {c_1,c_2,c_3,…,c_p}$,R时A到B的二元关系,R的关系矩阵为：
$$
M_R = \begin{bmatrix}
x_{11} & x_{12} & \cdots & x_{1m} \\
x_{21} & x_{22} & \cdots & x_{2m} \\
\vdots & \vdots & \ddots & \vdots \\
x_{n1} & x_{n2} & \cdots & x_{nm} \\
\end{bmatrix}
$$

其中：
$$
x_{ij} =
\begin{cases}
1 & (a_i,b_j)\in R \\
0 & (a_i,b_j) \notin R
\end{cases}
$$

S是B到C的二元关系，S的关系矩阵为：
$$
M_s = \begin{bmatrix}
y_{11} & y_{12} & \cdots & y_{1p} \\
y_{21} & y_{22} & \cdots & y_{2p} \\
\vdots & \vdots & \ddots & \vdots \\
y_{m1} & y_{m2} & \cdots & y_{mp} \\
\end{bmatrix}
$$
令$M_R\times M_S = [z_{ij}]$，即有：
$$
M_R \times M_S = \begin{bmatrix}
z_{11} & z_{12} & \cdots & z_{1p} \\
z_{21} & z_{22} & \cdots & z_{2p} \\
\vdots & \vdots & \ddots & \vdots \\
z_{n1} & z_{n2} & \cdots & z_{np} \\
\end{bmatrix}
$$
由矩阵乘法规则的：
$$
z_{ij} = x_{i1}\times y_{1j} + x_{i2}\times y_{2j}+ \dots + x_{im} \times y_{mj} = \sum\limits_{k = 1}^m x_{ik} \times y_{kj}
$$

对于式中的$x_{ik}\times y_{ik}$，当且仅当，$x_{ik},y_{kj}$同时为1时，计算结果才为1。又由于只有当$(a_i,b_k) \in R \and (b_k,c_j) \in S$时，才有$x_{ik} \neq 0 \and y_{kj} \neq 0$，故，由复合运算的定义可得，此时的$R \circ S$中应该包含$(a_{i},c_{j})$，即$z_{ij} \neq 0$。

故以此法就能通过矩阵乘法去确定一个复合关系的关系矩阵，而在计算矩阵乘法的过程中，我们只关注$\sum\limits_{k = 1}^m x_{ik} \times y_{kj}$中是否有1出现，故我们可以将此处的加法替换为布尔加（即 0+0 = 0，1+0 = 0+1 = 1，1+1 = 1），这样在编程实现中，就能使用与运算来代替10进制的加法运算，众所周知，代码的世界里，位运算要比10进制运算来的快。

我们用$M_R \circ M_S$来表示使用布尔加的矩阵乘法，于是可以得到如下定理

特征

复合关系具有如下特征：

1. 满足结合律
2. $R^i \circ R^j = R^{i+j}$（i,j为正整数）；$R^0$定义为${(a_1,b_1),(a_2,b_2),\dots ,(a_n,b_n)}$，即关系矩阵为单位矩阵

逆关系

定义

设R是A到B的二元关系，如果把R中的每一个有序对中的元素顺序互换，所得B到A的二元关系称为R的逆关系，记作$R^{-1}$或$\tilde{R}$

矩阵表示

若二元关系R的的关系矩阵为$M R$，则$M_R$的转置$M{R}^T$，就是关系$R^{-1}$的关系矩阵

特征

有矩阵转置的运算规则可知：

$(A \times B)^T = B^T \times A^T$

由此可得以下定理

关系的闭包运算

闭包运算的定义

在给定的二元关系中，添加==最少量==的有序对后，使其称为自反的，或对称的，或传递的二元关系，则这样的操作称为关系的闭包运算

自反、对称、传递闭包

设R是A上的二元关系，R的自反（对称、传递）闭包$R’$也是A上的二元关系，且满足：

1. $R’$是自反的（对称的，传递的）
2. $R’ \supseteq R$
3. 对于任何A上的自反的（对称的、传递的）二元关系$R’’$，如果$R’’ \supseteq R$，则必有$R’’\supseteq R’$

通常R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)

求闭包

对于自反闭包和对称闭包，通过简单的添加“缺啥补啥”的原则即可求出

但在求传递闭包时，补充的元素可能会和已有的元素再次构成隐含的传递关系，那么处理起来就比较麻烦，下面介绍Warchall提出的求传递闭包的算法：

1. 置矩阵$M = M_R$（$M_R$ 是关系矩阵）
2. 置 j = 1
3. 对所有i，如果$m_{ij} = 1$，则对$k = 1,2,\dots,n$，置$m_{ik} = m_{ik} + m_{jk}$，即把第j行加到第i行
4. j = j + 1
5. 如果$ j \leq n$，则跳转到步骤3，否则停止