Hall’s Marriage Theorem什么意思啊,小弟不才!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| = nadd supersource and supersink,if
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/19 02:09:05
Hall’s Marriage Theorem什么意思啊,小弟不才!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| = nadd supersource and supersink,if
Hall’s Marriage Theorem什么意思啊,小弟不才!
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.
Hall’s Marriage Theorem什么意思啊,小弟不才!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| = nadd supersource and supersink,if
应该是个计算机程序,还是什么说明之类的.
大厅婚姻定律
让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］两人提出的结婚定理