关系的闭包

需要改造 $R$ 为一个具有某种性质的关系， $R$ 的闭包是 $A$ 上具有该性质的关系中最小的一个 $R^{'}$ 。即：

$R^{'}$ 具有该性质
$R \subseteq R^{'}$
对 $A$ 上任何具有该性质的关系 $S$ ， $R^{'} \subseteq S$

$R$ 的自反闭包记作 $r (R) = R \cup R^{0} = R \cup I_{A}$ $R$ 的对称闭包记作 $s (R) = R \cup R^{- 1}$ $R$ 的传递闭包记作 $t (R) = R \cup R^{2} \cup R^{3} \cup \dots$

对有穷集 $A (| A | = n)$ ， $R$ 的传递闭包 $t (R) = R \cup R^{2} \cup \dots \cup R^{n}$

矩阵表示

分别设 $R, r (R), s (R), t (R)$ 的关系矩阵为 $M, M_{r}, M_{s}, M_{t}$ ，则

\begin{aligned} M_{r} & = M + I M_{s} & = M + M^{T} M_{t} & = M + M^{2} + M^{3} + \dots + M^{n} \end{aligned}

图表示

$r (R)$ ：在 $G_{R}$ 中添加自环
$s (R)$ ：在 $G_{R}$ 中添加对称边
$t (R)$ ：在 $G_{R}$ 中添加传递边

闭包的性质

$R$ 是自反的 $\Leftrightarrow$ $r (R) = R$ $R$ 是对称的 $\Leftrightarrow$ $s (R) = R$ $R$ 是传递的 $\Leftrightarrow$ $t (R) = R$

若 $R_{1} \subseteq R_{2}$ ，则 $r (R_{1}) \subseteq r (R_{2})$ $s (R_{1}) \subseteq s (R_{2})$ $t (R_{1}) \subseteq t (R_{2})$

$r (s (R)) = s (r (R))$
$r (t (R)) = t (r (R))$
$s (t (R)) \subseteq t (s (R))$
$t (s (r (R))) = r (t (s (R))) = t (r (s (R)))$

R	r(R)	s(R)	t(R)
自反	$✓$	$✓$	$✓$
对称	$✓$	$✓$	$✓$
传递	$✓$	$\times$	$✓$