正则二分图

· · 算法·理论

无向（不要求简单）二分图，左部 n 个点，右部 m 个点。

如果左部点度数 =d 且右部点度数 =d，则存在完美匹配。

如果左部点度数 =d 且右部点度数 \leq d，则存在完美匹配。

第一个证明考虑 Hall 定理。第二个证明考虑添加左部虚点转化为第一个。