霍尔定理

霍尔定理推论:

对于一个二分图G<V,E>,若点可以分为两部分N和M,N内部没有边,M同理,S'是N的某个子集(可以为空),f(S')是与该子集相邻的点集,则他的最大匹配为|N|-max(|S'|-|f(S')|),