9 . 4

闭包:对一个关系作最小的扩充,使扩充后的关系恰好具有给定的性质(自反对称传递及这些性质的组合)。严格的表述就是包含关系R且具有给定性质的关系一定也包含R的闭包R’。

证明关系R’是R的闭包:首先证R’包含R,然后证任何具给定性质,且包含R的关系R”,必然也包含R’。

自反闭包:原关系与对角关系(和单位矩阵类似)取并。

对称闭包:原关系与原关系的逆取并。

给出传递闭包的获得方式前,引入另一些概念。

有向图上的路径:就是从起始点到终点的边的序列组合。

长度为0的路径:不包含任意一条边的边集合(即空集),认为是任意一个结点到它自己的0长度路径。

循环:一条长度大于等于1,且起始终止点相同的路径称为一个循环。

注:一条有向图上的路径可以经过一条边、或一个结点超过一次。

R ^ n在路径概念基础上的理解:如果在R上,有一条从a到b,长度恰为n的有向图路径,则(a, b)属于R ^ n。这个定理是充要的。证明使用数学归纳法。

连通性关系:对未给定建立集合中元素个数的关系,R*就是把R的各次方从1到无穷进行求并。(注意这里用了和学校课本冲突的符号)

(闲的时候找找在wordpress输入数学表达式的办法……遇到公式全是靠自然语言去讲好难受……)

此时能引出传递闭包的获得方式:传递闭包就是等于R上的连通性关系R*。证明分这几步:证明R*包含R;证明R*传递;证明任何包含R且传递的关系S必然包含R*。

记一个小结论:如果关系R是传递的,则关系R ^ n仍然是传递的。证明使用数学归纳法。

关于路径长的定理:设A为具有n个元素的集合,R是在A上的关系。如果R上存在从a到b,长度至少为1的路径,则存在同样起终点的路径,长度不超过n。如果同时a != b,则之前的“长度不超过n”改为“不超过n – 1”。

用上述的定理,能将得到传递闭包的过程进行优化,只要对最多n次方进行求并即可。

从上面的叙述,很自然地得到最原始的求关系矩阵闭包的算法:就是从1到n次方全算一遍,再去求并。这个算法的复杂度是O(n ^ 4)。介绍Warshall算法,该算法的时间复杂度是O(n ^ 3)。

先引出一个内部顶点的概念:对一条有向图的路径,去掉首尾两点,剩下的结点就是内点。

记一下这个算法的执行方式:这个算法的目的在于要依次建立W0到Wn矩阵。先对图中出现的所有顶点定一个排列。W0就是原矩阵。每一次要计算Wi矩阵时,先把Wi – 1矩阵原封不动地搬到Wi中。之后对顶点的排列关注前i个。对Wi的每个还是为0的entry,关注从顶点i到顶点j是否存在一条路径,其内部顶点只有排列中前i个顶点出现。如果是,则把该entry的0变为1,如果已经为1,则跳过。依次进行。则Wn就是所求的原关系的传递闭包关系矩阵。

9 . 5

等价关系:如果一个关系同时满足自反、对称、传递,则它是等价的。

书上使用了~记法,如A ~ B。

模m等价:如果a mod m == b mod m,则称a、b模m等价。记作a == b (mod m)。

注意a、b“模m等价”等价于a – b被m整除。这个特性用于一些模m等价命题的证明。

等价类:令R为集合A上的等价关系。对A中某一个元素a,所有与a相关的元素集合即为a的等价类,记作[a]R。如果只考虑某一个关系,那么省略下标R。

属于等价类的一个元素称为这个等价类的一个代表。一个等价类中的任意一个元素都能作为该类的一个代表。

令R为A上的等价关系。注意这三个命题等价:aRb、[a] = [b]、intersection([a], [b]) != null。证明方式是依次证i推出ii,ii推出iii,iii推出i,得出等价。

两个等价类的交集或是某一个等价类本身(两个类相等)。或是空集(两个类不等)。

引出划分的概念:设非空A、若存在集合族A’,使A’所有元素非空、它们的并是A、A’的任意两个元素交集为空,则A’是A的一个划分。

R上的等价类集合族是A的一个划分。

 9 . 6

偏序:一个关系同时满足自反、反对称、传递,则其为偏序关系。

偏序类:记作(S, R),为一个集合S,并且在其上定义了偏序关系R。括号是想表示其为序偶,学校课本采用了尖括号。

偏序关系有专用的符号,不过一般常用普通的小于号表示偏序关系。

一个偏序类中。不一定所有元素都可以比较。由此引出“可比较”的概念:对(S, R),对其中某两个元素a、b,若a <= b或b <= a,则称a、b可比较。

如果一个偏序集中,任意两个元素均可比较,则称这个偏序是一个线序、或完全序、或链序。

良序:对一个完全序,若每一个非空子集S都存在一个最小元素,则称(S, R)是良序集。

Hasse图:把一个有向图中表示自反、以及为了表示传递性而必须具有的边去除,即结点a和b有边相连当且仅当不存在结点c使(a, c)和(c, b)在关系中。之后把有向图调整方向,偏序关系靠后的元素应该在Hasse图的下方。这时Hasse图即完成。

最大/最小元、极大/极小元、上界、下界、Least upper bound、Greatest lower bound。这样区分:最大/最小元一定是惟一的,极大/极小元不唯一。最大/最小/极大/极小元一定在给定的讨论集合中。上下界不一定在给定的讨论集合中(需要看Hasse图本身),上下界不一定唯一。Lub、Glb一定唯一。

格、拓扑排序