hall定理的证明

原文链接：https://blog.csdn.net/WerKeyTom_FTD/java/article/details/65658944
hall定理就是关于判定二分图是否存在完美匹配的东西啦。
那我们来一些基本定义吧。

基本定义
也没啥好定义的。。
学过网络流应该都懂本文要提到的东西。
完美匹配是指最大匹配数为min(|X|,|Y|)
也就是X或Y集合其中一个集合所有点都被匹配了。

定理内容
我们来假设X集合点少一点好了。X集合就当做有n个点。
那么二分图G存在完美匹配，则取任意正整数1<=k<=n，均满足我从X集合选出k个不同的点，那么它们连向的y集合的点个数不小于k。

必要性证明
假如一个二分图G存在完美匹配，且不满足Hall定理。
那么对于某k个点，它们连向的都不足k个点。
那么它们是怎么都被匹配上的？？？
很显然必要性正确。

充分性证明
假如一个二分图G不存在完美匹配，且满足Hall定理。
那么假如有一种最大匹配的方案，既然不存在完美匹配，可以找到至少一个未被匹配的点A。
因为这个二分图满足Hall定理，所以这个点一定连向了至少一个点B(有可能存在多个点）。
假如这个点B不在最大匹配中，它们就匹配了，怎么可能呢？？？
那么这个点B在最大匹配中！所以左边一定有一个点C和它匹配了。
C做为一个匹配点可能在右边找到D，就这样一直找下去，由于左部点数是＜＝右部点数
于是最终点落在右部点结束，找到一个增广路。
于是出现矛盾。

C也可能在右边找到别的匹配点了，因为C就只与B匹配，形如下图：

此时我们可以删除B，C这两个点，并不影响问题的求解，让A去找到D，再如上述的证明即可。