关系的闭包
关系R对于性质P的闭包指的是在关系R中添加最少的有序对得到性质P
自反闭包
在有向图中，对所有顶点添加环
在矩阵中，在对角线上添加1
对称闭包
在有向图中添加反向边
在矩阵对称位置添加1
传递闭包
传递闭包用$t(R)$表示
构建传递闭包比自反闭包和对称闭包难得多，如果a到b有一条路径，那么就在a和b间建立关系
连通关系$R^*$
关系R的传递闭包,等价于联通关系 $R^*$
由于一个图中的关系的简单路径长度不会超过n-1，所以可以把上式简化，去除重复经过的节点
等价关系
- 自反性
- 对称性
- 传递性
等价类
R是一个集合A上的等价关系，那么所有和元素a有等价关系的元素构成的集合就成为元素a的等价类，表示为$[a]_R$
其中等价类的每一个元素都可以作为该等价类的代表元。
集合的割
一个集合的割是该集合的一系列非空的不相交子集，他们的并集为该集合
一个等价关系就是集合的一个割
R是集合A上的一个等价关系，R的所有等价类的并集就是集合A
偏序
偏序关系指的是满足
- 自反性
- 反对称性
- 传递性
的一种关系
偏序的可比较性
一个偏序集里的两个元素a,b如果是可比较的，那么要么$a\leq b$要么$b\leq a$,如果a,b之间不存在前面这两条关系中的任何一条，那么这两个元素就是不可比较的
如果偏序集里所有的元素之间都是可以比较的，那么这个偏序集就成为全偏序（totally ordered）,或称为线性排序集（linear ordered set）
如果在全偏序的基础上，偏序集还满足每一个非空子集都有最小元，那么就称为良序集
哈氏图术语
极大元(maximal)
极小元(minimal)
最大元(greatest element)
最小元(least element)
上界(upper bound)
下界(lower bound)
最小上界(least upper bound)
最大下界(greatest lower bound)
格(lattice)
一个偏序集中每一对元素都有最小上界和最大下界，那么这样的偏序集就称为格
拓朴排序
每一次随机取入度为0的元素即可，在偏序集里就是每一次取最小的元素