Dilworth 定理
泛化ψ(｀∇´)ψ
这个东西其实是组合数学里的东西。
不过它的内容也可以转化为图论的语言表达，且 OI 中对它的应用一般都是图论方面的，所以我就放到了图论部分。
内容ψ(｀∇´)ψ
偏序集上最小链划分数等于其反链长度的最大值。
偏序集是什么就不提了，不知道的可以看：link
一个偏序集的链划分是指，我们选出若干个不相交的子集，使得每个子集中，任取两个元素，他们是可以比较的。
因为严格偏序关系的关系图就是一张 DAG，我们可以抽象成图论来更好的理解这个东西，它的意思就是选出一张 DAG 上的多条不交的链覆盖整个 DAG。
最小链覆盖是指链数最小的链覆盖。
反链则是，一个子集，使得任意两个元素不可比，换句话说在 DAG 上不可达，也就是独立集。
所以说 OI 话的表达就是：
DAG 上的最小链覆盖等于最大独立集。
这东西听起来很耳熟，我们在二分图的时候把最小点覆盖和最大独立集挂钩了。
而一个比较趣味的事情是，Dilworth 定理是可以用 König 定理证明的。
我还不会，挂个 wiki 链接：https://en.wikipedia.org/wiki/Dilworth%27s_theorem
例题ψ(｀∇´)ψ
TJOI2015 组合数学。
这个题还没时间，暂时不写。
JOISC2016 俄罗斯套娃
link，算是比较经典了。
最后更新:
November 9, 2023