发现不是很熟，所以整理一下。
无向图
- 在任意无向图中，最大独立集和最小点覆盖互补。（指其中一个取反得到另一个）
二分图
- König定理：二分图最小点覆盖大小等于最大匹配大小。
构造：从右边每个失配点走增广路，走到的点打标记。左侧的标记点和右侧的未标记点组成了最小点覆盖。
- 二分图最小边覆盖等于最大独立集大小。
\(\geq\)：每条边至多覆盖一个独立集中的点。
构造：选出所有匹配边，然后选出非匹配点任意选个邻边。
选的边数：点数 \(-\) 最大匹配 \(\Rightarrow\) 点数 \(-\) 最小点覆盖 \(\Rightarrow\) 最大独立集。
DAG
（点不相交，选出最少路径覆盖所有点）
对于图 \(G\)，每个点复制一下，DAG 中有 \((u,v)\) 就连上左侧 \(u\) 和右侧 \(v\)，得到二分图 \(H\)．
- \(G\) 的最小路径覆盖等于 \(n\) \(-\) \(H\) 的最大匹配．
最大匹配中有什么边，最小路径覆盖中的路径就选择上哪条边。每次相当于将两个路径合并，所以是互补的。
有向图
最大权闭合子图转最小割：
超源连向正权（存在表示选），负权连向超汇（存在表示不选），权值均为点权绝对值。原图边为 inf．
Dilworth 定理：最长反链长度（两两不可比的最大集合）等于最小链覆盖大小（划分成尽量少的两两可比的集合）
注意：严谨的 Dilworth 定理定义在偏序集中，或者说是一个已经传递闭包后的 DAG，那么这里链覆盖能不能经过重复点是一样的。但如果在普通 DAG 中，并不去求它的传递闭包，不可比定义为不可达，那么这里链覆盖实际上就是点可以相交的路径覆盖。
也就是：传递闭包前，必须是点不能相交；传递闭包后无区分，都一样。所以可以传递闭包后跑上面那个 DAG 最小路径覆盖。
标签：DAG,匹配,最大,覆盖,路径,最小,边覆盖 From： https://www.cnblogs.com/do-while-true/p/17197184.html