关于二分图点覆盖集与点独立集的笔记
搬论文耳。
以下讨论均基于二分图：
点覆盖集：每条边中至少有一个点在点集内。
点独立集：点之间相互没有边。
一个点覆盖集 对偶于 一个点独立集。
证明：
如果一个点集是覆盖集，那么其补集为独立集：
考虑使用反证法。
假设一个点集为覆盖集，补集不是独立集。那么存在一条边<u,v>在其补集中，而这条边没有被覆盖到。因此矛盾。
如果一个点集是独立集，那么其补集为覆盖集：
仍然考虑反证法：
假设一个点集为独立集，补集不是覆盖集。那么存在一条边<u,v>不在补集中，那么这条边会在独立集中。因此矛盾。
得证。
最小点覆盖集 对偶于 最大点独立集。
由于点的总数固定。两个点集的点数之和不变。当点独立集最大时，点覆盖集最小。
最小点覆盖集算法：
对于一张二分图，我们且把这张二分图的两个互不相交的子集称为X集与Y集。（本蒟不会称呼）
那么我们从原点向X集连一条容量为1的边。Y向汇点连一条容量为1的边。X与Y之间按照原图的连接方式，但都改为容量为正无穷、从X向Y的有向边。
我们考虑一条流<s,u>+<u,v>+<u,t>。首先由于我们已经令<u,v>为正无穷，不可能被割去。于是这条流的割，意味着<s,u>或者<u,t>或者<s,u>+<u,t>被割去。
根据最小割划分点集的思想，在这里被割去意味着选择到覆盖集中。
于是我们最小割，即为最小点覆盖集。
最小点权覆盖集：
最小点权覆盖集 对偶于 最大点权独立集。证明类似。
最小点权覆盖集的做法与最小点覆盖集类似。将<s,u>与<v,t>一部分的容量修改为u、v的点权即可。
正确性类似。
搬一个应用：
以前做过的题，今天发现原来可以这样思考。
对于一条边<u,v>，考虑到必须由u的删去入边或者v的删去出边（或者两个都操作），删去这条边。联想到，把删去入边这一操作视为X点集，删去出边这一操作视为Y点集。
那么这就转换为了一个最小点权覆盖集问题了。