Dilworth 定理

Rem_CandleFire · 2024-09-02 15:38:49 · 算法·理论

定理介绍

对于集合 A 和偏序关系 p（比如 \le,\ge），若集合 A 满足如下条件，我们称之为【偏序集】。

• 自反性，\forall x\in A,x\ p\ x
• 反对称性，若 a,b\in A，a\ p\ b 且 b\ p\ a，则 a=b。
• 传递性，若 a,b,c\in A，a\ p \ b 且 b\ p \ c，则 a\ p \ c。

然后有几个定义。

• 称两元素 x,y 可比，当且仅当有 x\ p \ y 或 y\ p \ x。
• 【链】，指对于集合 B\subseteq A，B 中任意两元素可比。
• 【反链】，指对于集合 B'\subseteq A，B' 中任意两元素均不可比。
• 【链覆盖】，若干链的并集为 A，两两交集为空。
• 【反链覆盖】，若干反链的并集为 A，两两交集为空。
• 【最长链】，元素个数最多的链。
• 【最长反链】，元素个数最多的反链。

Dilworth 定理指出，一个偏序集的最小链覆盖等于最长反链的长度。相应的，其最小反链覆盖等于最长链的长度。

Dilworth 定理与 DAG

将一个有向图 G 看做偏序集，其中两点是否可达作为偏序关系。那么，G 中的最小不可重链覆盖问题就是偏序集上的最小链覆盖。

对有向图拆点构造二分图，那么最长反链就对应着二分图上的最大独立集，也就是最小点覆盖的补集。而最小点覆盖又等于最大匹配。

由 Dilworth 定理，最小链覆盖等于最长反链。综合上述推理，有向图上最小不可重链覆盖就等于二分图最大独立集，也就是点数减去最大匹配。

一点应用

组合数学

估计人数