首页 > 其他分享 >Dilworth定理

Dilworth定理

时间:2023-02-07 13:35:00浏览次数:60  
标签:偏序 preceq cup 定理 元素 Dilworth 反链 条链

偏序关系

对于二元关系\(R\subseteq S \times S\),若\(R\)是自反的反对称的传递的,那么\(R\)称为偏序关系。

自反性
\(a \preceq a,\forall a\in S\)

反对称性
\(\forall a,b\in S\),若\(a\preceq b\)且\(b \preceq a\),则\(a=b\)

传递性
\(\forall a,b,c\in P\),若\(a\preceq b\)且\(b\preceq c\),则\(a\preceq c\)

按照定义,\(\le\)是个典型的偏序关系。在集合\(S\)中,若\(a\),\(b\)存在偏序关系,则称他们为可比的,反之不可比。

偏序集是由集合\(S\)与集合\(S\)上的偏序关系\(R\)构成的,记为\((S,R)\)

哈斯图(Hasse图)

对于元素\(x\),如果\(x\preceq y\)且不存在\(z\)使得\(x\preceq z\preceq y\),那么\(y\)就是\(x\)的覆盖元素,在哈斯图中连出一条\(x\rightarrow y\)的有向边。通过覆盖关系生成的图就是哈斯图。

例如,集合\(\{1,2,3,4,6,8,12\}\)上的关系\(\{(a,b)|a整除b\}\)画出的哈斯图如下:

在哈斯图中,通常将较小元放在下方,边的方向由点的相对位置隐士给出。

Dilworth定理

对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目。
设\(C\)是偏序集的一个子集,如果\(C\)中元素相互可比,那么可称\(C\)为,如果\(C\)中元素相互不可比,则称\(C\)是反链

上图中,红色部分就是一条链,蓝色部分是反链。
反链元素最多是2,整个图至少需要2条链\((\{1,2,4,8\}和\{3,6,12\})\)来覆盖。
通过上面的小栗子可以观察到Dilworth定理成立。

数学证明

设有限偏序集\((S,\preceq)\),\(|S|=n\),采用数学归纳法。
当\(n=1\)时,显然成立。
假设该命题对于\(n\le k\)均成立,下面证明\(n=k+1\)时也成立。
设\(A\)是一条最长反链,记为\(A=\{a_1,a_2,...,a_w\}\),定义
\(D(A)=\{x|\exists a\in A(x<a)\}\)
\(U(A)=\{x|\exists a\in A(x>a)\}\)
\(D(A)\),\(U(A)\)的含义为,对于集合中的每一个元素,能在\(A\)中找到小于或大于它的元素即可。
那么有\(S=A\cup D(A)\cup U(A)\)
对\(A\)进行分类讨论:

  1. 存在最长反链\(A\)使\(D(A)\)和\(U(A)\)均不为空。因为\(A\)是\(S\)的最长反链,所以\(A\)也是\(A\cup D(A)\)的最长反链,由于\(A\cup D(A)\)的元素个数小于\(k\),由归纳假设,\(A\cup D(A)\)可以划分为\(c_1,c_2,...,c_w\)共\(w\)条链,其中\(c_i\)的极大元是\(a_i\)。同理,\(A\cup U(A)\)也可以划分为\(d_1,d_2,...,d_w\)共\(w\)条链,其中\(d_i\)的极小元是\(a_i\),那么\(S\)可以划分为\(c_1\cup d_1\),\(c_2\cup d_2\),...,\(c_w\cup d_w\)共\(w\)条链。
  2. 对于每一个最长反链\(A\)都有\(D(A)\)或\(U(A)\)为空。那么反链\(A\)要么构成全上界,要么构成全下界。在\(S\)中选择一个极大元\(y\),在选择一个满足\(x\le y\)的极小元\(x\),则\(\{x,y\}\)可以构成一条链,且\(y\)在全上界中,\(x\)在全下界中。那么\(S-C\)中最长反链的元素个数为\(k-1\),根据归纳假设,其可以划分成\(k-1\)条链,再加上\(C\)得到\(w\)条链。

归纳证明完毕。

例题P1020 [NOIP1999 普及组] 导弹拦截
先构造出偏序集\(P=\{p_1,p_2,...,p_n\}\),记集合\(S=\{(i,p_i)|i\in N且1\le i \le n\}\),偏序关系\(R=\{((i,p_i),(j,p_j)|i\le j且p_i\ge p_j\}\)。\((S,R)\)构成一个偏序集。
第一问就是求最长链长度。
第二问的最少拦截系统对应着最少划分数等于最长反链中元素个数。反链意味着在当前的关系下不可比(集合中的点没有直接或间接相连的边),我们只要改变偏序关系,将\(p_i\ge p_j\)改为\(p_i<p_j\)(原先可比的点现在不可比,原先不可比的点现在可比),这样在新的哈斯图中最长链长的就对应着旧图中最长反链的长度。

参考博客偏序集,哈斯图与Dilworth定理

标签:偏序,preceq,cup,定理,元素,Dilworth,反链,条链
From: https://www.cnblogs.com/hetailang/p/17094852.html

相关文章

  • 杭电1163--9余项定理的例子
    #include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;intmain(){intn,a[10009];inti,t;while(scanf("%d",&n),n!=0){......
  • 9余数定理
    9余数定理可以验证灯饰两边是否相等......
  • 中国剩余定理
    【模板】中国剩余定理(CRT)/曹冲养猪题目描述自从曹冲搞定了大象以后,曹操就开始捉摸让儿子干些事业,于是派他到中原养猪场养猪,可是曹冲满不高兴,于是在工作中马马虎虎,有一次......
  • Ascoli-Arzelà 定理:各种版本
    Ascoli-Arzelà定理:各种版本目录Ascoli-Arzelà定理:各种版本紧空间,紧致度量空间,上确界拓扑紧空间,欧式空间,上确界拓扑紧空间,度量空间,上确界拓扑拓扑空间,度......
  • Lucas定理证明
    描述:当为大数,为素数时,Lucas定理是用来求的值。适用领域范围:在数论中求大组合数取模。通式:为素数证明:已知为素数,将非负整数转化成进制数:由于p是素数对于,都有由二项式定......
  • 威尔逊定理
    定义:为质数或者可以写成:为质数或者说:若为质数,则能被整除证明:必要性:利用反证法证明:假设不是质数,且是。易知,则而,前后矛盾!故充分性关于充分性的证明,如果直......
  • 中国剩余定理(孙子定理)
    中国剩余定理在《孙子算经》中有这样一个问题:“今有物不知其数,三三数之剩二(除以余),五五数之剩三(除以余),七七数之剩二(除以余),问物几何?”这个问题称为“孙子问题”,该问题的一般......
  • 费马小定理,欧拉定理
    定义费马小定理是这样的,对于整数,和质数,如果与互质,那么有欧拉将其上升为证明首先,给定一个小于p的正整数的集合明显与集合中所有的元素互质用乘以集合中所有的元素并......
  • HDU 6441 Find Integer (费马大定理)
    Description:peopleinUSSSlovemathverymuch,andthereisafamousmathproblemgiveyoutwointegersn,a,youarerequiredtofind......
  • UVA 11754 code feat (中国剩余定理+暴力枚举)
    题意:给出C,SC,SC,S,......