如何求解这个偏序集的问题？ 第1页

对于长为α(P)的反链，其元素两两之间不可比，也即两两不同链，故至少得有α(P)条链才能覆盖——这就是极限了。

下面证明为啥恰可以用α(P)条链覆盖：

数学归纳法。记|P|=k，假设对k<n时命题成立（k=1时显然），证k=n时命题亦成立。

先从P里边去掉一个极大元x，余下集合为P1。由归纳假设：剩下的元素可以用α(P1)条链覆盖。这里我们让每条链都尽可能地长，不怕重复。

如果α(P1)=α(P)-1，那么让x单独成链都能满足题意。简单。

而如果α(P1)=α(P)呢？

先后用α(P1)条链与最长为α(P1)的反链，把P1覆盖。则其中长为α(P1)的反链的每个元素都来自于这α(P1)条链各取一个。这里就把链中被长为α(P1)的反链分走的元素称为“荣誉元”吧。

每条链里都有一个最大的荣誉元，取出这些荣誉元，与x放在一起。由于其中已有α(P1)+1个元素，必存在两元素可比。这两个元素里一个为x，另一个记作y。设y来自链Y。

解释一下为什么必有一个是x而不是两个都为最大荣誉元：如果链A的最大荣誉元≤链B的最大荣誉元，那岂不是链A上所有荣誉元都与B的最大荣誉元可比？（链A荣誉元≤链A最大荣誉元≤链B最大荣誉元）那么包含这个“链B最大荣誉元”的最长反链，岂不是不包含链A的荣誉元？但我们上面已经说了，最长反链必定是从每条链中各取一个荣誉元。这就矛盾了。

由于x是极大元，有：x≥y≥Y上的荣誉元，它们构成一条链。

而把它们去掉，则最长反链里都丢失了来自Y的荣誉元，长度变为α(P)-1。由构造假设，这时可用α(P)-1条链覆盖。

加起来，正好也是α(P)条链。

证毕。

定理(Dilworth)：最长反链等于最小链覆盖。

证明：

先证弱对偶：对于任意一个链覆盖和任意一个反链，该链覆盖中的任意一条链都只能包含至多一个反链中的元素，因此最长反链小于等于最小链覆盖。

再证强对偶：

对每一个元素 建立两个点 和 。对每一对可比较的元素 ，在图中连接 。记该图为 。

引理： 最长反链大于等于 中的最大独立集数 减去左侧的顶点数 。

证明：对于任意一个独立集 ，我们将所有 与 同时属于 的元素 拿出，由独立集的性质，任意 和 的元素 对应的两个点中都至少有一个不属于 。由此我们构造出了一个大小至少为 的反链（因为对于任意一个集合，若想使得满足条件的元素数量尽可能少我们需要将其尽可能“摊开”到每个元素上，这种情况下我们恰好有独立集大小减 个满足条件的元素），而最长反链不会比这个反链短。

引理： 最小链覆盖等于 中左侧的顶点数 减去 中的最大匹配数 。

证明：最开始每个元素都是一条链，每匹配一条边即减少一条链，因此匹配方案与链覆盖方案一一对应。

由Konig定理，最大匹配数 等于最小点覆盖数 。而 。

因此最长反链大于等于 等于最小链覆盖。

然后就证完了。