自反传递闭包

来自GSXAB的知识库
自反传递闭包
术语名称 自反传递闭包
英语名称 reflexive transitive closure

自反传递闭包(reflexive transitive closure)是指对集合上的一个二元关系，包含其的最小的自反且传递的关系。 它是传递闭包和自反闭包的复合，且这两个运算顺序可交换。

定义

自反传递闭包
运算名称 自反传递闭包
运算符号 [math]\displaystyle{ R^* }[/math]
Latex ^*
运算对象 关系
运算元数 1
运算结果 关系
定义域 [math]\displaystyle{ \mathcal{P}(X\times X) }[/math]
陪域 [math]\displaystyle{ \mathcal{P}(X\times X) }[/math]

对集合 [math]\displaystyle{ X }[/math] 上的二元关系 [math]\displaystyle{ R }[/math] ，定义满足以下条件的所有关系 [math]\displaystyle{ S }[/math] ：

  • [math]\displaystyle{ S }[/math] 是自反关系
  • [math]\displaystyle{ S }[/math] 是传递关系
  • [math]\displaystyle{ S \supseteq R }[/math]

其中必有一个关系是其他所有关系的子集，称为关系 [math]\displaystyle{ R }[/math] 的自反传递闭包(reflexive transitive closure)，记作 [math]\displaystyle{ R^* }[/math] 。

性质

  • 基本性质
    • 计算： [math]\displaystyle{ R^* = \bigcup_{i=0}^\infty R^i = I_X \cup R \cup R^2 \cup R^3 \cup \dots }[/math] ，其中 [math]\displaystyle{ R^0 = I_X }[/math]，[math]\displaystyle{ R^{n+1} = R \circ R^n }[/math]
      • 在有限集合 [math]\displaystyle{ X }[/math] 上（[math]\displaystyle{ \operatorname{card}X = n }[/math]），由于 [math]\displaystyle{ n }[/math] 个顶点的图中任何长度超过 [math]\displaystyle{ n }[/math] 的路径必然包含重复顶点，传递闭包可在有限步内计算：[math]\displaystyle{ \operatorname{t}(R) = \bigcup_{i=0}^n R^i }[/math] 。
    • 自反传递闭包是包含R的最小自反传递关系。
    • 自反闭包是向 [math]\displaystyle{ R }[/math] 上添加最少有序对构成的自反传递关系。
  • 运算性质
    • 自反传递闭包运算是幂等的： [math]\displaystyle{ (R^*)^* = R^* }[/math] 。
    • 自反传递闭包运算是单调的：如果 [math]\displaystyle{ R \subseteq S }[/math] ，则 [math]\displaystyle{ R^* \subseteq S^* }[/math] 。
    • 自反传递闭包与并运算的关系： [math]\displaystyle{ (R \cup S)^* \supseteq R^* \cup S^* }[/math] 。
    • 自反传递闭包与逆关系可交换： [math]\displaystyle{ (R^{-1})^* = (R^*)^{-1} }[/math] 。
  • 与其他闭包的关系
    • 自反闭包与传递闭包可交换，都得到自反传递闭包： [math]\displaystyle{ R^* = \operatorname{r}(\operatorname{t}(R)) = \operatorname{t}(\operatorname{r}(R)) }[/math] 。
    • 由于自反闭包和传递闭包都是幂等运算，同时使用时会被自反传递闭包吸收。
  • 特殊关系的自反传递闭包
    • 空关系的自反传递闭包是恒等关系： [math]\displaystyle{ \varnothing^* = I_X }[/math] 。
    • 恒等关系的自反传递闭包是其自身： [math]\displaystyle{ I_X^* = I_X }[/math] 。
    • 全关系的自反传递闭包是其自身： [math]\displaystyle{ (X \times X)^* = X \times X }[/math] 。
  • 表示
  • 关系图
    • 自反传递闭包的关系图中，存在从a到b的边当且仅当在原关系图中存在从a到b的路径（包括零长度路径）
    • 自反传递闭包对应于图的可达性关系，包括每个顶点到自身的可达性
    • 在有向图中，自反传递闭包给出了所有顶点对之间的可达性信息，包括每个顶点到自身
  • 关系矩阵


关系
定义属性 前域、后域、定义域 [math]\displaystyle{ \operatorname{dom} }[/math]、值域 [math]\displaystyle{ \operatorname{ran} }[/math]、域 [math]\displaystyle{ \operatorname{fld} }[/math]
特殊关系 空关系 [math]\displaystyle{ \varnothing }[/math]、恒等关系 [math]\displaystyle{ I }[/math]、全关系 [math]\displaystyle{ A\times B }[/math]
二元齐次关系类型 自反、反自反、对称、反对称、传递
运算 集合运算 交 [math]\displaystyle{ \cap }[/math]、并 [math]\displaystyle{ \cup }[/math]、补 [math]\displaystyle{ \bar{\bullet} }[/math]、差 [math]\displaystyle{ \setminus }[/math]
类映射运算 转置/逆 [math]\displaystyle{ \bullet^\mathrm{T}/\bullet^{-1} }[/math]、复合 [math]\displaystyle{ \circ }[/math]（幂 [math]\displaystyle{ \bullet^n }[/math]）、限制 [math]\displaystyle{ \bullet_{|\bullet} }[/math]
闭包运算 自反 [math]\displaystyle{ \operatorname{r}() }[/math]/[math]\displaystyle{ \bullet^= }[/math]、对称 [math]\displaystyle{ \operatorname{s}() }[/math]/[math]\displaystyle{ \bullet^\sim }[/math]、传递 [math]\displaystyle{ \operatorname{t}() }[/math]/[math]\displaystyle{ \bullet^+ }[/math]、自反传递 [math]\displaystyle{ \bullet^* }[/math]、等价 [math]\displaystyle{ \bullet^\equiv }[/math]
检索自“https://knowledge.gsxab.top/index.php?title=自反传递闭包&oldid=5674”