偏序集

偏序关系

首先回顾一下偏序,集合X上的偏序是一个自反、反对称且传递的关系

  • 如果对于X中所有的x,都有x R x,则R是自反
  • 如果对于X中所有x和y,若x R y和y R x同时成立则x=y,则R是反对称
  • 对于X中所有的x,y和z,只要x R y且y R z,就有x R z,则R是传递

通常用\le取代R来表示偏序关系,常见的偏序关系有集合的包含,小于等于,整除等。<<表示严格偏序(反自反,反对称,传递),比如严格包含于,小于关系等。

可比与不可比

对于X中x和y,如果x R y或者y R x,则说x和y是可比的,否则就说x和y不可比

极小元极大元

对于偏序集X中的元素a,不存在满足x<a的元素x,则a是偏序集的一个极小元。对于偏序集X中的元素b,不存在满足b<y的元素y,则b是偏序集的一个极大元。

链与反链

(X,)(X,\le)是有限偏序集,是X的一个子集C,它的每一对元素都可比,因此链C是X的一个全序子集,链的元素可以被线性排序。反链是X的一个子集A,他的任意两个元素都不可比。

由定义可知

链的子集也是链,反链的子集还是反链。

如果A是一个反链而C是一个链,则AC1\left| A\cap C\right|\le 1

重要定理

定理1(X,)(X,\le)是有限偏序集,设 rr 是链的最大大小。则X可以被划分成 rr 个反链,但不能划分成少于 rr 个反链

定理2 (Dilworth定理) 设(X,)(X,\le)是有限偏序集,设 mm 是反链的最大大小。则 XX 可以被划分成 mm 个链,但不能划分成少于 mm 个链

定理1的证明大概是每次找到偏序集的极小元集合,然后删掉,这样实际上得到的 rr 个极小元集合就是划分成 rr 个反链的方案。定理2是定理1的“对偶”定理,但是证明就比较复杂了。

题目

1.导弹拦截

最经典的题目,把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。这里的偏序关系i R j,可以理解为 i<ji<ja[i]<a[j]a[i]<a[j]

2.2017 ICPC Nanning The Maximum Unreachable Node Set

求一个DAG的最大的两两不可达的点集大小。

需要先做floyd,然后转化为求最小不相交路径覆盖就可以了,每个点拆成两个点,形成一个左右各 nn 个点的二分图,对于一条边 (i,j)(i,j) 左边的 ii 连向右边的 jj,最终答案为 nn 减去二分图最大匹配的数量。


偏序集
https://izard.space/2018/08/29/偏序集/
作者
forever_you
发布于
2018年8月29日
许可协议