各种覆盖——学习笔记

点覆盖:一个点集,使得所有边至少有一个端点在点集里。

边覆盖:一个边集,使得所有点都与集合里的边邻接。

\(DAG\) 路径覆盖:用不相交的简单路径覆盖所有点。

独立集:一个点集,其中任意两点没有边相连。

团:一个点集,其中任意两点都有边相连。

边独立集:即匹配。一个边集满足任意两边无公共端点。

有关二分图:

  • 二分图最小点覆盖 \(=\) 最大匹配数

    证明戳这里 ,同时给出了构造。

  • 注意到若 \(V'\) 是点覆盖集,那么一定不存在边 \((u,v),\ u,v \in \overline{V'}\)\(\overline {V'}\) 一定为点独立集。

    点覆盖集与点独立集是互补的,最大独立集+最小点覆盖集=点数,这对一般图也适用。

    结合上面的结论,有 二分图最大独立集 \(=\) 点数 \(-\) 最大匹配数

  • 二分图最小边覆盖 \(=\) 点数 \(-\) 最大匹配数

    就是选匹配边能 \(1\)\(2\) ,剩下没被覆盖的点,每个需要 \(1\) 条边。算一下就得到了。

有关 \(DAG\) :

  • \(DAG\) 最小路径覆盖:

    注意这是不相交路径覆盖。把每个点拆成出入两点\(x,x’\) ,建成二分图,对于原图的边 \((u,v)\) ,连边 \(u \to v'\)

    \(DAG\) 最小路径覆盖 \(=\) 原图点数 \(-\) 对应二分图最大匹配数。

    正确性比较显然,选一条边相当于接上两条链。

    要求可相交路径覆盖,就传递闭包一下,转化成不相交即可。

  • 最长反链:

    反链意思是一个点集中任意两点谁也不能走到谁。最长反链即满足要求的最大点集。

    最长反链 \(=\) 最小链覆盖vfk的证明