首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >不连通图的最大二部匹配

问不连通图的最大二部匹配
EN

Stack Overflow用户
提问于 2011-04-19 20:32:50
回答 3查看 1.2K关注 0票数 3

当您的图有多个组成部分时,如何找到最大二部匹配?每个组件都可以用两种方式着色。为了运行最大匹配例程,您如何确定两个集合X和Y?

EN

回答 3

Stack Overflow用户

发布于 2011-04-20 05:44:15

如果您的图有几个不同的连接组件,您可以通过在每个组件中找到最大匹配并返回它们的并集来查找图中的最大匹配。

至于如何确定集合X和Y,存在许多算法来检测特定图是否为二部图,如果是,则为节点分配标签以恢复这两个组。您可以使用修改后的DFS或BFS相当容易地做到这一点。因此,针对您的问题的算法可能是

  1. 在整个图上运行DFS以将其分解为连接的每个组件:
    1. 在这些组件上运行DFS以恢复组X和Y中的哪些节点。
    2. 使用最大二部匹配算法在该component.

中查找最大匹配

​

  1. 将所有结果组合在一起,得到整体答案。

希望这能有所帮助!

票数 1
EN

Stack Overflow用户

发布于 2011-04-20 06:30:37

不要从边的角度来看匹配,而是将看作一组边。这一观点使我们更加清楚地认识到,无论您如何连接子结果,它在以后仍然是可以的。

  1. 使用您选择的算法将您的图分割为多个已连接的图对每个图组件进行最大匹配。
  2. 找到的匹配项的并集是整个图的最大匹配。
票数 1
EN

Stack Overflow用户

发布于 2011-04-20 04:13:47

我不知道断开连接的图,但如果你有一个像我这样的完整图,你可能会感兴趣:http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html。它使用一种改进的Floyd-Warshall算法来寻找最大匹配。我不知道这和匈牙利算法有什么不同。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5716386

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档