Hall定理

Hall定理

Tags：图论

zybl

---

二分图(G=<V1,V2,E>)中，(|V1|<|V2|)，当且仅当(V1)中任意(k(=1,2,3..|V1|))个顶点都与(V2)中至少(k)个点相邻时，该二分图存在完美匹配

证明见此博客
例题见HNOI省队集训