Dilworth 定理

这是一个关于偏序集的定理,事实上它也可以扩展到图论,dp等中,是一个很有意思的东西

偏序集

偏序集是由集合 S S S以及其上的一个偏序关系 R R R定义的,记为 ( S , R ) (S,R) (S,R)

偏序关系:

对于一个二元关系 R ⊂ S × S R\subset S\times S RS×S,如果其满足:

  • ∀ x ∈ S , x R x \forall x\in S,xRx xS,xRx 自反性
  • ∀ x , y ∈ S \forall x,y\in S x,yS,若 x R y xRy xRy y R x yRx yRx,则 x = y x=y x=y 反对称性
  • x R y , y R z → x R z xRy,yRz\rightarrow xRz xRy,yRzxRz 传递性
    显然自然数集 N N N以及最常见的小于等于关系 ≤ \leq , ( N , ≤ ) (N,\leq) (N,)就构成了一个偏序集
    事实上 ( N ∗ , ∣ ) (N^*,|) (N,)也是一个偏序集,其中 ∣ | 表示正整数的整除关系

以下为了讨论方便,我们将 R R R简记为 ≤ \leq ,当然它可以指代小于等于关系之外的其它关系

此外, ∀ x , y ∈ S \forall x,y\in S x,yS,如果 x ≤ y x\leq y xy y ≤ x y\leq x yx,那么我们就说它们是可比的,否则说它们是不可比

定义完了偏序集,我们可以从图上来看看它具体的样子

哈斯图(Hasse 图)

考虑一个偏序集 ( S , ≤ ) (S,\leq) (S,), ∀ x , y ∈ S \forall x,y\in S x,yS,如果 x ≤ y x\leq y xy且不存在 z   S . T .   x ≤ z ≤ y z\ S.T. \ x\leq z\leq y z S.T. xzy,我们称为 y y y覆盖 x x x,那么此时我们就连一条从 x x x指向 y y y的有向边,最后得到的图就称为这个偏序集 ( S , ≤ ) (S,\leq) (S,)的Hasse图

比如下图是 x , y , z {x,y,z} x,y,z的幂集关于包含关系得到的Hasse图
image.png|370

由于偏序关系满足了反对称性,所以Hasse图里面一定没有自环(否则就会合并成一个点),所以我们可以说Hasse图一定是一张DAG

其它偏序集的前置芝士

还是记我们要讨论的偏序集为 ( S , ≤ ) (S,\leq) (S,)


偏序集中的一个全序子集。形式化地说,若集合 C ⊂ S C\subset S CS,且 ∀ a , b ∈ C \forall a,b\in C a,bC, a , b a,b a,b是可比的,那么 C C C就是 S S S的一个链
链这个名字起的就很有水平,因为我们不难发现,偏序集中的一个全序子集,其在Hasse图中似乎就一定表现为一条链。比如上图中的 { { x , y , z } , { x , z } , { x } , { ϕ } } \{\{x,y,z\},\{x,z\},\{x\},\{\phi\}\} {{x,y,z},{x,z},{x},{ϕ}}就是一个全序子集,在图中刚好也表现成一条链。但我没有严格证明,这边搁置。
类似地,我们定义一个反链
反链
若集合 C ⊂ S C\subset S CS,且 ∀ a , b ∈ C \forall a,b\in C a,bC, a , b a,b a,b是不可比的,那么 C C C就是 S S S的一个反链
在图上看的话, { { x } , { y } , { z } } \{\{x\},\{y\},\{z\}\} {{x},{y},{z}}就是一个反链

深度:
最长链大小

宽度
最长反链大小

以上两个定义也是相当的形象。因为我们不难发现,如果把Hasse图按照偏序关系从低到高排列的话,链在图中往往就是一条竖着的,而反链是横着的,由此给出如上定义

最小链划分
将集合 S S S划分为最少的若干个不相交的链

最小反链划分
将集合 S S S划分为最少的若干个不相交的反链

Dilworth 定理

现在可以给出Dilworth 定理的具体内容了

Lemma1 对于任意有限偏序集,其最长反链大小必等于最小链划分中链的数目
其对偶形式也成立:
Lemma2 对于任意有限偏序集,其最长链大小必等于其最小反链划分中反链的数目

以下讨论均假定偏序集有限

总结以下:
最小链划分 = 最长反链大小 = 偏序集宽度
最小反链划分 = 最长链大小 = 偏序集深度

先来证Lemma2:

记定理中的最长链大小为n,我们对n做数学归纳法
显然n=1时定理成立
若n=k时定理成立,我们来证 n=k+1时定理成立
此时偏序集中的最长链长度为k+1,我们取出集合 S S S的所有极大元,组成集合 M M M,显然 M M M是一个反链,并且考虑 S − M S-M SM,其最大链长一定为k(因为取出了所有的极大元),根据之前的归纳假设, S − M S-M SM的最小反链划分数目为 k,再加上M自己是一个反链,从而此时S的最小反链划分数为 k+1 = 最长链长度 □ \square

再来看Lemma1:

考虑偏序集 ( S , ≤ ) (S,\leq) (S,),记 ∣ S ∣ = m |S|=m S=m,我们对m进行归纳
m = 1 m=1 m=1时Lemma1显然成立
m = k m=k m=k时定理成立,我们来证 m = k + 1 m=k+1 m=k+1时定理成立:

A A A是集合 S S S的一条最长反链,记为
A = { a 1 , a 2 , . . . a w } A = \{a_1,a_2,...a_w\} A={a1,a2,...aw}
其中 ∣ A ∣ = w |A|=w A=w
我们取
D ( A ) = { x ∉ A ∣ ∃ α ∈ S , x ≤ a } D(A) = \{x\notin A|\exists \alpha \in S,x\leq a\} D(A)={x/A∣∃αS,xa}
U ( A ) = { x ∉ A ∣ ∃ α ∈ S , a ≤ x } U(A) = \{x\notin A|\exists \alpha \in S,a\leq x\} U(A)={x/A∣∃αS,ax}
显然 D ( A ) ⋃ U ( A ) ⋃ A = S D(A)\bigcup U(A)\bigcup A = S D(A)U(A)A=S

若存在最长反链 A A A使得 D ( A ) , U ( A ) D(A),U(A) D(A),U(A)均非空:
A A A S S S的最长反链,故 A A A也是 A ⋃ D ( A ) A\bigcup D(A) AD(A)的一个最长反链。注意到 ∣ U ( A ) ∣ ≥ 1 |U(A)|\geq 1 U(A)1,故 ∣ A ⋃ D ( A ) ∣ ≤ k |A\bigcup D(A)|\leq k AD(A)k,从而由归纳假设, A ⋃ U ( A ) A\bigcup U(A) AU(A)可以划分为 w w w条链 c 1 , c 2 , . . . c w c_1,c_2,...c_w c1,c2,...cw,其中 c i c_i ci的极大元是 a i a_i ai.(这一点显然)
同理, A ⋃ D ( A ) A\bigcup D(A) AD(A)也可以划分为 w w w条链 d 1 , d 2 , . . . d w d_1,d_2,...d_w d1,d2,...dw,其中 d i d_i di的极小元是 a i a_i ai
从而,我们就可以将 S S S划分为 w w w条链: c 1 ∪ d 1 , . . . . c w ∪ d w c_1\cup d_1,....c_w\cup d_w c1d1,....cwdw

若对于任意最长反链 A A A,都有 D ( A ) = ϕ D(A)=\phi D(A)=ϕ U ( A ) = ϕ U(A)=\phi U(A)=ϕ
由假设,任一条反链 A A A必定构成全上界或者全下界。在 S S S中选一个极大元 y y y,再选一个极小元 x x x满足 x ≤ y x\leq y xy, { x , y } \{x,y\} {x,y}构成一条链 C C C,从而在集合 S − C S-C SC中,任一条最长反链的大小为 w − 1 w-1 w1(必定去除了一个元素),从而根据归纳假设, S − C S-C SC的最小链划分数为 w − 1 w-1 w1,再加上 C C C自己是一条链,故 S S S的最小链划分数为 w w w

□ \square

应用举例

求一个序列的最大非递增序列长度以及其最少可以划分为多少个非递增序列

考虑由(位置,元素大小)这个二元组组成的集合,再定义一个偏序关系 < < <:
a < b a<b a<b当且仅当 a a a的位置< b b b的位置且 a a a的值 < b <b <b的值

从而这就构成了一个偏序集 ( s , < ) (s,<) (s,<),并且要求的分别就是集合的最长反链以及最小反链划分数
第一个问题可以直接dp即可,第二个问题,根据Dilworth 定理,实际上就是求偏序集的最长链大小,实际上也就是序列的LIS,非常妙的一个转化。

与DAG

之前说过,Hasse图就是一个DAG,而反过来,我们将DAG的点作为集合 S S S的元素,将偏序关系 ≤ \leq 定义为点之间的可达性,就定义了一个偏序集 ( S , ≤ ) (S,\leq) (S,)
从而DAG上的最小可重路径覆盖(要求覆盖所有点)就等价于偏序集 ( S , ≤ ) (S,\leq) (S,)上的最小链覆盖

同理,将DAG上的有向边作为集合 T T T的元素,将偏序关系 ≤ ′ \leq' 定义为边之间的可达性,就得到的另一个偏序集 ( T , ≤ ′ ) (T,\leq') (T,)
从而DAG上的最小可重路径覆盖(要求覆盖所有)就等价于偏序集 ( T , ≤ ′ ) (T,\leq') (T,)上的最小链覆盖

Erdős–Szekeres 定理

含至少 r s + 1 rs+1 rs+1个元素的实数序列 { a } \{a\} {a}要么有一个长为 r + 1 r+1 r+1的不下降子序列,要么有一个长为 s + 1 s+1 s+1 的不上升子序列
Proof:
设序列长度为 n ≥ r s + 1 n\geq rs+1 nrs+1,定义偏序集 { ( i , a i ) } i = 1 n \{(i,a_i)\}_{i=1}^{n} {(i,ai)}i=1n,其上的偏序关系 ≤ \leq 定义为:
( i , a i ) ≤ ( j , a i ) ⇔ ( i ≤ j   ∧   a i ≤ a j ) (i,a_i)\leq (j,a_i)\Leftrightarrow (i\leq j \ \wedge \ a_i\leq a_j) (i,ai)(j,ai)(ij  aiaj)
假设该偏序集的宽度 ≤ s \leq s s,则由Dilllworth定理可知其最小链覆盖数 ≤ s \leq s s,若这些链的长度都 ≤ r \leq r r,则总元素数 ≤ r s < r s + 1 ≤ n \leq rs< rs+1\leq n rs<rs+1n
矛盾。
□ \square

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/641052.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python筑基之旅-MySQL数据库(四)

目录 一、数据表操作 1、新增记录 1-1、用mysql-connector-python库 1-2、用PyMySQL库 1-3、用PeeWee库 1-4、用SQLAlchemy库 2、删除记录 2-1、用mysql-connector-python库 2-2、用PyMySQL库 2-3、用PeeWee库 2-4、用SQLAlchemy库 3、修改记录 3-1、用mysql-conn…

力扣HOT100 - 21. 合并两个有序链表

解题思路&#xff1a; class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dum new ListNode(0), cur dum;while (list1 ! null && list2 ! null) {if (list1.val < list2.val) {cur.next list1;list1 list1.next;} els…

力扣刷题---3146. 两个字符串的排列差

题目描述 给你两个字符串 s 和 t&#xff0c;每个字符串中的字符都不重复&#xff0c;且 t 是 s 的一个排列。 排列差 定义为 s 和 t 中每个字符在两个字符串中位置的绝对差值之和。 返回 s 和 t 之间的 排列差 。 示例 1&#xff1a; 输入&#xff1a;s “abc”, t “b…

四万字长文详解——node.js使用移动云,EOS对象存储

目录 前言 安装及安装前的操作 前置条件 如何创建认证信息 使用npm安装SDK开发包 安装开发包命令 初始化操作 存储桶 查看结果命令 查看桶列表 查看结果命令 删除桶 查看结果命令 创建桶 获取桶列表 判断桶是否存在 查询桶所属地域 查询桶的访问权限 管理桶的…

基于springboot+vue+Mysql的校园台球厅人员与设备管理系统

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…

【C语言】冒泡排序详解

前言 排序&#xff0c;就是将一组数据按特定的规则调换位置&#xff0c;使这组数据具有某种顺序关系&#xff0c;一般就是递增或递减。 在接触C语言不久&#xff0c;我们就会遇到其中一种有名的排序算法——“冒泡排序”&#xff0c;不知道你是否已经掌握了&#xff0c;如果还…

2024最新 Jenkins + Docker 实战教程(五)- 配置Gitee Webhooks实现自动构建部署

&#x1f604; 19年之后由于某些原因断更了三年&#xff0c;23年重新扬帆起航&#xff0c;推出更多优质博文&#xff0c;希望大家多多支持&#xff5e; &#x1f337; 古之立大事者&#xff0c;不惟有超世之才&#xff0c;亦必有坚忍不拔之志 &#x1f390; 个人CSND主页——Mi…

等保建设:打造MySQL数据库审计系统

1、建设目标 在等级保护三级->应用安全->安全审计中强制需要有审计平台(满足对操作系统、数据库、网络设备的审计&#xff0c;在条件不允许的情况下&#xff0c;至少要使用数据库审计) 数据库审计服务符合等级保护三级标准&#xff0c;帮助您满足合规性要求&#xff0c;…

什么是组态?什么是工业控制中的组态软件?

随着工业4.0和智能制造的发展&#xff0c;工控软件的应用越来越广泛&#xff0c;它们在提高生产效率、降低能耗和减少人力成本等方面发挥着越来越重要的作用。 什么是工控软件&#xff1f; 工控软件是指用于工业控制系统的软件&#xff0c;主要应用于各种生产过程控制、自动化…

Java中流的概念细分

按流的方向分类&#xff1a; 输入流&#xff1a;数据流向是数据源到程序&#xff08;以InputStream、Reader结尾的流&#xff09;。 输出流&#xff1a;数据流向是程序到目的地&#xff08;以OutputStream、Writer结尾的流&#xff09;。 按处理的数据单元分类&#xff1a; 字…

在winnas中使用docker desktop遇到的问题及解决方法记录

最近在尝试从群晖转向winnas&#xff0c;一些简单的服务依然计划使用docker来部署。群晖的docker简单易用且稳定&#xff0c;在win上使用docker desktop过程中遇到了不少问题&#xff0c;在此记录一下以供后来人参考。 一、安装docker desktop后启动时遇到无法启动docker引擎 …

构建数字未来:探索Web3在物联网中的新视角

引言 随着Web3时代的来临&#xff0c;物联网技术正迎来一场新的变革。在这个数字化时代&#xff0c;Web3所带来的技术创新将为物联网的发展开辟新的视角。本文将深入探讨Web3在物联网领域的应用&#xff0c;揭示其在构建数字未来中的重要性和影响。 Web3与物联网的融合 区块链…

运用HTML、CSS设计Web网页——“西式甜品网”图例及代码

目录 一、效果展示图 二、设计分析 1.整体效果分析 2.头部header模块效果分析 3.导航及banner模块效果分析 4.分类classify模块效果分析 5.产品展示show模块效果分析 6.版权banquan模块效果分析 三、HTML、CSS代码分模块展示 1. 头部header模块代码 2.导航及bann…

QQ个性网空间日志网站模板源码

QQ个性网空间日志网站模板源码自带后台登录设置&#xff0c;适用于博客、文章、资讯、其他类网站内容使用。模板自带eyoucms内核&#xff0c;原创设计、手工书写DIVCSS&#xff0c;完美兼容IE7、Firefox、Chrome、360浏览器等;主流浏览器;结构容易优化;多终端均可正常预览。由于…

保安维稳,四信以科技构筑高速公路安全智慧防线

近日&#xff0c;广东梅大高速发生严重塌方事故&#xff0c;造成了严重的人员伤亡和财产损失。这一事件在公众心中敲响了安全的警钟&#xff0c;再次引起了公众对于交通设施运营安全性的重点关注。 国务院安委会办公室和国家防灾减灾救灾委员会办公室等主管机构先后印发紧急通知…

FuTalk设计周刊-Vol.053

#AI漫谈 热点捕手 1.Midjourney推出新功能Room 用户可在聊天室中一起创作图像 Midjourney最近推出了一个有趣的新功能——Room&#xff0c;为用户提供了一个协作和社交平台&#xff0c;用户可以一起创建和分享图像&#xff0c;并参与实时聊天。Room促进了用户之间的互动和合作…

Mujava 工具的简单使用

首先下载openjava.jar和mujava.jar&#xff0c;以及自己手写一个mujava.config指向存放mujava的目录&#xff0c;并将这些文件放在mujava目录下。此时&#xff0c;基本的mujava环境就搭建好了。 分别创建src&#xff08;存放源码文件&#xff09;、classes&#xff08;存放源码…

excel poi的titleRows 和 headRows含义

titleRows 这个参数的意思是&#xff1a;excel标题占多少行&#xff0c;而不是第几行headRows 这个参数的意思是&#xff1a;excel表头占几行&#xff0c;而不是第几行&#xff08;多行的意思是合并的行数&#xff09; 比如有一个excel如下&#xff0c;1-2行是标题&#xff0c…

webstorm新建vue项目相关问题

前言 这个迭代后端需求偏少&#xff0c;前端code的键盘都起火星子了。来了4个外包支持&#xff0c;1个后端3个前端&#xff0c;还是不够用啊。刚好趁这个机会稍微学习下vue&#xff0c;其实之前环境也配置过了&#xff0c;所以这里就不分享环境配置了&#xff0c;主要分享下新建…

Orangepi Zero2 linux系统摄像头设备文件名固定

文章目录 1. 寻找设备规则2. 使用udev规则修改挂载设备文件名称 问题&#xff1a; 在多次插拔usb摄像头或者在使用中不小心碰到或松了会导致设备文件名称变化&#xff0c;如从/dev/video1和/dev/video2变为/dev/video2和/dev/video3, 所以每次发生变化后都要充型修改代码或者重…