dilworth 定理

本文主要是介绍dilworth 定理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

定义集合 \(\mathbb{S}\) 上的偏序集 \((\mathbb{S}, \le)\)，其中 \(\le\) 表示一种关系（不一定就是不大于），满足如下性质：

• 自反性 \(:a \le a\)。

• 反对称性 \(:a \le b, b \le a \Longleftrightarrow a = b\)

• 传递性 \(:a \le b, b \le c \Longrightarrow a \le c\)

定义偏序集 \((\mathbb{S}, \le)\) 的 全序集 为：\(T \in S, \forall i, j \in T, i \le j\) 或 \(j \le i\)。

定义一个偏序集的 最大元 为 \(\forall i \in S, \nexists j \in S, j \ne i, i \le j\)，类似地可以定义最小元。

定义全序集覆盖为：选出若干个全序集使得集合中的每个元素都 至少 在这些全序集中出现一次。

于此同时，最小全序集覆盖为选出 最少 的全序集使得这些全序集构成覆盖。

定义偏序集 \((\mathbb{S}, \le)\) 的一条 反链 为：\(T \in S, \forall i, j \in T\) 不存在 \(i \le j\) 或 \(j \le i\)。

\(\rm dilworth\) 定理给出断定：

• 对于任意一个偏序集 \((\mathbb{S}, \le)\) 其 最长反链的长度等于最小全序集覆盖的大小。

证明如下：

首先我们可以发现如下基础性质：

• 一定存在一组最小全序集方案使得全序集两两不交

对于任意一个最小全序集覆盖，我们都可以调整至其中的全序集两两不交。

具体地，每次选择任意一个全序集 \(a\)，再选择一个与其有交的全序集 \(b\)，我们按照从前往后的顺序考虑每个相交的区域，然后将 \(b\) 在进入该区域之前的点连向进入该区域之后的点。

此时我们对于每个全序集维护一个集合表示其中有多少个节点与其他全序集覆盖。

通过上述的调整，可以发现每次 \(a\) 对应的集合会清空，其他全序集对应集合不会加入新的节点，因此可以每次选择一个非空的集合不断迭代即可。

于是我们有推论（以下我们默认最小全序集覆盖全序集两两不交）：

• 对于任意一个最长反链，一定恰好使得在最小全序集覆盖中的每个全序集中存在一个元素。

有了上述性质，我们考虑归纳证明：

因为偏序集为一张 \(\rm DAG\)，于是我们考虑每次剥去最大元 \(m\) 归纳证明（按照点数归纳，假设 \(n' < n\) 成立，显然 \(n = 0, 1\) 时均成立，令 \(p\) 为当前最长反链长度）。

此时我们仍可以发现如下性质：

• 由推论，对于最小全序集覆盖的任意一个全序集 \(i\) 我们我们维护出其中可能做为最长反链上的节点（存在一条最长反链使得这个节点在该最长反链上）的 极大元 \(a_i\) 构成集合 \(A\)。则 \(A\) 为一条反链。

证明考虑反证法：假设存在偏序关系 \(i, j \in A, i \le j\)，那么由于 \(j\) 可能在最长反链上，那么 \(i\) 所在的全序集中一定至少存在一个可能在最长反链上的节点于其不可比，又 \(i\) 为这样节点的极大元，这样的节点都可以到 \(i\)，矛盾。

接下来我们分两类情况讨论：

1. 最大元与 \(S - \{m\}\) 中任意一个元素不可比，显然归纳正确。
2. 最大元与 \(S - \{m\}\) 中的若干元素可比，放到全序集上考虑，显然只需保留这些元素在全序集上的极大元，令这些极大元构成集合 \(B\)。

对于任意的全序集 \(i\)，若 \(A_i > B_i\) 显然此时 \(m\) 与 \(i\) 上每个可以为最长反链上元素的点都可不比，此时可以直接考虑最长反链选入这些节点。同时可以发现最小全序集一定要单独花费一个全序集覆盖 \(m\)，因此此时最长反链和最小全序集覆盖都 \(+1\)。

否则，若存在全序集 \(i, A_i \le B_i\)，我们令集合 \(D = \{m\} \cup \{x \in i, x \le B_i\}\)，可知 \(S - D\) 的最长反链为 \(p - 1\)（因为删去 \(D\) 后 \(S - D\) 的连边只删去了 \(D\) 的影响，不同全序集之间的连边保留）。又 \(|D| > 1\)，有归纳 \(S - D\) 的最小全序集覆盖为 \(p - 1\)，加入 \(D\) 后最小全序集覆盖为 \(p =\) 最长反链数量。

这篇关于dilworth 定理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！