2.5 关系的闭包
本章目录 · 1 节
本章导读
闭包的目的,是只通过补加必要的有序对,让原关系获得指定性质,并尽量少加。这里的“最小”指按集合包含比较的最小关系,不是仅指某种画法的边数看起来较少。它同时保留原有关系、满足目标性质,并被任何同样符合要求的关系包含。
定义2.5.1:设 是非空底集 上的关系。自反闭包是满足以下条件的 :它自反;;对任何自反且包含 的关系 ,均有 。把“自反”分别换成“对称”和“传递”,得到对称闭包与传递闭包。分别记为 。若两个关系都满足同一种闭包定义,它们按最小性彼此包含,因此相等,说明闭包唯一。
定理2.5.1:三种闭包可直接表示为
自反闭包只补缺少的全部对角项;对称闭包只补已有边的反向边;传递闭包补齐所有正长度有向游走的起终点关系。传递闭包的并从1开始,不包含零次幂。若某顶点没有经过正长度回路回到自身,它在传递闭包中仍可没有自环。要允许零步到达,再额外并上 ,得到另一种自反可达关系。
证明自反闭包公式时, 显然自反且包含 ;任意自反关系若包含 ,也必须包含 ,所以包含二者之并。对称闭包同理:任意对称的超关系必须同时包含 ,而 本身对称。
传递闭包公式需要同时检查性质和最小性。令 。若 且 ,存在正整数 使 ,由幂运算律得到 ,所以 ,即 传递。若 是任意包含 的传递关系,归纳可知 对每个正整数成立,因此 。这说明 不仅是一个传递超关系,而且确实是最小的那个。
推论2.5.1:有限底集上的传递闭包只需有限多个幂相并。若 ,更具体地有
其原因不是把所有游走的长度都限制为 ,而是任何可达的起终点都能选取一条足够短的代表游走:不同起终点之间删去重复顶点形成的回路后至多 步;相同起终点的正长度闭路可取一条至多 步的简单回路。所以考虑前 个正次幂已覆盖全部可达有序对。
在矩阵中,相应公式为 、、,其中矩阵乘法和按位置相加均按布尔运算解释。这里 是同阶单位矩阵;若使用普通数值加法,会把两个1加成2而不再得到关系矩阵。
在关系图中,补自反闭包就是给没有自环的顶点加环;补对称闭包就是给缺少反向边的有向边加反向边;补传递闭包就是对每个起点找出所有正长度可达的终点并连边。顶点集始终保持为原底集,不因补边新增顶点,也不因某个点暂时没有出边而删除它。
【例2.5.1】设 ,,求原关系及三种闭包的关系图。
解:原图有5条边;自反闭包添加四个自环,共9条边;对称闭包为每个缺少反向边的有序对补反向关系,共8条边。原图中 可经 到达每个顶点, 也都能绕回并到达 ,所以任意两个顶点之间都有正长度游走,包括回到各自本身。因此 ,含16个有序对,四个自环也都必须出现。
沃舍尔算法用动态规划求传递闭包。固定顶点顺序 ,。矩阵 表示正长度游走的内部顶点只允许取自 时的可达关系。加入允许经过的顶点 时,有
不经过 的路径由第一项保留;经过它的路径可以分成从 到 和从 到 两段,由第二项连接。重复经过中间点的绕行可先删去,所以这一分类足以描述可达性。
算法开始时复制原关系矩阵,随后把 从1到 置于最外层;对每个 ,再遍历全部 ,更新 。最终矩阵为 。时间复杂度为 ;原地更新只需 的矩阵存储。不能任意把外层的 与内层循环交换后仍沿用同一个动态规划证明。也不能为了方便预先把主对角线全部设为1,那样计算的是额外含恒等关系的闭包。
对上一例,按 顺序,五个阶段为
每个阶段只增加已证实存在路径的有序对,最后结果与图中判断的全域关系一致。
定理2.5.2: 自反当且仅当 ; 对称当且仅当 ; 传递当且仅当 。若原关系已有性质,它自身就是合格的最小超关系,无需再补边;反过来,若与相应闭包相等,就具有该闭包的性质。
定理2.5.3:若 ,则 、、。自反和对称闭包可直接用公式证明;传递闭包则由任意 路径也是 路径得到。三种闭包还都满足再次取同一种闭包不再变化,这是定理2.5.2的直接应用。
定理2.5.4:若 自反,则 仍自反;若 对称,则 仍对称;若 传递,则 仍传递。第一组因为两个闭包都包含原来的全部自环。第二组中, 的两部分都对称;而对称关系上的任意有限路径都能反向走,因此每个正次幂以及它们的并都对称。第三组中,新增的恒等步骤不改变路径起终点,所以 仍传递。
对称闭包却未必保持传递性。例如 、 原本传递,但 缺少两个由往返路径要求的自环,因而不传递。若要同时获得自反、对称、传递三种性质,可按 的顺序构造,让传递闭包最后完成。所得关系保留三种性质,并且包含于任意同时满足三种性质且包含 的关系;后面可用等价关系进一步解释这种联合闭包。
