在“婚姻问题”中,我们有N个男孩和N个女孩,以及一个NxN的二进制矩阵告诉我们哪些配对是适合的,并且想要将每个女孩与一个男孩配对(即在二分图中找到完美匹配)。
霍尔定理说,如果每个男孩节点集合都与至少与同样多的女孩节点相邻,则可以找到完美匹配;并且有快速增广路径算法可以找到这些完美匹配。
我正在寻找一种有效的方法来查找男孩节点集合,这些集合与恰好与女孩节点相邻(即在霍尔定理中有相等性)。这些男孩必须与这些女孩配对,其余男孩与其余女孩配对,以便所有完美匹配都尊重这种划分。
我的图论有点生疏,肯定有比枚举所有2^N子集并计算每个子集的邻居更好的方法吧?
霍尔定理说,如果每个男孩节点集合都与至少与同样多的女孩节点相邻,则可以找到完美匹配;并且有快速增广路径算法可以找到这些完美匹配。
我正在寻找一种有效的方法来查找男孩节点集合,这些集合与恰好与女孩节点相邻(即在霍尔定理中有相等性)。这些男孩必须与这些女孩配对,其余男孩与其余女孩配对,以便所有完美匹配都尊重这种划分。
我的图论有点生疏,肯定有比枚举所有2^N子集并计算每个子集的邻居更好的方法吧?