最大二分图(1，n)“匹配”
我有一个二部图。我正在寻找最大 (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 个关联对。
I have a bipartite graph. I am looking for a maximum (1,n) "matching", which means that each vertex from partitation A has n associated vertices from partition B.
The following figure shows a maximum (1,3) matching in a graph. Edges selected for the matching are red and unselected edges are black.
See figure http://www.freeimagehosting.net/uploads/9a8df2d97c.gif
This differs from the standard bipartite matching problem where each vertex is associate with only one other vertex, which could be called (1,1) matching with this notation.
If the matching cardinality (n) is not enforced but is an upper bound (vertices from A can have 0 < x <= n associated vertices from B), then the maximum matching can be found easily by transforming the graph to a flow network and finding the max flow. However, this does not guarantee that the maximum number of vertices from A will have n associated pairs from B.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是 NP 难问题，是最大独立集问题的简化。对于任何图
G，您可以构造（在多项式时间内）问题的一个实例，使得：G的现在，实例中的最大“匹配”映射回
G中的最大独立集。This is NP-hard, reduction from maximum independent set problem. For any graph
Gyou can construct (in polynomial time) an instance of your problem such that:GG. For this to be always possible, pick n=Δ(G).Now the maximum 'matching' in the instance maps back to maximum independent set in
G.