Dilworth 定理(偏序集分解定理)

关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。

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

对偶也是真: 任意有限偏序集,最长链元素的数目必等于最小反链划分中反链的数目

一些定义

原点集 = V

偏序( R 表示二元关系): 集合中一些元素可以比较大小

• 自反: A R A
• 反自反: A R B 且 B R A 则 A = B
• 传递: A R B 且 B R C 则 A R C

全序: 集合中元素两两可以比较大小

链: V的子集, 是全序集

反链(antichain): V的子集,其任意元素之间都不可以比较大小

链覆盖: 若干个链的并 = V, 且任意两个链不包含重复点

反链覆盖: 若干个反链的并 = V, 且任意两个反链不包含重复点

最长链: 所有链中点个数最多的链

最长反链: 所有反链中点个数最多的链

偏序集高度 = 最长链的点的个数

偏序集宽度 = 最长反链的点的个数

定理: 最小(链的数量最少)链覆盖个数 = 最长反链点的个数 = 偏序集宽度

最小(反链的数量最少)反链覆盖 = 最长链的元素个数 = 偏序集的深度

证明:

归纳法

对于点集$V$, 最大反链集合$A$

$d = |A|$

显然$A$的最小链覆盖 $\ge d$, (因为A中每个点覆盖的链一定两两不同, 其实要证的是等号)

若任何$V$的真子集(归纳更小的点数而不是更小的d)都满足 其最大反链集合大小=最小链覆盖

如果V中两两不可比较, 则 d = |V|, 正确性显然

如果 存在$A \neq \max(V)$, $V$中的最大元素构成的集合, 同时$A \neq \min(V)$, $V$中最小元素构成的集合

拆分$V$为 $A$ 和$\ge A$的集合$V_1$,$A$和$\le A$的集合$V_2$, (这里注意到$A$是最大反链意味着$V$中所有元素至少可以和$A$中的其中一个元素比较大小,所以这里才能拆分)

显然$V_1,V_2$的元素个数都比V小

A依然是$V_1,V_2$ 的最大反链集合, 因为首先不可能超过$A$, 否则同样的方案可以用在$V$上, 因此$A$是一个可达的上界

那么有$V_1,V_2$ 都是最小d个链覆盖, 且每个$A$中的被一条链覆盖, 这样靠着把V1,V2的链通过A中的点一一对应拼接上, 则依然是d条链覆盖, 所以是存在=d的方案

如果$A = \max(V)$

• 如果A中存在一个独立的不能和其它点比较的点$u$, 则$V - u$的最大反链 = $A - u$, 归纳得证
• 否则$A$中 每个点都存在更小的点和它能比较的点, $u\in \max(V)$ 使得 $V - u$ 的最大反链集合的$A_0$
  • 如果存在$|A_0|$元素个数依然是$d$, 则这个方案 也可以用在$V$中, 满足$A_0 \neq \max(V)$
    • 如果$A_0 \neq \min(V)$, 则满足第一种情况可证
    • 如果$A_0 = \min(V)$, 则考虑$A_0$中取一个能和$u$比较的点$v$, (V\u)\v
      • 如果这个最大反链集合$A_1$ 如果$|A_1|=d$, 则$A_1 \neq \max(V)$, $A_1 \neq \min(V)$, 满足第一种情况,可证
      • 否则$|A_1| = d-1$, 这里说明(V\u\v + [u,v]) 左边可以d-1条链覆盖，右边可以1条链覆盖，$\le d$ 和最开始的$\ge d$得到只能是$d$
  • $|A_0| = d-1$时, A\u 是一个$A_0$的方案, 说明$d-1$链能覆盖 V\u, 多加一个u 能覆盖V,得证

证毕

综上,归纳法有 最大反链集合的个数 = 最小链覆盖条数

相关

abc237Ex

abc354G

https://oi-wiki.org/math/order-theory/#dilworth-%E5%AE%9A%E7%90%86%E4%B8%8E-mirsky-%E5%AE%9A%E7%90%86

https://baike.baidu.com/item/%E7%8B%84%E5%B0%94%E6%B2%83%E6%96%AF%E5%AE%9A%E7%90%86/18900593

https://blog.csdn.net/qq_43408238/article/details/104542949

TLDR

有依赖关系的选择的问题，可以转化成 图论的最小割问题，再黑盒性质使用 最小割=最大流求出

project selection problem

https://codeforces.com/blog/entry/101354

流问题是算法竞赛的一个高级课题。 流问题的主要挑战往往不在于算法本身，而在于图的建模。 为了解决Project Selection Problem，我们将把它建模为最小切割问题的一个实例：”给你一个带加权边的有向图。 一个节点被指定为源节点，另一个节点被指定为汇节点。 删除一组总重量最小的边，使源点和汇点断开。 如果源点和汇点之间不再存在有向路径，则视为断开。 请注意，我们可以将最大流量问题视为一个黑盒子，它可以解决我们的最小切割问题。 因此，一旦我们设法将问题简化为最小切割，我们就可以认为问题已经解决。

Project Selection Problem 常见的形式

TL;DR;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

vector<int> euler_circuit(vector<vector<pair<int, int>>> G, int n/*点*/, int m/*边*/) { // 欧拉回路
    vector<int> path;
    vector<bool> used(m, false); // 边是否被使用
    function<void(int)> dfs=[&](int u) {
        for(auto [v,e]: G[u]) { // (点, 边)
            if(!used[e]) {
                used[e] = true;
                dfs(v);
            }
        }
        path.push_back(u);
    };
    dfs(0);
    reverse(path.begin(), path.end());
    return path;
}

直觉的数学证明

1. 所有点都是偶度

当我们对所有边至多访问一次进行dfs

那么对于非起始点u，dfs(u) 什么时候返回

1
2
3

dfs(u):
	for 未访问过的边edgeid，v : g[u]:
		dfs(v) <----- ?什么时候返回

直觉告诉我们，

1. 如果绕到了u的父节点来源 且无法dfs更深时会返回
2. 如果只是绕回了u,而u还有边是不会因此导致返回的

所以只有两种情况

1. 第一次返回 是 绕到更深无法继续，第二次是 绕回u且没有多的边
2. 只有一次 绕到更深无法继续

而发现 只要把顺序反过来就好了

相关

abc227H

https://codeforces.com/contest/1994/problem/F

https://codeforces.com/contest/1991

G Grid Reset

给定n,m,k

n * m 的白色矩阵

给定长度q的序列 H/V

如果H需要放入 1 * k的黑色横条

如果V需要放入 k * 1的黑色竖条

每次放入后，一行或一列全 黑，则同时删除对应行或列（变回白色）

问有没有方法 完成序列q,

如果有给出具体的方案，每次输出放置的左上角坐标

n,m 100, q 1000

2s

256mb

我的思路

想完美的消除 a个横 和 b个列， 那么形状 是 类似

1
2
3
4
5

三川川川川
三
三
三
川

那么对于 多行消除，需要 k个横 和 m-k竖

那么对于 多列消除，需要 k个竖 和 n-k横

想的是画二维(横个数，竖个数) 的坐标图，找边界

其实可以切割成 横(k,n-k,n),竖(k,m-k,m), 其中 n-k,m-k和k的大小关系不一定

然后这里其实是离线的，也就是我们可以知道最先达到哪个状态，但对于9宫格每个里面应该怎么摆，还没有具体的尝试

https://codeforces.com/contest/1994

F Stardew Valley

n点m边，边有颜色0/1

要求找方案 从某点开始 经过所有1的边回到你选定的点，其中每个边最多经过一次，颜色为1的边必须经过1颜色为0的边可以经过1次

保证任意两点之间有纯1的路径

输出具体方案 或 不可行-1

n,m 5e5

2s

256mb

我的思路

核心应该是欧拉回路，但是不知道如何选0边