Hall's Theorem
bipartite perfect matching 指的是二分图某一侧的顶点都和匹配边相连，我之前确实以为 perfect matching 都是说所有顶点都和匹配边相连。
在 proofs from the book 27章读到的用集合描述的 Hall’s theorem
system of distinct representatives(SDR)
Consider finite set and a collection of subsets of . A sequence is a SDR if s are distinct elements in and for all .
实际上就是存在二分图的 perfect matching.
Hall’s Theorem
存在 SDR(存在perfect matching) 的充要条件是 中任取 个子集的并集, 得到的集合大小至少是 .
proof
这是 proofs from the book 给出的一个证明
证明这种东西很容易就能想到对的大小归纳，这两个证明几乎是完全相同的，不过从两个不同角度来想这个证明还是挺有意思的
exercise
proofs from the book 上这章竟然有一道课后题
从二分图来考虑我觉得总是比集合要直观一点. 我们证明对于任意的k，这样的图都满足 Hall’s theorem 的条件。然后总存在一个匹配，把所有匹配边删掉，图左侧的点度数都是 k-1， 右侧的点度数都小于等于k-1，又满足 Hall’s theorem.
把题目中描述的这种二分图叫做, 唯一需要证明的就是 存在一个perfect matching使得所有匹配边都删掉之后图变成一个 。 问题在于图右侧有一些点度数=k, 也就是我们需要证明存在一个 perfect matching 包含所有右侧的度数等于的顶点.
如果二分图是 k-regular(所有顶点的度数都是k) 那么这个问题也很好解决。。删除一个 perfect matching, 所有点的度数都会-1，变成. Prove by induction on . (exercise12)
但是我们可以在二分图的左侧加上顶点，并且向右侧度数小于k的点连边，把图变成一个 k-regular bipartite graph. 唯一的变化就是我们的到的k个 element distinct SDR 全都比我们想要的更长，在SDR中把新加入的点对应的元素删掉就行了