graph-theory - 在二部图中划分完美匹配

Question

在“婚姻问题”中，我们有 N 个男孩和 N 个女孩，以及一个 NxN 二进制矩阵，告诉我们哪些配对是合适的，并希望将每个女孩与一个男孩配对。 (即我们想在二分图中找到完美匹配)。

霍尔定理说，如果每个男孩节点集合都至少与同样多的女孩节点相邻，则可以找到完美匹配；并且有快速增广路径算法可以找到完美的这些匹配。

我正在寻找一种有效的方法来找到男孩节点的集合，这些男孩节点与完全相邻的女孩节点数量相同(即我们在 Hall 的标准中是平等的)。这些男孩必须与这些女孩配对，其余男孩与其余女孩配对，以便所有完美匹配都遵循这种划分。

我的图论有点生疏，肯定有比枚举所有 2^N 个子集并计算每个子集的邻居更好的方法吗？

Answer 1

这在多项式时间内是可能的。将您的二分匹配问题建模为有向图中的最大流问题。然后使用一种算法来枚举最小割。在 Google 上搜索“enumerate minimum cuts”，或 Vazirani & Yannakakis 或 Yeh & Wang 的论文。