霍尔定理

发表于 分类于 ， ， 阅读次数： 本文字数： 209 阅读时长 ≈ 1 分钟

霍尔定理推论:

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