跳到主要内容

关系闭包与 Warshall 算法

在离散数学中，很多结构问题都可归结为“关系是否满足某种性质”。
闭包思想用于以最小代价补全关系，Warshall 算法则给出传递闭包的标准计算流程。

1. 关系闭包的基本概念​

设 R⊆A×AR\subseteq A\times A。

  • 自反闭包：Rr=R∪IAR_r=R\cup I_A，其中 IA={(a,a)∣a∈A}I_A=\{(a,a)\mid a\in A\}。
  • 对称闭包：Rs=R∪R−1R_s=R\cup R^{-1}。
  • 传递闭包：最小的传递关系 RtR_t，且 R⊆RtR\subseteq R_t，记作 R+R^+。

若同时要求自反与传递，常记 R∗=R+∪IAR^*=R^+\cup I_A。

例题 1（自反与对称闭包）​

设 A={1,2,3}A=\{1,2,3\}，R={(1,2),(2,3)}R=\{(1,2),(2,3)\}，求 Rr,RsR_r,R_s。

解：

Rr=R∪{(1,1),(2,2),(3,3)}, R_r=R\cup\{(1,1),(2,2),(3,3)\}, Rs=R∪{(2,1),(3,2)}.R_s=R\cup\{(2,1),(3,2)\}.

2. 传递闭包与路径解释​

把关系 RR 看作有向图边集，R+R^+ 恰好表示“存在长度至少 1 的有向路径”的可达关系。

定理 1​

R+=R∪R2∪R3∪⋯ R^+=R\cup R^2\cup R^3\cup\cdots

在有限集上最多累积到 ∣A∣−1|A|-1 次复合即可稳定。

例题 2（路径法求传递闭包）​

设 A={1,2,3}A=\{1,2,3\}，R={(1,2),(2,3)}R=\{(1,2),(2,3)\}。

解： 有 (1,2),(2,3)∈R(1,2),(2,3)\in R，故 (1,3)∈R2(1,3)\in R^2。
因此：

R+={(1,2),(2,3),(1,3)}. R^+=\{(1,2),(2,3),(1,3)\}.

3. 关系矩阵表示​

对 A={a1,…,an}A=\{a_1,\dots,a_n\}，关系矩阵 MR=(mij)M_R=(m_{ij}) 定义为：

mij={1,(ai,aj)∈R,0,otherwise. m_{ij}= \begin{cases} 1,&(a_i,a_j)\in R,\\ 0,&\text{otherwise}. \end{cases}

矩阵布尔乘法对应关系复合。
因此可用矩阵迭代计算传递闭包。

例题 3（矩阵建模）​

设 A={1,2,3}A=\{1,2,3\}，R={(1,2),(2,3)}R=\{(1,2),(2,3)\}，写出 MRM_R。

解：

MR=(010001000). M_R= \begin{pmatrix} 0&1&0\\ 0&0&1\\ 0&0&0 \end{pmatrix}.

4. Warshall 算法​

Warshall 算法用于直接求可达矩阵（传递闭包矩阵）。

设初始矩阵 W(0)=MRW^{(0)}=M_R，递推：

wij(k)=wij(k−1)∨(wik(k−1)∧wkj(k−1)),k=1,…,n. w_{ij}^{(k)}=w_{ij}^{(k-1)}\lor\big(w_{ik}^{(k-1)}\land w_{kj}^{(k-1)}\big), \quad k=1,\dots,n.

含义：逐步允许中间点来自 {1,…,k}\{1,\dots,k\}。

例题 4（Warshall 核心一步）​

对例题 3 的矩阵，当 k=2k=2 时，为什么会把 (1,3)(1,3) 置为 1？

解： 因为 w12(1)=1w_{12}^{(1)}=1 且 w23(1)=1w_{23}^{(1)}=1，故

w13(2)=w13(1)∨(w12(1)∧w23(1))=0∨(1∧1)=1. w_{13}^{(2)}=w_{13}^{(1)}\lor(w_{12}^{(1)}\land w_{23}^{(1)})=0\lor(1\land1)=1.

例题 5（等价闭包构造）​

给定关系 RR，如何得到最小等价关系包含它？

解： 可按步骤构造：

  1. 先取对称闭包 Rs=R∪R−1R_s=R\cup R^{-1}；
  2. 再取其自反传递闭包 (Rs)∗(R_s)^*。
    得到的关系即包含 RR 的最小等价关系。

5. 本章练习​

练习 1​

设 A={1,2,3}A=\{1,2,3\}，R={(1,2)}R=\{(1,2)\}，求 RR 的对称闭包。

点击查看过程与答案
Rs=R∪R−1={(1,2),(2,1)}. R_s=R\cup R^{-1}=\{(1,2),(2,1)\}.

练习 2​

设 R={(1,2),(2,3),(3,4)}R=\{(1,2),(2,3),(3,4)\}（定义在 {1,2,3,4}\{1,2,3,4\} 上），求 (1,4)(1,4) 是否属于 R+R^+。

点击查看过程与答案

因为存在路径 1→2→3→41\to2\to3\to4，故 (1,4)∈R+(1,4)\in R^+。

练习 3​

在 Warshall 更新公式中，若某一步 wik=0w_{ik}=0，还能否通过该 kk 让 wijw_{ij} 变成 1？

点击查看过程与答案

不能。因为

wik∧wkj=0∧wkj=0, w_{ik}\land w_{kj}=0\land w_{kj}=0,

该中间点 kk 对 (i,j)(i,j) 的可达更新无贡献。

练习 4​

关系 RR 已自反、对称但不传递。若要得到最小等价关系，需要补什么闭包？

点击查看过程与答案

只需补传递闭包并保留自反性：

Req=R∗. R_{\text{eq}}=R^*.

6. 学习闭环​