二分图匹配总结

对于任意图:

|最小边覆盖|+|最大匹配|=|V|

二分图的最大匹配=最小点覆盖数

对于二分图:

以下数值等价.

最大匹配

最小点覆盖

|V|-最大独立集(二分图or有向无环图)

|V|-最小边覆盖数

|V|-最小路径覆盖数(有向无环图)

|V|-最小路径覆盖数/2(无向图)

(上面括号里有有向无环图的,均是将一个点拆成两个点连边匹配)

由于任意图的那几个几乎用不到于是这里只贴二分图的定义

最小点覆盖:理解为点覆盖边,即用最小的点覆盖所有的边。(若一条边的其中一个端点被选用,这条边就被覆盖了)

最大独立集:求一个最大的点集,里面的点不存在任何的边相连。

最小边覆盖:理解为边覆盖点,用最少的边把图中的点全部覆盖。

最小路径覆盖:用最少的路径把图中的所有点覆盖。

另外:最大独立集与最小覆盖集互补。

推广到有权的形式也一样,即最大点权独立集最小点权覆盖集互补

求最小点权覆盖集可以这样求:

先对图黑白染色,然后向白色的点放X部,黑色的点放Y部。

1、连边[S,i],容量等于i的点权。(对于二分图的X集)

2、连边[i,T],容量等于i的点权。(对于二分图的Y集)

3、对于有边的i和j连边[i,j](i∈X,j∈Y),容量为INF

最后得出的最大流就是最小点权覆盖,实际上是最小割与之对应。

对于求了传递闭包以后的有向无环图:

最大反链=|V|-最大匹配

加入对话

3条评论

留下评论

您的电子邮箱地址不会被公开。