用网络流最大权闭合子图证明二分图最大点覆盖等于其最大匹配:
我们发现网络流最大权闭合子图的构造是:i到j有边,则意味着有 i→j 的约束条件,同时正权点与S连边,负权点与T连边。
然后二分图最大点覆盖有一个性质:对于两边的点 ai,bj 若他们之间有一条边,则意味着他们中至少有一个需要被选取到点覆盖内。
根据集合论的知识,p∣q=!p→q
则我们对于每个左侧节点i,新建节点否i。
现在我们要求一个最大的集合,假设我们先让所有的左侧节点进入集合。因为我们要集合的元素个数最小,所以我们每次拿出一个节点(也就是在最大权闭合子图中选取了左侧节点的否节点)计为1,放入一个节点(选取右侧节点)则计为-1。最后求最大权闭合子图即可。
观察最大权闭合子图,容易发现,若不考虑边权,其构造恰好与二分图最大匹配的构造相同。因为每个点最多只有一个入流,所以本来为正无穷的边其实与1的边是相同的。所以实际上最大权闭合子图的最小割与二分图最大匹配的最大流一模一样!
由于最大权闭合子图需要先累加正权点,也就是 numleft ,而这里最大权的意义又恰好是在只有左侧节点的点集中删去最大权个数的点。
也就是说最后的答案是 numleft−(numleft−maxflow)=maxflow ,也就是二分图最大匹配。