基础
最小点覆盖 = 最大匹配
我们假设最小点覆盖的集合为 \(V\)，最大匹配的集合为 \(E\)，因为最大匹配中的边都互相不交，
所以我们可以让最大匹配中的边的端点任意选择一个点，就有：
于是另一边不太好证明，我们就记住这一边的证明，感性理解～
最大独立集 = 总点数 - 最小点覆盖
假设最小点覆盖为 \(V_1\)，最大独立集为 \(V_2\)，我们考虑最小点覆盖的补集，如果补集中的任意两点之间有边，那么对应的最小点覆盖这一条边就没有被覆盖，与最小点覆盖冲突了。即最小点覆盖的补集是独立集。所以有：
\[n-|V_1|\le |V_2|\tag 1 \]同理，最大独立集的补集也一定满足点覆盖，那么就有：
\[n-|V_2|\ge |V1| \]即：
\[n-|V_1|\ge|V_2|\tag 2 \]根据 \((1),(2)\) 两式可得：\(n-|V_1|=|V_2|\)。
DAG：
基本定义：
- 最小路径覆盖：用最少的路径覆盖 DAG 上的所有点，路径之间不能有交。
- 最小链覆盖：和最小路径覆盖的区别是路径之间可以有交（点），边不可以交。
- 最长反链：最大的点集，满足两点之间互相不连通。
最小路径覆盖 = 总点数 - 拆点后的最大匹配
对于一张 DAG，我们考虑让入点和出点做二分图匹配，考虑匹配的意义：
最开始所有的点属于自己的路径，当一个入点匹配出点的时候，表示两个点合并到同一条路径上了。那么式子就非常显而易见了。
最长反链 = 最小链覆盖
对于反链中的点两两不连通，那么覆盖每一个点都至少需要这么多的路径，于是：
\[最长反链 \le 最小链覆盖 \]同样的另一边不太好证明，我们感性理解即可。
导弹拦截问题
原问题就是求一个序列最少由多少个非递增序列构成，我们考虑建出一张 DAG，对于
\(i<j,a_i\ge a_j\)，连边： \(i\longrightarrow j\)，那么就会形成一张 DAG。
那么原题就相当于求这一张 DAG 的最小路径覆盖（因为路径不能有交）。
但是仔细考虑，发现对于这样的建图，如果 \(i\to j,j\to k\)，那么就一定有一条边 \(i\to k\)，
那么就会发现对于任意有交的情况，一定可以转为无交的情况。
也就是对于这张特殊的 DAG，有最小路径覆盖 = 最小链覆盖，所以原问题就转变为求最长反链，
那么最长反链就相当于原序列中的最长上升子序列。。