【学习笔记】从 CTSC 2008 祭祀谈起的最长反链及最小链覆盖相关问题的解决方法

本题的题意:给出一个 DAG,求最长反链。

Dilworth 定理:偏序集上最长反链的长度等于最小链覆盖中链的数量。

先做一遍传递闭包,使得 DAG 中 \(x<y\) 的定义"从 \(x\) 向 \(y\) 有连边"变为了"从 \(x\) 出发能够到达 \(y\)“,此时就可以直接套用 Dilworth 定理了。

1. 求解最小链覆盖大小

将所有的点拆为 出(\(x_0\))、入(\(x_1\)) 两点,形成一个二分图。对于 DAG 上的 \(x<y\),连边 \((x_0,y_1)\) 。因为每个出点只能匹配一个入点,每个入点只能匹配一个出点,此时求该二分图的最大匹配

令最大匹配大小为 \(m\),假设最开始每个点自成一条链,接下来每匹配一条边那么最小链覆盖大小就减一,所以最小链覆盖大小为 \(n-m\) 。当然从最大匹配可以还原出最小链覆盖。

2. 构造最长反链方案

这个部分较复杂。

  • Step 1. 求出最小顶点覆盖

    结论:最小顶点覆盖大小等于最大匹配大小

    考虑这么一个构造最小顶点覆盖的方法:选取右侧没有匹配点开始 dfs,从右侧往左侧 dfs 走非匹配边,左侧往右侧走匹配边

    那么最小顶点覆盖的方案为:左侧被访问过的点,右侧没被访问过的点

    接下来考虑证明两个问题:1. 最小顶点覆盖大小 等于 最大匹配大小。 2. 这样选出来的点集的确覆盖了所有的边。

    先考虑第一个问题:可以发现右侧留下的点一定都是匹配边端点,并且其匹配的左侧点一定没有被访问过(否则右侧的这个点也会被访问),不会留下。同时可以发现左侧留下的点一定都是匹配边端点(否则出现一组新的匹配),并且其匹配的右侧点一定被访问过。

    也就是说,留下的肯定都是匹配边端点,并且每条匹配边恰好留下一个端点,所以有 最小顶点覆盖大小 等于 最大匹配大小

    接着考虑第二个问题:讨论每一条边,如果这条边的左侧端点被访问过,或者右侧端点没被访问过,那么这条边必定被覆盖。接下来只需要讨论"左侧端点没被访问过,右侧端点被访问过"这种边了,可以证明这种边不存在:

    • 假设右侧端点是非匹配点,那么没访问左侧端点的情况只有该边是匹配边,与假设矛盾。
    • 假设右侧端点是匹配点,那么一定是从左侧的另一条匹配边访问过来的(如果从当前边访问过来显然矛盾),也就是说,当前边一定是非匹配边,所以左侧端点必然被访问,与条件矛盾。

    所以所有遍都被覆盖了,我们选出来了最小顶点覆盖。

  • Step 3. 求出最大独立集

    结论:最大独立集、最小顶点覆盖互为补集

    考虑最小顶点覆盖的补集中的一个点,与其相邻的点必须都在最小顶点覆盖中,才能够覆盖所有相邻的边。这句话的意思是,最小顶点覆盖的补集中的点两两不相邻。

    同时考虑最大独立集的补集中的一个点,与该点相邻的点中一定有最大独立集中的点,为了覆盖这之间的边,该点必须属于最小定点覆盖。

  • Step 2. 通过最大独立集构造最长反链方案

    考虑这么一个做法:对于每个 \(x\),如果 \(x_0,x_1\) 都在最大独立集中,那么将 \(x\) 加入到反链中。

    注意到因为最小顶点覆盖大小为 \(m\),所以最大独立集大小为 \(2n-m\) 。同时令构造出的反链大小为 \(t\),那么最大独立集(记为 \(S\))大小为 \(t+\sum\limits_{x}[(x_0\in S)\lor (x_1\in S)]\),注意到因为后面部分不超过 \(n\),所以可以得到 \(t\geq n-m\) 。

    也就是说 \(t\) 不小于 \(n-m\) 。事实上,根据 Dilworth 定理,\(t\) 恰好为 \(n-m\),我们构造出了最长反链方案。

3. 完成本题的第三问

本篇文章的主体内容到这里就结束了,接下来是"祭祀"一题第三问的做法。

其实只需要删除该点以及相邻的点,然后再求最大反链即可,如果大小差为 \(1\) 说明可以。时间复杂度为 \(O(n^2m)\) 。

上一篇:SQL Server 2008 允许远程连接的解决方法


下一篇:yolov4 绘制pr曲线