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

Question

我读了《算法设计》一书，它对如何将二元匹配转换为独立集问题做了很简短的描述，但我不明白。

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

Answer 1

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

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