UC知道Hall’s Marriage Theorem什么意思啊，小弟不才！
来源：百度知道 编辑：UC知道 时间：2024/09/24 08:27:45
Let R be a relation from A to B. Then there exists a complete matching M if and only if for each XA, |X||R(X)|
Proof:
Obviously
|A| = n
add supersource and supersink, if max flow value is |A|, then we get it.
If min cut has value |A|, we get it.
什么意思啊！！
Proof:
Obviously
|A| = n
add supersource and supersink, if max flow value is |A|, then we get it.
If min cut has value |A|, we get it.
什么意思啊！！
应该是个计算机程序，还是什么说明之类的。
大厅婚姻定律
让R作为A到B的一个连接。（下面这个假设条件，没搞懂直接意思，只有直接翻译出来）如果只要对于每个X A,X RX，就会存在个完整的组合M。
then there exists a complete matching M if and only if for each X A X RX...这句话有问题。if and only if：如果只要,这意思很别扭，不知道写这句话的作者是什么意思。直接翻译出来，就是上述翻译。
证据：
很明显：
A=N
加上超源程序和超收点，如果最大流动值的计算结果是A，那么我们就会得出它。（这个它应是上述中程序的计算结果，N）
如果最小剪切值的计算结果是A，我们会得出它。（同上）
由［Frobenius 1917,Hall 1935］两人提出的结婚定理