首页 > 其他分享 >Dilworth

Dilworth

时间:2023-01-12 17:23:10浏览次数:35  
标签:偏序 全序集 le 集合 forall Dilworth 反链

Dilworth

定理

偏序集能划分成的最少的全序集个数等于最大反链的大小

名词解释

偏序

在集合 \(S\) 中定义的二元关系 \(\le\),如果它满足以下三个性质:

  1. 自反性:\(\forall x\in S\) 有 \(x\le x\)。
  2. 反对称性:\(\forall x,y\in S\),若 \(x\le y,y\le x\),则有 \(x=y\)。
  3. 传递性:\(\forall x,y,z\in S\),若 \(x\le y,y\le z\),则有 \(x\le z\)。

则称 \(\le\) 为 \(S\) 中的一个偏序关系,\((S,\le)\) 为一个偏序集。

全序集

对于定义在集合 \(S\) 上的偏序关系 \(\le\),若集合 \(T\) 满足 \(T\subseteq S\),且 \(\forall x,y\in T\) 有 \(x\le y\) 或者 \(y\le x\) 成立,则称 \((T,\le)\) 为一个全序集。

换句话说,全序集就是不包含两个不可比元素的集合。

反链

反链的定义恰恰与全序集相反。

对于定义在集合 \(S\) 上的偏序关系 \(\le\),若集合 \(T\) 满足 \(T\subseteq S\),且 \(\forall x,y\in T\) 有 \(x\le y\) 和 \(y\le x\) 都不成立,则称 \((T,\le)\) 为一个全序集。

换句话说,反链就是元素两两不可比的集合。

证明

不会,略。以后补。

应用情形

一般多元组集合

考虑最简单的二元组,那么得到的结论就是:导弹拦截可以用最长上升子序列求解。

图论模型

考虑定义 \(u\le v\) 当且仅当 \(u\) 可以到达 \(v\)。对于一个 DAG,发现 \(\le\) 是定义在点集 \(V\) 上的偏序关系,那么就有最小路径覆盖等于图上最长反链。在某些题目中,这个定理可以将网络流改为贪心,例如网络流 24 题中的魔术球。

这里附上魔术球的做题记录:

\(n\) 个容器,从 1 开始往容器里放数,要求放的容器为空,或者放的数和容器里上一个放的数的和是完全平方数。问最多能放到多少,并构造方案。

\(n\le55\)

首先,答案必然递增。那么可以二分。如何判断是否可行?发现是最小路径覆盖。同一原理的另一种做法是不二分,每次加入一个点,然后继续跑一次网络流(不清空),第一次遇到容器不够的情况时退出。理论复杂度前者优,实际上后者常数很小。另一种思路是贪心,贪心地加入,能加就加,不能加就开新容器。正确性可以证明,利用 Dilworth 定理之类的东西。感性理解的话可以看作某个程度上的模拟网络流。

标签:偏序,全序集,le,集合,forall,Dilworth,反链
From: https://www.cnblogs.com/Diwanul/p/17047268.html

相关文章

  • Dilworth 定理
    Dilworth定理对于偏序集\(D\),我们有若干概念:链:\(D\)中的一个子集\(C\)满足\(C\)中任意两个元素都可比,即构成全序集。反链:\(D\)中的一个子集\(B\)满足\(B\)......