学习了一下König定理的证明, 在这里记录一下.
König定理: 二分图的最小顶点覆盖数等于最大匹配数. 参考: 二分图最大匹配的König定理及其证明 | Matrix67: The Aha Moments
首先, 显然有 最大匹配数 ≤ 最小顶点覆盖数. 接下来, 构造一种方案, 说明等号能取得.
在二分图上跑一遍匈牙利算法, 然后进行DFS: 从右部所有未盖点出发, 依次走非匹配边, 匹配边, 非匹配边, 匹配边......沿途标记所有访问过的顶点. 左部所有标记点和右部所有非标记点构成最小顶点覆盖集.
选出的点数等于最大匹配数. 因为这些点与匹配边一一对应. - 边对应点. 对于DFS中经过的匹配边, 它的左右端点均被标记, 与左部的标记点对应. 对于DFS中没经过的匹配边, 它的左右端点均未被标记, 与右部的非标记点对应. - 点对应边. 左部标记点和右部非标记点均是已盖点 (如果右部非标记点是未盖点, 则它会作为DFS的起点).
选出的点覆盖了所有边. 一条边被覆盖, 当且仅当左端点是标记点或右端点是非标记点. 如果一条边没被覆盖, 那么它的左端点是非标记点且右端点是标记点, 且不会是匹配边. 如果右端点是未盖点, 则它会作为DFS的起点; 否则, 到达右端点时走的是匹配边, 这条非匹配边是一定会走的.
证毕.
如果是用网络流跑二分图最大匹配, 则从源点开始, 沿未满流的边DFS.
题外话: 我觉得网上喷Matrix67的人很无聊......