二分图匹配概念&结论&证明的整理总结

设 \(M\) 是 \(G(V,E)\) 的一个匹配

1. 先称 \(M\) 中的边为匹配边，不在 \(M\) 中的边为非匹配边
2. 与匹配边相关联的点，称之为配对点，不与匹配点相关联的点，称之为非配对点
3. 如果 \(G\) 中的每个点都是配对点，则称 \(M\) 是 \(G\) 的一个完美匹配
4. 在 \(G\) 中，由匹配边和非匹配边交替组成的路径，称之为交错路经
5. 起点和终点都是非配对点的交错路径，称之为增广路经

可能上面只有最后一句话重要（

有几个概念(顾名思义，因此只写名字)：

1. 最小点覆盖集
2. 最大点独立集
3. 最小边覆盖集
4. 最大边独立集
5. 最小路径覆盖(这里没有重复经过的点)

点覆盖集是以点覆盖边，边覆盖集是以边覆盖点

1. |最小点覆盖集| = |最大匹配|
2. |最大点独立集| = 顶点总数 - |最大匹配|
3. |最小边覆盖集| = 顶点总数 - |最大匹配|（无孤立点）
4. |最大边独立集| = |最大匹配|
5. |DAG中最小路径覆盖| = 顶点总数 - |最大匹配|

下面是一些上述结论的证明：

1. |最小点覆盖集| = |最大匹配|

这里有个构造方式（需要耐心看）（Konig定理）

甚妙！

2. |最大点独立集| = 顶点总数 - |最大匹配|

最大点独立集其实就是所有的点扔去最小点覆盖的点

因为最小点覆盖的点覆盖了所有的边，即任意一条边都有一个点在最小点覆盖中，所以只要扔去了这些点，每条边上就只会有一个端点，也就没有边相连，自然就是独立集了。

而扔去的最小点覆盖的点数满足最小，所以这个点独立集就满足最大。

所以得出结论：|最大点独立集| = 顶点总数 - |最大匹配|

3. |最小边覆盖集| = 顶点总数 - |最大匹配|（无孤立点）

设最大匹配数为 \(m\)，总顶点数为 \(n\)。为了使边数最少，又因为一条边最多能干掉两个点，所以尽量用边干掉两个点

也就是取有匹配的那些边，当然这些边是越多越好，那就是最大匹配了，所以先用最大匹配的边干掉大多数点

剩下的解决没有被匹配的点，就只能一条边干掉一个点了

所以|最小边覆盖集| = |最大匹配| + (顶点总数 - 2 * |最大匹配|) = 顶点总数 - |最大匹配|

所以|最小边覆盖集| = 顶点总数 - |最大匹配|。

4. |最大边独立集| = |最大匹配|

最大匹配不就是最大边独立集吗

5. |DAG中最小路径覆盖| = 顶点总数 - |最大匹配|

对于原图的每个点分成二分图中的左部点和右部点，如果有一条有向边 \(A\rightarrow B\)，那么左部点中的节点 \(A\) 连向右部点中的节点 \(B\)，最大匹配指的是这个图的最大匹配

实际上，一开始每个点都是独立的为一条路径，总共有 \(n\) 条不相交路径。我们每次在二分图里面找一条匹配边就相当于把两条路径合并成一条路径，也相当于总路径数 \(-1\)。所以有几条匹配边，路径数就减少了多少。

所以有|DAG中最小路径覆盖| = 顶点总数 - |最大匹配|。