我读了《算法设计》一书，第一章，它对如何将二部匹配转化为独立集问题做了很简短的描述，但我没有理解。
有人知道有详细的矩阵来描述这个过程吗谢谢！
最佳答案
最大二部匹配是一个二部图中的边集，没有两个边是相邻的。最大独立集是图中的一组节点（顶点），没有两个顶点相邻。
因此，可以通过将二分图中的每一条边转换为一个节点来将二分图匹配问题转换为独立集，然后在原始图中共享一个公共端点的所有新创建节点之间添加一条边。然后，新的图中的最大独立集对应于原始问题中的最大二部匹配。
我读了《算法设计》一书，第一章，它对如何将二部匹配转化为独立集问题做了很简短的描述，但我没有理解。
有人知道有详细的矩阵来描述这个过程吗谢谢！
最佳答案
最大二部匹配是一个二部图中的边集，没有两个边是相邻的。最大独立集是图中的一组节点（顶点），没有两个顶点相邻。
因此，可以通过将二分图中的每一条边转换为一个节点来将二分图匹配问题转换为独立集，然后在原始图中共享一个公共端点的所有新创建节点之间添加一条边。然后，新的图中的最大独立集对应于原始问题中的最大二部匹配。