二分图の模型

网络流

---

---

一、参考资料

https://blog.sengxian.com/algorithms/networkflow-variants
http://www.matrix67.com/blog/archives/116
http://dsqiu.iteye.com/blog/1689505

二、匹配，边覆盖，独立集，点覆盖之间的三组关系及原理

（一）最大匹配与最小边覆盖

  对于任意连通图，有：

$$|M_\max|+|F_\min|=|V|$$
  用中文描述就是： $最大匹配数+最小边覆盖数=顶点数$

证明：
  若在边覆盖集中新增一条边，则有三种情况：
① 当边的两端都被覆盖时，多覆盖了 $0$ 个点
② 当边一端覆盖一端未覆盖时，多覆盖了 $1$ 个点
③ 当边的两端都未被覆盖时，多覆盖了 $2$ 个点

  由于我们要用最小的边，覆盖所有的 $n$ 个点，所以每次覆盖的边肯定越多越好。
  能覆盖 $2$ 个点的边就是最大匹配，接下来，对于每个没有被覆盖的点，找到一条它与被覆盖的点的连边，把这条边连起来就好了。

  所以 $|F_\min|=(|V|-2*|M_\max|)+|M_\max|$
  所以 $|M_\max|+|F_\max|=|V|$

（二）最大独立集与最小点覆盖的关系

  对于任意图，有：

$$S_\max\cup S_\min=V$$
  数量化之后，有
$$|S_\max|+|S_\min|=|V|$$
  用中文描述就是：在点集 $V$ 中，最大独立集 $S_\max$ 与最小点覆盖 $S_\min$ 互补

证明：
  对于一个独立集 $P$ ，设它在 $V$ 中的补集为 $Q$ 。
  根据独立集的定义， $P$ 中的节点两两不相邻，所以与 $P$ 中节点相连的边对应的节点一定在补集 $Q$ 中。而还有一种类型的边，就是两个点都在补集 $Q$ 中。
  所以，对于每条边，它一定至少有一个端点在补集 $Q$ 中，即 $Q$ 是一个点覆盖集。
  所以对于任意一个独立集，有且仅有一个点覆盖集与其互补。
  所以当且仅当独立集为最大独立集时，最大独立集的补集为最小点覆盖。

（三）二分图中最大匹配与最小点覆盖的关系（König定理）

König定理：在二分图中，有

$$|M_\max|=|S_\min|$$
用中文描述就是，最大匹配数=最小点覆盖数

证明：
  首先提出构造方法。
  进行二分图最大匹配，对于右端所有没被匹配的点，找增广路，将点进行标记。
  最小点覆盖为左端所有被标记的点，和右端所有未被标记的点。

  为什么点的个数等于最大匹配数？这是因为，在我们选取的点集中，每个点都在一个匹配上，且每个匹配上只有一个点集上的点。即：最大匹配上的每一条边有且仅有一个点集中的点。

  为什么点集为点覆盖集？即证明：不存在一条边，左边的点为被标记，右边的点被标记。
  假设存在一条边，左边的点为被标记，右边的点被标记，分类讨论：当这条边是匹配边时，必然是从左走到右，既然左边没有被标记，那么右边也不能被标记；当这条边未被匹配时，必然是从右走到左，既然右边被标记了，那么就可以走到左边啊。所以不存在。

  为什么点覆盖集最小？
  这是因为，我们既然有了最大匹配的边数$M$，则至少有$2M$个点，所以至少要用$M$个点来覆盖。所以取到了下限。

  综上，有 $|F_\max|=|S_\min|$

三、二分图最大匹配

【构造方法】【计数方法】 Hungary算法

#define rep(i,a,b) for (int i=(a);i<=(b);i++)
int mp[N][N];
int used[N],att[N];
int res;
int Hungary(int x) {
    rep(nx,1,n)
        if (!used[nx]&&mp[x][nx]) {
            used[nx]=1;
            if (!att[nx]||Hungary(att[nx])) {
                att[nx]=x;
                return 1;
            }
        }
    return 0;
}
void Match(void) {
    rep(i,1,n) {
        memset(used,0,sizeof used);
        Hungary(i);
    }
    res=0;
    rep(i,1,n)
        res+=(att[i]>0);
    printf("%d\n",res);
}

四、二分图最小边覆盖

【计数方法】 $|F_\min|=|V|-|M_\max|$ ，只需要求二分图最大匹配即可；
【构造方法】
① 求二分图最大匹配，最大匹配的边全部都要取
② 然后对于没有被匹配的点，选取一条它与被匹配的点相连的边

五、二分图最小点覆盖

【计数方法】 $|S_\min|=|M_\max|$
【构造方法】
① 二分图最大匹配
② 对于右边所有没有被匹配的点，尝试找增广路，把遍历的点进行标记
③ 点覆盖集为：左边被标记的点+右边未被标记的点

六、二分图最大独立集

【计数方法】 $|S_\max|=|V|-|S_\min|=|V|-|M_\max|$
【构造方法】求出最小点覆盖，取补集。

七、二分图最大团

【计数方法】 $最大团的大小=补图的最大独立集$
【构造方法】 补图的最大独立集

八、最小路径覆盖问题

【定义】在图 $G$ 中，用最少的路径覆盖所有的点
为了方便表示，记最小路径覆盖数为 $T_\min$

【建模】在图 $G$ 中，将每个点 $i$ 拆成两个点 $x_i,y_i$ ，构成二分图，若 $(u,v)\in E$ ，则把 $x_u$ 向 $y_v$ 连接一条边。若要求路径不交叉，则直接连接；若路径可以交叉，则应该先用Floyd求解传递闭包。
【计数方法】

$$|T_\min|=|V|-|M_\max|$$
【构造方法】
  进行二分图最大匹配，若 $x_u$ 向 $y_v$ 连接了一条边，说明有 $u->v$ 的路径。