在二分图中划分完美匹配

Question

3

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

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

我正在寻找一种有效的方法来查找男孩节点集合，这些集合与恰好与女孩节点相邻（即在霍尔定理中有相等性）。这些男孩必须与这些女孩配对，其余男孩与其余女孩配对，以便所有完美匹配都尊重这种划分。

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

- Sam McCall

我不确定是否理解，如果存在完美匹配，则由N个男孩组成的节点集将具有等式属性。 - tonfa

我正在寻找男孩的一个真子集，比如说M个，其中M < N，并且他们之间认识恰好M个女孩。 - Sam McCall

正如jcd所回答的那样，构建流网络是正确的方法。可以参考Narsingh Deo的《计算机科学中的图论及其应用》或者Cormen等人的《算法导论》。已经有很好的库来计算流量。 - Dilawar

2个回答

1

如果我理解你的意思，那么很遗憾，在多项式时间内没有聪明的方法来做到这一点。在一般图上找到这样的分区是一个NP完全问题。

- John Feminella

匹配问题的维基百科文章指出，您可以在O（|V| * |E|）或O（sqrt（|V|）* |E|）中计算M。http://en.wikipedia.org/wiki/Maximum_matching#Maximum_matchings_in_bipartite_graphs - sdadffdfd

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jcd · Accepted Answer

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