转载请注明出处：http://blog.csdn.net/hei_nero/article/details/20479361
本篇尝试从网络流构图上证明K?nig定理，个人理解，仅作参考，不喜勿喷
K?nig定理：二分图的最小点覆盖数等于原图最大匹配
首先，你得知道网络流，然后，你得知道最大流等于最小割，然后我们就可以开始了
用网络流解决二分图最大匹配的思路：
二分图最大匹配可以解释为，从原图中选择尽量多的相邻顶点对，每个顶点最多只能被选择一次
因此在网络流中的建图就是这样：
源向左侧点连容量为1的边，右侧点向汇连容量为1的边，表示每个点最多只能被选择一次
对于每条边(u,v)，设u在左侧，则在容量图中由u向v连容量为1的边，(这里的容量取值改为无穷大也是可以的，不影响答案)
最大流就是最大匹配
用最小割解决二分图最小点覆盖的思路：
考虑一对顶点u和v(设u为左侧顶点)，以及边(u,v)，u和v至少有一个要在点覆盖集中
那么不妨将其构造成 源 -> u -> v -> 汇 这样一条4点3边的路径，将选择点u视为断开 (源,u) 这条边，将选择点v视为断开 (v,汇) 这条边，由于在覆盖集中点u和点v至少选一个，则可以看作必须从(源,u)和(v,汇)中至少断开一条边使源和汇不连通
那么可以构建这样的网络：
源向左侧点连容量为1的边，右侧点向汇连容量为1的边，
对于每条边(u,v)，设u在左侧，则在容量图中由u向v连容量为无穷大的边，
那么问题就从选择原图的一个最小点集，转化成选择容量图中的一个最小边集，使得源汇不连通，也就是容量图的最小割
由最大流最小割定理，也就是最大流
因此，二分图最大匹配对应的容量图，与二分图最小点覆盖对应的容量图，在构图上一致
因此，两幅图的最大流在数值上也相等
因此，二分图最大匹配等于二分图最小点覆盖
证毕
二分图König定理的网络流思路证明,布布扣,bubuko.com
原文：http://blog.csdn.net/hei_nero/article/details/20479361