Dilworth
Dilworth
定理
偏序集能划分成的最少的全序集个数等于最大反链的大小。
名词解释
偏序
在集合 \(S\) 中定义的二元关系 \(\le\),如果它满足以下三个性质:
- 自反性:\(\forall x\in S\) 有 \(x\le x\)。
- 反对称性:\(\forall x,y\in S\),若 \(x\le y,y\le x\),则有 \(x=y\)。
- 传递性:\(\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 定理之类的东西。感性理解的话可以看作某个程度上的模拟网络流。
最新文章
- Go语言实战 - revel框架教程之MongDB的最佳搭档revmgo
- NULL的陷阱:Merge
- Windows7 安装vs2015 之后 调试Web项目IIS启动不了 aspnetcore.dll未能加载
- I am back-电商网站开发&;jQuery
- C#中的延迟加载
- 基于贪心算法的几类区间覆盖问题 nyoj 12喷水装置(二) nyoj 14会场安排问题
- Java中堆、栈、常量池分析
- 如何关闭UINavigationController 向右滑动 返回上一层视图
- request.getAttribute( ";result";);和request.setAttribute(";result";,username);
- 使用Code::Blocks配置Python编译环境
- Robotium API -- 除click/clickLong外的其他操作
- POJ 3450 Corporate Identity(KMP)
- 2014年蓝桥杯预选赛 C/C++ 本科A组试题--切面条
- Codeforces#360Div2
- hadoop-1.x的运行实例
- badboy录制兼容性有趣测试
- 用Redis作为缓存服务器,加快数据库操作速度
- MVC3/4/5/6 布局页及Razor语法及Route路由配置
- R+NLP︱text2vec包——BOW词袋模型做监督式情感标注案例(二,情感标注)
- c#中@标志的作用
热门文章
- 异常处理的第二种方式-Throwable类中3个异常处理的方式
- UML 图
- .NET周报 【2月第1期 2023-02-04】
- 【学习日志】MySQL分表与索引的关系
- 有效的字母异位词&;两个数组的交集&; 快乐数&; 两数之和
- 《深入理解java虚拟机》第七章读书笔记——虚拟机类加载机制
- ctfshow_web入门 反序列化(254~266)
- 我有一篇Java Stream使用手册,学了就是你的了!
- 《爆肝整理》保姆级系列教程-玩转Charles抓包神器教程(8)-Charles如何进行断点调试
- Vue js引用警告 “export ‘default‘ (imported as ‘xxx‘) was not found