2.7 二元关系闭包

二元关系闭包

闭包的定义

闭包（Closure）是指在保持关系原有性质的基础上，添加最少的有序对，使关系具有某种特定性质。

自反闭包 r(R)

自反闭包（Reflexive Closure）：在关系 $R$ 中添加最少的有序对使其具有自反性，记作 $r(R)$。

$r(R)=R\cup I_A$，其中 $I_A$ 是 $A$ 上的恒等关系。

对称闭包 s(R)

对称闭包（Symmetric Closure）：在关系 $R$ 中添加最少的有序对使其具有对称性，记作 $s(R)$。

$s(R)=R\cup R^{-1}$，其中 $R^{-1}$ 是 $R$ 的逆关系。

传递闭包 t(R)

传递闭包（Transitive Closure）：在关系 $R$ 中添加最少的有序对使其具有传递性，记作 $t(R)$。

$t(R)=R\cup R^2\cup R^3\cup \dots$（关系的所有正幂的并集）

Warshall 算法

Warshall 算法是计算传递闭包的高效方法：

简单来说，就是从 $1$ 到 $n$ 遍历所有的纽带元素 $i$，对于每一个 $i$，考察第 $i$ 列，第 $i$ 列中为 $1$ 的行是调整的对象，而第 $i$ 行为调整的参照，将参照行逻辑并上对象行作为新对象行，直到 $i$ 取完 $n$。

链接到

• 上一个知识点：2.6 二元关系运算
• 下一个知识点：2.8 等价关系与划分