二分图匹配专题总结

入门级

必备知识点

定理一：
最小点覆盖：选取尽可能少的点，使得任意的一条边都有至少一个端点被选到。
|最小点覆盖| = |最大匹配数|

定理二：
最大独立集：选取尽可能多的点，使得所取得点中，任意的两点均不相连。
|最大独立集| = |V| - |最大匹配数|

定理三：
最小边覆盖: 选取最少边的让所有点都被覆盖
|最小边覆盖| = |V| - |最大匹配数|

最小路径覆盖：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。
|最小路径覆盖| = |顶点数| - |最大匹配数|

具体最小路径覆盖分为路径可相交和路径不可相交，具体可以参考这篇博客

定理证明

以下定理证明均是自己的理解，如果想知道详细证明可以参考其他博客
定理一
$取最大匹配的所有边的一个端点，必定可以覆盖所有边。如果还有边没有被覆盖的话$取最大匹配的所有边的一个端点，必定可以覆盖所有边。如果还有边没有被覆盖的话
$，也就说这个边的两个端点没有被包括最大匹配内，那么最大匹配就要+1。所以反证得出结论$，也就说这个边的两个端点没有被包括最大匹配内，那么最大匹配就要+1。所以反证得出结论

定理二
$设最大匹配数为n,也就说剩下的点中两两没有边。所以最大独立集=顶点数-最大匹配$设最大匹配数为n,也就说剩下的点中两两没有边。所以最大独立集=顶点数−最大匹配

定理三
$取最大匹配的边，设为m个。也就是还剩下\mid V\mid -2\ast m个点没有覆盖。那么我只需要\mid V\mid -2\ast m+m$取最大匹配的边，设为m个。也就是还剩下∣V∣−2∗m个点没有覆盖。那么我只需要∣V∣−2∗m+m
$即\mid V\mid -\mid m\mid 个边即可$即∣V∣−∣m∣个边即可

定理四
$假设我们有n个点，我们把每个点拆成两个点(a,a^{\prime })，这样对于这些点如果有有两个不同点相连，路径数-1$假设我们有n个点，我们把每个点拆成两个点(a,a′)，这样对于这些点如果有有两个不同点相连，路径数−1
$最小路径数就等于总路径数-最大匹配数$最小路径数就等于总路径数−最大匹配数

刷题链接**
<独立AC多于15道>**

心得总结

1. 对于我们可以点分成两个集合的，我们二分匹配的时候只需要在点数少的集合里面查找有无增广路。但是对于我们不可以完全找到的时候就需要遍历所有的点。

2. 思考问题的时候可以根据矛盾关系建立边（一定要判断二分图有无奇环）
   题目链接
   这个题目就是根据每个人如果存在会使得哪些人不存在，从而建立一条矛盾边。然后答案就是最大独立集
   这个题目其实证明无奇环挺容易的。

3. 对于矩形块问题，我们有两种构图方式
   （1）直接一个集合只包括行，一个集合包括列。对于存在一个点，我们把它的行与列建边
   （2）把每一个点看成一个整体，编号即为 $i\ast c+j$i∗c+j

4. 奇环判断：dfs画图

5. 对与一个图，删边变成二分图
   题目链接
   我们可以枚举所有点的情况，然后删一定的边。这道题还要用状态压缩优化，具体可以做一下。

6. 最少路覆盖问题我们可以大致归结于有向图建边
   具体理解可以归结于这道题

模板

可以参考白书模板（邻接表）
复杂度 $O(N\ast M)\left(N表示枚举的点\right)$O(N∗M)(N表示枚举的点)