首页 > 其他分享 >Dilworth 定理

Dilworth 定理

时间:2022-10-31 08:35:19浏览次数:48  
标签:偏序 DAG 覆盖 定理 路径 Dilworth 反链 最长

Dilworth 定理

对于偏序集 \(D\),我们有若干概念:

  • 链:\(D\) 中的一个子集 \(C\) 满足 \(C\) 中任意两个元素都可比,即构成全序集。
  • 反链:\(D\) 中的一个子集 \(B\) 满足 \(B\) 中任意两个元素都不可比,即任意非空子集都不是全序集。
  • 链覆盖(链划分):若干个链的并集为 \(D\),且两两之间并集为 \(\empty\)。
  • 反链覆盖(反链划分):若干个反链的并集为 \(D\),且两两之间并集为 \(\empty\)。
  • 最长链:元素个数最多的链(可以有多个)。
  • 偏序集高度:最长链的元素个数。
  • 最长反链:元素个数最多的反链(可以有多个)。
  • 偏序集宽度:最长反链的元素个数。
  • 极小元:\(D\) 中的一个元素 \(a\) 满足不存在 \(x<a\) 的元素。偏序集的所有极小元集合形成一条反链。
  • 极大元:\(D\) 中的一个元素 \(a\) 满足不存在 \(x>a\) 的元素。偏序集的所有极大元集合形成一条反链。

Dilworth 定理:

  • 对于任意有限偏序集,其最长反链中元素的数目必等于最小链覆盖中链的数目。

    即:最小链覆盖 = 最长反链 = 偏序集宽度

    证明:

    首先显然有最小链覆盖小于等于最长反链,所以我们只需构造一组链覆盖等于最长反链即可。假设最长反链大小为 \(m\)。

    • 情形 1:存在一个大小为 \(m\) 的反链 \(A\),它既不是 \(D\) 的所有极大元集合,也不是 \(D\) 的所有极小元集合。

      那么对于 \(D\) 中的任意一个元素 \(x\),它要么属于 \(A\),要么小于 \(A\) 中的某个元素,要么大于 \(A\) 中的某个元素。因为:1. 若 \(x\) 上述三种情况都不满足,那么显然 \(A\) 加入 \(x\) 之后仍为一条反链且更长,矛盾;2. 若 \(x\) 同时满足三种情况中的任意两种情况,说明 \(A\) 中存在两个元素是可比的,矛盾。

      那么如果我们把设 \(A^{+}\) 表示 \(\{x:x\in D\land \exist a\in A,x\geq a\}\),\(A^{-}\) 表示 \(\{x:x\in D\land \exist a\in A,x\leq a\}\),那么就有 \(A^+\cap A^-=A\) 且 \(A^+\cup A^-=D\)。

      显然 \(A^+\) 和 \(A^-\) 的最长反链大小都不变,仍然是 \(m\),于是我们对它们归纳处理,可以得到 \(A^+\) 和 \(A^-\) 都能被划分成 \(m\) 条链,且 \(A\) 中的每一个元素在 \(A^+\) 和 \(A^-\) 都恰好在一条链中。于是我们把 \(A^+\) 和 \(A^-\) 各自的 \(m\) 条链拼接起来即可得到 \(X\) 的一个链划分。

    • 情形 2:不存在一个大小为 \(m\) 的反链 \(A\),它既不是 \(D\) 的所有极大元集合,也不是 \(D\) 的所有极小元集合。即 \(A\) 的可选范围只有极小元集合或极大元集合。

      那么我们选取一个极小元 \(x\) 和一个极大元 \(y\) 满足 \(x\leq y\),那么 \(X-\{x,y\}\) 的最长反链就一定是 \(m-1\),然后对它归纳处理。于是将 \(X-\{x,y\}\) 的 \(m-1\) 条链和链 \(\{x,y\}\) 一起给出了将 \(X\) 划分成 \(m\) 条链的一种构造。

  • 对于任意有限偏序集,其最长链中元素的数目必等于其最小反链覆盖中反链的数目。

    即:最长链 = 最小反链覆盖 = 偏序集高度

    证明:

    首先显然有最小反链覆盖大于等于最长链,所以我们只需构造一组反链覆盖等于最长链即可。假设最长链大小为 \(m\)。

    我们注意到:最长链一定包含恰好一个极小元;所有极小元集合形成一条反链。那么我们可以把所有极小元集合单独提出来当成一条反链,并对偏序集剩下的部分归纳处理(剩下的部分的最长链长度一定是 \(m-1\)),即可得证。

Dilworth 定理与 DAG

我们可以把 DAG 上的点集当成偏序集,DAG 上点的 “可达性” 当成偏序关系,那么 DAG 上的最小可重路径覆盖(要求覆盖所有点)就是这个偏序集上的最小链覆盖。

同理,我们可以把 DAG 上的边集当成偏序集,DAG 上边的 “可达性” 当成偏序关系,那么 DAG 上的最小可重路径覆盖(要求覆盖所有边)就是这个偏序集上的最小链覆盖。

对于 DAG 上的最小点不交路径覆盖问题(要求覆盖所有点),我们可以用二分图最大匹配来解决。我们知道在点不交路径覆盖中,路径的条数等于 \(n\) 减去所有路径的边数之和。那么我们直接对于每个点拆点,然后在入点出点的二分图上跑最大匹配即为所有路径边数之和的最大值。

对于 DAG 上的最小边不交路径覆盖问题(要求覆盖所有边),我们知道路径的条数等于 \(m\) 减去各条路径中拼接两条边的这样的拼接点的个数,那么答案就等于 \(m-\sum_{u=1}^n\min(in_u,out_u)\)。

对于 DAG 上的最小可重路径覆盖问题(要求覆盖所有点),我们有一种暴力解法:我们把路径上任意可达的两个点 \(u,v\) 之间都连边,即补全这个偏序图,形成 \(O(n^2)\) 条边。然后转变为 DAG 上的最小点不交路径覆盖问题,因为对于原问题中的任意一组解,都存在一种把每个点分配给每条路径的方式,使得在新图中变成条数相同的路径,而显然对于新问题中的任意一组解,都存在对应回原问题的一组解。

对于 DAG 上的最小可重路径覆盖问题(要求覆盖所有边),暴力解法也是类似的,只不过要补全的是 \(O(m^2)\) 条边的偏序图。

标签:偏序,DAG,覆盖,定理,路径,Dilworth,反链,最长
From: https://www.cnblogs.com/ez-lcw/p/16843025.html

相关文章

  • Burnside引理和Polya定理
    Burnside引理设\(A\)和\(B\)为有限集合,\(X\)为\(A\toB\)的一个映射集合,\(G\)是\(A\)上的一个置换群,\(X/G\)表示置换群\(G\)作用在\(X\)上产生的所有映射......
  • 【XSY4231】人赢(图论,Hall定理,Trie树,树形DP)
    首先二分答案,设为\(mid\)。现在的问题是:若\(a_i\oplusa_j\geqmid\),则\(i,j\)之间有一条连边,判断是否存在一种选边方式使得每个点都恰好在一个简单环上(可以是自环或......
  • 定理
    ChickenMcNuggetTheorem:两个互质的数n,m。x=a∗m+b∗n。a>=0,b>=0x=am+bn。a>=0,b>=0x=a∗m+b∗n。a>=0,b>=0其中不能构造的最大的数是n∗m−......
  • 从贝叶斯定理到卡尔曼滤波
    从贝叶斯定理到卡尔曼滤波可以选择直接跳至卡尔曼滤波部分开始之前一个问题引入:如何确定一个随机事件发生的概率频率学派认为可以利用大数定理,重复进行无数次随机试......
  • 2017蓝桥杯 K倍区间 前缀和+同余定理
    2017蓝桥杯K倍区间前缀和+同余定理给定一个长度为的数列,。如果其中一段连续的子序列之和是的倍数,我们就称这个区间是倍区间。你能求出数列中总共有多少个倍区间吗?看到“......
  • 数论-费马小定理 学习笔记
    1.定理内容如果p是一个质数,而整数a不是p的倍数,则有。即:若为素数,,则。第二种表述形式:对于任意整数,有。在实际的应用中,我们最多用的是第二种表述形式。2.证明设一个质数为......
  • 威尔逊定理
    1、定义\((p-1)!\equiv-1~(mod~p)\)是\(p\)为素数的充分必要条件。2、证明摘自:威尔逊定理......
  • 策梅洛定理
    一条在博弈论中重要的定理描述:在二人的有限游戏中,如果双方皆拥有完全的资讯,并且运气因素并不牵涉在游戏中,那先行或后行者当中必有一方有必胜/必不败的策略。......
  • 约数个数定理、约数和定理简单证明
    唯一分解定理:一个大于一的正整数可以唯一分解为若干个质数的乘积,记为约数个数定理:这些约数的个数为证明:由于都为质数,所以的约数有共个,同理,根据乘法原理,的约数个数就是......
  • 欧拉定理相关性质及证明
    欧拉定理:当与互质时,有通项公式及其证明:如果,为质数,则证明:当一个数不包含质因子时就能与互质,小于等于的数中包含质因子p的只有个,即,把他们去除即可由唯一分解定理可知,这就是......