本文为《离散数学及其应用》的第九章的笔记

设 A 和 B 是集合，一个从 A到 B 的二元关系是 $A \times B$ 的子集。换句话说，一个从 A 到 B 的二元关系 R，其中每个有序对的第一个元素取自 A 而第二个元素取自 B。我们使用记号 aRb 表示 $(a, b) \in R$，称为 a 与 b 有关系 R。

一、集合的关系

集合 A 上的关系是 A 到 A 的关系，也就是集合 A 上的关系是 $A \times A$ 的子集。

二、关系的性质

  • 自反关系：

在某些关系中，某元素总是与自身相关。若对每个元素 $a \in A$，都有 $(a, a) \in R$，那么定义在集合 A 上的关系 R 称为自反的。

用量词描述即为 $\forall a ((a, a) \in R)$。

  • 对称关系：

对任意 $a, b \in A$，若只要 $(a, b) \in R$ 就有 $(b, a) \in R$，则称定义在集合 A 上的关系 R 为对称的。

用量词描述即为 $\forall a \forall b((a, b) \in R) \rightarrow (b, a) \in R)$

  • 反对称关系：

对任意 $a, b \in A$，若只要 $(a, b) \in R$ 且 $(b, a) \in R$，一定有 $a = b$，则称定义在集合 A 上的关系 R 为反对称的。

用量词描述即为 $\forall a \forall b((a, b) \in R \bigwedge (a, b) \in R) \rightarrow (a=b))$

  • 传递关系：

若对于任意 $a, b, c \in A$，$(a, b) \in R$ 并且 $(b, c) \in R$ 则 $(a, c) \in R$，那么定义在集合 A 上的关系 R 称为传递的。

用量词描述即为 $\forall a \forall b \forall c (((a, b) \in R \bigwedge (b, c) \in R) \rightarrow (a, c) \in R)$

三、关系的合成

设 R 是从集合 A 到集合 B 的关系，S 是从集合 B 到集合 C 的关系。R 和 S 的合成是由有序对 (a, c) 的集合构成的关系，其中 $a \in A$，$c \in C$，并且存在一个 $b \in B$ 的元素，使得 $(a, b) \in R$ 且 $(b, c) \in S$。用符号 $S \circ R$ 表示 S 和 R 的合成。

  • 幂的合成

设 R 是集合 A 上的关系。R 的 n 次幂 $R^n(n = 1, 2, 3,…)$ 递归地定义为 $R^1 = R$ 和 $R^{n+1} = R^n \circ R$

  • 传递关系的幂是该关系的子集

集合 A 上的关系 R 是传递的，当且仅当对 n = 1, 2, 3, … 有 $R^n \subseteq R$。

四、n 元关系

设 $A_1$，$A_2$，…，$A_n$ 是集合。定义在这些集合上的 n 元关系是 $A_1 \times A_2 \times … \times A_n$ 的子集。这些集合 $A_1$，$A_2$，…，$A_n$ 称为关系的域，n 称为关系的阶。

五、n 元关系的运算

  • 投影

投影 $P_{i_1,i_2,…,i_m}$，其中 $i_1 < i_2 < … < i_m$，将 n 元组 $(a_1, a_2, …,a_n)$ 映射到 m 元组 $(a_{i_1},a_{i_2},…,a_{i_m})$ ，其中 $m \leq n$。

换句话说，投影 $P_{i_1,i_2,…,i_m}$ 删除了 n 元组的 n - m 个分量，保留了 $i_1$，$i_2$，…，$i_m$ 个分量。

上述定义比较抽象，此处我们借用一个例子来说明：当对四元组 (2, 3, 0, 4)、(Jane Doe, 234111001, 地理学, 3.14) 以及 ($a_1$，$a_2$，$a_3$，$a_4$) 用投影 $P_{1,3}$ 时，结果应为 (2, 0)、(Jane Doe, 地理学) 和 $(a_1, a_3)$。

  • 连接

设 R 为 m 元关系，S 为 n 元关系。连接运算 $J_p(R, S)$ 是 m + n - p 元关系，其中 $p \leq m$ 和 $p \leq n$，它包含了所有的 (m + n - p) 元组 $(a_1,a_2,…,a_{m-p},c_1,c_2,…,c_p,b_1,b_2,…,b_{n-p})$。其中 m 元组 $(a_1,a_2,…,a_{m-p},c_1,c_2,…,c_p)$ 属于 R 且 n 元组 $(c_1,c_2,…,c_p,b_1,b_2,…,b_{n-p})$ 属于 S。

同样，我们通过举例帮助理解：

列A 列B
a b
c d
列B 列C
b B

将上述两表进行连接运算 $J_1$，将会得到：

列A 列B 列C
a b B

可以发现：连接运算 $J_p$ 将 m 元组的后 p 个分量与 n 元组的前 p 个分量相同的第一个关系中的所有 m 元组和第二个关系的所有 n 元组组合产生一个新的关系。

不难发现，上述运算可以和我们熟悉的 SQL 多表查询做类比：

1
2
3
SELECT column_a, column_b
FROM table_a, table_b
WHERE ""

六、关系的表示

  • 用矩阵表示关系

可以用一个 0-1 矩阵来表示一个有穷集之间的关系。假设 R 是从 $A = {a_1,a_2,…,a_m}$ 到 $B={b_1,b_2,…b_n}$ 的关系。关系 R 可以用矩阵 $M_R = [m_{ij}]$ 来表示，其中：$m_{ij}=\begin{cases} 1 \text{$(a_i,b_j)\in R$} \0 \text{$(a_i,b_j)\notin R$} \end{cases}$

换句话说，当 $a_i$ 和 $b_j$ 有关系时表示 R 的 0-1 矩阵的 (i, j) 项为 1，当 $a_i$ 和 $b_j$ 没有关系时表示 R 的 0-1 矩阵的 (i, j) 项为 0。

  1. 如果 $M_R$ 的主对角线上所有元素都等于 1，那么 R 是自反的。

  2. 如果对于 $M_R$ 来说，都有 $m_{ij} = m_{ji}$，那么关系 R 是对称的。

  3. 如果对于 $M_R$ 来说，如果 $m_{ij} = 1$，$i \not= j$，则 $m_{ji} = 0$;

    换句话说：当 $i \not= j$ 时，$m_{ij} = 0$ 或 $m_{ji} = 0$;

    那么关系 R 是反对称的。

关系的并、交、布尔积的矩阵表达式：

$M_{R_1 \bigcup R_2} = M_{R_1} \bigvee M_{R_2}$

$M_{R_1 \bigcap R_2} = M_{R_1} \bigwedge M_{R_2}$

$M_{S \circ R} = M_R \bigodot M_S$

性质：

$M_{R^n} = M_{R}^{[n]}$

  • 用图表示关系

我们将一个有穷集上的关系看作一个有向图，节点 a、b 如果存在一条由 a 到 b 的有向线段，则代表 a 和 b 之间存在关系。

七、关系的闭包

如果存在包含 R 的具有性质 P 的关系 S，并且 S 是所有包含 R 且具有性质 P 的关系的子集，那么 S 叫做 R 的 关于性质 P 的闭包。

上述 P 可取：自反、传递、对称。

  • 一个关系的传递闭包 等价于 在相关的有向图确定哪些顶点对之间存在路径。
  • 设 R 是集合 A 上的关系。连通性关系 $R^*$ 由形如 (a, b) 的有序对构成，使得在关系 R 中，从 a 到 b 之间存在一条长度至少为 1 的路径。
  • 关系 R 的传递闭包等于连通性关系 $R^*$。

传递闭包的计算：

算法1: 设 $M_R$ 是定义在 n 个元素集合的关系 R 的 0-1 矩阵。那么传递闭包 $R^*$ 的 0-1 矩阵是 $M_{R^*} = M_R \bigvee M_R^{[2]} \bigvee M_R^{[3]} \bigvee … \bigvee M_R^{[n]}$

但如上算法为从 n 个 $M_R$ 的布尔幂求 $M_{R^*}$，需要求 n - 1 个 0-1 矩阵的布尔积。计算每个布尔积使用 $n^2(2n-1)$ 次位运算。因此，计算这些乘积需要使用 $n^2(2n - 1)(n - 1)$ 次位运算。因此，该算法的复杂度为 $O(n^4)$，显然时间开销较大。

沃舍尔算法：

假设 R 是定义在 n 个元素集合上的关系。设 $v_1$，$v_2$，…，$v_n$ 是这 n 个元素的任意排列。如果 a，$x_1$，$x_2$，…，$x_{m-1}$，b 是一条路径，它的内部顶点为 $x_1$，$x_2$，…，$x_{m-1}$，即除了第一和最后一个顶点之外出现在路径中的所有顶点。

沃舍尔算法的基础是构造一系列的 0-1 矩阵。这些矩阵记作 $W_0$，$W_1$，…，$W_n$，其中 $W_0 = W_R$ 是这个关系的 0-1 矩阵，且 $W_k = [\omega_{ij}^{(k)}]$。如果存在一条从 $v_i$ 到 $v_j$ 的路径使得这条路径的所有内部顶点都在集合 ${v_1,v_2,…,v_k}$,那么 $\omega_{ij}^{(k)}$ = 1，否则为 0。

注意：$W_n = M_{R^*}$。因为 $M_{R^*}$ 的第 (i , j) 项是 1，当且仅当存在一条从 $v_i$ 到 $v_j$ 的路径，且全部内部顶点都在集合 ${v_1,v_2,…,v_n}$ 中。

沃舍尔算法通过有效计算 $W_0 = M_R$，$W_1$，$W_2$，…，$W_n = M_{R^*}$ 来计算 $M_{R^*}$

八、等价关系

定义在集合 A 上的关系叫做等价关系，如果他是自反的、对称的和传递的。

如果两个元素 a 和 b 由于等价关系而相连，则称他们是等价的。写作 a ~ b。

  • 等价类：

设 R 是定义在集合 A 上的等价关系。与 A 中的一个元素 a 有关系的所有元素的集合叫做 a 的等价类。A 的关于 R 的等价类记作 $[a]_R$。当只考虑一个关系的时候可以省略下标 R 并把这个等价类写作 [a]。

换句话说，如果 R 是定义在集合 A 上的等价关系，则元素 a 的等价类是：$[a]_R = {s|(a, s) \in R }$

如果 $b \in [a]_R$，b 叫做这个等价类的代表元。一个等价类的任何元素都可以作为这个类的代表元。

定理：设 R 是定义在集合 A 上的等价关系，下面的关于集合 A 中 a、b 两个元素的命题是等价的。

  1. aRb
  2. [a] = [b]
  3. [a] $\bigcap$ [b] $\not=$ $\emptyset$

  • 现在将说明一个等价关系怎样划分一个集合：设 R 是定义在集合 A 上的等价关系，R 的所有等价类的并集是集合 A，因为 A 的每个元素 a 都在它自己的等价类中。换句话说 $\bigcup _{a \in A} [a]_R = A$。

    更确切地说，所有等价类的并集就是集合 A。

定理：设 R 是定义在集合 S 上的等价关系。那么 R 的等价类构成 S 的划分。反过来，给定集合 S 的划分 ${A_i | i \in I}$，则存在一个等价关系 R，它以集合 $A_i(i \in I)$ 作为它的等价类。

九、偏序

定义在集合 S 上的关系 R，如果它是自反的、反对称的、传递的，就称为偏序。集合 S 与定义在其上的偏序 R 一起称为偏序集，记作 (S, R)。集合 S 中的成员称为偏序集的元素。

偏序集 (S, $\leq$) 中的元素 a 和 b 称为可比的。当 a 和 b 是 S 中的元素并且既没有 $a \leq b$，也没有 $b \leq a$，则称 a 和 b 是不可比的。

偏序集 (S, $\leq$) 是偏序集，且 S 中的每对元素都是可比的，则 S 称为全序集或线序集，且 $\leq$ 被称为全序。

对于偏序集 (S, $\leq$)，如果 $\leq$ 是全序，并且 S 的每个非空子集都有一个最小元素，则称为良序集。

  • 哈塞图

我们可以从一个例子来理解哈塞图：已知集合 {1, 2, 3, 4} 上的偏序 {(a, b) | $a \leq b$}，则可以画出有向图如图a。由于这个关系是偏序的，所以必然是自反的，因此我们省略顶点到自身的环得到图 b。再者，我们假设所有的线段都是自下而上的，同时借助关系的传递性，我们可以得到图 c。

十、极大元和极小元

如果偏序集中的一个元素不小于这个偏序集中的其他元素，则称为极大元。反之，称为极小元。

通过哈塞图可以很容易识别极大元和极小元，分别为最顶部和最底部的元素。

  • 上界和下界：

有时候可以找到一个元素大于或等于偏序集 (S, $\leq$) 的子集 A 中的所有元素。如果 u 是 S 中的元素，使得对所有的元素 $a \in A$，有 $a \leq u$，那么 u 称为 A 的一个上界。如果一个上界 x 小于 A 的任何其他上界，则称为最小上界。

  • 格：

如果一个偏序集的每对元素都有最小上界和最大下界，就称这个偏序集为格。

十一、拓扑排序

我们定义：如果只要 $aRb$ 就有 $a \leq b$，则称一个全序 $\leq$ 与偏序 R 是相容的。

从一个偏序构造一个相容的全序称为拓扑排序。

参考书籍：《离散数学及其应用》Kenneth H. Rosen 著