考虑点集A，B二分图
最小点覆盖：
概念：用最少的点覆盖二分图中所有边。
结论：最小覆盖点=最大匹配
证明：选择点集A所有匹配点，如果还存在一条边的两个端点都不在匹配点中那么让该两点匹配则最大匹配数目会增加，矛盾。
最小边覆盖：
概念：用最少的边覆盖点集A，B中的所有点。
结论：最小边覆盖=总点数-最大匹配
证明：最小边覆盖=最大匹配+没匹配的点数，总点数=2×最大匹配+没匹配的点数。因此最小边覆盖=总点数-最大匹配
最大独立集
概念：选出最多的点使得点集内部没有边。
结论：最大独立集=总点数-最大匹配
证明：由于最小点覆盖能过覆盖所有边，因此只需选择除了最小点覆盖中的点即可。即最大独立集=总点数-最小覆盖点=总点数-最大匹配
最小路径点覆盖
概念：对于一个有向图，选出最少的不相交路径使其覆盖所有点。
结论：最小路径覆盖=总点数-最大匹配
证明：将每个点拆成出点和入点，不妨让点集A为出点集合，B为入点集合，那么两点之间的有向边一定能过对应集合A向集合B中的一条边。而路径数目等于起点数目或者终点数目，即出点集合A中所有未匹配点即是终点。让终点数目最小即匹配数目最多，因此最小路径覆盖=总点数-最大匹配
最小路径重复点覆盖
概念：对于一个有向图，选出最少的（能相交）路径使其覆盖所有点。
结论：对原图求传递闭包之后再对新图求最小不相交路径覆盖
证明：对于原图的相交路径，如A->O->C和B->O->D，我们可以传递闭包的方法使之变成A->O->C和B->D这两条不相交的路径。对于新图的不相交路径我们可以通过传递闭包方法连接的路径中间点加上即原图的一条相交路径。

以上全是口胡论述，存在很多不严谨之处，不建议新学者看，记下来只是为了方便自己记忆。如果有严重错误或者更简洁的论述请在下方评论谢谢。