Hall 定理

Hall 定理

之前只记了 hall 定理的结论，这里来做一下证明

结论

左部点大小 (|X|) 右部点大小 (|Y|)，满足 (|X| le |Y|)

最大匹配即为 (|X|-max_{s subseteq X}{(|S|-|to_s|, 0)})

有最大匹配时即为任意一个子集出发的邻点个数大于等于本身

证明

必要性显然，来证充分性

如果没有完美匹配，找到左部点里一个没有匹配的点 x，它一定可以找到一条出边，如果右部图的那个点 y 没有匹配，显然答案加一。否则 y 找到和它匹配的那个点 tx，断掉匹配，重新和 x 匹配。根据 Hall 定理，两点对一点是不存在的，所以 tx 还可以找到另外一个出边。一直找下去，直到这个集合里有了 n 个点，第 n 个点一定能找到另外一个没有匹配的点。证毕。