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

Question

我读过“算法设计”一章，它给出了如何将二部匹配转换为独立集问题的简短描述，我不明白。

有没有人知道任何详细的matriel来描述这个过程？谢谢！

Answer 1

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

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