我读了《算法设计》一书，第 1 章，它非常简短地描述了如何将二分匹配转换为独立集问题，但我不明白。
有谁知道任何详细的 Material 来描述这个过程？谢谢!
最佳答案
最大二分匹配是二分图中的一组边，没有两条边相邻。最大独立集是图中的一组节点(顶点)，没有两个顶点相邻。
因此，您可以通过将二分图中的每条边转换为节点，然后在所有这些新创建的节点之间添加一条边，这些节点在原始图中共享一个公共(public)端点，从而将二分匹配问题转换为独立集。则新图中的最大独立集对应原问题中的最大二分匹配。
关于algorithm - 如何将二分匹配转换为独立集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9919234/