最大二分图 (1,n) 匹配

Question

我有一个二分图，想要找到一个最大的(1,n)“匹配”，这意味着从A部分的每个顶点都会与B部分中的n个相关联的顶点匹配。

下面的图展示了一个最大的(1,3)匹配。匹配所选的边为红色，未选中的边为黑色。 查看图片 http://www.freeimagehosting.net/uploads/9a8df2d97c.gif 这与标准的二分图匹配问题不同，标准问题是每个顶点只与另一个顶点相关联，可以称为(1,1)匹配。

如果匹配的基数(n)没有被强制执行，但是是一个上限(来自A的顶点可以有0

- Imre Kelényi

---

其实不是 :) 我正在开发一个基于BitTorrent的P2P协议，我需要匹配算法来将对等方与数据块关联起来... - Imre Kelényi

所以，您想要最大化恰好具有n个连接的对等方数量？ - Olexiy

我猜肯定还有其他的限制条件需要被最大化（比如覆盖碎片？）否则这个算法就太简单了。至少如果图片是正确的，并且在B中一个顶点可以有多条边（通常在执行最大匹配时不是这种情况）。 - HerdplattenToni

HerdplattenToni：之前的图片是错误的，感谢指出。在B中，你只能像标准（1,1）匹配一样，将一个边与顶点相连。 - Imre Kelényi

Answer 1

这是NP难问题，从最大独立集问题进行约化。对于任何图G，您可以构造一个问题实例（在多项式时间内），使得：

• A中的顶点表示G的顶点
• A中的每个顶点恰好连接B中的n个顶点
• 如果且仅当A中的两个顶点在G中相连时，它们有一个公共邻居在B中。为了始终满足此条件，请选择n=Δ(G)。

现在，实例中的最大“匹配”映射回G中的最大独立集。

- Rafał Dowgird

---

你的最后一个条件并不总是能够满足。例如，G有一个顶点v，它有N+1个邻居。这N+1个邻居中没有一个相互连接。根据鸽笼原理，为了使v有一个具有N+1项的公共邻居，只能使用N条出边。两个公共邻居必须共享一条出边，这将在G中连接它们，这是不正确的。如果你添加了G的最大度数为N的限制，那么你的证明就成立了。我认为当最大度数为1或2时，最大独立集不是NP难问题，因此你的证明仅适用于N>=3。 - theycallhimtom

但在构建问题实例时，您可以自由选择N。只需选择N = |V(G)|。 - Rafał Dowgird

我的第一反应与theycallhimtom的类似，但考虑到N的额外限制，证明似乎是可靠的。您需要选择N，使得N> = D（G），其中D（G）是G的最大度数。一个小错别字/错误是缩减来自“最大独立集问题”，而不是“极大”，因为后者是一个不同的问题，并且更容易。非常感谢您的答案，它帮了很多忙。（我一旦有足够的声望就会给您评分。） - Imre Kelényi