基本定义
完美匹配是指最大匹配数为min(|X|,|Y|)
也就是X或Y集合其中一个集合所有点都被匹配了。
定理内容
我们来假设X集合点少一点好了。X集合就当做有n个点。
那么二分图G存在完美匹配,则取任意正整数1<=k<=n,均满足我从X集合选出k个不同的点,那么它们连向的y集合的点个数不小于k。
证明
我只会一些乱来的证明,但是是严谨的
必要性
假如一个二分图G存在完美匹配,且不满足Hall定理。
那么对于某k个点,它们连向的都不足k个点。
那么它们是怎么都被匹配上的???
很显然必要性正确。
充分性
假如一个二分图G不存在完美匹配,且满足Hall定理。
那么假如有一种最大匹配的方案,既然不存在完美匹配,可以找到至少一个未被匹配的点。
因为这个二分图满足Hall定理,所以这个点一定连向了至少一个点。
假如这个点不在最大匹配中,如果连向了在y集合内最大匹配内的点,那么就不符合hall定理。
那如果连向了在y集合内最大匹配外的点,那么这就不是最大匹配。
那么这个点在最大匹配中!所以一定有一个点和它匹配了。
看懂了吧!我们一定能推出矛盾!
所以充分性正确。