Hall定理

Hall定理：

此定理使用于组合问题中；二部图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4, .........,Xm}

, Y={y1, y2, y3, y4 , .........,yn},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：

X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)

本论还有一个重要推论：

二部图G中的两部分顶点组成的集合分别为X,Y, 若∣X∣=∣Y∣,且G中有一组无公共端点的边，一端恰好组成X中的点，一端恰好组成Y中的点，

则称二部图G中存在完美匹配。若图G的每个点度数为t，则称二部图G为t---正则的二部图存在完美匹配。

本定理是二分图匹配问题中匈牙利算法的基础。