二分图及其相关知识总结

pre:

二分图：图G划分为两个点集A,B且在同一点集内的所有点互不相交的图.
匹配：在二分子图的边集M中如果M中的每条边的两个端点只有该条边与这两个端点相连，则M称为一个匹配。
匹配边：两个相匹配的点之间的连线。
最大匹配：图中包含边数最多的匹配。
完备匹配：如果有一边的点全都是匹配点，则称这个匹配为完备匹配。
完美匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。
最小覆盖： 用最少的点(两边都行)让每条边都至少和其中一个点关联。（也就是说每个边至少有一个端点是匹配点）

路径：就是连着的几条边（1->2->3就是一条路径）
最小路径覆盖问题：在有向无环图中，用最少的路径条数（不相交的路径，即不仅不能有重合的边，连重合的点都没有）覆盖掉所有顶点。
最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．（如果图Ｇ满足二分图条件）可以用二分图匹配来做.

带权匹配：使得该二分图的权值和最大（或最小）的匹配。
最大匹配：使得该二分图边数最多的匹配。
完备匹配：使得点数较小的点集中每个点都被匹配的匹配。
完美匹配：所有点都被匹配的匹配。
可知：完美匹配一定是最大匹配和完备匹配。

定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）
定理2：最大匹配数 = |V| - |最大独立集|
定理3：最小路径覆盖数 = 顶点数 - 最大匹配数

无权匹配：匈牙利算法
带权匹配：km算法
【求二分图的最小匹配】
只需把权值取反，变为负的，再用KM算出最大权匹配，取反则为其最小权匹配.

1.二分图最大匹配

这东西一般用匈牙利算法解决.复杂度O(n)O(n3)$O(n^3)$
算法思想:在已有匹配的基础上通过寻找增广路来增加匹配.
实现方法:对于当前希望加入的点,找到一个与它相邻的点,判断它是否能被用上
　　一个点能被用上有两种情况: 1.它没有被另个匹配相连
　　　　　　　　　　　　　　2.与它匹配的点能换个点匹配(这里保证前面的解不变)
　　那么显然对于第二点我们需要递归处理
具体实现如下

bool search(int x)
{
    int i;
    for(i=1;i<=m;i++)
        if(map[x][i] && !used[i]) {//有边相连并且这个点还没试过
            used[i]=1;//注意标记打在这(要不然下一步就没法递归了)
            if(b[i]==0 || search(b[i])){//没有匹配或者匹配能更换
                b[i]=x;
                return true;
            }
        }
    return false;
}
int main() {
    for(i=1;i<=n;i++) {
        memset(used,0,sizeof(used));//注意清空
        if(search(i)) ans++;
    }

定理:
定理1：最大匹配数 = 最小点覆盖数(König定理)
定理2：最大匹配数 = |V| - 最大独立数
定理3：最小路径覆盖数 = 顶点数 - 最大匹配数
(如果搞不灵清就画个样例跑一跑呗)

2.二分图最佳匹配

于二分图最大匹配不同的是:它的匹配中加入了权值,目标是使所选的权值和最大

针对这类问题我们使用KM算法予以解决: