algorithm - 如何将二分匹配转换为独立集

Question

我阅读了《算法设计》一书，第 1 章，它对如何将二分匹配转换为独立集问题进行了非常简短的描述，但我不明白。

有人知道描述这个过程的任何详细资料吗？谢谢！

Answer 1

最大二分匹配是二分图中的一组边，没有两条边是相邻的。最大独立集是图中的一组节点（顶点），没有两个顶点相邻。

因此，您可以通过将二分图中的每条边转换为一个节点来将二分匹配问题转换为独立集，然后在原始图中共享一个公共端点的所有新创建的节点之间添加一条边。那么新图中的最大独立集对应于原始问题中的最大二分匹配。