algorithm - 最大二分图（1，n）“匹配”

Question

我有一个二分图。我正在寻找最大（1，n）“匹配”，这意味着来自分区 A 的每个顶点都有来自分区 B 的 n 个关联顶点。

下图显示了图中的最大 (1,3) 匹配。为匹配选择的边缘为红色，未选择的边缘为黑色。

见图 http://www.freeimagehosting.net/uploads/9a8df2d97c.gif

这不同于标准的二分匹配问题，其中每个顶点仅与一个其他顶点相关联，可以将其称为 (1,1) 匹配与此表示法。

如果匹配基数 (n) 不是强制的，而是一个上限（来自 A 的顶点可以有 0 < x <= n 个来自 B 的关联顶点），那么通过将图转换为流网络和找到最大流量。但是，这并不能保证来自 A 的最大顶点数将具有来自 B 的 n 个关联对。

Answer 1

这是 NP-hard，从最大独立集问题减少。对于任何图形G，您都可以（在多项式时间内）构建问题的一个实例，例如：

• A 中的顶点表示G
• A的每个顶点都连接到B的恰好n个顶点
• A 的任意两个顶点在 B 中具有公共邻居当且仅当它们在 中连接G。为此，请选择 n=Δ(G)。

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